Amazon Interview Question
SDE-2sTeam: Bangalore
Country: India
Interview Type: In-Person
I m confused about when you ll calculate the abs difference. If you are calculating in the final sorted array, there is a chance of giving the min difference from the same arrary right ?
@Anirudh: you are right. thanks for pointing it out. Simple merging will cause that problem.
@Guru: it actually is way different from merge. Thanks.
This is my implementation... (...others posted here are also pretty good)
public static int[] getMinDiff(int a[], int b[]) {
int mindiff = Integer.MAX_VALUE;
/*
* pos1, pos2 : positions of the numbers forming the min-pair
* ...one from each array
*/
int pos1 = 0, pos2 = 0, i=0, j=0;
while(i < a.length && j < b.length) {
if(mindiff > abs(a[i] - b[j])) {
mindiff = abs(a[i] - b[j]);
pos1 = i; pos2 = j;
}
if(a[i] <= b[j])
i++;
else
j++;
}
return new int[] {pos1, pos2, mindiff};
}
@Guru
Actually I think the "merge" step in the merging sort is not much different from what we are doing here. Think this way: we can first merge the two arrays into one, then we just need to compare the distance between adjacent elements in the merged array. This takes 2*N time. Then we realize that we do not need to store the merged array and the calculation of the distance between adjacent elements can be done "on-the-fly", and this reduces the time to 1*N and it is essentially what me.mrig gives...
Actually, the problem with merging like the way its done in mergesort, is that, minimum abs. difference pair may come from same array (as @anirudh pointed out)..
Algo:
1. Take two variable ptr1 and ptr2. Initialized both of them to zero
2. Take 3rd variable diff initialized with INT_MAX
3. While (ptr1 < arr1.length || ptr2 < arr1.length){
If(diff > abs(arr[ptr1] – arr[ptr2])){
Diff = abs(arr[ptr1] – arr[ptr2])
}
If(arr[ptr1] > arr[ptr2])
Ptr2++;
Else
Ptr1++;
}
Please advise guys ??
Correct approach..
After looking at your solution, I found that people have provided the same solution in above posts but instead of writing the logic they just copied a bunch of code...thats why perhaps I saw your solution before looking at theirs..
The answer has already been posted, but for anyone that wants some working code, this should do the trick:
private static int[] closestNumbers(int[] a1, int[] a2) {
int i = 0, j = 0;
int x = 0, y = Integer.MAX_VALUE;
while (true) {
if (Math.abs(a1[i] - a2[j]) < Math.abs(x - y)) {
x = a1[i];
y = a2[j];
}
if (i < a1.length - 1 && a1[i] < a2[j]) i++;
else if (j < a2.length - 1) j++;
else break;
}
return new int[] { x, y };
}
Someone please correct me if you see anything wrong.
public static void getMinAbsDiff(int[] A, int[] B)
{
int lenA = A.length;
int lenB = B.length;
int diff;
int i = 0; //index to traverse Array A
int j = 0; // index to traverse Array B
int minDiff = Integer.MAX_VALUE; // default min Diff
while(i < lenA && j < lenB)
{
// if A[i] <= B[j] finding the diff and incrementing the lower value index
if (A[i] <= B[j])
{
diff = Math.abs(A[i] - B[j]);
i++;
}
else
{
diff = Math.abs(A[i] - B[j]); // else incrementing the jth index
j++;
}
if (diff < minDiff) // updating the minimum diff value.
minDiff = diff;
}
System.out.println("Min Diff :" + minDiff);
}
Hey I happen to saw this algorithm is an open course: first sort array 1, then for each element in array 2, use binary search to find the element in array 1 that forms the smallest gap with it, store it, then look for the minimum among all such differences. The algorithm takes O(n lg n) time.
Note that the arrays are already sorted in this problem.
Binary searching will still take O(log n) per element, and so you will get O(n log n) complexity with your approach as you mentioned.
However, since the arrays are passed to you sorted, you could have simply advanced two pointers, one through each of the two arrays, to finish with the optimal O(n) complexity. It would be a similar technique to how the "merge" step of mergesort steps through two sorted arrays.
public class Test {
public static void main(String[] args){
int arr1[]={13,19,21,37,89};
int arr2[]={23,30,45,67,99};
int min = Math.abs(arr1[0]-arr2[0]);
for(int i=0;i<5;i++){
for(int j=0;j<5;j++){
if(Math.abs(arr1[i]-arr2[j]) < min){
min = Math.abs(arr1[i]-arr2[j]);
}
}
}
System.out.println(min);
}
}
I feel this should be done in o(n)
static int GetMinAbsoluteDiff(int[] a, int[] b)
{
int minDif = int.MaxValue;
int i = 0;
minDif = Math.Min(minDif, Math.Abs(a[i] - b[i]));
minDif = Math.Min(minDif, Math.Abs(a[i] - b[i + 1]));
for (i = 1; i < a.Length-1; i++)
{
minDif = Math.Min(minDif, Math.Abs(a[i] - b[i-1]));
minDif = Math.Min(minDif, Math.Abs(a[i] - b[i]));
minDif = Math.Min(minDif, Math.Abs(a[i] - b[i+1]));
}
minDif = Math.Min(minDif, Math.Abs(a[i] - b[i - 1]));
minDif = Math.Min(minDif, Math.Abs(a[i] - b[i]));
return minDif;
}
Correct me if there are any complexities involved in it.
This problem is similar to merging except we need to tweak it a bit
So, the main criteria we need is that the previous element inserted while merging should be from the other array and the present element to be inserted should be from this array, hence we can keep a boolean value to indicate from which array was the last element was inserted.
now while inserting an element, check from where was the last element was inserted, if from the same array do nothing, if from the other array, check the difference and update the values if the difference turns out to be lesser than the previous value
the only other change is to make the while loop as
while(i < size1 && j < size2) instead of while(i < size1 || j < size2)
Do it in O(N) time, simulating the merge stage of the merge sort algo and keeping track of the absolute difference between any current elements of the array. Below is the s/c and the test driver:
#include <stdio.h>
int absdiff(int a, int b)
{
if (a == b)
return 0;
if (a > b)
return (a - b);
return (b - a);
}
int min_diff_els(int a[], int b[], int size, int& idx1, int& idx2)
{
int i = 0, j = 0;
idx1 = 0;
idx2 = 0;
int mindiff;
mindiff = absdiff(a[0], b[0]);
// special case when there is no better solution,
// since absdiff(a, b) can't be < 0
if (0 == mindiff)
return 0;
++i; ++j;
while (i < size && j < size){
int cv = absdiff(a[i], b[j]);
if (cv < mindiff) {
idx1 = i;
idx2 = j;
mindiff = cv;
}
if (a[i] < b[j])
++i;
else
++j;
}
return mindiff;
}
int main()
{
//
int a[] = {5, 9, 12, 15, 18, 25};
int b[] = {1, 3, 6, 10, 17, 22};
int size = sizeof(a)/sizeof(a[0]);
int idx1, idx2, val;
val = min_diff_els(a, b, size, idx1, idx2);
printf("Min Abs Diff: %-3d Idx1: %-3d Idx2: %-3d\n",
val, idx1, idx2);
return 0;
}
This is exactly same to the case of "merge"-ing in merge-sort.
- iammrigank July 22, 2013Two sorted arrays can merged in linear time. And while merging, absolute difference between any pair of consecutive elements in the final sorted array is stored (along with the pair), such that it is lesser than previous one.
Hence the final value yields the required result.