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.

- adr July 22, 2018 | Flag Reply
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) {
            arr.add(cntr);
            System.out.print("" + cntr + "\t");
        }
    }
}

- PeyarTheriyaa July 22, 2018 | Flag Reply
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

- Saurabh July 22, 2018 | Flag Reply
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.

- nooreddin August 04, 2018 | Flag Reply
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;
}

}

- Anom August 07, 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