Nuts & Bolts Problem

Question

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.

The order of the nuts or bolts does not matter. You just need to find the matching bolt for each nut.

Tags

Quick Sort Sort

Related Problems

Medium First Bad Version

Analysis

螺帽螺母问题脱胎于排序问题，这里的特别之处在于需要通过两个array进行对应的排序。这就需要利用一个array中的元素对另一个array进行partition，并反过来重复这一个过程，最终让两个array都满足comparator所定义的相同顺序。

这里要注意的是partition的变式，因为pivot并非来源当前array，只能通过一方元素作为基准，对另一个array进行partition。

核心在于：首先使用 nuts 中的某一个元素作为基准对 bolts 进行 partition 操作，随后将 bolts 中得到的基准元素作为基准对 nuts 进行 partition 操作。

Solution

Two Pointers Partition

http://www.jiuzhang.com/solutions/nuts-bolts-problem/

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;

        qsort(nuts, bolts, compare, 0, nuts.length - 1);
    }

    private void qsort(String[] nuts, String[] bolts, NBComparator compare,
                       int l, int u) {
        if (l >= u) return;
        // find the partition index for nuts with bolts[l]
        int part_inx = partition(nuts, bolts[l], compare, l, u);
        // partition bolts with nuts[part_inx]
        partition(bolts, nuts[part_inx], compare, l, u);
        // qsort recursively
        qsort(nuts, bolts, compare, l, part_inx - 1);
        qsort(nuts, bolts, compare, part_inx + 1, u);
    }

    private int partition(String[] str, String pivot, NBComparator compare,
                          int l, int u) {
        for (int i = l; i <= u; i++) {
            if (compare.cmp(str[i], pivot) == 0 ||
                compare.cmp(pivot, str[i]) == 0) {
                swap(str, i, l);
                break;
            }
        }
        String now = str[l];
        int left = l;
        int right = u;
        while (left < right) {
            while (left < right &&
            (compare.cmp(str[right], pivot) == -1 ||
            compare.cmp(pivot, str[right]) == 1)) {
                right--;
            }
            str[left] = str[right];

            while (left < right &&
            (compare.cmp(str[left], pivot) == 1 ||
            compare.cmp(pivot, str[left]) == -1)) {
                left++;
            }
            str[right] = str[left];
        }
        str[left] = now;

        return left;
    }

    private void swap(String[] str, int l, int r) {
        String temp = str[l];
        str[l] = str[r];
        str[r] = temp;
    }
}

Another Way of Partition

http://algorithm.yuanbin.me/zh-hans/problem_misc/nuts_and_bolts_problem.html

/**
 * 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;
        }

        int totalLength = nuts.length;
        qsort(nuts, bolts, 0, totalLength - 1, compare);
    }

    public void qsort(String[] nuts, String[] bolts, int l, int r, NBComparator compare) {
        if (l >= r) {
            return;
        }
        // Find partition index for nuts, with bolts[l]
        int partIndex = partition(nuts, bolts[l], l, r, compare);
        // Partition bolts, with nuts[partIndex]
        partition(bolts, nuts[partIndex], l, r, compare);

        // quick sort recursively
        qsort(nuts, bolts, l, partIndex - 1, compare);
        qsort(nuts, bolts, partIndex + 1, r, compare);
    }

    public int partition(String[] arr, String pivot, int l, int r, NBComparator compare) {
        // pivot is from another array
        int m = l;
        for (int i = l + 1; i <= r; i++) {
            if (compare.cmp(arr[i], pivot) == -1 || compare.cmp(pivot, arr[i]) == 1) {
                m++;
                swap(arr, i, m);
            } else if (compare.cmp(arr[i], pivot) == 0 || compare.cmp(pivot, arr[i]) == 0) {
                swap(arr, i, l);
                i--;
            }
        }
        swap(arr, m, l);

        return m;
    }

    public void swap(String[] arr, int l, int r) {
        String temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;
    }
}

Reference

• geeksforgeeks: Nuts & Bolts Problem (Lock & Key problem)

• yuanbin: Nuts and Bolts Problem