Nut and Bolt Problem (OR Key and Lock Problem) - Matching Nuts and Bolts when nuts cannot be compared with nuts and bolts with bolts

 Posted on May 1, 2014  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Problem You are given a collection of nuts of different size and corresponding bolts. You can choose any nut & any bolt together, from which you can determine whether the nut is larger than bolt, smaller than bolt or matches the bolt exactly. However there is no way to compare two nuts together or two bolts together. Suggest an algorithm to match each bolt to its matching nut. Compute time complexity of your algorithm. [Read More]
kodeknight  quicksort  partition