Tricky Google interview question

Question

Dijkstra derives an eloquent solution in "A Discipline of Programming". He attributes the problem to Hamming. Here is my implementation of Dijkstra’s solution.

int main()
{
    const int n = 20;       // Generate the first n numbers

    std::vector<int> v(n);
    v[0] = 1;

    int i2 = 0;             // Index for 2
    int i5 = 0;             // Index for 5

    int x2 = 2 * v[i2];     // Next two candidates
    int x5 = 5 * v[i5];

    for (int i = 1; i != n; ++i)
    {
        int m = std::min(x2, x5);
        std::cout << m << " ";
        v[i] = m;

        if (x2 == m)
        {
            ++i2;
            x2 = 2 * v[i2];
        }
        if (x5 == m)
        {
            ++i5;
            x5 = 5 * v[i5];
        }
    }

    std::cout << std::endl;
    return 0;
}

here is a more refined way of doing it (more refined than my previous answer, that is):

imagine the numbers are placed in a matrix:

     0    1    2    3    4    5   -- this is i
----------------------------------------------
0|   1    2    4    8   16   32
1|   5   10   20   40   80  160
2|  25   50  100  200  400  800
3| 125  250  500 1000 2000 ...
4| 625 1250 2500 5000 ...
j on the vertical

what you need to do is 'walk' this matrix, starting at (0,0). You also need to keep track of what your possible next moves are. When you start at (0,0) you only have two options: either (0,1) or (1,0): since the value of (0,1) is smaller, you choose that. then do the same for your next choice (0,2) or (1,0). So far, you have the following list: 1, 2, 4. Your next move is (1,0) since the value there is smaller than (0,3). However, you now have three choices for your next move: either (0,3), or (1,1), or (2,0).

You don't need the matrix to get the list, but you do need to keep track of all your choices (i.e. when you get to 125+, you will have 4 choices).

Use a Min-heap.

Put 1.

extract-Min. Say you get x.

Push 2x and 5x into the heap.

Repeat.

Instead of storing x = 2^i * 5^j, you can store (i,j) and use a custom compare function.

A FIFO-based solution needs less storage capacity. Python code.

F = [[1, 0, 0]]             # FIFO [value, i, j]
i2 = -1; n2 = n5 = None     # indices, nexts
for i in range(1000):       # print the first 1000
    last = F[-1][:]
    print "%3d. %21d = 2^%d * 5^%d" % tuple([i] + last)
    if n2 <= last: i2 += 1; n2 = F[i2][:]; n2[0] *= 2; n2[1] += 1
    if n5 <= last: i2 -= 1; n5 = F.pop(0); n5[0] *= 5; n5[2] += 1
    F.append(min(n2, n5))

output:

  0.                     1 = 2^0 * 5^0
  1.                     2 = 2^1 * 5^0
  2.                     4 = 2^2 * 5^0
 ...
998. 100000000000000000000 = 2^20 * 5^20
999. 102400000000000000000 = 2^27 * 5^17

This is very easy to do O(n) in functional languages. The list l of 2^i*5^j numbers can be simply defined as 1 and then 2*l and 5*l merged. Here is how it looks in Haskell:

merge :: [Integer] -> [Integer] -> [Integer]
merge (a:as) (b:bs)   
  | a < b   = a : (merge as (b:bs))
  | a == b  = a : (merge as bs)
  | b > a   = b : (merge (a:as) bs)

xs :: [Integer]
xs = 1 : merge (map(2*)xs) (map(5*)xs)

The merge function gives you a new value in constant time. So does map and hence so does l.