Google Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Phone Interview
Can also do it with a bit vector to use less memory than a hashmap, while keeping it O(n)
Good Question..
Lemme give my view.. Every prgm either hv to compromise of Time or Space Complexity..
Algo:-
1> Space Compromise :-
a> Read a array and hash it.
b> Before putting into hash table check if that place is filled.
c> if Filled its duplicate else not keep it in there.
2> Time Compromise :-
Usual Sorting algo with little modification will work.
a> Pick an element search for its duplicity in the array with min complexity.
1. Sort the array in nlogn time (in place). Find Duplicates in O(n) time. Overall 0(n lg n) time. -- Limited memory approach
2. Use Hash table to check if a number is already present. -- Unlimited memory approach.
3. Use distributed approach, lets say you have 10 machines, distribute the numbers as number % 10. And those 10 machines removes the duplicate among assigned number, Union of all those will be the distinguish numbers.
4. Another unlimited memory approach could be BloomFilter (conceptually similar to HashTable). But it save memory if the range of numbers is not too big with respect to the number of numbers. For 32 bit numbers. Memory requirement will be 4BG/8 = 256MB.
In fact you can get it in O(n)
Maintain two numbers x and y and a temporary variable
while iterating through the array, temp= x^array[i]
if(temp==0), print that number.. else keep x=x^array[i] as it is
in order to see that the same number not to get printed store the printed number in y
temp = y^(printed number)
print the number only if temp!=0
Help this explains the algorithm!!
i am sorry... the above program gives wrong solution in some inputs.. i just realized :)
Your solution works for the following question "we are given a SORTED array, which consists of nos. which occur EVEN no. of times, except one, which occurs ODD no. of times. find the that number"
Use Hash Map...
- Amit Modi October 28, 2011Say unique number of elements is k
Extra Memory O(k)
Time O(n)
Sort numbers and do it
Time to sort O(n log n)
No Extra memory required