Centro Interview Question Senior Software Development Engineers
Country: United States
Interview Type: Phone Interview
Why is it necessary to sort?
My optimized solution which the interviewer accepted:
Each object has a hashcode function, such that the array indices may act as keys in a hashtable. Then, iterate over the smaller array. During iteration, use each object's hashcode to calculate an index into the other array(e.g. hashcode % length). If found, it is a common element.
This solution has running time O(n). Space: O(1).
Can you explain more about your answer? I don't quite understand it. How can you use a hashcode of an object to find out the index in another array? My thought was to get the hash code in the shorter array and store them in a hash set, then iterate through the longer array?
This is easier said than done. How do you get an index to the other array out of the hash code? This requires a very specific and contextualized hash function. How do you choose the hash function? How do you even find it efficiently?
Can such a hashcode function exist? I mean, technically, the equal objects could be anywhere in an array of a different size. Which I could shuffle at any moment. How do you deterministic get it's index from a hash function that is ran on a completely different array.
{a, b, c, d} {e, b, d, q, f, g, v}
vs
{a, b, c, d} {e,q, b, v, f, g, d}
vs
{a, b, c, d} {d,b,c,q,a}
The first array is exactly the same, so the hash keys should be the same. But the second one is completely different and you have no way of knowing that. How do you get the index from the hashcode? Note that the second array in the first example and the second array in the second example have the same lengths and thus hashcode%length would need to give you two different values on the same hashcode.
This is assuming that I understand you right in that you only hash the smaller array values and then try to "make indices come out of thin air" from that hash.
1) Sort the smaller array O(m*log m)
- teli.vaibhav June 25, 20152) Binary search each element in the larger array in the sorted array. O(log n)
Total Time complexity : O(m*log m + log n)