Interview Question for Software Engineer at Google:

before i post the answer, i'm curious if anyone here could explain the approach that you should use. i didn't understand how the sequence worked.

How is 3 (the third number in the sequence) equal to 2^i * 5^j? Is 3 supposed to be there, or is it a typo?

Good catch! Sorry about the typo. I'll write a little more too:
The start of the sequence is 1,2,4,5,8,10,16, 20, 25, 32...

Any thoughts?

There are two sets: -
Set-I is powers of 2 {2, 4, 8, 16, 32, 64....}
Set-II is powers of 5 {5, 25, 125....}
Set-III is composite function of both the above set {10, 20, 40,50, 80.......}

Now start with Set-I and keep on displaying it until it is less than 1st element of Set-II ans Set-III or otherwise display an element of Set-II or Set-III which ever is less.

Note:- Set-III is formed by multiplying Set I and Set II in sorted manner. (A code snippet is required to generate it)

There are two sets: -
Set-I is powers of 2 {2, 4, 8, 16, 32, 64....}
Set-II is powers of 5 {5, 25, 125....}
Set-III is composite function of both the above set {10, 20, 40,50, 80.......}

Now start with Set-I and keep on displaying it until it is less than 1st element of Set-II ans Set-III or otherwise display an element of Set-II or Set-III which ever is less.

Note:- Set-III is formed by multiplying Set I and Set II in sorted manner. (A code snippet is required to generate it)

There are two sets: -
Set-I is powers of 2 {2, 4, 8, 16, 32, 64....}
Set-II is powers of 5 {5, 25, 125....}
Set-III is composite function of both the above set {10, 20, 40,50, 80.......}

Now start with Set-I and keep on displaying it until it is less than 1st element of Set-II ans Set-III or otherwise display an element of Set-II or Set-III which ever is less.

Note:- Set-III is formed by multiplying Set I and Set II in sorted manner. (A code snippet is required to generate it)

I would also take the approach from An Idiot. What was the answer given by the interviewer?

public class googleAnswer {

    public static void main(String args[]){
        int[] sequence={1,2,4,5,8,10,16, 20, 25, 32};
        System.out.println(getNextNumber(sequence));
    }

    public static int getNextNumber(int[]sequence){
        int curNum=sequence[sequence.length-1];
        System.out.println(curNum);
        boolean found=false;
        while(!found){
            curNum++;
            int tempNum=curNum;
            while(tempNum%5==0){
                tempNum=tempNum/5;
            }
            while(tempNum%2==0){
                tempNum=tempNum/2;
            }
            if(tempNum==1){
                found=true;
            }
        }
        return curNum;
    }
}

The interviewer said something like multiply each number by 2 and also by 5 (two separate operations). This would give you:

1 x 2 = 2
1 x 5 = 5

then look at the smallest unused number and use that for the next set of operations:
2 x 2 = 4
2 x 5 = 10

and so on ...

I like the way of thinking about it as three sets better. Too bad I didn't think of that during the interview! I was hung up looking for a pattern in the exponents since he phrased it as 2^i * 5^j. It seemed like there was one until he gave me sample values after 20.

This question really threw me off because it's not like the other google interview questions I read about. It would have been interesting to pursue it past the math sequence portion (merging sets of streams of numbers).

Thanks for the feedback, though!

At a second glance, the sequence is surprisingly simple. It is merely the set of all numbers 2^i * 5^j in ascending order (where i, j >= 0).

The above answer can be implemented by a stack sorted in ascending order. Start off with 1, multiply it by 2 and 5, and put the products in the stack. Then go through each element in the stack, multiplying it by 2 and 5 and putting the products in the stack. (However, you don't want to insert duplicate entries, so you'd need to check for that while inserting the entries, but that wouldn't reduce the space/time efficiency.)

Anyone with more efficient solutions?

Here's an easy python solution. it doesn't print the first element in the sequence (1):

#!/usr/bin/env python
from operator import itemgetter

a = 2
b = 5
x = 0
y = 0
ptr1 = 2
ptr2 = 5

for i in range(30):
    h = { a**(x+1) * b**y : (lambda x,y,ptr1,ptr2: [x+1,y,ptr1,ptr2]),
            a**x * b**(y+1) : (lambda x,y,ptr1,ptr2: [x,y+1,ptr1,ptr2]),
            a * ptr1 * ptr2 : (lambda x,y,ptr1,ptr2: [x,y,ptr1*a,ptr2]),
            ptr1 * b * ptr2 : (lambda x,y,ptr1,ptr2: [x,y,ptr1,ptr2*b]) }

    for k, v in sorted(h.iteritems(), key=itemgetter(0), cmp=lambda i, j: i - j):
        if k > 0:
            print k
            x,y,ptr1,ptr2 = v(x,y,ptr1,ptr2)
            break

Slight modification to my solution to fix an off-by-one error

#!/usr/bin/env python
from operator import itemgetter

a = 2
b = 5
x = 0
y = 0
ptr1 = 2
ptr2 = 5
last = 1

for i in range(30):
    h = { a**(x+1) * b**y : (lambda x,y,ptr1,ptr2: [x+1,y,ptr1,ptr2]),
            a**x * b**(y+1) : (lambda x,y,ptr1,ptr2: [x,y+1,ptr1,ptr2]),
            ptr1 * ptr2 : (lambda x,y,ptr1,ptr2: [x,y,ptr1,ptr2]),
            a * ptr1 * ptr2 : (lambda x,y,ptr1,ptr2: [x,y,ptr1*a,ptr2]),
            ptr1 * b * ptr2 : (lambda x,y,ptr1,ptr2: [x,y,ptr1,ptr2*b]) }

    for k, v in sorted(h.iteritems(), key=itemgetter(0), cmp=lambda i, j: i - j):
        if k > last:
            print last
            x,y,ptr1,ptr2 = v(x,y,ptr1,ptr2)
            last = k
            break

Well, we can make several observation:
 * a number multiplied by 8 (2^3) is always larger than that multiplied by 5.
 * if we seed the list with 2 consecutive multiple of 2 (e.g. 2 and 4), we do not need to multiply the number by 2 (2*2 = 4 is already in the list) and only need to multiply by 4 (see that 2*4 = 8, then 4*2 = 8, oops already in the list)
 * if we have a number that is divisible by 5, we simply need to multiply it by 5 since the results of multiplying the number by 2 or 4 would have been generated previously (we note that 5n * 4 is equivalent to 4n * 5, obviously 4n < 5n; similar argument for multiplication by 2).

Hence, here is a very simple algorithms to generate the first n numbers in the sequence:
 1. we start with a seed of [1, 2]
 2. we iterate through the list until length of list = n, for each number k we see,
     (a) if k is divisible by 5, append to the list 5k, otherwise
     (b) append 4k and 5k

def createPowerList(n):
    lst = [1, 2];
    i = 0
    while len(lst) < n:
        currentValue = lst[i]
        if currentValue % 5 == 0:
            lst.append(currentValue * 5)
        else:
            lst.append(currentValue * 4)
            lst.append(currentValue * 5)
        i = i + 1
    return lst