Bob the builder has a set N of n nuts and a set B of n bolts

Bob, the builder, has a set N of n nuts and a set B of n bolts, such that each nut in N has a unique matching bolt in B. Unfortunately, the nuts in N all look the same, and the bolts in B all look the same as well. The only kind of comparison that Bob can make is to take a nut-bolt pair (a, b), such that a epsilon N and b epsilon B, and test it to see if the threads of a are larger, smaller, or a perfect match with the threads of b. Describe an efficient algorithm for Bob to match up all the nuts in N with the corresponding bolts in B. What is the average running time of this algorithm in terms of nut-bolt comparisons that Bob must do? This is a great interview question. It\'s probably easy to come up with the straightforward, inefficient solution. The non-trivial solution, on the other hand, requires some thinking. How about we apply the spirit of \"partitioning\" from quicksort here?

Solution

Consider the following algorithm:

Step 1: Take any nut at random and using it to partition the bolts into two groups. One group has diameter smaller than the chosen nut and the other group has the diagram larger than the chosen nut.

This results in finding out the bolt that matches with the nut and forming two sub-groups.

------------------------------------------------------------------------------------------------------------------

Step 2: Next use the bolt and partition the nuts into two groups. One group has diameter smaller than the bolt and the other group has diameter larger than the bolt.

------------------------------------------------------------------------------------------------------------------

Step 3: It is given that every bolt has an unique matching nut. So, the size of the group of bolts with smaller diameter is equal to the size of the group of nuts with smaller diameter. Same result holds for the bigger group also.

Therefore, repeat the above method on each of the 2 matching groups. This method is repeated till all matching is done.

------------------------------------------------------------------------------------------------------------------

Time Complexity of this algorithm:

Each round needs a maximum of O(n) comparisons in order to sub divide the groups into two smaller groups. And there are a total of O(log n) such groups.

So, the total comparisons = O(n log n). This is the time complexity.