The Nuts n Bolts Problem

Posted: February 13, 2011 in Algorithms, data structures, inMobi

Q. There are n nuts and corresponding bolts. However, all nuts and bolts are shuffled and we have to device a technique to pair them.

  • No two pairs are of same size.
  • Each nut has exactly one bolt for it.
  • You can’t compare nut with a nut and same with bolt.
  • You can determine by a comparison if a nut is greater or a bolt is greater.

A. This problem can also be solved in a quick sort kind of technique.

  • Pick up nut n1 with all bolts. Divide all bigger bolts on one side and smaller bolt on other side. One bolt say b1 matches n1 to make the pair.
  • Take nut n2 and compare with bolt b1. If bigger bolt is required look in greater set otherwise in the smaller set.
  • Do the same with rest of the nuts. This way we are saving the number of comparisons by categorizing.

Time complexity is approximately O(nlogn)

Advertisements
Comments
  1. Badrinath says:

    There are N nuts and N bolts. All are of different size and each nut has a bolt for it.So, Just sort both of them.Then one-one mapping!

  2. Also as the question clearly states that you are not allowed to compare a nut with another nut, or a bolt with another bolt, its inherently impossible to sort them initiaaly.
    The approach mentioned is a brainy workaround , and does almost the same thing in the same time.

  3. Karma says:

    @Badrinath: You can’t compare nut with nut (bcoz of Rule 3) and hence can’t sort . So your method is INVALID.
    @Harsh : Sorting twice is still O(nlogn) if sorting once cost you O(nlogn).

  4. Anonymous says:

    yes ur method is wrong. As u are sorting bolts , before comparing nut n1 with bolt b1.
    Anyone has a better method, other than comparing each nut to each and every bolt ?

    Thanks.

  5. chittu says:

    I dont see any things wrong with the approch though, still this approch may not be optimal always, it depends on number of nuts and bolts given and size of the first pick.

  6. dave says:

    This method is actually performing merge sort so, its worst case will be n squared complexity (when he always picks up smallest or largest nut) and best will be nlogn when he picks up middlemost nut evey time

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