Amazon Interview Question for Quality Assurance Engineers


Country: United States
Interview Type: Phone Interview




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

I donot know whaat you answered but for my solution the complexity is n2 + logn
here is the solution

public class MinimumDiffPrimeNumbers {
	
	public static void main(String[] args) {
		int[] numbers = {101,-113,1,45,78,-2,-3,7};
		new MinimumDiffPrimeNumbers().findPrimes(numbers);	
		
	}
	
	private int[] findPrimes(int [] numbers) {
		int [] returnArray = new int[2];
		TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
		
		for(int i=0;i<numbers.length;i++){
			if(isPrime(numbers[i]))
				map.put(numbers[i], numbers[i]);
		}
		
		returnArray[0]= map.firstKey().intValue();
		returnArray[1]= map.lastKey().intValue();
		return returnArray;
	}
	
	private boolean isPrime(int n){
			
		if(n<0)
 			n = 0 - n;  //just convert n to positive for simplicity
		for(int i = 2;i<n/2;i++){
			if(n%i==0)
				return false;
		}
		return true;
	}
}

- dkholia January 22, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sorry I got the question wrong .. I thought the two numbers needs to be returned.. This solution returns the minimum difference

import java.util.HashMap;
import java.util.TreeMap;

/**
 * You are given an array of integers. Find the minimum difference between two prime numbers(Positive or negative) 
 * in the array when present with minimum time complexity and provide the test data to test the this code.
 */
public class MinimumDiffPrimeNumbers {
	
	public static void main(String[] args) {
		int[] numbers = {101,-113,1,45,78,-2,-3,7};
		System.out.println(new MinimumDiffPrimeNumbers().findPrimes(numbers));	
		
	}
	
	private int findPrimes(int [] numbers) {
		TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
		
		for(int i=0;i<numbers.length;i++){
			if(isPrime(numbers[i]))
				map.put(numbers[i], numbers[i]);
		}
		
		return map.firstKey().intValue() - map.lastKey().intValue();
	}
	
	private boolean isPrime(int n){
			
		if(n<0)
 			n = 0 - n;  //just convert n to positive for simplicity
		for(int i = 2;i<n/2;i++){
			if(n%i==0)
				return false;
		}
		return true;
	}
}

- dkholia January 22, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It would be good if you can have a map of <Integer, Boolean> and store the number and boolean value(prime not not prime).

- raghu January 22, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My solution is:
Complexity is about n*sqrt(n). Description in comments.

public class MinDiffBetweenPrimes {

  public static void main(String[] args) {
    try (Scanner in = new Scanner(System.in)) {
      int T = in.nextInt();
      for (int t = 0; t < T; t++) {
        int n = in.nextInt();
        int[] array = new int[n];
        for (int i = 0; i < n; i++) {
          array[i] = in.nextInt();
        }
        System.out.println(getMinDiffBetweenPrimes(array));
      }
    }
  }

  /**
   * Complexity:
   * 1. ~n*sqrt(n) to select all primes
   * 2. ~n*log(n) to sort primes
   * 3. ~n to find the difference
   * So, maximum is n*sqrt(n)
   * @return non-negative difference between primes, -1 in case if it is not possible to calculate
   * the difference.
   */
  private static int getMinDiffBetweenPrimes(int[] array) {
    int minDiff = Integer.MAX_VALUE;
    List<Integer> primesAtArray = new ArrayList<>();
    for (int a : array) {
      if (isPrime(a)) {
        primesAtArray.add(a);
      }
    }
    if (primesAtArray.size() < 1) {
      return -1;
    }
    Collections.sort(primesAtArray);
    int diff;
    for (int i = 0; i < primesAtArray.size() - 1; i++) {
      diff = primesAtArray.get(i + 1) - primesAtArray.get(i);
      if (diff < minDiff) {
        minDiff = diff;
      }
    }
    return minDiff;
  }

  /**
   * Complexity ~ sqrt(n)
   * @param n
   * @return is parameter a prime number or not
   */
  static boolean isPrime(int n) {
    if (n < 0) {
      n = -n;
    }

    if (n == 1) {
      return false;
    }

    if ((n >> 1) << 1 == n) {
      return false;
    }

    double sqrtN = Math.sqrt(n);
    for (int p = 3; p <= sqrtN; p += 2) {
      if (n % p == 0) {
        return false;
      }
    }

    return true;
  }
}

Sample Input:

