Amazon Interview Question
Country: India
Interview Type: Phone Interview
Algo:
1. During the first scan create a hashmap for all elements storing the count of the key.
2. Now during the next scan consider only those elements whose hash[key] ==1 (Meaning key present only once in the input.) and find the desired element based on the index.
May be you are not familiar with the concept of 'streaming'.
You don't get a second chance.
We need to track numbers that are distinct, so need to go with Set. We need to check if the next number already exists in the Set and if it does then we need to remove it, so need to have a quick lookup - Hash. Insertion order is important so need to be Linked. So, use LinkedHashSet - add numbers as they arrive but check if it exists already. If it exists then rather than additing to the Set, remove it from the Set. So, O(n) time and O(n) space.
Using LinkedHashMap-----
static Map<Integer,Integer> inputs = new LinkedHashMap<Integer,Integer>();
private static void processStream(int a){
int count = 0;
if(inputs.containsKey(a)){
count = inputs.get(a);
}
inputs.put(a, ++count);
}
private static int findNumber(int index){
int i = 0;
for(Entry<Integer,Integer> ent : inputs.entrySet()){
if(ent.getValue() == 1){
i++;
if(i==index){
return ent.getKey();
}
}
}
return -1;
}
Can you explain how the answer is 8 for n = 3?
- eugene.yarovoi November 05, 2012