Thursday, February 5, 2015

Microsoft Question: Nuts and Bolts problem

Question: Given an array of nuts of different sizes and array bolts of different sizes. There is a one-one mapping between nuts and bolts. Match nuts and bolts efficiently with the given constraint that comparison of a nut to another nut or a bolt to another bolt is not allowed. It means nut can only be compared with bolt and bolt can only be compared with nut to see which one is bigger/smaller.

Solution: Tweak quick sort to achieve it.

Implementation:

int split(int *arr, int low, int high, int pivot)
{
        int j = low;
        for(int i = low; i < high; ++i)
        {
                if(arr[i] < pivot)
                {
                        std::swap(arr[i], arr[j]);
                        ++j;
                }
                else if(arr[i] == pivot)
                {
                        std::swap(arr[i], arr[high]);
                        --i;
                }
        }
        std::swap(arr[j], arr[high]);
        return j;
}

void matchNutsBolts(int *nuts, int *bolts, int low, int high)
{
        if(!nuts || !bolts)
                return;
        if(low < high)
        {
                int pivot = split(nuts, low, high, bolts[high]);
                split(bolts, low, high, nuts[pivot]);
                matchNutsBolts(nuts, bolts, low, pivot - 1);
                matchNutsBolts(nuts, bolts, pivot + 1, high);
        }

}

Complexity: O(nlogn)

1 comment:

  1. Hey! I have a doubt. What is the significance of :

    else if(arr[i] == pivot)
    {
    std::swap(arr[i], arr[high]);
    --i;
    }

    What purpose does this solve?

    ReplyDelete