Nuts & Bolts Problem

LintCode Q 399 - 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.
Using the function we give you, you are supposed to sort nuts or bolts, so that they can map in order.

Example
Given nuts = ['ab','bc','dd','gg'], bolts = ['AB','GG', 'DD', 'BC'].
Your code should find the matching of bolts and nuts.
According to the function, one of the possible return:
nuts = ['ab','bc','dd','gg'], bolts = ['AB','BC','DD','GG'].

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.

Solution

Solution : Two pointers

This given compare function is:

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.

• define a sort function quickSort(nuts, bolts, l, r, compare)
  • choose nuts[l] as pivot, partition the bolts array, get the pivot position.
  • according to the pivot position, choose bolts[pivot_pos] as pivot, partition the nuts array
  • do the quick sort recursively.
• the key point is step 2.

Code:

public void sortNutsAndBolts (String[] nuts, String[] bolts, NBComparator compare) {

	if (nuts == null || bolts == null || nuts.length != bolts.length) return;

	quickSort(nuts, bolts, compare, 0, nuts.length);

	return;
}

private void quickSort (String[] nuts, String[] bolts, NBComparator compare, int left, int right) {

	if (left >= right) return;

	// find the partition index for bolts with nuts[l]
	int parIndex = partition(bolts, nuts[left], compare, left, right);

	// partition nuts with bolts[arIndex]
	partition(nuts, bolts[parIndex], compare, left, right);

	// qsort recursively
	quickSort(nuts, bolts, compare, left, parIndex - 1);
	quickSort(nuts, bolts, compare, parIndex + 1, right);
}

private void partition (String[] strs, String pivot, NBComparator compare, int left, int right) {
	
	// find pivot in another string
	for (int i = l; i <= r; 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 = r;
        
	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;
}