Google Interview Question
Web:
www.google.com
|
HQ:
Mountain View, CA
Overview |
| |
Salaries |
| |
Reviews |
| |
Interviews |
| |
Photos |
| |
Jobs |
| |
|
1,223 Interview Reviews |
Back to all Google Interview Questions & Reviews
Interview questions and reviews posted anonymously by interview candidates
Interview Question for Software Engineer at Google:
Mar 1, 2010
Give 2 coding solutions on returning an array by removing duplicates. One solution with O(n^2) and the other Linear.
Add Tags
[?]
Helpful Question?
Yes |
No
Inappropriate?
Answers & Comments (4)
Mar 3, 2010
O(n^2) would be to use two for loops to compare each element in the array with every other element in the array.
For linear, you could push all elements into a hash as key and assign value 1 to each key. This would get rid of duplicates. Then get all keys and push it back to the array.
For linear, you could push all elements into a hash as key and assign value 1 to each key. This would get rid of duplicates. Then get all keys and push it back to the array.
Helpful Answer?
Yes |
No
Inappropriate?
Apr 23, 2010
hash select is O(n). What if the hash function is "return 0"? it degenerates into a linked list.
Not sure how you can do this in O(n). If the values are integers of a set size, you can use a lookup table or sort in O(size*n) . Otherwise sort O(nlogn)
Not sure how you can do this in O(n). If the values are integers of a set size, you can use a lookup table or sort in O(size*n) . Otherwise sort O(nlogn)
Helpful Answer?
Yes |
No
Inappropriate?
1 of 1 people found this helpful
Apr 24, 2010
You can use a hash. Either assume that you have a good hash function or write one (I doubt the interviewer would ask you to do a very complex hashing, but he'd appreciate you telling him about the assumption you made).
Instead of the solution by venk T, I'd suggest another easier one. For every values you have, push it to the hashtable, usually a standard hashtable will return true or false depending on whether the value is already in the hashtable. If the value is not already in hashtable, output it in your answer, otherwise don't output. This will cut the last step of getting all the values off the hashtable.
Instead of the solution by venk T, I'd suggest another easier one. For every values you have, push it to the hashtable, usually a standard hashtable will return true or false depending on whether the value is already in the hashtable. If the value is not already in hashtable, output it in your answer, otherwise don't output. This will cut the last step of getting all the values off the hashtable.
Helpful Answer?
Yes |
No
Inappropriate?
To comment on this
question,
Sign In with Facebook or
Sign Up
You might also be interested in: Interview Questions, Software Engineer Interview Questions, Google Interview
0 of 0 people found this helpful
by Anonymous: