CareerCup

java solution by sorting

import java.util.Arrays;

public class FindMinDiff {
    public static void findWithSort(int[] a, int[] b) {
        Arrays.sort(a);
        Arrays.sort(b);
        int ia = 0, ib = 0;
        int diff = Integer.MAX_VALUE;
        int ea = 0; // element from A
        int eb = 0; // element from B
        do {
            int curDiff = Math.abs(a[ia] - b[ib]);
            if (diff > curDiff) {
                ea = a[ia];
                eb = b[ib];
                diff = curDiff;
            }
            if (a[ia] < b[ib]) {
                ia++;
            } else {
                ib++;
            }
        } while (ia < a.length && ib < b.length);
        System.out.println("diff(" + ea + ", " + eb + ") = " + diff);
    }
}

After both arrays are sorted, we can go through the same logic as the merge sort (the actually sorted array output is not necessary). While we going though both arrays during the merge processes, if the previous pick and current pick are from different source array (A,B) we calculate & Keep track of the Min ABS(A-B) value (if the value from A and B are the same we can stop the program and and return "0" ). Once one of the array is done processing just make sure do the last check with the other array for the Min.

Approach 1: w/o sorting it’ll be O(n^2) as we need to iterate the 2nd list for each element of 1st list
Approach 2: sort the arrays with O(nlgn), n is the size of larger array. Then for each element in first array find the last element of a decreasing diff sequence in the 2nd array. The sequence starts from the next element of the previous sequence’s last element in the 2nd array. So, we are scanning both the array at most once and hence the complexity is O(m+n) = O(n). Total complexity: O(nlgn)+O(n) = O(nlgn)

O(nlgn) solution:

int minDiff(int[] A, int B[])
{
	int i, j, diff, Prevdiff, mindiff = MAX_INTEGER;
     quicksort(A);
	quicksort(B);

	for(i=0, j=0; i<A.length; i++)
	{
		prevdiff = MAX_INTEGER;
		while(j<B.length && (diff = Math.abs(A[i]-B[j])) <= prevDiff)
		{			
                  prevDiff = diff;
                  j++;
		}
		
		if(prevDiff <= mindiff)
			mindiff = prevDiff;
	}

	return mindiff;
}

assuming size of arrays are j, k and n = j + k

without sorting:
compare all possible sets in O(n^2)

with sorting: combine both arrays into a combined array with extra data flag identifying with set it is from. Now sort the combined array according to value. Iterate over the combined array and compare adjacent(opposite flagged) elements. Note that if the elements are not adjacent and opposite then cannot be best pair(can prove if needed). Find best pair in O(n log n)

Can we view this question as putting several points on a x-axis and finding the closest two points?
Here's a thought, probably will have time tomorrow to try it out:
1. put A and B in HashSet setA and setB while keeping track of max and min value of all data.Check duplicate while adding data to maps. If there is overlap between A and B, simply return the overlapping element. ( |X-Y|==0 )
O(n)
2. boolean[] buffer = new boolean[max-min];
3. mark all data from setA and setB in the boolean array. buffer[data-min] = true; O(n)
4. the above process automatically sorted all the data. now we just need to count the distance between every two adjacent elements which are from different HashSets in the buffer. keep track of the minimum count and the indexes correspond to the minimum count. O(n)
5. return the indexes + min.

Overall, it should be O(3n) time and O(2n) space.

If the arrays are sorted we can apply merging step of merge sort and if not sorted theb we can do it by comparing one element with every other..

using namespace std;

int FindPairWithMinDiff(vector<int> a, vector<int>b, pair<int, int> &minDiffPair)
{
	if(a.size() < 1 || b.size() < 1)
		return -1;

	int min = abs(a[0] - b[0]);
	int aPtr = 0, bPtr = 0, aIter = 0, bIter = 0;

	while(min > 0 && aIter < a.size() && bIter < b.size())
	{
		int curDiff = abs(a[aIter] - b[bIter]);
		if(min > curDiff)
		{
			min = curDiff;
			aPtr = aIter;
			bPtr = bIter;
        }

        if(a[aIter] < b[bIter])
        {
        	++aIter;
        }
        else
        {
        	++bIter;
        }
    }

    while(min > 0 && aIter < a.size())
    {
    	int curDiff = abs(a[aIter] - b[bIter - 1]);
    	if(min > curDiff)
    	{
    		min = curDiff;
    		aPtr = aIter;
    		bPtr = bIter - 1;
        }
        ++aIter;
    }

    while(min > 0 && bIter < b.size())
    {		
        int curDiff = abs(a[aIter - 1] - b[bIter]);
    	if(min > curDiff)
    	{
    		min = curDiff;
    		aPtr = aIter - 1;
    		bPtr = bIter;
        }
        ++bIter;
    }
    minDiffPair = make_pair(a[aPtr], b[bPtr]);
    
    return 0;
}

