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?

Question

Ran · Accepted Answer

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.

Anonymous · Answer

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 · Answer

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

Anonymous · Answer

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.

Siavash Mahmoudian · Answer

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

Stanley · Answer

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.

Ani · Answer

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

Google

Google interview question

Interview Answers

Followed companies

Job searches

Bowls

Want the inside scoop on your own company?