Puzzle : Nuts and Bolts

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

Advertisements

Tags:

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: