## 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 = 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]);
}
}``````

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

Can you explain how it works?

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

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

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

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.

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.

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

Nice solution!

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

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

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.

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

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

This doesn't work..

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

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

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

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

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

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

My mistake.

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(, merged)
output = (k for k, v in groupby(combined))
return result

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

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  == 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 = 
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()``````

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

}}

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

}
}}

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] + " ");
}``````

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

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

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] + " ");
}``````

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

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>();

for (int i = 0; i < N; i++)
{
int x = queue.remove();
System.out.println(x);

if (!queue.contains(x * 2))
if (!queue.contains(x * 5))
}
}

public static void main(String[] args) {
printFirstElements2i5j(10);
}``````

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.