Amazon Interview Question Software Engineer / Developers


Country: United States
Interview Type: Phone Interview


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

If a number is divisible by a number less than itself, it is divisible by a number less than or equal to (int)Math.sqrt(n). Can you see why?

- eugene.yarovoi on October 31, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

u can tweak it further by saying the composite number will be divisible by a prime<=sqrt(n).sth like blw to find 1st n primes

int primes[n]
boolean isPrime
primes[0]=2,primes[1]=3
i=5
while primes[n-1]!=0
 isPrime=true
 for k=1 to n-2
  if primes[k]>sqrt(i)
   break
  else if i%primes[k]==0
   isPrime=false
   break
 if(isPrime)
  primes[k+1]=i
 i+=2

- AB on October 31, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sure, at least if you're willing to use extra space to store those primes.

- eugene.yarovoi on November 01, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Run the loop from 1 to n/2

- Anonymous on October 31, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

and check only for odd numbers

- Anonymous on October 31, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

and check only for odd numbers

- Anonymous on October 31, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Asked about optimization in no.of divisons.

Here the initial case is 1 to n, little bit improved is 1 to n/2 but we have to use from 2 to sqrt(n)

- Nani on November 03, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

We only need to check for all prime number between 1 and sqrt(n).

- sausax on November 04, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nani's solution is probably the most optimal for finding if a single no. is prime or not. To generate a series of primes we can apply a sieve.

- Odi on December 22, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Exclude cases:
1. last digit is: 0,2,4,6,8,5
2. check special cases for divisibility of 3 (and 7, 11 if u want)

- andy on November 04, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Cant we divide it only by n/2, n/3, n/4, .... to see if its prime or not? Its not primse if the operation returns an integer other than 1.

- Srikant Aggarwal on November 19, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

For a given range of number say 1 to n we can check for primeness in the following
ie isPrime(int n)
1. if number is 1 or if n % 2 == 0 (if a number is even )then return false
2. use the axiom that if n has divisor from 1<d < n then it has divisor 1< do < sqrt(n)

isPrime(int n )
{
   if ( (n ==1) || (n %2 ) == 0 )
          return false;

   if(n ==2 )
        return true;

   for(int i=3; i<=(int)sqrt.(n) ; i++)
        if(n %i ==0)
           return false;

  return true;

}

- mvishnu2005 on February 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class PrimeTest2 {

/**
* @param args
*/
public static void main(String[] args) {

int count=0, p, numberOfPrimes;
List<Integer> primeList = new LinkedList<Integer>();

System.out.print("Enter the number of primes you want to get: ");
Scanner scan = new Scanner(System.in);
while(true){
if(!scan.hasNextInt()){
System.out.print("please enter only integer: ");
scan.next();
continue;
}else{
numberOfPrimes = scan.nextInt();
break;
}
}
p=1;
while(count<numberOfPrimes){
if(checkPrime(p)){
primeList.add(p);
count++;
}
p++;
}
System.out.println("First "+numberOfPrimes+" primes: "+primeList);
}

public static boolean checkPrime(int x){
int a, k;
if(x==1 || x ==2) return true;
if(x%2==0) return false;
k=3;
a=x/k+x%k;
while(k<=a){
if(x%k==0){
return false;
}else{
k+=2;
a = x/k+x%k;
}
}
return true;
}

}

- zoro's hub on July 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class PrimeTest2 {

/**
* @param args
*/
public static void main(String[] args) {

int count=0, p, numberOfPrimes;
List<Integer> primeList = new LinkedList<Integer>();

System.out.print("Enter the number of primes you want to get: ");
Scanner scan = new Scanner(System.in);
while(true){
if(!scan.hasNextInt()){
System.out.print("please enter only integer: ");
scan.next();
continue;
}else{
numberOfPrimes = scan.nextInt();
break;
}
}
p=1;
while(count<numberOfPrimes){
if(checkPrime(p)){
primeList.add(p);
count++;
}
p++;
}
System.out.println("First "+numberOfPrimes+" primes: "+primeList);
}

public static boolean checkPrime(int x){
int a, k;
if(x==1 || x ==2) return true;
if(x%2==0) return false;
k=3;
a=x/k+x%k;
while(k<=a){
if(x%k==0){
return false;
}else{
k+=2;
a = x/k+x%k;
}
}
return true;
}
}


}

- zoro's hub on July 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The code below will give us the minimum number of divisions performed to check whether a number is prime or not.

public boolean checkPrime(int x){
if(x==1 || x==2) return true;
if(x%2==0){
return false;
}
int k = 3;
int a = x/k ;
while(k <= a){
if(x%k == 0){
return false;
}else{
k+=2;
a = x/k ;
}
}
return true;
}

- zoro's hub on July 12, 2013 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through 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