Nuts and bolts problem
  • sorting
  • quicksort
  • matching
  • randomizedquicksort
  • Posted: 7 years ago
  • Updated: 6 years ago
  • Edit
  • answers (1)
  • views (8764)

You are given a mixed pile of n nuts and n bolts. Each nut exactly fits one bolt and vice-versa. You can see which one is bigger, smaller or equal by fitting a nut and bolt together, but you can't compare two nuts or two bolts directly. How will you design an algorithm to find the matching pairs of nuts and bolts.

Posted Answers

We can find the matching pairs of nuts and bolts by modifying randomized quicksort.

  • Pick a random bolt \( b \) .
  • Compare bolt \( b \) with all the nuts, partition the nuts into those of size lessThan \( b \) and greaterThan \( b \).
  • Partition the bolts - Since we can't compare bolt to bolt and from the last step we know the matching nut \( n \) to bolt \( b \), we compare \( n \) to all the bolts and partition the bolts into those of the size lessThan \( n \) and greaterThan \( n \).
  • Recurse for the lessThan and greaterThan partitions of nuts and bolts.

Running time of this algorithm is \( O(n^{2}) \).

Let the nuts be denoted by \( [a_1, a_2,...,a_n] \) and bolts be \( [b_1, b_2,...,b_n] \).

for i = 1 to n
for j = 1 to n
if a(i) matches b(j)
pair (a(i), b(j));
return all the pairs

You need to Sign In to post your solution.