Finding matches in two bags

Question

This was one of the interview questions, and I was wondering if I did it right, and want to know if my solution is the most efficient one. O(n log n)

Given a bag of nuts and a bag of bolts, each having a different size within a bag but exactly one match in the other bag, give a fast algorithm to find all matches.

Since there is always a match between 2 bags, I said there will be same number of nuts and same number of bolts. Let the number be n.

I would first sort components in each bag each component's weight, and it is possible to do that because they all have different size within a bag. Using merge sort, it will have O(n log n) time complexity.

Next, it would be just easy process of matching each component in 2 bags from lightest to heaviest.

I want to know if this is the right solution, and also if there is any other interesting way to solve this problem.

Answer 1

There is a solution to this problem in O(nlgn) that works even if you can't compare two nuts or two bolts directly. That is without using a scale, or if the differences in weight are too small to observe.

It works by applying a small variation of randomised quicksort as follows:

1. Pick a random bolt b.
2. Compare bolt b with all the nuts, partitioning the nuts into those of size less than b and greater than b.
3. Now we must also partition the bolts into two halves as well and we can't compare bolt to bolt. But now we know what is the matching nut n to b. So we compare n to all the bolts, partitioning them into those of size less than n and greater than n.
4. The rest of the problem follows directly from randomised quicksort by applying the same steps to the lessThan and greaterThan partitions of nuts and bolts.