Give 2 coding solutions on returning an array by removing duplicates. One solution with O(n^2) and the other Linear.

Question

Give 2 coding solutions on returning an array by removing duplicates.  One solution with O(n^2) and the other Linear.

Shards · Accepted Answer

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.

Anonymous · Answer

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)

venk T · Answer

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.

Anonymous · Answer

Create a new array. Run through the original array, on each element insert to new array in sorted order. O(n^2)

Google

Google Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches