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?

Advertisements
Standard

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s