Amazon Interview Question for Quality Assurance Engineers


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.

- Anonymous December 22, 2016 | Flag Reply
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.

- CT December 28, 2016 | Flag Reply
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

- kaijieqin December 22, 2016 | Flag Reply
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.

- punitram yadav December 22, 2016 | Flag Reply
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

- Punitram Yadav December 22, 2016 | Flag Reply
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

- Punitram Yadav December 22, 2016 | Flag Reply
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

- Punitramyadav December 22, 2016 | Flag Reply
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;
    }
}

- Anonymous December 26, 2016 | Flag Reply
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;
    }
}

- FooBar December 26, 2016 | Flag Reply
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.

- FallenAnt December 28, 2016 | Flag Reply
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);
        }

- Anonymous December 31, 2016 | Flag Reply
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;
    }

- Andrew January 04, 2017 | Flag Reply
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;
}

- tjcbs2 January 04, 2017 | Flag Reply
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

- srterpe January 06, 2017 | Flag Reply
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;
	}

}

- Anonymous January 07, 2017 | Flag Reply
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;
}
}

- Anonymous January 07, 2017 | Flag Reply
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;
}
}

- Anonymous January 07, 2017 | Flag Reply
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.

- Punitram Yadav December 22, 2016 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More