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

View Allnum of num

6 Answers

▲

5

▼

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

▲

4

▼

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.

▲

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

▲

16

▼

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.

▲

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.

To comment on this, Sign In or Sign Up.

Would you like us to review something? Please describe the problem with this {0} and we will look into it.

Your feedback has been sent to the team and we'll look into it.

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