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
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/

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
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. Easy DP problem

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

5. Alexander Bourne

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

6. 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))

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

8. mohammed hassan ali

Recursive

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

10. Second year CS course discrete math question.

11. Danyshman Azamatov

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

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

13. bepali lakshminarayana

I sir

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

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

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

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

18. Uresh Dassanayake

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

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

20. 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)

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

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

23. 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?