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.
Solution
Method 1 - Brute force
Since we can’t compare a nut with
other nuts and a bolt with other bolts, we can’t sort them. So current
best possibility seems to pick nuts one-by-one and find matching bolts
for them. In this manner, we will match all the pairs in O(n^2) time
complexity.
Can we do better?
Method 2 - Partition similar to quicksort
This problem can also be solved in a quick sort kind of technique. We can’t compare a nut with other nuts
and so for bolts, we can compare a nut with bolts and vice-versa. Also
keep in mind that if a Nut(N) is smaller than a Bolt(B) than N is fit
only for bolts smaller than B. Similarly if a Bolt(B’) is smaller than a
Nut(N’) than N is fit only for bolts smaller than B’. So we can go like
following in solving this problem.
- Take a nut from the nuts pile
- Divide bolts around it in 2 parts, which are smaller and larger than this.
- Find a matching bolt to this nut.
- Divide nuts in 2 parts, which are smaller and larger than matching bolt.
Now
we have 2 subsets of Nuts and Bolts. If we pick a nut from small size
nuts pile, we will get a corresponding bolt in smaller size bolts pile
and similarly for large size piles. At every step, we will be able to
divide these piles in 2 halves and reduce complexity by a factor of 2 in
average case. In this case time complexity will be O(nlogn).
In worst case we might have choose the
smallest/largest nut/bolt as reference and our one pile will have zero
nut/bolt and another pile will have all the remaining. In this case time
complexity will be O(n^2), as it is with quicksort.
Algorithm:
Take
a nut; partition the bolts with respect to this nut. We will find the
matching bolt for this nut. Now take the bolt; partition the nuts.
In this manner, we have divided the Original problems into 2 sub-problems.
private static void matchPairs(char[] nuts, char[] bolts, int low,
int high)
{
if (low < high)
{
// Choose last character of bolts array for nuts partition.
int pivot = partition(nuts, low, high, bolts[high]);
// Now using the partition of nuts choose that for bolts
// partition.
partition(bolts, low, high, nuts[pivot]);
// Recur for [low...pivot-1] & [pivot+1...high] for nuts and
// bolts array.
matchPairs(nuts, bolts, low, pivot-1);
matchPairs(nuts, bolts, pivot+1, high);
}
}
T(n) = T( i ) + T(n-i ) + O(n)
Where we have chosen the ith largest nut from a particular pile.
Average time complexity = O(nlogn).
Worst time complexity = O(n^2).
0 comments:
Post a Comment