Amazon Interview Question Quality Assurance Engineers
Country: United States
Interview Type: Phone Interview
There is a way to solve it in O ( n + m ) which is loosely based on Quick Select ( Note: Not Quick Sort )
Select random element in first and second array.
Move all smaller element of first array left, bigger right.
Move all bigger elements of second array left, smaller right.
If the difference of the two elements is negative, recursevilly work with left parts of both arrays
If the difference of the two elements is positive, recursevilly work with right parts of both arrays.
(In case exact 0 that is a perfect diff)
Note: include this pivot pair in those recursive sub-arrays because it may be best pair and must be considered too
Ending conditions: one of the array parts has two or less element, in which case brut force solution, which will be O ( p ) where p is the size of the larger ending sub-array and therefore should not affect the performance of the whole algorithm.
public class Main {
private int minDelta = Integer.MAX_VALUE;
public static void main(String[] args) {
Main m = new Main();
}
public Main() {
int[] a1 = new int[]{-4, 7, 57, 98, 999};
int[] a2 = new int[]{99, 57};
java.util.Arrays.sort(a1);
java.util.Arrays.sort(a2);
for (int num : a2) {
findMinDelta(a1, num);
}
System.out.println(this.minDelta);
}
public void findMinDelta(int[] a, int key) {
int minValue;
int minIndex = 0;
int maxIndex = a.length - 1;
if (key <= a[minIndex]) {
minValue = Math.abs(key - a[minIndex]);
} else if (key >= a[maxIndex]) {
minValue = Math.abs(key - a[maxIndex]);
} else {
minValue = search(a, key, minIndex, maxIndex);
}
if (minValue < this.minDelta) {
this.minDelta = minValue;
}
}
private int search(int[] a, int key, int minIndex, int maxIndex) {
int start = (minIndex + maxIndex) / 2;
int value = Math.abs(key - a[start]);
if (start != minIndex) {
search(a, key, minIndex, start);
}
if (start + 1 != maxIndex) {
search(a, key, start, maxIndex);
}
return value;
}
}
public class Main {
private int minDelta = Integer.MAX_VALUE;
public static void main(String[] args) {
Main m = new Main();
}
public Main() {
int[] a1 = new int[]{-4, 7, 57, 98, 999};
int[] a2 = new int[]{99, 57};
java.util.Arrays.sort(a1);
java.util.Arrays.sort(a2);
for (int num : a2) {
findMinDelta(a1, num);
}
}
public void findMinDelta(int[] a, int key) {
int minValue;
int minIndex = 0;
int maxIndex = a.length - 1;
if (key <= a[minIndex]) {
minValue = Math.abs(key - a[minIndex]);
} else if (key >= a[maxIndex]) {
minValue = Math.abs(key - a[maxIndex]);
} else {
minValue = search(a, key, minIndex, maxIndex);
}
if (minValue < this.minDelta) {
this.minDelta = minValue;
}
}
private int search(int[] a, int key, int minIndex, int maxIndex) {
int start = (minIndex + maxIndex) / 2;
int value = Math.abs(key - a[start]);
if (start != minIndex) {
search(a, key, minIndex, start);
}
if (start + 1 != maxIndex) {
search(a, key, start, maxIndex);
}
return value;
}
}
static void Main(string[] args)
{
var a = new[] {-4, 7, 57, 98, 999};
var b = new[] {99, 57};
a = a.OrderBy(p => p).ToArray();
b = b.OrderBy(p => p).ToArray();
int minDif = int.MaxValue;
foreach (int aa in a)
{
var curMin = int.MaxValue;
foreach (int bb in b)
{
var dif = Math.Abs(aa - bb);
if (dif < curMin)
curMin = dif;
else
break;
}
if (curMin < minDif)
minDif = curMin;
}
Console.WriteLine(minDif);
}
Considering that "minimum delta" is min (b_i - a_j) for each pair (b_i, a_j) from B, A
The optimal solution is the following
1. find the minimum (min) and maximum (max) elements in the second and first array correspondingly. Complexity: O(A + B)
2. calculate the delta. Complexity: O(1)
private static Integer getMinDelta(int[] a, int[] b) {
if (a.length > 0 && b.length > 0) {
int minB = getMinElement(b);
int maxA = getMaxElement(a);
return minB - maxA;
}
return null;
}
private static Integer getMinElement(int [] a) {
Integer minElement = null;
for (int i=0; i< a.length; i++){
if (minElement == null || minElement > a[i]){
minElement = a[i];
}
}
return minElement;
}
private static Integer getMaxElement(int [] a) {
Integer maxElement = null;
for (int i=0; i< a.length; i++){
if (maxElement == null || maxElement < a[i]){
maxElement = a[i];
}
}
return maxElement;
}
int Smallest_Difference(const std::vector<int>& a, const std::vector<int>& b)
{
std::vector<int> comb = a;
comb.insert(a.begin(), b.begin(), b.end());
std::sort(comb.begin(), comb.end());
int dif = std::numeric_limits<int>::max();
for (int i = 0; i < (int)comb.size()-1; i++)
dif = std::min(dif, std::abs(comb[i] - comb[i+1]));
return dif;
}
Time: O(n + m)
Space: O(n + m)
module.exports = function (A, B) {
// Let's assume that A & B are both sorted, if not
// we have to deal with it.
var T = []
// Merge the arrays into T
// maintaining the order
var i, j
i = j = 0
for (; i < A.length; ++i) {
if (j >= B.length) {
T.push({ value: A[i], source: A })
continue
}
if (A[i] < B[j]) {
T.push({ value: A[i], source: A })
} else {
while (B[j] < A[i]) {
T.push({ value: B[j++], source: B })
}
T.push({ value: A[i], source: A })
}
}
for (; j < B.length; ++j) {
T.push({ value: B[j], source: B })
}
var delta = Infinity
for (i = 0, j = 1; j < T.length; ++i, ++j) {
// If we care to restrict this delta to different source arrays...
if (T[i].source === T[j].source) {
console.log('Skipping `' + T[i].value + '` & `' + T[j].value + '`')
continue
}
var d = [Math.abs(T[i].value - T[j].value), Math.abs(T[j].value - T[i].value)]
for (var k = 0; k < d.length; ++k) {
if (d[k] === 0) {
return 0 //`0` is of course the minimum delta
}
if (d[k] < delta) {
delta = d[k]
}
}
}
return delta
}
var A = [-3, 1, 999]
var B = [-1, 2, 3]
var delta = module.exports(A, B)
console.log(delta)
// $ node minimum-delta.js
// Skipping `2` & `3`
// 1
public int getdelta(int[] a, int [] b){
int delta = Integer.MAX_VALUE;
int len1 = a.length;
int len2 = b.length;
if(len1!=-1 && len2!=-1){
for( int x : b){
for(int i=0; i<len1; i++){
int b1 = x;
int a1= a[i];
int diff = Math.abs(a1-b1);
if(diff < delta){
delta = diff;
}
}
}
return delta;
}
return 0;
}
}
public int getdelta(int[] a, int [] b){
int delta = Integer.MAX_VALUE;
int len1 = a.length;
int len2 = b.length;
if(len1!=-1 && len2!=-1){
for( int x : b){
for(int i=0; i<len1; i++){
int b1 = x;
int a1= a[i];
int diff = Math.abs(a1-b1);
if(diff < delta){
delta = diff;
}
}
}
return delta;
}
return 0;
}
}
public int getdelta(int[] a, int [] b){
int delta = Integer.MAX_VALUE;
int len1 = a.length;
int len2 = b.length;
if(len1!=-1 && len2!=-1){
for( int x : b){
for(int i=0; i<len1; i++){
int b1 = x;
int a1= a[i];
int diff = Math.abs(a1-b1);
if(diff < delta){
delta = diff;
}
}
}
return delta;
}
return 0;
}
}
public static void main(String[] args) {
int[] arr1 = {10, 5, 40};
int[] arr2 = {50, 90, 80} ;
int [] first;
int [] second;
int min = Integer.MAX_VALUE;
Arrays.sort(arr1);
Arrays.sort(arr2);
if(arr1.length<arr2.length)
{
first=arr1;
second=arr2;
} else
{
first=arr2;
second=arr1;
}
for (int num : first) {
for (int i = 0; i < second.length; i++) {
int value=Math.abs(num - second[i]);
if (min > value) {
min = value;
}
if (second[i] > num) {
break;
}
}
}
System.out.println(Math.abs(min));
}
public static void main(String[] args) {
int[] arr1 = {10, 5, 40};
int[] arr2 = {50, 90, 80} ;
int [] first;
int [] second;
int min = Integer.MAX_VALUE;
Arrays.sort(arr1);
Arrays.sort(arr2);
if(arr1.length<arr2.length)
{
first=arr1;
second=arr2;
} else
{
first=arr2;
second=arr1;
}
for (int num : first) {
for (int i = 0; i < second.length; i++) {
int value=Math.abs(num - second[i]);
if (min > value) {
min = value;
}
if (second[i] > num) {
break;
}
}
}
System.out.println(Math.abs(min));
}
The best you can do is sort both lists (assuming unsorted), then merge them together, keeping track of the difference between the two elements of each array at each step of the merge. O(m log m + n log n) time, where m is the size of list a and n is the size of list b.
- Anonymous December 22, 2016