Amazon Interview Question
Developer Program EngineersCountry: India
Interview Type: In-Person
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.
fenwick,
It seems we have similar answers. Can you state what n would be in your case, would it be size(A) + size(B)? Also when you state time would be O(n) that is in addition to the sorting of O(n log n)?
You are basically doing bucket sort. Space needed for it can be huge if max-min is very large.
If,
m = no. of elements in A,
n = no. of elements in B
Then,
Time Complexity : O(m + n + max - min)
Space Complexity : O(m + n + max - min)
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))
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
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;
}
java solution by sorting
- gensay December 05, 2013