Amazon Interview Question Quality Assurance Engineers
Country: United States
Interview Type: Phone Interview
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;
}
}
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
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;
}
}
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;
}
}
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]
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
}
// 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;
}
}
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);
}
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);
}
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))
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))
public static Boolean isPrime(int n) {
//Converting the negative numbers to positive, for better usage
if(n<0) {
n = 0-n;
}
for(int i=2; i<n/2; i++) {
if(n%i == 0) {
return false;
}
}
return true;
}
public static ArrayList<Integer> findPrimeNumbers(int[] a) {
ArrayList<Integer> alPrimeNumbers = new ArrayList<>();
for(int i=0;i<a.length;i++) {
if(isPrime(a[i])) {
alPrimeNumbers.add(a[i]);
}
}
return alPrimeNumbers;
}
public static void minimumDifference(ArrayList<Integer> al) {
Collections.sort(al, Collections.reverseOrder());
int diff;
int min = al.get(0) - al.get(1);
for(int i=0; i<al.size()-1; i++) {
diff = al.get(i) - al.get(i+1);
min = diff < min ? diff : min;
}
System.out.println(min);
}
public static void main(String[] args) {
int[] a = {2,3,5,7,8};
ArrayList<Integer> al = findPrimeNumbers(a);
minimumDifference(al);
}
I donot know whaat you answered but for my solution the complexity is n2 + logn
here is the solution
- dkholia January 22, 2017public 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; } }