More DBA job interview questions and answers at
http://dba.fyicenter.com/Interview-Questions/

*(Continued from previous question...)*

**
Google Technical Interviews in Management round: Given that you can take one step or two steps forward from a given step. So find the total number of ways of reaching Nth step.
**

# Solution:The simple recurrence relation governing this problem is f(N)=f(N-1) +f(N-2)(why?),which is a fibonacci sequence.

Nth state can be arrived directly by taking 2 step movement from N-2 or 1 step from N-1.Remember N-2 -> N-1 -> N is not a direct path from N-2th state to Nth state.Hence the no of solutions is no of ways to reach N-2th step and then directly taking a 2 jump step to N + no of ways to reach N-1th step and then taking 1 step advance.

*(Continued on next question...)*