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/

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)

Was Fibonacci series created this way

Easy DP problem

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

return func(n-1) + func(n-3) + func(n-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))

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

Recursive

would be nice if you showed the function in action

Second year CS course discrete math question.

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

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

I sir

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

Can you solve the Gas Station Problem ?

You need to travel from city A to B with minimal cost refueling when needed.

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

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

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

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

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)

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.

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

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?