Amazon Interview Question for SDE1s


Team: WebStore
Country: India
Interview Type: Phone Interview




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

void print(int N)
{
    int arr[N];
    arr[0] = 1;
    int i = 0, j = 0, k = 1;
    int numJ, numI;
    int num;
    for(int count = 1; count < N; )
    {
       numI = arr[i] * 2;
       numJ = arr[j] * 5;
       if(numI < numJ)
       {
           num = numI;
           i++;
       }
       else
       {
           num = numJ;
           j++;
       }
       if(num > arr[k-1])
       {
          arr[k] = num;
          k++;
          count++;
       }
    }
    
    for(int counter = 0; counter < N; counter++)
    {
        printf("%d ", arr[counter]);
    }
}

- Nitin Gupta March 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you explain how it works?

- susantam25 March 20, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

cool answer.. I'm still wondering how did this work?

- Anonymous March 20, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

This is the best way to do this. You can think of i and j as chasing pointers, where i's value is waiting to be doubled and j's value is waiting to be quintupled. After a while your array will look something like this:

1
2
4
5
8 j
10
16 i
20
25
?? k

i is pointing to 16, which means it's queuing up 2*16 == 32
j is pointing to 8, which means it's queuing up 5*8 == 40.

On the next pass, 32 will be smaller, so that's you're next result, and then i will advance to 20, thereby queuing up 40.

On the next pass, you'll have a tie.

@nitingupta180, nicely done.

- showell30@yahoo.com March 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

This is a famous problem (ugly numbers problem or hamming numbers problem), and this solution is well known as Dijkstra's solution.

- Anonymous March 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice solution!

- alex March 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

The logic should be as follows:
Maintain two queues. Q2 having one element 2. And Q5 having one element 5.
From both the queues, extract the min number that stood in front of queue. If the number comes out of Q2, append 2*number to Q2 and 5*number to Q5. If the min number is from Q5, append 5*number in Q5. Repeat the process.

For example:
Step 1: Initialization
Q2 = 2
Q5 = 5

Step 2
min is 2; print 2
Q2 = 4
Q5 = 5, 10

step 3
min 4; print 4
Q2 = 8
Q5 = 5, 10, 20

step 4
min 5; print 5
Q2 = 8
Q5 = 10, 20,25

step 5
min 8; print 8
Q2 = 16
Q5 = 10, 20, 25, 40

on and on....till we print N numbers

- aasshishh March 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is a fine way of approaching the problem, but if you are storing the results as you emit them, then you can make Q2 and Q5 be virtual queues. In other words, don't store all upcoming Q5 values; instead, simply keep track of the head of the queue. For Q5=10,20,25,40, think of it as 5*[2,4,5,8], where [2,4,5,8] is just a subset of the numbers that you've already produced. In this case, you just store the index of "2" in the original result to know the head of the queue. When you peek at Q5, you multiple 2 by 5 to get 10. When you pop Q5, then the next element will the index of 4 in your result set. This type of reasoning basically gets you to the solution that @nitingupta180 presented.

- showell30@yahoo.com March 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Question says we need to print N numbers.
Every step compare 2^i with 5^j and print the minimum. In every step increment i and j based on what you have used in that step.

package algo;

public class PrintN {

	public static void printN(int N){
		int count =0;
		int num1=1;
		int num2=1;
		while(count <N){
			int k=num1*2;
			int l=num2*5;
			if(k<l){
				System.out.print(k+" ");
				num1=num1*2;
			}else{
				num2=num2*5;
				System.out.print(num2+" ");
			}
			count++;
		}
	}
	
	public static void main(String args[]){
		PrintN.printN(10);
	}
}

- Krishna K Tiwari March 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This doesn't work..

for N=10, it prints
[2 4 5 8 16 25 32 64 125 128].... well 20 is missing out

- Anonymous March 20, 2013 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 votes

Actually 20 is not producible from 2^i or 5^j.

- Krishna K Tiwari March 20, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think the question is for 2^i X 5^j... you should take a look at it, which makes
20 = 2^2 X 5^1 i.e. i=2,j=1... by the way the solution is provided by nitingupta180, it works as expected

- Anonymous March 20, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

My mistake.

- Krishna K Tiwari March 20, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python Blow-Your-Mind Version.

Google "activestate python hamming numbers" for more explanation. This code is a minor adaptation:

