Amazon Interview Question
SDE1sTeam: WebStore
Country: India
Interview Type: Phone Interview
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.
This is a famous problem (ugly numbers problem or hamming numbers problem), and this solution is well known as Dijkstra's solution.
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
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.
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);
}
}
This doesn't work..
for N=10, it prints
[2 4 5 8 16 25 32 64 125 128].... well 20 is missing out
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
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)))
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()
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] + " ");
}
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] + " ");
}
#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;
}
}
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);
}
- Nitin Gupta March 20, 2013