Google Interview Question: This was one of the more stan... | Glassdoor

Interview Question

Software Engineer Intern Interview

This was one of the more standard questions. You have

stairs with N number of steps. You can take either one step steps or two step steps; how many ways can you climb the stairs?

0

1 .
2 ..
3 ...
4 1111 121 211 112 22 5
5 11111 221 122 212 1112 2111 1211 1121 8
6 111111 222 2112 1122 2211 11112 11211 12111 21111 11121 11112 11

3n-7 for n&gt;3

sman on Nov 26, 2013
1

mistake in my last answer, it's actually a fib seq. here is the code:

void main()
{
int n,k;
printf("Enter no. of stairs: ");
scanf("%d",&amp;n);
k=fibo(n);
}

int fibo(int n)
{
if(n==0)
return 0;

if (n==1)
return 1;
else
return(fibo(n-1)+fibo(n-2));

}

sman on Nov 26, 2013
2

Better to do it the dynamic programming way; it shows that you understand that a double recursive solution is terribly inefficient.

Python makes this incredibly easy:

def stairs(n):
a = [1, 2]
for i in range(0, n-2):
a.append(a[-1] + a[-2])
return a[-1]

Anonymous on Nov 22, 2014
0

This person from Google told me what to expect in this interview. it was really good info and helpful. Here's their profile: