Amazon Coding Interview Question - Recursive Staircase Problem

Amazon coding interview question and answer - recursive staircase problem!

(That’s a referral link, and you can get a 10% discount through that link. Their free option and blog articles are good, too, though.)

Outline (check my comment for the clickable outline):
0:07: Problem description
1:14: A variation of the problem
2:15: Thinking about simple cases
4:18: Finding a pattern
5:24: Relabeling the steps
6:41: Revisiting the pattern with the new labels
7:53: The pattern we’ve found - recap.
8:11: The recursive relationship we’ve found
8:50: What about when N = 0?
9:40: Writing a naive recursive solution
10:39: Why this solution is not efficient
11:24: How to fix it with dynamic programming (bottom-up)
12:27: The bottom-up solution in code
13:34: How to make it more efficient in terms of space
14:19: Solution to the variation of the problem
14:49: The recursive relationship for this problem (the variation)
15:08: A naive, INCORRECT recursive solution to this problem
15:50: A naive, CORRECT recursive solution to this problem
16:17: A naive, correct recursive solution in code
17:11: A dynamic programming / bottom-up approach

[CSDojo]

Below is an outline of this video with timestamps.
Btw as I mentioned in the video, for daily coding problems, I’d recommend this website called Daily Coding Problem. It’s actually made by a friend of mine who I used to work with at Google.

0:07: Problem description
1:14: A variation of the problem
2:15: Thinking about simple cases
4:18: Finding a pattern
5:24: Relabeling the steps
6:41: Revisiting the pattern with the new labels
7:53: The pattern we’ve found - recap.
8:11: The recursive relationship we’ve found
8:50: What about when N = 0?
9:40: Writing a naive recursive solution
10:39: Why this solution is not efficient
11:24: How to fix it with dynamic programming (bottom-up)
12:27: The bottom-up solution in code
13:34: How to make it more efficient in terms of space
14:19: Solution to the variation of the problem
14:49: The recursive relationship for this problem (the variation)
15:08: A naive, INCORRECT recursive solution
15:50: A naive, CORRECT recursive solution
16:17: A naive, correct recursive solution in code
17:11: A dynamic programming / bottom-up approach

[MrBartolomeo]

It's funny that all those IT companies bombard the candidate with algorithmic questions during the interview, but in the actual job you just glue some libraries together and hope for the best

[codinginflow]

Me: Just take the elevator
Amazon: You're hired

[SeanIsCrispy]

*Amazon:* Write a function that solves this problem
*Me:* Goes to Stack Overflow
*Amazon:* You're hired

[technbyond]

I got the same exact question for my McGrow Hill interview. They gave me 10 min to solve. I got it in 2 hours :D

[uthoshantm]

I conducted several interviews from a technical point of view. What I care about is consistency, attention to details, responding to questions in an intelligent way, saying I do not know instead of playing around, previous projects even as an undergrad that shows that the candidate is passionate about the field, details on how he solved a problem in a clever way maybe after a bit of struggling. I hate bulshit, show-off and overconfidence or the other way around excessive timidity, no determination. I do not mind getting a fresh graduate willing to learn and being mentored as long as he sticks around after gaining experience and becoming productive.

Most important part of this question is that it is giving a well known problem in different presentation and expecting you to figure it out. Remaining part is just coding.

[s]

Ok, but it didnt print "hello world"

[AnythingBros]

Please do more coding interview Questions!! Your awesome btw

[ninjanerdstudent]

This is also what they ask their delivery men at the interview to find out which step of porches they will drop off packages.

[Monotoss]

Thank you Dojo, unlike anybody else who just brags and doesn't know how to easily explain the problem, you are truly qualified to make a teaching video. Easy to understand, brilliant man. respect.

[peg]

Bottom up approach (python):
def num_ways(N):
if N == 0:
return 1
elif N == 1:
return 1
step=1
pprev = 1
prev = 1
while step < N:
step+=1
ways = pprev + prev
pprev = prev
prev = ways
return ways

print(num_ways(int(input())))

[jf]

I have never encountered those kind of interview questions in my career. Instead it is more common to give an interviewee a task as a homework, like a mini project, that he can solve at home. This should not take more than 2 to 4 hours of his time. This usually gives a better overview of different skills the interviewee has. E.g. which prog lang, techs and libs he preferred. are there tests written. is he using versioning tools. how is his build chain...
the next interview is then usually based on evaluating the results of the assignment and why the interviewee made the choices, he did.

[tsgv]

I did it in 8 lines of code and felt so proud of myself. The fibonacci sequence didn't cross my mind even after testing the first 20 values of N. Well I guess I've developed a unique way of calculating the fibonacci sequence.

[ljdelight]

Great video! Having the perfect solution isn't possible without knowing different ways to approach a problem, and even rephrasing the problem as you did takes a lot of skill so I give you props. You're a good teacher. But... I wanted to point out things that would cause difficulty if the interviewer is having a bad day and knows a lot about the algorithm asked. 1: Big-oh was skipped, for space and time, so this would be a tough sell. 2: The problem "count the number of ways to go up stairs" given the step types, which is identical to "ways to count change" given denominations, results in a "Wrong Answer" if the step denominations aren't feasible with the steps (example: stepping {3, 5} at a time cannot solve a stair height of 4, but this is not considered). 3: Extended interviewer question because it's fun to wreck the solution: Now provide the steps taken for the solution with the minimum number of movements.

[ochism]

The solution to the easier problem is just the Fbonacci sequence, and therefore be written num_ways(N){return

[sarahb]

Dude, WHERE WERE YOU when I was trying to understand recursion in school? This is the most clear explanation ever. Thank you!

[hihey]

We did this in semester one of CS, on "Fundamentals of programming".
Amazon, here I come

[IlyaGazman]

If you notice that the first part of the question is just Fibonacci numbers then you can approximate the solution with a golden ration in O(1) or provide an exact answer by computing the multiplication of N matrices in O(log(N)), however the last method is a bit trickier as it's performance depends on your multiplication algorithm

[Kyrelel]

Dynamic Programming or, as we used to call it back in the 80's ... Programming.