algorithms

# A Google Job Interview Test

The story goes as follows. Google gave two lists to a job contender, instructing him to programmatically find their mutual members.

After that, the candidate was supposed to convert both lists to two lists consisting of prime numbers, such that two different members would always give a different prime and two equal members of any list would give the same prime numbers.

For example, if one list were [1,2,3,4,5] and the second were [7,4], they were expecting to transform them to [2,3,5,7,11] and [17,7].

To the first, second, third, fourth and fifth prime number and to the fourth and seventh prime number. Then, they were expected to multiply the first list to 2310 and then to try to divide it first by 17 and then by 7. As 7 divides 2310, 4 (as 7 is the prime number 4) is in both lists.

Neat, isn’t it? No it isn’t, very far from a good solution, for a number of reasons.

The Internet is full of this story, you may Google it yourself.

The question is, how to do it optimally. I’ll give you the short answer, with no mathematical proof, however.

1. sort the first list
2. sort the second list
3. bisection for A[0]  from B[0] to B{max] to index_b
4. if A[0]==B[index_b] you have the first pair
5. in any case index_b+1 will be useful for the next low boundary of B when bisecting it the next time
6. use the first unpaired element of B and bisect it in A (index_b or index_b+1, depends on equality
7. turn the tables between A and B
8. do it to the top

This way, if the names of all Americans were in list A, and all Chinese names in list B, both in the UTF-8 coding, the algorithm would be able to find those rare matches without even touching the wast majority of elements of both lists; except in the sorting part.

Do you even need a Python code example now?

Standard