Amazon Interview Question for Software Engineer / Developers

• 0

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?

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

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

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

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

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

Run the loop from 1 to n/2

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

and check only for odd numbers

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

and check only for odd numbers

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

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)

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

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

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

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.

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)

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.

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;

}

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

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

public class PrimeTest2 {

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

int count=0, p, numberOfPrimes;

System.out.print("Enter the number of primes you want to get: ");
Scanner scan = new Scanner(System.in);
while(true){
if(!scan.hasNextInt()){
scan.next();
continue;
}else{
numberOfPrimes = scan.nextInt();
break;
}
}
p=1;
while(count<numberOfPrimes){
if(checkPrime(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;
}

}

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

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

public class PrimeTest2 {

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

int count=0, p, numberOfPrimes;

System.out.print("Enter the number of primes you want to get: ");
Scanner scan = new Scanner(System.in);
while(true){
if(!scan.hasNextInt()){
scan.next();
continue;
}else{
numberOfPrimes = scan.nextInt();
break;
}
}
p=1;
while(count<numberOfPrimes){
if(checkPrime(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;
}
}

}

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

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.