## Centro Interview Question for Senior Software Development Engineers

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
0
of 0 vote

1) Sort the smaller array O(m*log m)
2) Binary search each element in the larger array in the sorted array. O(log n)

Total Time complexity : O(m*log m + log n)

Comment hidden because of low score. Click to expand.
0

If the short array is m and the long array is n, step 2 would be n log m.
Yes binary search is O(log m) on the short array but you have to do it n times.
So its O((n+m)log m)

Comment hidden because of low score. Click to expand.
0
of 0 vote

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).

Comment hidden because of low score. Click to expand.
0

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?

Comment hidden because of low score. Click to expand.
0

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?

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Can you explain your answer more? I don't quite understand it. How can you use the hashcode to find out the index of another array?

Comment hidden because of low score. Click to expand.
0
of 0 vote

Create a hashcode for an Object. Then the index into the other array is obj.hashcode() % array.length. Assume the array is big enough such that there are no collisions.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Just like how most hashtables check for equal keys after finding an entry, check the value

Comment hidden because of low score. Click to expand.
0
of 0 vote

The Hastable/Map is correct. If you don't want reference equality you can always override Equals AND GetHashcode and just end up using Set<T> as long as T implements IEQuatable you are good to go.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.