Nuts & Bolts Problem

Given a set of n nuts of different sizes and n bolts of different sizes. There is a one-one mapping between nuts and bolts. 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.

We will give you a compare function to compare nut with bolt.

Example:

Given nuts = ['ab','bc','dd','gg'], bolts = ['AB','GG', 'DD', 'BC'].

Your code should find the matching bolts and nuts.

one of the possible return:

nuts = ['ab','bc','dd','gg'], bolts = ['AB','BC','DD','GG'].

Solution:

This is a modified Quick Sort. We need to perform following steps:

1. Use a pivot from nuts to partition bolts.
2. Use the index from previous partition to find a new pivot in bolts
3. Use this pivot to partition nuts
4. Repeat 1 to 3 for left part and right part for nuts and bolts.

Code:

/**
 * public class NBCompare {
 *     public int cmp(String a, String b);
 * }
 * You can use compare.cmp(a, b) to compare nuts "a" and bolts "b",
 * if "a" is bigger than "b", it will return 1, else if they are equal,
 * it will return 0, else if "a" is smaller than "b", it will return -1.
 * When "a" is not a nut or "b" is not a bolt, it will return 2, which is not valid.
*/
public class Solution {
    /**
     * @param nuts: an array of integers
     * @param bolts: an array of integers
     * @param compare: a instance of Comparator
     * @return: nothing
     */
    public void sortNutsAndBolts(String[] nuts, String[] bolts, NBComparator compare) {
        if (nuts == null || bolts == null) {
            return;
        }
        if (nuts.length != bolts.length) {
            return;
        }
        quickSort(nuts, bolts, 0, nuts.length - 1, compare);
    }

    private void quickSort(String[] nuts, String[] bolts, int left, int right, 
                            NBComparator compare) {
        if (left >= right) {
            return;
        }
        String pivot = bolts[left + (right - left) / 2];
        int index = partition(nuts, pivot, left, right, compare);
        partition(bolts, nuts[index], left, right, compare);
        quickSort(nuts, bolts, left, index - 1, compare);
        quickSort(nuts, bolts, index + 1, right, compare);
    }

    private int partition(String[] strs, String pivot, int left, int right, NBComparator compare) {
        for (int i = left; i <= right; i++) { 
            if (compare.cmp(strs[i], pivot) == 0 || compare.cmp(pivot, strs[i]) == 0) {
                String temp = strs[i];
                strs[i] = strs[left];
                strs[left] = temp;
                break;
            }
        }
        String spivot = strs[left];
        while (left < right) {
            while (left <= right && (compare.cmp(strs[right], pivot) == -1 ||
                                        compare.cmp(pivot, strs[right]) == 1)) {
                right--;
            }
            strs[left] = strs[right];
            while (left < right && (compare.cmp(strs[left], pivot) == 1 ||
                                        compare.cmp(pivot, strs[left]) == -1)) {
                left++;
            }
            strs[right] = strs[left];
        }
        strs[left] = spivot;
        return left;
    }
}