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)