Goldman Sachs Interview Question
Java DevelopersCountry: India
Interview Type: Phone Interview
Constant time is impossible when you must evaluate each element at least once to determine if it's a duplicate or not.
That being said, you can get constant time in determining if the element is indeed a duplicate by iterating through your list and inserting each value into a hash table. Use the numbers as the key values, and they hash table will automatically filter out any duplicates upon insertion.
A quick code example in Java:
HashMap<Integer, Integer> hm = new HashMap();
int[] a = {0,5,9,5,6,7,6,9};
for(int i: a){
hm.put(i, i);
}
for(Integer i: hm.keySet()){
System.out.println(hm.get(i));
}
quite simple... if only u have single digit numbers... use hash functn as k mod 10 where k is the number... and if a number already exists at that position.. then its a duplicate number
Every here is mentioned HashMap and do this do that.
I am really wondering where is the cream of intellectual people gone.
USE HASHSET ..Just Single Traversal is required
3-way quick sort, no extra space of HashMap or HashSet. Best in practice for removing duplicates. Average linear bound runtime (because of duplicates).
Essentially the max bound for comparision is reduced drastically from log(n!) to log(n!/x1!x2!...xn!) where x1, x2, x3...xn are number of duplicate occurences of various elements in array. This is approximately = sum (xilogxi/N) which is linear.
Cheers.
in an interview setting, there not much value in using language features like those to answer these types of questions
Instead of a hash table you can also use a bit vector to save space.
Read input and set the corresponding bit in the bit vector
If bit is already set skip the input value as its a duplicate (because the bit set indicates we've seen the exact value before)
You only save space if the value of the numbers is quite small, in the order of N, N being the number of elements in the list.
Suppose the value of the numbers in the list can be as high as 10000000000000000000000. The bit vector need to have that many bits, while the hash table continues to have size O(N)
Come on, how do you possibly think you can go through N elements in constant time?
- Miguel Oliveira September 11, 2013The constant time part is about using a hash table to check if a number was already seen in the list. And also insert numbers in the hash table in constant time.