Interview Question

Software Engineer Intern Interview

You are climbing a stair case. Each time you can either

  make 1 step or 2 steps. The staircase has n steps. In how many distinct ways can you climb the staircase ?

Interview Answer

8 Answers


2.*1*n distinct ways to climb

Anonymous on 2011-01-25

Let c(i-1) = the total for a staircase with i-1 steps. Now add one step to the beginning. You have two choices: start with one step and then do c(i-1), or start with two steps and then do c(i-2). In other words, c(i) = c(i-1) + c(i-2). The basis for the recurrence is c(0) = c(1) = 1.

This is exactly the Fibonacci sequence. I submit that the solution to this problem of n steps is Fib(n+1). Let's verify for small values of n:

1 steps: There's only one way to take one step. (1)
2 steps: There are 2 ways (1+1) or (2)
3 steps: 3 ways (1+1+1), (1+2), (2+1)
4 steps: 5 ways (1+1+1+1), (1+1+2), (1+2+1), (2+1+1), (2+2)

lamont on 2011-01-28

No. of integral solutions to equation:

x+y = n

= n+2-1C2

vkc on 2011-02-03

int getways(int n)
  int i,j;
  int sumways=0;
      int subways=1;

Shane on 2011-02-03

If I may take the steps in 1 or 2 or any combination thereof =4 (remember, # of stairs are not factored). HOWEVER, this combination may have infinite combination the more stairs there are! You would still use the basic steps as the question has a base of two :

1+1+1+1+2+2+2+2. . . .

Wendy Godfrey on 2011-03-04

this is fibonacci

your first step can be either 1 or 2 step.
if first step is 1 step, remaining is an N-1 problem.
if first step is 2 steps, remaining is an N-2 problem.
N problem = N-1 problem + N-2 problem

dantepy on 2011-05-21

This is a dynamic programming puzzle with the Fibonacci recurrence: s(i) = s(i-1) + s(i-2).

More details here:

Mihai Roman on 2011-10-17


dfrnascimento on 2014-03-07

Add Answers or Comments

To comment on this Question, Sign In with Facebook or Sign Up