6
10
1 2 3 4 5 6 7 8 9 10
16
10 8 3 4 16 32 44 15 127 45 14 19 16 12 100 101
10
-10 10 -8 8 -6 6 -7 7 -4 4
5
3 3 3 3 3
4
7 5 3 1
8
23 -3 0 15 38 47 46 45

Sample Output:

1
16
14
0
2
24

- Mike L January 22, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package primNumbersDistance;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class main {
public static void main(String[] args) {
int[] a = { 23, -3, 0, 15, 38, 47, 46, 45 }; //Driver (test data)
System.out.print(findIfItsPrime(a));
}

public static int findIfItsPrime(int[] a) {
List<Integer> temp = new ArrayList<Integer>();
for (int i = 0; i < a.length; i++) {
if (findIfItsPrime(a[i])) { // This if check if numbers is prime or not, if it's then the number is added to the List
temp.add(a[i]);
}
}
Collections.sort(temp); //sort the arraylist in ascending order
return Math.abs(temp.get(temp.size() - 1) - temp.get(0)); //returns greater number (the one lying farthest to the right on a number line) - lesser number (the one lying farthest to the left).
}

//Method to check if number is primer or not
public static boolean findIfItsPrime(int i) {
if (i < 0) {
i = i * -1; // Convert number to positive just for convenience
}

if (i <= 1) {
return false;
} else if (i <= 3) { //Number is prime if number is 2 or 3
return true;
} else if (i % 2 == 0 || i % 3 == 0) { //number is not prime if it's divisible by 2 or 2
return false;
}
return true;
}
}

- Jose January 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is my solution:

package primNumbersDistance;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class main {
	public static void main(String[] args) {
		int[] a = { 23, -3, 0, 15, 38, 47, 46, 45 }; //Driver (test data)
		System.out.print(findIfItsPrime(a));
	}

	public static int findIfItsPrime(int[] a) {
		List<Integer> temp = new ArrayList<Integer>();
		for (int i = 0; i < a.length; i++) {
			if (findIfItsPrime(a[i])) { // This if check if numbers is prime or not, if it's then the number is added to the List 
				temp.add(a[i]);
			}
		}
		Collections.sort(temp); //sort the arraylist in ascending order
		return Math.abs(temp.get(temp.size() - 1) - temp.get(0)); //returns greater number (the one lying farthest to the right on a number line) - lesser number (the one lying farthest to the left).
	}

	//Method to check if number is primer or not
	public static boolean findIfItsPrime(int i) {
		if (i < 0) {
			i = i * -1; // Convert number to positive just for convenience
		}

		if (i <= 1) {
			return false;
		} else if (i <= 3) { //Number is prime if number is 2 or 3
			return true;
		} else if (i % 2 == 0 || i % 3 == 0) { //number is not prime if it's  divisible by 2 or 2 
			return false;
		}
		return true;
	}
}

- Jose January 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def isprime(n):
    """Returns True if n is prime."""
    if n == 2:
        return True
    if n == 3:
        return True
    if n % 2 == 0:
        return False
    if n % 3 == 0:
        return False

    i = 5
    w = 2

    while i * i <= n:
        if n % i == 0:
            return False

        i += w
        w = 6 - w

    return True

def minDifferenceBetweenTwoPrimeNumbers(array):
    primeArray = []
    for i in array:
        if isprime(i):
            primeArray.append(i)
    return sorted(primeArray)[1] - sorted(primeArray)[0]

- revanthpobala January 25, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function isPrime (n) {
	var d = 2
	var factors = []
	while (d * d <= n) {
		var isFactor = false
		var pow = 0
		while (n % d === 0) {
			isFactor = true
			n /= d
			pow += 1
		}
		if (isFactor) {
			factors.push({ factor: d, pow: pow })
		}
		d += 1
	}
	if (n > 1) {
		factors.push({ factor: n, pow: 1 })
	}
	return factors.length === 1 && Math.abs(factors[0].pow) === 1
}
module.exports = function (A) {
	A.sort(function (a, b) {
		if (a < b) {
			return -1
		} else if (a > b) {
			return 1
		}
		return 0
	})
	var i, j
	i = j = 0
	var min = Infinity
	for (; i < A.length;) {
		var a = A[i]
		if (isPrime(Math.abs(a))) {
			j = i + 1
			while (!isPrime(Math.abs(A[j])) && j < A.length) {
				j++
			}
			if (j >= A.length) {
				// No more primes
				return min
			}
			var b = A[j]
			var d = Math.abs(a - b)
			if (min > d) {
				min = d
			}
			i = j
		} else {
			i++
		}
	}
	return min
}

