Google
4.2 of 5 2,085 reviews
www.google.com Mountain View, CA 5000+ Employees

Google Software Engineer Intern Interview Question

"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 ?"
Add Tags [?]
Answer Flag Question

Part of a Software Engineer Intern Interview Review - one of 2,765 Google Interview Reviews

Answers & Comments

0
of 2
votes
2.*1*n distinct ways to climb
- Anonymous on Jan 25, 2011 Flag Response
9
of 9
votes
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 Flag Response
0
of 0
votes
No. of integral solutions to equation:

x+y = n

= n+2-1C2
- vkc on Feb 03, 2011 Flag Response
0
of 0
votes
int getways(int n)
{
  int i,j;
  int sumways=0;
  for(i=0;i<=n-i;i++)
  {
    if(i==0)
      sumways++;
    else
    {
      int subways=1;
      for(j=1;j<=i;j++)
        subways*=((n-j)/j);
      sumways+=subways;
    }
  }
}
- Shane on Feb 03, 2011 Flag Response
0
of 0
votes
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 04, 2011 Flag Response
0
of 0
votes
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 Flag Response
1
of 1
vote
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 Flag Response
0
of 0
votes
Fibonacci....
- dfrnascimento on Mar 07, 2014 Flag Response

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


Tags are like keywords, helping to categorise interview questions that have something in common.

Glassdoor is your free inside look at Google interview questions and advice. All interview reviews are posted anonymously by Google employees and interview candidates.