from itertools import tee, chain, islice, groupby
from heapq import merge

def hamming_numbers():
    def deferred_output():
        for i in output:
            yield i

    result, p2, p5 = tee(deferred_output(), 3)
    m2 = (2*x for x in p2)
    m5 = (5*x for x in p5)
    merged = merge(m2, m5)
    combined = chain([1], merged)
    output = (k for k, v in groupby(combined))
    return result


if __name__ == '__main__':
    print(list(islice(hamming_numbers(), 10)))

- showell30@yahoo.com March 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple Python Version.

def test():
    assert [] == list(smooth_2_5(0))
    assert [1] == list(smooth_2_5(1))
    assert [1,2,4] == list(smooth_2_5(3))
    assert [1,2,4,5,8,10,16,20] == list(smooth_2_5(8))

def smooth_2_5(n):
    if n == 0:
        return
    queue = [1]
    cnt = 0
    while True:
        result = queue.pop(0)
        yield result
        n -= 1
        if n == 0:
            return
        if result*2 not in queue: queue.append(result*2)
        if result*5 not in queue: queue.append(result*5)
        queue.sort()

test()

- showell30@yahoo.com March 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{{


count =0
i=0;
j=0;
N=10
while(count<N):
tresult = (2**i)*(5**j)
print tresult
ithnum = (2**(i+1))*(5**j)
jthnum = (2**i)*(5**(j+1))
if ithnum<jthnum:
i+=1
else:
j+=1
count+=1

}}

- shinde.sandip.s March 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{{
public static void main (String args[]){
int counter=0;
int i=0,j=0;
System.out.println("1");
double sum1,sum2;
while(counter<10){
sum1=Math.pow(2, i+1);
sum2=Math.pow(5,j+1);
if(sum1<sum2){
System.out.println(sum1);
i=i+1;
}else{
System.out.println(sum2);
j=j+1;
}
counter++;
}

}
}}

- jagdish March 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void printNum(int i, int j) {
		int[] a = new int[i+j];
		for(int m=0;m<=i;m++) {
			a[m] = (int)Math.pow(2*1.0, m*1.0);
		}
		for(int m=1;m<=j;m++){
			a[m+i-1] = (int)Math.pow(5*1.0, m*1.0);
		}
		Arrays.sort(a);
		for(int n=0;n<a.length;n++)
			System.out.print(a[n] + " ");
	}

- lin March 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

the above is wrong. discard it. It is 2^i*5^j not 2^i or 5^j. I misunderstood the question

- lin March 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void printNum(int i, int j) {
		int len = (i+1)*(j+1);
		int[] a = new int[len];
		int tmp=0, k=0;
		for(int m=0; m<=i; m++) {
			tmp = (int)Math.pow(2*1.0, m*1.0);
			for(int n=0; n<=j; n++) {
				a[k] = tmp*((int)Math.pow(5*1.0, n*1.0));
				k++;
			}			
		}
		
		Arrays.sort(a);
		for(int n=0;n<a.length;n++)
			System.out.print(a[n] + " ");
	}

- lin March 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <set>

int printIncreasingOrder(int i, int j, int N)
{
    std::set<int> myset;
    std::set<int>::iterator it

    // note that std::set sorts the values in increasing order...
    for(int x=0; x<i; x++) myset.insert(pow(2.0, x));
    for(int y=0; y<j; y++) myset.insert(pow(5.0, y));

    for(int count = 0, it=myset.begin(); it!=myset.end(); ++it, ++count)
    {
        if(count < N)
            std::cout << ' ' << *it;
        else
	    break;
    }
}

- Darrell April 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use a min Heap. Start by putting in 1 (i = 0, j = 0). Pop 1, print it and increase your printed count. Then throw back in the heap 1 * 2, and 1 * 5. Rinse and repeat until your count reaches N.

public static void printFirstElements2i5j(int N)
    {
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
        queue.add(1);
        
        for (int i = 0; i < N; i++)
        {
            int x = queue.remove();
            System.out.println(x);
            
            if (!queue.contains(x * 2))
                queue.add(x * 2);
            if (!queue.contains(x * 5))
                queue.add(x * 5);
        }
    }
    
    public static void main(String[] args) {
        printFirstElements2i5j(10);
    }

- houseUrMusic September 19, 2013 | 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