## Amazon Interview Question for Quality Assurance Engineers

• 0

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

sort the two arrays and use two pointer iterate through the list

Comment hidden because of low score. Click to expand.
0
of 0 vote

Sort both the arrays first.Take the delta or difference of the first element of two arrays and the difference of the last element of two arrays.Then compare both the differences to view smaller one.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Sort both the arrays first.Take the delta or difference of the first element of two arrays and the difference of the last element of two arrays.Then compare both the differences to view smaller one

Comment hidden because of low score. Click to expand.
0
of 0 vote

Sort both the arrays first.Take the delta or difference of the first element of two arrays and the difference of the last element of two arrays.Then compare both the differences to view smaller one

Comment hidden because of low score. Click to expand.
0
of 0 vote

Sort both the arrays first.Take the delta or difference of the first element of two arrays and the difference of the last element of two arrays.Then compare both the differences to view smaller one

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Input Array A and Array B
Algorithm
1. Sort A
2. Sort B
3. Select Min ( A ) and traverse through B to find minimal delta.
4. Store the location of B which has got the minimal delta
5. Move to the next min element from A . Repeat 3- 4
6. Perform the same step for Array B.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}

Comment hidden because of low score. Click to expand.
-1
of 3 vote

Sort bot the arrays first.Take the difference or Delta of the first element of two arrays and the last element of two arrays and then compare both the differences to see which is smaller.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.