Google Interview Question: You are climbing a stair case... | Glassdoor

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 ?

1

2.*1*n distinct ways to climb

Anonymous on Jan 25, 2011
15

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

No. of integral solutions to equation:

x+y = n

= n+2-1C2

vkc on Feb 3, 2011
1

int getways(int n)
{
int i,j;
int sumways=0;
for(i=0;i&lt;=n-i;i++)
{
if(i==0)
sumways++;
else
{
int subways=1;
for(j=1;j&lt;=i;j++)
subways*=((n-j)/j);
sumways+=subways;
}
}
}

Shane on Feb 3, 2011
0

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+2
2+1
2+2
1+1+1+1+2+2+2+2. . . .

Wendy Godfrey on Mar 4, 2011
2

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

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

More details here: http://dailyjobquestions.com/2011/10/17/stairs/

Mihai Roman on Oct 17, 2011
0

Fibonacci....

dfrnascimento on Mar 7, 2014