## Amazon Interview Question for SDE-2s

Team: Amazon Prime
Country: United States
Interview Type: In-Person

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

I don't believe amazon asks this.

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

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) {
System.out.print("" + cntr + "\t");
}
}
}``````

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

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

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

Create an array of booleans of length (n+1)^2 and set all indexes to true.
Starting from 2, print 2 and set all the indexes multiple of 2 to false. Go forward, whenever you reach to a true index, print it and set all the multiple of that index to false.

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

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

}

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

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

}``````

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.