Well,
This is a quite easy puzzle. It was asked to my friend Sanjeet Khaitan during one of the technical interviews in some company.
Problem : You are given a set of nuts and bolts of different sizes. Each nut has a corresponding unique bolt for it. We need to find out for each nut its corresponding bolt. The condition is that a nut can only be compared with a bolt and vice versa. So you can not compare two nuts and two bolts for their sizes directly. How would you do it?
Solution : Actually, this nut and bolt stuff is just an added complication. If we look at it, it is nothing but a quick sort algorithm. We can choose a nut as a pivot and using which we can partition bolts. Also during this process, we would have been able to find out its corresponding bolt. Using this bolt, we will partition nuts. Now recurse on left and right partition exactly the same way we do it for quick sort.
–Saurabh Joshi
Tags: puzzle
