Amazon Interview Question
SDE-2sTeam: Amazon Prime
Country: United States
Interview Type: In-Person
something like this might work better
basically prime numbers are numbers that are only divisible by themselves and 1
but cheating at it we can check for n
1 divisibility by numbers less than n/2
2 and only by other prime numbers less than n/2
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
System.out.print("Enter the limit : ");
int n = in.nextInt();
boolean flag;
List<Integer> arr = new ArrayList<>();
for (int cntr = 2; arr.size() < n; cntr++) {
flag = true;
if (!arr.isEmpty()) {
int index = 0;
for (int slct = arr.get(index++); slct <= cntr / 2; slct = arr.get(index++))
if (cntr % slct == 0) {
flag = false;
break;
}
}
if (flag) {
arr.add(cntr);
System.out.print("" + cntr + "\t");
}
}
}
I think it's worth mentioning to the interviewer that since prime numbers do not change, it's always a good idea to pre-calculate the prime numbers using algorithms like "sieve of eratosthenes" and just use them whenever required.
For example, to get first N prime numbers, just make a lookup into a pre-calculated list of prime numbers and get first N numbers from there.
Having said that if the requirement is to calculate first N prime numbers, here is a simple code to get that.
public class FirstNPrimeNumbers {
public static void main(String[] args) {
int n = 10;
firstNPrime(n);
}
private static void firstNPrime(int n) {
int x = 1;
int i = 3;
System.out.print(2 + " ");
while(x < n) {
boolean prime = true;
//Check if there exists any number that divides I. If yes, its not a prime
for(int j = 2; j < Math.sqrt(i); j++) {
if(i % j == 0) {
prime = false;
break;
}
}
if(prime) {
System.out.print(i + " ");
x++;
}
i++;
}
}
}
Output:
======
2 3 4 5 7 9 11 13 17 19
We know that prime numbers can be generated using (6*i - 1) and (6*i + 1) formula where i >= 1.
vector<int> getPrimes(int n)
{
if (n <= 0)
return {};
if (n == 1)
return {2};
if (n == 2)
return {2, 3};
vector<int> ans{2,3};
for (int i = 1; ans.size() < n; i++)
{
ans.push_back(6*i - 1);
if (ans.size() == n)
return ans;
ans.push_back(6*i + 1);
}
return ans;
}
}
package com.sample.test;
import java.util.Objects;
import java.util.Scanner;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class FastestPrimePrint {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner ss = new Scanner(System.in);
System.out.println("Please enter the integer till which you wish to print prime numbers :");
int n = ss.nextInt();
printPrimes(n);
}
static void printPrimes(int seed) {
System.out.println(IntStream.range(2, seed+1).mapToObj(num ->{
int sqRoot = (int)Math.sqrt(num);
boolean isPrime = true;
for(int s=2; s<=sqRoot; s++){
if(num%s==0) {
isPrime = false;
break;
}
}
if(isPrime) {
return String.valueOf(num);
} else {
return null;
}
})
.filter(Objects::nonNull)
.collect(Collectors.joining(", ")));
}
}
I don't believe amazon asks this.
- adr July 22, 2018