Amazon Interview Question for Software Engineer / Developers






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

Sieve of Eratosthenes is a much better solution for a problem where you have to find primes in 1-N. For 1-100, you will only need 8 iterations to find all primes.
See: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

- SG October 20, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yep.

We can make a 100-length bit array.
Then iterate as follows:
Do a separate iteration over 4,6,8, etc and flip all bits at those indices.
For index from 3 to root-of-100 (i.e. 10):
If bit at index not equal to 1:
Turn to 1 bits at (index+2*index*k), where k=1,2,3,...
(e.g. for index=3, you flip 9,15,21, etc; skip even numbers)

- mathytime September 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.lang;
public static void Main(String[] args)
{
int [] intArray = new int[101];
for(int i=0;i<intArray.length ;i++)
{
intArray[i]=1;
}
for(int i = 2;i<101;i++)
{
int count =2;
while(count<101)
{
if(count != i)
{
if((count%i)==0)
{
intArray[count] =0;
}// end If
count++;
}// end if
}// end While
}// end for

for(int i = 0; i <intArray.length;i++)
{
if(intArray[i] == 1)
System.out.println(" values which are prime numbers:" + intArray[i]);
} // end for
}// end Main


Order of O(^2).

Please provide a feedback and a better one if possible.

Thanks
AB

- AB October 20, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.lang;
public static void Main(String[] args)
{
int [] intArray = new int[101];
for(int i=0;i<intArray.length ;i++)
{
intArray[i]=1;
}
for(int i = 2;i<101;i++)
{
int count =2;
while(count<101)
{
if(count != i)
{
if((count%i)==0)
{
intArray[count] =0;
}// end If
count++;
}// end if
}// end While
}// end for

for(int i = 0; i <intArray.length;i++)
{
if(intArray[i] == 1)
System.out.println(" values which are prime numbers:" + intArray[i]);
} // end for
}// end Main


Order of O(^2).

Please provide a feedback and a better one if possible.

Thanks
AB

- AB October 20, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The outer for loop need not to iterate for 101 times i.e.,
Line 9: for(int i = 2;i<101;i++)
it is enough to iterate for sqrt of(101).

- arvinthc November 27, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Good explanation and C# and VB.net implementation
http://www.nist.gov/dads/HTML/sieve.html
http://blogs.msdn.com/brada/articles/409081.aspx

- AK December 23, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Primes are all odd... So check i+2 start with 3....

- Amon February 12, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple. Just hardcode it! Only upto 100, right?

- T March 16, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I quickly came up with this (I feel it is correct, but u never know!)

1. Check only odd numbers.
2. For those numbers, check if the number is divisible by 3, 5 or 7.
3. If the number obeys the above 2 conditions, it is not prime, else prime.

- Anonymous May 28, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Cute. This looks right. But a hardcoded version beats this.

Suppose some composite odd number k <= 100 is not divisible by 3,5, or 7.

Let k = a*b where a is a prime.

a must be >= 11. Also, since b is not divisible by 3,5, or 7 and is odd, b >= 11 also. This k >= 121, not possible.

- T May 28, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I dont get it.. why must a be >=11? isn't 1,2,3,5,7 a few prime numbers less than 11?
it could be 5. 55 is an odd number, and is NOT prime.. Besides hard-coding is barely an algorithmic solution.
Further, i don't think using such a brute force mechanism is going to be a greatly intelligent idea at all, where u find all odd numbers that are not divisible by 3,5,7.

- optimus July 05, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

ok.. sorry 1 is not a prime number, or it is.. lets keep away from that discussion. Lets just say its not. I take 1 back.

- optimus July 05, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What are you talking about?

What I wrote tries to prove that the algorithm given by Anonymous on May 28th (checking an odd number for divisibility by 3,5,7) is correct.

- T July 05, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

oh? ok i probably royally misunderstood ur point, pardon that.

- optimus July 05, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

You can keep a boolean array range from 0-100 (call it prime). Make all entries in the array as true.
We know that 0,1 are not prime. So prime[0] and prime[1] = false.
Now starting from 2 - cancel out all factors of 2,which means prime[4],prime[6] and so on make it as (false). Once thats done, go to the next entry in prime which is true;i.e 3.

boolean[] primeArray = new boolean[n + 1];
Arrays.fill(primeArray, true);
int range = (int)Math.sqrt(n);
		
primeArray[0] = false;
primeArray[1] = false;
		
for (int count = 2; count <= range; count++)
{
    if (primeArray[count])
    {
	for (int countFactors = count*count; countFactors<=n; countFactors = countFactors + count)
					primeArray[countFactors] = false;
   }
}

- Tom July 14, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

c# function..

List<int> arr = new List<int>();            
            for (int i = 1; i < 100; )             
                arr.Add(++i);

            for (int i = 2; i <= 10; i++)             
                arr.RemoveAll(a => a != i && a % i == 0);

- bobo August 09, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

suppose u have number 'n', to check if it is prime, what if we check if it is divisible by a prime number less than n.
if it is divisible, then it is composite, else it is prime.
example -> n = 17
so u will check if 7 gives a remainder with 2,3,5,7,11 or 13. it doesnt hence, it is prime.
suppose n = 18. try again with 2,3,5,7,11,13,17. it is divisible by 2 and 3. hence, composite.
thus, we need to maintain a list of all prime numbers encountered below n.

- Anon October 06, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's Python:

def sieve_primes(N):
   """Find all primes <= N using the sieve of Eratostenes"""
   is_prime = 2*[False] + (N-1)*[True] # 0,1,2,3 ...
   primes = []
   p = 1
   while 1:
       try:
           p = (p+1) + is_prime[(p+1):].index(True)
       except ValueError:
           break # no more primes in range
       primes.append(p)
       for i in range(2*p,N+1,p):
           is_prime[i] = False
   return primes

print(sieve_primes(100))

- Bullocks December 29, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Prime {

public static void main(String[] args) {
int flag = 0;

System.out.print("2 ");

for (int i = 3; i<101; i = i + 2) {
flag = 0;
for (int j = 2; j <= Math.sqrt(i); j++) {
if (i % j == 0) {
flag = 1;
}
}
if (flag != 1)
System.out.print(i + " ");
}
}

}

- Anonymous January 23, 2010 | 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