Nuts and Bolts

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.

Thoughts

我感觉这一题比较难，只能互相之间比较

采用quicksort中partion的方法

1. 在bolt中取一个value做pivot, 可以定为每次取剩下array中的最后一个
2. 对nuts坐partition,得到pivot对应的nut的index
3. 再用这个nut对Bolt坐partion
4. 这样在nuts和bolts中pivot这个upper和lower的位置就是确定的了
5. 然后再recursivly call两边left和right

Solution

我用自己的compare测试是对的，但是lint通不过

# class Comparator:
#     def cmp(self, a, 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.
class Solution:
    # @param nuts: a list of integers
    # @param bolts: a list of integers
    # @param compare: a instance of Comparator
    # @return: nothing
    def sortNutsAndBolts(self, nuts, bolts, compare):
        # write your code here
        if not nuts or not bolts:
            return
        lengthN = len(nuts)
        lengthB = len(bolts)
        if lengthN != lengthB:
            return

        self.matchPair(nuts, bolts, 0, lengthN-1, compare)

    def matchPair(self, nuts, bolts, start, end, compare):
        if start < end:
            pivot = self.quickSort(nuts, start, end, bolts[end], compare)
            self.quickSort(bolts, start, end, nuts[pivot], compare)

            self.matchPair(nuts, bolts, start, pivot-1, compare)
            self.matchPair(nuts, bolts, pivot+1, end, compare)

    def quickSort(self, arr, start, end, pivot, compare):
        if start >= end:
            return arr[start:end + 1]

        mid = start
        # select first one as pivot
        for i in range(start + 1, end + 1):
            if (compare.cmp(arr[i], pivot) == -1) or (compare.cmp(pivot, arr[i]) == 1):
                mid += 1
                arr[mid], arr[i] = arr[i], arr[mid]
            elif (compare.cmp(arr[i], pivot) == 0) or (compare.cmp(arr[i], pivot) == 0):
                arr[i], arr[start] = arr[start], arr[i]
                i -= 1

        # swap pivot and mid, very important!!
        arr[start], arr[mid] = arr[mid], arr[start]

        return mid

/**
 * 本代码由九章算法编辑提供。没有版权欢迎转发。
 * - 九章算法致力于帮助更多中国人找到好的工作，教师团队均来自硅谷和国内的一线大公司在职工程师。
 * - 现有的面试培训课程包括：九章算法班，系统设计班，BAT国内班
 * - 更多详情请见官方网站：http://www.jiuzhang.com/
 */

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) {
          //
        int m = l;
        for (int i = l + 1; i <= u; i++) {
            if (compare.cmp(str[i], pivot) == -1 || 
                compare.cmp(pivot, str[i]) == 1) {
                //
                m++;
                swap(str, i, m);
            } else if (compare.cmp(str[i], pivot) == 0 || 
                       compare.cmp(pivot, str[i]) == 0) {
                // swap nuts[l]/bolts[l] with pivot
                swap(str, i, l);
                i--;
            }
        }
        // move pivot to proper index
        swap(str, m, l);

        return m;
    }

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