Cookies help us deliver our services. By using our services, you agree to our use of cookies. Click here to learn more

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 25 Jan 2011

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 28 Jan 2011

No. of integral solutions to equation:

x+y = n

= n+2-1C2

vkc on 3 Feb 2011

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

Shane on 3 Feb 2011

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 4 Mar 2011

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 21 May 2011

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

More details here:

Mihai Roman on 17 Oct 2011


dfrnascimento on 7 Mar 2014

Add Answers or Comments

To comment on this, Sign In or Sign Up.