Expedia Interview Question Java Developers
Country: India
Interview Type: Phone Interview
With little extra space, it is possible to use hashing algorithms and find results in O(N) time as well.
Store shorter array in a different array using hashing technique, and find the another array's element into it.
If the range of number is given (if they say that numbers lie between 0 to 10k), then we can use bit vector approach to do it with time complexity O(max(n1, n2)) and space complexity of O(min(n1,n2)). With bit vector approach, we would use only one bit (not byte) to mark the presence of an integer. Approach is : put smaller array in bit vector and then check the elements of larger array in bit vector.
The size of the arrays shouldn't matter in this case since each bit represents an integer value. Regardless of the size of the array, you will need 1 bit for each integer in range.
As to the individual complaining that the Set approach is disallowed...see Java Set. What is described here is not a Set as I interpret it.
Sort the smaller of the two given arrays. O(log n)
- teli.vaibhav December 28, 2013Use Binary Search to search each element for the other array in the sorted one.
Total Time complexity O(n*log n + m*logn)