Interview Question

Product Manager Interview

-Mountain View, CA

Google

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?

AnswerAdd Tags

Interview Answers

7 Answers

17

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

6

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

Anonymous on

5

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

5

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

1

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

0

Here is an illustration of what you are trying to solve for the case of 𝑛=4 n = 4 steps (taken from this website, which also gives a combinatorial solution) enter image description here Any staircase with 𝑛 n steps allowing paths with increments of 1 or 2 steps at a time will end up in one of two states before the last path is taken: either we've climbed (𝑛−1) ( n − 1 ) steps already and have 𝑜𝑛𝑒 o n e more step to take, or we've climbed (𝑛−2) ( n − 2 ) steps already and we have 𝑡𝑤𝑜 t w o more steps to take (if we took only one step here then we'd end up in an arrangement from the first state). enter image description here Thus, to get the total number of possible ways to climb 𝑛 n steps, we just add the number of possible ways we can climb (𝑛−1) ( n − 1 ) steps and the number of possible ways we can climb (𝑛−2) ( n − 2 ) steps, giving the familiar recurrence relation: 𝐹𝑛={1𝐹𝑛−1+𝐹𝑛−2𝑛=0,1𝑛≥2

Ani on

10

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. :)

Anonymous on

Add Answers or Comments

To comment on this, Sign In or Sign Up.