- srterpe January 28, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1) Iterate over the array. If an element is a prime add it to a PrimesArray.
At the end of the loop we have all primes of original array stored in PrimesArray.
2) Sort PrimesArray
3) Linear scan of PrimesArray and find the minimum difference between consecutive elements.

- codingwarrior01 January 30, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// the program returns the difference between the smallest and largest prime

import java.util.TreeSet;

public class Difference_Among_Prime {

	public static void main(String[] args) {
		int[] input = { 22, 3, 56, 73, 11, -7, 67, 98 };
		int output = PrimeNumbers(input);
		System.out.println(output);
	}

	static int PrimeNumbers(int[] input) {
		TreeSet<Integer> prime = new TreeSet<Integer>();
		for (int i = 0; i < input.length; i++) {
			if (IsPrime(input[i]))
				prime.add(input[i]);
		}

		int difference = (int) prime.last() - (int) prime.first();
		return difference;
	}

	private static boolean IsPrime(int p) {
		int count = 0;

		boolean flag = false;
		for (int j = 2; j < p / 2; j++) {
			if (p % j == 0)
				count++;
		}
		if (count == 0)
			flag = true;

		else
			flag = false;

		return flag;
	}
}

- Hyder April 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python:

def min_value(list):
pl= []
for j in list:
a = 0
if j>2:
for i in range(2, j):
if j%i == 0:
a = 1
if a == 0:
pl.append(j)
print pl
return sorted(pl)[1]-sorted(pl)[0]

>>> min_value([2,3,37,5,27,7,64,1,2])
[2, 3, 37, 5, 7, 1, 2]
1

- Madhu Mohan May 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static int diff =0;
public void diffPrimeNumbers(int []arr){

int temparr[] = arr;
for(int i=0;i<temparr.length;i++){
if(temparr[i]<0)
temparr[i]= 0;

}
List<Integer> tempAL = new ArrayList<Integer>();
for(int i=0;i<temparr.length;i++){
if(temparr[i]==2 || temparr[i]==3 || !(temparr[i]%2==0 || temparr[i]%3==0))
tempAL.add(temparr[i]);
}
Collections.sort(tempAL);
System.out.println("tempAL :" +tempAL);

int temp =0;
for (int i=0; i<tempAL.size()-1;i++){
temp=tempAL.get(i+1)-tempAL.get(i);

if (temp<diff || i==0) {
diff=temp;
if(diff==1 || diff==2)
break;
}

}
System.out.println("Min difference :" +diff);
}

- Nikhil P October 10, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static int diff =0;
	public void diffPrimeNumbers(int []arr){
		
		int temparr[] = arr;
		for(int i=0;i<temparr.length;i++){
		if(temparr[i]<0)
			temparr[i]= 0;
			
		}
		List<Integer> tempAL = new ArrayList<Integer>();
		for(int i=0;i<temparr.length;i++){
			if(temparr[i]==2 || temparr[i]==3 || !(temparr[i]%2==0 || temparr[i]%3==0))
				tempAL.add(temparr[i]);
		}
		Collections.sort(tempAL);
		System.out.println("tempAL :" +tempAL);
		
		int temp =0;
		for (int i=0; i<tempAL.size()-1;i++){
			temp=tempAL.get(i+1)-tempAL.get(i);
			
				 if (temp<diff || i==0)	{				
					diff=temp;
					if(diff==1 || diff==2)
						break;
				}
				 
		}
		System.out.println("Min difference :" +diff);
	}

- Nikhil P October 10, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def primelist(l):
list = []
for n in l:
if all(n%i !=0 for i in range(2, n)):
list.append(n)

return list

def minDiff(pl):
x = sorted(pl)
w = []
for f in range(1, len(x)):
ans = x[f] - x[f - 1]
w.append(ans)
return sorted(w)[0]



l = [101,-113,1,45,78,-2,-3,7]
s =[2,3,37,5,-27,-7,-64,-1,2]

x =primelist(s)

print('ans.', minDiff(x))

- jeeva March 09, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def primelist(l):
    list = []
    for n in l:
        if all(n%i !=0 for i in range(2, n)):
            list.append(n)

    return list

def minDiff(pl):
    x = sorted(pl)
    w = []
    for f in range(1, len(x)):
        ans = x[f] - x[f - 1]
        w.append(ans)
    return sorted(w)[0]



l = [101,-113,1,45,78,-2,-3,7]
s =[2,3,37,5,-27,-7,-64,-1,2]

x =primelist(s)

print('ans.', minDiff(x))

- jeeva March 09, 2018 | 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