Find the unique mapping between elements of two same size arrays

I was recently asked this question in an interview:

There are 开发者_运维知识库two arrays of size 'n' each. One array has nuts, the other one has bolts. Each nut fits exactly one bolt and vice-versa. When you compare a nut with a bolt, you get one of the 3 results: tight,loose,fits.

How do you efficiently find the unique mapping?

Sorting is not possible on either of the sets. You never know if b1 is smaller than b2 or

n1 is smaller than n2. Where n1,n2 are nuts and b1,b2 are bolts. Only thing you can do is compare a nut with a bolt and get a result: tight,fits,loose.

---

The quicksort like algorithm does the job:

1. Randomly pick a nut n and use it as pivot to partition the set of bolts B into three sets: tight (B1), loose (B2), fits.
2. Mark the fit bolt as b. Now you use this bolt as pivot to partition the nuts set N\n into two set: tight (N1) or loose (N2).
3. Now you have three pairs: N1 and B1, n and b, N2 and B2. All of them are of the same size. You can do the same partitioning recursively on (N1,B2) and (N2,B1) and you can get the final answer.

It is obvious the complexity is O(N log N), the same as quicksort.

---

Take one nut N0 and compare it against all bolts. With the resulting information, we can split the bolts array into [bolts smaller than B0] + B0 + [bolts larger than B0]. There is always a unique B0 that fits N0 based on the statement of the question.

Then take the next nut N1 and compare it against B0. If the result is "tight", we search the smaller half as we did above with N0. Otherwise, we do the same but with the larger half. Doing this will further split one of the two halves into 2.

Continue doing this until you've worked through all nuts. This is equivalent to quicksort. Average case is O(N logN), but there's the obvious worst case complexity of O(N^2) when the list is "sorted" already.

---

For formal analyses (including quicksort) see http://www.wisdom.weizmann.ac.il/~naor/PUZZLES/nuts_solution.html and http://compgeom.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/05-nutsbolts.pdf