int main()
{
   vector<int> a = {0, 12, 44};
   vector<int> b = {5, 10, 11, 12};
   
   pair<int, int> pr;
   
   if(0 == FindPairWithMinDiff(a, b, pr))
      cout << pr.first << ", " << pr.second << endl;
   
   return 0;
}

If both arrays are sorted, This can be done in O(log m log n).
Here is how
1. Find middle element of both arrays say a=A[mid1] and b=B[mid2].
2. If a==b return 0, we have found the min
3. If(a>b) min is Min(|a-b|, minimum in A(0.. mid1) and B(mid2... end))
4. if(a<b) min is Min(|a-b|, minimum in A(mid1... end) and B(0... mid2))

Here is a simple python solution:

from numpy import *
def axbkron(a, b):
x = array(zip(kron(a, ones(len(b))),kron(ones(len(a)), b)))
return max(abs((x[:, 0]-x[:,1])))

This O(nlogn) solution.
First sort both the arrays A and B. Now for each element in A search for the nearest element of A in B using binary search.
The complexity is O(nlogn+mlogm+nlogm) = O(nlogn)

1.merge Sort the arrays .
2.put the elements in a single array with an extra flag indicating which array
3.find the most adjacent numbers form the single array we have(assume like number line).
4.in case we hit an element with both flags enabled thts it, we can return (implies present in both arrays)
5.other wise maintain a variable tht has the min value we are looking for.
::calulate the min value based on the flags (whether present in both arrays or array1 or array2)


-1 2 4
-3 -4 5

-4(0,1) -3(0,1) -1(1,0) 2(1,0) 4(1,0) 5(0,1)

//(0,1)====> (not present in first array, present in second array)

//only compare the adjacent values, only if its from different array take the diff and stor it

For Sorted arrays:

|A[i+1] - B[j]| < |A[i] - B[j+1]| then increment i, otherwise increment j

Create a BST using the Array A:
1. If it is sorted create the root node with n/2th element and create the tree recursively inserting not n/4th and 3n/4th node in the 2nd iteration etc.
2. If it is not sorted then just create a BST going from 1st to nth element.

Now keep a variable MIN, retX, retY.
From Array B try to insert the element y, one by one. You will find a place (z) to insert the element. Find the m = min(z, parent(z)), and then update MIN, retX, retY.

Return the retX and retY.

#include <iostream>
using namespace std;

int main (int argc, char * argv [])
{
void closest (int a1[], int size1, int a2[], int size2);

int n, m;
cout<<"Please enter the size of the first array:"<<endl;
cin>>n;
int * array1 = new int [n];
cout<<"Please enter each element of the first array:"<<endl;
int i;
for (i = 0; i < n; ++i)
{
cin>>array1[i];
}
cout<<"Please enter the size of the second array:"<<endl;
cin>>m;
int * array2 = new int [m];
cout<<"Please enter each element of the second array:"<<endl;
for (i = 0; i < m; ++i)
{
cin>>array2[i];
}

closest (array1, n, array2, m);

return 0;
}


void closest (int a1[], int size1, int a2[], int size2)
{
int i;
int j;
int Min_Distance;
int a1_number;
int a2_number;

if (a1[0] > a2[0])
{
Min_Distance = a1[0] - a2[0];
}
else
{
Min_Distance = a2[0] - a1[0];
}

for (i = 0; i < size1; ++i)
{
for (j = 0; j < size2; ++j)
{
if (a1[i] < a2[j])
{
if (a2[j] - a1[i] < Min_Distance)
{
Min_Distance = a2[j] - a1[i];
a1_number = i;
a2_number = j;
}
}

else
{
if (a1[i] - a2[j] < Min_Distance)
{
Min_Distance = a1[i] - a2[j];
a1_number = i;
a2_number = j;
}
}
}
}

cout<<"The Minimum Distance is:"<<endl;
cout<<Min_Distance<<endl;
cout<<"The two index are:"<<a1_number<<" "<<a2_number<<endl;

}

# include<stdio.h>
# include<string.h>
# include<math.h>
void bubble(int a,int n);
int main()
{
int a[80],b[80];
int sizea,sizeb;
int i,j,mindif,dif,indexa,indexb;
printf("Enter size of a:");
scanf("%d",&sizea);
printf("Enter %d integers:",sizea);
for(i=0;i<sizea;i++)
scanf("%d",&a[i]);
printf("Enter size of b:");
scanf("%d",&sizeb);
printf("Enter %d integers:",sizeb);
for(i=0;i<sizeb;i++)
scanf("%d",&b[i]);
mindif=abs(a[0]-b[0]);
for(i=0;i<sizea;i++)
for(j=0;j<sizeb;j++)
{
if(abs(a[i]-b[j])<mindif)
{
mindif=abs(a[i]-b[j]);
indexa=i;indexb=j;
}
}
printf("The min difference of a and b is abs(a[%d]-b[%d])=%d\n",indexa,indexb,mindif);
return 0;
}