Amazon Interview Question
Software Engineer / DevelopersFirst sort the array.
Then store the difference between the first two as min.
then go on by comparing the difference between the next two element if it is less than min consider that as the min.
Now problem comes when the array has both the Negative and positive numbers.we can follow the above method if the array contains only positive or only negative.
suppose if one element is positive in one array and the corresponding element in other array is negative then get the difference Binary search for that difference+positive num. modify the binary search such that it return the next small no index if a current is not found. From that position you have track. and see whether you are getting the minimum element.
First sort both the linked lists
Set pointer x1 to 1st sorted linked list and x2 to 2nd sorted linked list.
1) Initialize min to distance between the values pointed by x1 and x2.
2) if value pointed by x1 is less than the value pointed by x2 then move x1 to next element otherwise move x2 to next element.
3) Then take distance between the elements pointed by x1 and x2 and update min if necessary.
4) repeat steps 2 and 3.
If input arrays are not sorted by default sort them using some in-place algo.
a) have two integer(index1, index2) pointing to position on two array and currentBestIndex1, currentBestIndex2
b) i)assume array2 will lead the way, loop through array until MIN(sizeof(array1), sizeof(array2))
ii) increase index1, index2 according to local best difference and update currentBestIndex1, currentBestIndex2 if index1, index2 values are smaller
iii) once we reach the end of one of the array we are done
Time/Space
Assume Array1 is N, Array2 is M and also array1 is smaller than array2
Time=O(N) if already sorted
=O(nlogn + mlogm)
Space O(1)
int main()
{
int array2[] = {8, 14, 27, 29};
int array1[] = {2, 3, 5, 10, 12, 16, 19, 20}
int array1Size = sizeof(array1)/sizeof(int);
int array2Size = sizeof(array2)/sizeof(int);
int index1,index2 = 0;
int lowestIndex1, lowestIndex2 = 0;//local minimum found so far
for(int i = 1; i < array1Size && i < array2Size; i++)
{
if(abs (array1[index1] - array2[index2]) > abs (array1[(index1+1)] - array2[index2]))
{
if((index1+1) < array1Size)
index1++;
}
else if(abs (array1[index1] - array2[index2]) > abs (array1[index1] - array2[(index2+1)]))
{
if((index2+1) < array2Size)
index2++;
}
else if(abs (array1[index1] - array2[index2]) > abs(array1[index1+1] - array2[index2+1]))
{
if((index1+1) < array1Size)
index1++;
if((index2+1) < array2Size)
index2++;
}
//overwrite current lowest if index1,2 is lower
if(abs(array1[lowestIndex1] - array2[lowestIndex2]) > abs(array1[index1] - array2[index2]))
{
lowestIndex1 = index1;
lowestIndex2 = index2;
}
}
printf("index1 = %d, index2 = %d\n", index1, index2);
}
The loop will run until the end of the maximum sized array so O(n)/space(1) if arrays are already sorted
Considerering the size to be M and N.. it can easily be done in O(max(lg(max(M, N)), min(M, N)))
So, if M > N it can be done in
O( max(Lg(M), N) )-time
sort the lists (if not sorted before)
merge the two lists and keep track of the minimum difference
Assume that arrays are sorted. Otherwise sort the arrays first
namespace MinDistanceBetweenWordsIn2Docs
{
class Program
{
//use binary search in second array
static void Main(string[] args)
{
int[] ar1 = { 2, 3, 5, 10, 12, 16, 19, 20 };
int[] ar2 = { 8, 13, 27, 29 };
Console.WriteLine(MinimumDistance(ar1,ar2));
Console.Read();
}
public static int MinimumDistance(int[] arr1, int[] arr2)
{
int min = int.MaxValue;
for (int i = 0; i < arr1.Length; ++i)
{
int left = 0, right = arr2.Length - 1;
while (left <= right)
{
int mid = (left + right) / 2;
if (Math.Abs(arr1[i] - arr2[mid])<min)
{
min = Math.Abs(arr1[i] - arr2[mid]);
}
if (mid > left && Math.Abs(arr1[i] - arr2[mid - 1]) < min)
{
min = Math.Abs(arr1[i] - arr2[mid - 1]);
right = mid - 1;
}
else if (mid < right && Math.Abs(arr1[i] - arr2[mid + 1]) < min)
{
min = Math.Abs(arr1[i] - arr2[mid + 1]);
left = mid + 1;
}
//mid element distance is the least
else break;
}
}
return min;
}
}
}
1. Without extra space time: O(N^2)
- Anonymous April 11, 20112. With O(N) space time: O(N)