## Amazon Interview Question for Software Engineer / Developers

• 0

Comment hidden because of low score. Click to expand.
1
of 1 vote

I think fib is correct. This is the simple observation:
Let f(i) be the number of ways that can be taken to reach step i.
f(2) = 1
f(i) = f(i-1) + f(i-2)
That is, if we assume that we are about to take the last step for reaching i, either we are at step i-1 or at step i-2. Coming to step (i-1) we could have taken f(i-1) ways, for coming to i-2, we could have taken f(i-2) different ways.

Comment hidden because of low score. Click to expand.
0
of 2 vote

Hi Guys, can you please help me understand how were u able to relate this problem to fibanocci series..

Comment hidden because of low score. Click to expand.
0
of 0 vote

Now, the number of ways to reach step 2 from 1 is 1 and to reach every step from 3 to n, there are 2 ways, either from n-2 nd step or n-1st step.
Therefore, there are 2^(n-2)ways for steps 3 to n. And there is one way to reach step 2.

Thus, the answer shud be 2^(n-2)+1.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Yes Fibonacci no. for the nth step is the right answer.

Comment hidden because of low score. Click to expand.
0
of 0 vote

If N is Even x = N/2
If N is odd X = N/2-1
Xc0+Xc1+Xc2....+Xcx
Correct me if my answer is wrong.

Comment hidden because of low score. Click to expand.
0

The above answer is Wrong , i think the right solution is f(n-1)+f(n-2)

Comment hidden because of low score. Click to expand.
0
of 0 vote

Guys!!!

who ever not willing to accept fibonacci series as answer, try to use mathematical induction and you'll get the answer as Fibonacci series.....

already at step-1 : hence if n=1 , no.of ways=1
if n=2, already at step-1: hence only 1 way possible hence-> 1
n=3 (1,1) or (2) -> 2 ways

f(3)=f(2)+f(1);

Comment hidden because of low score. Click to expand.
0

Fibonacci is the correct solution.
#steps : #ways
1 : 1
2: 2
3: 3
4: 5
5: 8
...
hence its a perfect Fibonacci series

Comment hidden because of low score. Click to expand.
0
of 0 vote

Fibonacci is the correct solution.
But the defination should be as below:
f(n) = f(n-1) + f(n-2) +1
f(1) = 0
f(2) = 1

Comment hidden because of low score. Click to expand.
0

Dude how is f(1)=0?? You mean to say that there is no way to climb step one?

Comment hidden because of low score. Click to expand.
0

you are on step 1

Comment hidden because of low score. Click to expand.
0
of 0 vote

F(4) should be equal to 3 bt the above formula is giving 4. There are 3 ways
1->2->3->4
1->2->4
1->3->4.

Comment hidden because of low score. Click to expand.
0

2-4

i think they went from the floor

Comment hidden because of low score. Click to expand.
0
of 0 vote

it should be defined as
F(1)=1;
F(2)=1;
F(n)=F(n-1)+F(n-2)

Comment hidden because of low score. Click to expand.
0

F(2) = 2 because there are two ways to reach two steps, one is 1 and 1 and the other is 2

Comment hidden because of low score. Click to expand.
0
of 0 vote

f(0) = 1 [Possible ways of reaching the step on which ur already there]
f(1) = 1 (1)
f(2) = 2 (1,1) (2)
f(3) = 3 (1,1,1) (1,2) (2,1)
f(4) = 5 (1,1,1,1) (1,1,2) (1,2,1) (2,1,1) (2,2)
...

Comment hidden because of low score. Click to expand.
0
of 0 vote

it's a kind of dp problem,if ny one thoroughly looks into that then it can be seen easily
idea is that initialize an array a[n+1] with a=1,a=1
i=2
loop:
if i <=n
a[i]=a[i-1]+a[i-2]
else
break
i++
goto loop
print a[n+1]

Comment hidden because of low score. Click to expand.
-1
of 1 vote

f(n) = 2 + f(n-1) + f(n-2)

Which is basically the fibonacci series.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

f(n) = f(n-1) + f(n-2) + f(n-3)

F(n) = total number of ways

Comment hidden because of low score. Click to expand.
0

f(n) = f(n-1) + f(n-2) as he can take 1 or 2 steps

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.