2. (30 points) Bob, the builder, has a set N of n nuts and a set B of n bolts, s
ID: 3606144 • Letter: 2
Question
2. (30 points) Bob, the builder, has a set N of n nuts and a set B of n bolts, such that each nut in N has a unique matching bolt in B. Unfortunately, the nuts in N all look the same, and the bolts in B all look the same as well. The only kind of comparison that Bob can make is to take a nut-bolt pair (a,b), such that a N and b B, and test it to see if the threads of a are larger, smaller, or a perfect match with the threads of b. Describe an efficient algorithm for Bob to match up all the nuts in N with the corresponding bolts in B. What is the average running time of this algorithm in terms of nut-bolt comparisons that Bob must do? This is a great interview question. It's probably easy to come up with the straightforward, ineff cient solution. The non-trivial solution, on the other hand, requires some thinking. How about we apply the spirit of "partitioning" from quicksort here?Explanation / Answer
Answer is as follows:
We can do this with quick sort as follows bby two functions i.e. Partition and Matching
Partition is used for sorting and Matching is used to match both bolts and nuts of same type.
Partition Function:
Partition(bolts[lo...hi], nut):
j = lo
for i in range(lo, hi):
if bolts[i] < nut:
swap(bolts[i], bolts[j])
j += 1
else if bolts[i] == nut:
swap(bolts[i], bolts[hi])
// the bolt that ends up at i might be larger than nut
i -= 1
swap(bolts[j], bolts[hi])
return j
Similar procedure for partitioning nuts according to a given bolt
Matching Function:
Match(nuts[lo...hi], bolts[lo...hi]):
if lo < hi:
// choose a nut in [lo...hi] at random
chosen = nuts[random(lo, hi+1)]
// partition bolts around the chosen nut
pivot = Partition(bolts[lo...hi], chosen)
// partition nuts around the bolt at the pivot position
Partition(nuts[lo...hi], bolts[pivot])
// nut and bolt at the pivot position match
// solve the subproblem [lo...pivot-1] recursively
Match(nuts[lo...pivot-1], bolts[lo...pivot-1])
// solve the subproblem [pivot+1...hi] recursively
Match(nuts[pivot+1...hi], bolts[pivot+1...hi])
// lines are comments....
if there is any query please ask in comments...
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.