Interview Question Financial Software Developers
He means that have a single million bit BitSet... and set bits wherever the number fits in the set.... this would work well if the numbers were the first million numbers... 0-1M .... since this is not the case... wed require a mapping function to the BitSet....
If the range of the numbers in the array is given then following algorithm works
i=1
Repeat while i=n
{
if(a(abs(a[i])>0)
then
a(abs(a[i])=-a(abs(a[i])
else
print a(abs(a[i])
endif
i=i+1
end while
Time Complexity O(n) and Space Complexity O(1)
I could not understand this program, what is abs(a[i]>0) will do.
Could you please elaborate... !!!
@Piyush: It is not abs(a[i]>0), it is abs(a[i])>0). abs(a[i]) returns the absolute value of a[i], i.e., if a[i] is 5, it returns 5, if a[i] is -5, it still returns 5.
Instead of using a HashMap , we can rather use a HashSet. Add the element in HashSet from given array. If add(Object o) method returns false (means element is already there in Set) then print that no.
But the problem with this approach is it's using extra memory.
Building of Hashset depends on the efficiency of our hashCode. If a unique hash code is guaranteed for all ur numbers then the complexity of soultion is O(n) which means you have to traverse all the collection before making a Hashset. What if the hash code results in unique hashcode for all elements. Then it will be really worse.
A simple approach can be
prepare a BST with the million integers. while preparing just check if the element exists in BST. this will have a complexity of O(logn). just print the duplicates.
@Rustum:
I agree that BST would be a good choice. But I hope you did not forget that You would traverse your BST for each number... running time O(10^6logn).. or O(nlogn) if I may.
Getting the same hashCode is very rare... and a risk that can be taken with a million numbers. If you know the range of the numbers, and its small, hashTable is a very good way.
However, it is best to ask the interviewer to elaborate on the question. For example, how much extra memory do I have? Do we know the range ? and other such restrictions.
Can't we just sort the array, e.g., merge sort? and then scan the array in linear time and find the duplicates?
Use BitSet to solve this issue. Read the given numbers one by one and set the corresponding bit into the BitSet. Before setting this, just check whether bit is already set or not. If yes, print the number.
- Anonymous December 04, 2010