Yahoo Interview Question Software Engineer / Developers
if range of array element known (Say max no is n) Use index array say idx of size n, set to ZERO.
Iterate through given array a and set idx as idx[a[i]]++;
Count of 1 in idx is the answer. Time: O(n), Space: O(max array value).
Will take more space if range is high (And array values are sparse)
Otherwsie:
Use BST/AVL etc (As Mike said)..
Keep inserting in Tree if it is not there already (Don't insert duplicates)
and keep track of tree size.
At the end, Tree size is the answer.
Time: O(n log n), Space: O(n)
OR even better, Use hash table.
Iterate through the array and insert elements in hash table (Don't insert in case of collision i.e. duplicates).
Hash table size is the answer.
Time: O(n), Space: O(n)
Yep.. a slight modification, computing size of hash table for obtaining the count is not the optimal way.
Instead, use a count variable which is incremented if the element is inserted into hash table else dont increment.
Hi, I think you need to decrement the count variable if the element already exists in the hash table, as you previously counted it.
I guess storing element in hash and increment/decrement counter will not do here.
e.g. for input 1,2,3,4,3,5,2,2,7
Answer should be: 4 (1,4,5,7 are unique, others repeated).
So one soln would be to use index array (as told above) given that input range is known and input is not sparse (Else space wastage will be there).
Other soln would be to use hash where key is given input no and value will be count of that no (i.e. index array concept only but use hash instead of array to avoid space wastage). At the end, count the keys in hash having value ONE which will be the answer.
-> For every element 'i' in array
Insert in hash table, if already exists (--count) else (++count)
O(n) time and space
This will not work for
1,2,3,4,2,3,3
Answer should be: 2 (1 and 4 are unique)
But above will give 1.
Right soln will be as I said, put in hash with array element as key and it's count as value (value 1 if inserted 1st time, increment later on while duplicate).
At the end, just count the hash element having value 1.
@Anurag, the problem with iterating through hash table would add a bit more computations to it i.e. atleast 'n'
Here's a modified solution:
-> For every element 'i' in array
if key=array[i] doesn't exist in hash table
insert with value=1 and ++count
else{ //already exists then
if value==2
continue loop;
if value==1
--count and set value = 2;
}
//This should give you result without iterating hash table in the end
keep on inserting elements in AVL tree. when redundant element is encountered increment the count & do not add it. At the end subtract count from total elements in array & it is the answer.
- mike January 28, 2011Complexity O(n log n).
Any better solution. I am sure it will exist!!