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'].

we will tell you the match compare function. If we give you another compare function.

the possible return is the following:

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

So you must use the compare function that we give to do the sorting.

Solution: partition.

public void sortNutsAndBolts(String[] nuts, String[] bolts, NBComparator compare) {
    if(nuts == null || bolts == null || nuts.length != bolts.length) {
        return ;
    }
    findMatch(nuts, bolts, 0, bolts.length - 1, compare);
}
public void findMatch(String[] nuts, String[] bolts, int nstart, int nend, NBComparator compare) {
    if(nstart > nend) {
        return ;
    }
    int pivot = partition(nuts, nstart, nend, bolts[nstart], compare);
    partition(bolts, nstart, nend, nuts[pivot], compare);
    findMatch(nuts, bolts, nstart, pivot - 1, compare);
    findMatch(nuts, bolts, pivot + 1, nend, compare);
}
public int partition(String[] strs, int left, int right, String pivot, NBComparator compare) {
    for(int i = left; i <= right; i++) {
        if(compare.cmp(strs[i], pivot) == 0) {
            String tmp = strs[left];
            strs[left] = strs[i];
            strs[i] = tmp;
            break;
        }
    }
    String now = strs[left];
    while(left < right) {
        while(left < right && (compare.cmp(pivot, strs[right]) == -1 || compare.cmp(strs[right], pivot) == 1)) {
            right--;
        }
        strs[left] = strs[right];
        while(left < right && (compare.cmp(pivot, strs[left]) == 1 || compare.cmp(strs[left], pivot) == -1)) {
            left++;
        } 
        strs[right] = strs[left];
    }
    strs[left] = now;
    return left;
}