Nuts and bolts. A disorganized carpenter has a mixed pile of N nuts and N bolts. The goal is to find the corresponding pairs of nuts and bolts. Each nut fits exactly one bolt and each bolt fits exactly one nut. By fitting a nut and a bolt together, the carpenter can see which one is bigger (but the carpenter cannot compare two nuts or two bolts directly). Design an algorithm for the problem that uses NlogN compares (probabilistically).
My thoughts and solution:
Well, according to the question, the nut and bolt has a one-to-one relation. So the first thing come into my mind is to sort the nuts and bolts into ascending order and then we can put them together to a pair one by one.
However, we cannot compare two nuts or bolts directly. So we have to think about indirect ways. Say we have two nuts N1 and N2. Well, since the nut and bolt has a one-to=one relation, there must exist two bolts B1 and B2 which exactly fit with N1 and N2. So if we try to fit both nuts with B1 (or B2), we can tell which nut is bigger. This is also suggested by the question that “By fitting a nut and a bolt together, the carpenter can see which one is bigger”. The same works for comparing B1 and B2 indirectly.
OK, the question did mention NlogN compares probabilistically. Well that reminds me of QuickSort. So how does it apply here? QuickSort requires partitioning and recursion. OK, let’s look at partitioning.
To partition the nuts, we need to randomly select one nut, then compare it with the rest. But we cannot, at least not directly. So the alternative is to randomly select one bolt “B”, then compare each nut with it. In the end, we will have two small piles of nuts (one smaller than the bolt “S” and the other larger “L”) and the right one fits in the bolt “N”. Done!
Then we can do recursion, right? for both piles of nuts, randomly choose a bolt to partition…But wait! Whatever bolt we pick for “S” should come from the set of bolts that correspond to the nuts in “S” and so is the case for “L”. Otherwise, we cannot guarantee the correctness of the QuickSort algorithm.
So before we do the recursion, we have to find out the corresponding piles of bolts for “S” and “L”. How? Well, we do know the nut “N” that fits into “B” perfectly. We can do a partition of the bolts based on “N”. Then we will get our desired piles of bolts for “S” and “L”.
Now we can go on to the recursion.
About the comparison, it is O(NlogN). But I’m afraid we are using 2NlogN since we compared 2N in partitioning the bolts and nuts. If you have some good ideas, please leave some comments.