Google Interview Question: You have a ladder of N steps ... | Glassdoor

Interview Question

Product Manager Interview Mountain View, CA

You have a ladder of N steps (rungs). You can go up the

  ladder by taking either 1 step or two steps at a time, in any combination. How many different routes are there (combinations of 1 steps or 2 steps) to make it up the ladder?

Interview Answer

6 Answers


This is actually an example of the fibonacci sequence. Paths at level N = paths at level n-1 + paths at level n-2.

I'll leave the proof as an exercise to the reader. :)

Interview Candidate on Dec 2, 2014

And how in the hell does this question relate to being a Product Manager if you do not know the formula?

Anonymous on Jan 21, 2015

Speculating here, but I think the point is to be able to derive some sort of formula. Saying "it's a Fibonacci sequence!" should only get you points if your interviewer is a dweeb.

Anonymous on Jan 22, 2015

The answer is 89.

You can use recursive fibonacci function, in this case n is 10:

function countP(n) {
    if (n == 1 || n == 2) return n;
    return countP(n-1) + countP(n-2);

Or you can use combinations. There can be 10 ones, 8 ones and 1 two, 6 ones and 2 twos, 4 ones and 3 twos, 2 ones and 4 twos, or 5 twos which means. We can pick the place of ones (or twos) in 10 slots:

C(10,10)+c(9,8)+C(8,6)+C(7,4)+C(6,2)+C(5,0) = 89

Siavash Mahmoudian on Feb 5, 2015

You don't need to be familiar with the Fibonacci series. Simply test the first few cases manually and you can deduce that there's a pattern.
A ladder with 2 rungs (that is, the floor, rung #1 and rung#2): 2 ways to climb. 1+1, 2.
A ladder with 3 rungs: 3 ways to climb. 1+1+1, 1+2, 2+1.
A ladder with 4 rungs: 5 ways to climb. Think of it as climbing 1 rung and then you're at a 3-rung ladder (3 ways to climb) or climbing 2 rungs and then you're at a 2 rungs ladder (2 ways to climb). Overall you have 3+2 ways.
A ladder with 5 rungs: like the previous case, you climb 1 and reach a 4-rungs ladder, or climb 2 and reach a 3-rungs ladder. overall 5+3, or 8 ways.
A ladder with N rungs: sum of climbing (N-1) ladder and climbing (N-2) ladder:
Ways(N) = Ways(N-1) + Ways (N-2).

this can be solved with recursion or brute force.

Ran on Mar 16, 2015

It could be also solved using combination theory. It's obvious that the max step is N and the minimum step is N/2 (if N is odd number, then use ceiling function to get the integer). Then among all possible steps, we have two strategy: 1 step or 2 steps. Assuming we choose "2-step" strategy i times (i = 0,1,2,... N/2), then the solution will be sum of C(N,i) where i = 0,1,2,... N/2.

Stanley on Oct 17, 2015

Add Answers or Comments

To comment on this, Sign In or Sign Up.