# Nuts and 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.


## 题解

### Python

# 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):
if nuts is None or bolts is None:
return
if len(nuts) != len(bolts):
return
self.qsort(nuts, bolts, 0, len(nuts) - 1, compare)

def qsort(self, nuts, bolts, l, u, compare):
if l >= u:
return
# find the partition index for nuts with bolts[l]
part_inx = self.partition(nuts, bolts[l], l, u, compare)
# partition bolts with nuts[part_inx]
self.partition(bolts, nuts[part_inx], l, u, compare)
# qsort recursively
self.qsort(nuts, bolts, l, part_inx - 1, compare)
self.qsort(nuts, bolts, part_inx + 1, u, compare)

def partition(self, alist, pivot, l, u, compare):
m = l
i = l + 1
while i <= u:
if compare.cmp(alist[i], pivot) == -1 or \
compare.cmp(pivot, alist[i]) == 1:
m += 1
alist[i], alist[m] = alist[m], alist[i]
i += 1
elif compare.cmp(alist[i], pivot) == 0 or \
compare.cmp(pivot, alist[i]) == 0:
# swap nuts[l]/bolts[l] with pivot
alist[i], alist[l] = alist[l], alist[i]
else:
i += 1
# move pivot to proper index
alist[l], alist[m] = alist[m], alist[l]

return m


### C++

/**
* class Comparator {
*     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.
*/
class Solution {
public:
/**
* @param nuts: a vector of integers
* @param bolts: a vector of integers
* @param compare: a instance of Comparator
* @return: nothing
*/
void sortNutsAndBolts(vector<string> &nuts, vector<string> &bolts, Comparator compare) {
if (nuts.empty() || bolts.empty()) return;
if (nuts.size() != bolts.size()) return;

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

private:
void qsort(vector<string>& nuts, vector<string>& bolts, Comparator 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);
}

int partition(vector<string>& str, string& pivot, Comparator 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;
std::swap(str[m], str[i]);
} else if (compare.cmp(str[i], pivot) == 0 ||
compare.cmp(pivot, str[i]) == 0) {
// swap nuts[l]/bolts[l] with pivot
std::swap(str[i], str[l]);
--i;
}
}
// move pivot to proper index
std::swap(str[m], str[l]);

return m;
}
};


### Java

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

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