Amazon Coding Interview Question – Recursive Staircase Problem



Amazon coding interview question and answer – recursive staircase problem!

For daily coding problems like this one, I’d recommend this website called Daily Coding Problem. You can find it here:
(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
19:17: How to get daily coding problems like this one (go to

Also, keep in touch on Facebook:

Nguồn: https://inst-wd.com/

Xem thêm bài viết khác: https://inst-wd.com/game/

23 Comments

  1. 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.
    You can use this referral link to get a discount, but their free option and blog articles are great, too: https://csdojo.io/daily

    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
    19:17: How to get daily coding problems like this one (go to https://csdojo.io/daily)

  2. Was Fibonacci series created this way

  3. Can we appreciate this guys , how amazing he is ♥️♥️♥️♥️

  4. return func(n-1) + func(n-3) + func(n-5);

  5. The first problem u can solve it python in the net form :
    n = int(input('write the the number of steps:'))

    def num_ways(n):

    if n == 0 or n == 1:

    return 1

    else :

    return num_ways(n-1) + num_ways(n-2)

    print(num_ways(n))

  6. Man, I pay internet cost each month for this kind of content? totally worth it

  7. would be nice if you showed the function in action

  8. Second year CS course discrete math question.

  9. you can make code better if you delete nums which bigger than n.

  10. we can solve the first problem without recursion I guess for example:

    def find_ways(n)
    a,b = 1,1
    len = 0
    while len < n: #n is the given number of steps
    a,b = b,a+b
    len += 1
    return b

  11. I liked your video just after you said, "Hey Everyone" lol

  12. Can you solve the Gas Station Problem ?
    You need to travel from city A to B with minimal cost refueling when needed.

  13. answer is nC1 + nC2 where C is combination term
    implement it value as ( n+n(n-1)/2)
    give him variable
    and call the variable

  14. Why am i watching this at 2:00 AM and trying to understand. I wouldn't understand it at day either

  15. Just imagine if X={1,2,3,5} n=3 will return 4. I feel the final step, if( i – j ) >= 0 is wrong.

  16. misleading logic with the explanations on f(n-1) +f(n-2)

  17. here's my non-recursive (i think) solution to the first problem (Python):
    def num_Ways(N):
    import math
    waysCt = 0
    for i in range(int((N-(N%2))/2)+1):
    onesteps = 2*i + N%2
    twosteps = (N – onesteps)/2
    waysCt += (math.factorial(onesteps+twosteps))/((math.factorial(onesteps))*math.factorial(twosteps))
    return int(waysCt)

  18. 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.

  19. i want to join a coding group , it may be in whatsapp group or else , ; but i dont want to join those group which is by companies or organisation for learning , because mostly people in that group start with "how do i learn to code", but i know coding , just want guys to discuss with ,or maybe share and compete with
    if anyone has any such groups please i want you to get me a invite
    i know C,CPP,java , python , a bit about linux and a gamer , i got my data structures down good

  20. It is my code in python:

    def num_ways(N,X):
    num = 0 # success times
    if N < 0: return -1 # fail
    if N == 0: return 1 # success
    for data in X:
    tmp = num_ways(N-data,X)
    if tmp != -1: num += tmp
    return num;

    What do you think?

Leave a Reply

Your email address will not be published. Required fields are marked *