Amazon Coding Interview Question - Recursive Staircase Problem
HTML-код
- Опубликовано: 24 май 2018
- 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: csdojo.io/daily
(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 csdojo.io/daily)
Also, keep in touch on Facebook: / entercsdojo
![*SUPER RARE* THE PARADIGM IS BACK?!?!? Fortnite Item Shop [August 6th, 2024] (Fortnite Chapter 5)](http://i.ytimg.com/vi/ru6xSH1RaPw/mqdefault.jpg)
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: 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 csdojo.io/daily)
very nice video,learnt new things :D
Thankyou so much :D :)
Once I saw the pattern i realized it was Fibonacci immediately, really cool to see other real world fibonacci patterns, thanks cs dojo! :D
dailycodingproblem.com is just gonna send one problem-solution every morning. Which means around 30 questions /month or 366 questions/year for which they are asking a fee of around $8/month or $80/year (considering your 10% discount) which is around 5400 INR/year . How on earth does that even makes sense. Who is gonna pay that amount for just one question daily !!!!!
CS Dojo can i contact you
CS Dojo will the interview questions b such easy?
Me: Just take the elevator
Amazon: You're hired
Yup, hired for the warehouse job
EasilyFallsForClickbait 😂
What if there's cut off 😂
EasilyFallsForClickbait im pretty sure all of the warehouse work in amazon is handled by robots
@@preddy09 yep but then they whine about people not "thinking outside the box" lol
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
With algorithmic questions they can evaluate how good is your logic and your programming logic (these are different). These things are the most important when you're building a software, if you don't have good logic and programming logic you could find a lot of obstacles when solving a problem (which means time lost = money lost), and if you get it solved your software could have a lot of bugs, couldn't run for all the cases, and its efficiency could be wicked (which means hardware badly used = more money lost), that's why it's important to improve your logic and your programming logic, the only way to do this is practicing. Finally, your logic and your programming logic are more important that your knowledge in using frameworks, libraries, etc... Even a child can learn how to use a framework or a library watching a RUclips tutorial or a Stack Overflow post.
+ Nicolas
You have no fucking clue what you're talking about.
@@_VeritasVosLiberabit_ moronic sheeple
@MuffinMan0521 If I have not clue of what I'm talking about, then why do not you enlighten me? Get away with your comments without arguments.
@@_VeritasVosLiberabit_ Your logic seems to be very high level. These so called special frameworks/libraries you mention can be very powerful tools that have a lot of capabilities that companies expect their employees to know as hired software developers/engineers. IE React
*Amazon:* Write a function that solves this problem
*Me:* Goes to Stack Overflow
*Amazon:* You're hired
Is this really true? :)
@@ankitmathur4u Nope. Companies like Amazon, Google, Microsoft want their candidates to think and figure out the logic of the problem by themselves.
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
Why
@@ytg6663 Because I didn't figure out that was a fibonacci sequence. Once you find out the pattern, it's easy to code.
@@technbyond8144 so, are you placed now ?
@@ytg6663 Nope 👎
@@technbyond8144 why, what now
Ok, but it didnt print "hello world"
T Fierro lol
XDDDD best comment
Lol lol lol
Ha ha ha
🤣🤣
Thanks to your DP explanation something finally clicked in my head and I understand the "Making change with coins" problem as well! The two are practically identical
Wow, I really like your approach. I didn't know that if an algorithm works backwards, it might become efficient! This blew my mind. Thanks for the post!😊👍👍👍
Great video. You are amazing. I love the hard coding questions that hint at how they make sure they maintain the quality minds that are part of the real secret sauce driving their success and phenomenal growth! I cannot even imagine the difficulty level of their questions about some of the intricacies of tax avoidanceand wage to work ratios! Anyone seen these?
Please do more coding interview Questions!! Your awesome btw
*you're
Really, do you understand the optimal way in the last minute? Or u just said that bcos u don't understand
"For God so loved the world, that he gave his only begotten Son, that whosoever believeth in him should not perish, but have everlasting life." John 3:16
Only Jesus Christ is the way to Heaven and be saved from hell.
"But God commendeth his love toward us, in that, while we were yet sinners, Christ died for us."
Romans 5:8
"Jesus saith unto him, I am the way, the truth, and the life: no man cometh unto the Father, but by me." John 14:6
Have you believed in your heart that Jesus Christ died on the cross for your sins, was buried, and rose from the grave? You must believe that Jesus is the one who paid for your sins and rose again to be saved from eternal damnation and instead go to heaven
"That if thou shalt confess with thy mouth the Lord Jesus, and shalt believe in thine heart that God hath raised him from the dead, thou shalt be saved." Romans 10:9
"For there are three that bear record in heaven, the Father, the Word, and the Holy Ghost: and these three are one." 1 John 5:7
@Karan do you know if you'll go to heaven when you die
@@mohmreski46yh32 hahaha was thinking the same. Good point
You taught me a lot CS dojo, I have always been grateful to you. Specially knapsack problem. Hats off
Man, you are so awesome in explaining things, hats off to your patience in creating this! You're better than paid services!
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.
thank you for giving us some hope!
i needed to hear this for various reson xD
How to apply for ur company?
This is also what they ask their delivery men at the interview to find out which step of porches they will drop off packages.
This was actually a very well done explanation, thank you. Had not seen the bottom up approaches before.
love this channel. Will spend my time reading these valuable tutorials
Again, a perfect video. Thank you so much for making this helpful videos.
Please make a video about "Largest Rectangular Area in a Histogram" problem! Thanks!
For that question you can refer to geeksforgeeks article..
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.
Thanks a lot for all the hard work you put in to make these videos. It's really helping me a lot.
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.
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.
Thank you so much sir ! You are great !
Best ever explanation for this problem.. Thanks .. Please do more such interview problems.. You are really getting into the depth of it..
Dude, WHERE WERE YOU when I was trying to understand recursion in school? This is the most clear explanation ever. Thank you!
Amazing teaching style and love the way you go through the thought process while writing them down so seamlessly. Thanks for creating this content.
I remember learning similar problems like this in my discrete math and algorithms class.
Thank you for this video. I was stuck in a similar problem. This helped me!
love the way you presented...im totally new to programming and i can easily understand this video...expecting more videos from you..
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
You're certainly an industry leader and a genius well done!!
This is still one of the best explanations I have seen online.
Detail level of explanation and optimisation. Very easy to understand . Thanks a lot !
it is fiboonacii series??
brillient way to solve problem...
It is coincidentally fibonacci, i.e only in the case when allowed steps are 1 and 2. Because f(n) = 1*f(n-1) + 1*f(n-2) = f(n-1) + f(n-2) which happens to be fibonacci. For any other value(s). It is not fibonacci. e.g {1,3,5} steps allowed. f(n) = f(n-1) + f(n-3) + f(n-5). Yes this can be called custom(number of values and the values) fibonacci.
@@sanjarcode I guess you're saying that if we're allowed to take k1, k2, .. kn steps, then the solution is f(n-k1) + f(n-k2) +.... + f(n-kn).. Why do you think that's true?
The base case is different. fib(n) is 1 for fib(1) and fib(2), fib(0) is zero
Can we appreciate this guys , how amazing he is ♥️♥️♥️♥️
Keep solving problems like this. I learn a lot
you are too good.
I'm new in your channel and I see I'll learn all principles of programming from you.
keep posting. I want to be a good programmer.
We did this in semester one of CS, on "Fundamentals of programming".
Amazon, here I come
you wold be surprised how many cs mayors have forgoten or never understood this. However, it doesn't mean they are unproductive at work.
Congratulations bro on completing 1 successful year on RUclips. Love from India :)
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.
ur channel like heaven for me ... i studting software engennering i u help me a lot for some challage with this problem like gymnastics
... God bless u from tunisia
Labeling the steps the way you did makes the problems incredibly easy! My first approach was a combinatorics one: given N steps and a set of rules--the number of steps you can take at at time, how many different ways can you make the sum of N. The way you labeled the steps, I went ahead and made a tree and was able to derive a recursive formula (forgive me, I'm a mathematician), which I then implemented into quite simple code. Thank you for the practice problem! I have the coding test tomorrow!
Dynamic Programming or, as we used to call it back in the 80's ... Programming.
Actually this technique was originally named dynamic programming, and it's programming means tabular math instead of programming a computer.
Dynamic programming was invented by Bellman before the invention of the first electronics computer.
Oh boy did I fucking hate dynamic programming in a class. They explained it bad, and didn't really show useful cases when one would need it. Turns out, it's pretty good.
PS: fuck that teacher in particular.
great vid YK. keep the tutorials going
You are amazing man, Thanks for yours videos.
The solution to the easier problem is just the Fbonacci sequence, and therefore be written num_ways(N){return floor(((1/sqrt(5))(1+sqrt(5))/2)^n))}
Alex Vitkov this way cost constant time. Also There’s another way to compute the fibonacci number without dealing with floating point in constant time.
@Alex Vitkov ah yeah, my bad. But sill the best case is log(n) time for computing the n-th fibonacci number because the question is a special case where there's only 2 ways to jump.
Well I wrote a function to do this, but something seems off about these solutions.
His solution at 13:26 does seem to account for just walking up 5 steps 1 by 1
This thread is a pretty clear demonstration of theory vs. experience lmao
Can do with a bit dp+matrix
Hey Joseph! Awesome tutorial here! Isn't the variation problem Bottom Up Approach a space efficient way of the first bottom up approach without the X = {1,3,5} constraints?
Very nice explanation! It took me awhile to understand.
Thank you for the video and all efforts!
Same question was asked to me and in exam, i was trying to remember permutation & combination formulas.
which exam
@@harshith3062 one of the IT company written test
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.
Its been 2 years but, Can you show me how you did it?
beautifully explained!
Best explanation. Great job! Thanks for the effort.
Thanks for the great presentation. I watched this a while ago and was mystified. I did a lot of reading and watched again and it was very clear and a great presentation. Thanks. It would be great if you could put your code on github. I love watching the videos but I learn a lot by transcription. Doing that FROM a vid sort of sucks.
It is simply amazing how you can explain algorithm problem + recursion + dynamic programming + complexity to one wideo which 10 years old can understand. Please make more. Subscribed
What a fancy explanation! You made a difficult problem looks like a very easy problem. Thanks a lot
@CS Dojo I think we can even break the inner "for" loop if the condition (i-j)>=0 fails so it reduces checking other values in X(In the last problem)
Hi @CS Dojo, I really love your interactive videos!
I've got a question regarding a similar problem. Say instead of stairs, we had coins. C is the amount of money we need, and V is a set of coins which have positive integer values, e.g. V = {1, 3, 5}. Using your solution (which I thought of as well when I first encountered this problem), we could effectively calculate the number of ways to reach C, i.e. the permutations. What would be the DP solution if we wanted the combination of coins instead? Would really love your input or anyone else's input on this. Thanks!
This is exactly what i thought that n should be the sum and we should compute that sum from the given numbers in n possible ways.
I'm so happy I did it myself. I actually recognised that it is fibonacci series XD
Great tutorial your explanation was easy to follow.
Luv u CS dojo
Have you ever made a video about Developing solving problem skills? If you haven't, could you make it? How to practice it, best books to read about it, best resources.
Not yet. I'll put it in my list :)
@JuxChannel
Wow That is some motivation.
Of course you can learn problem solving. You can learn how to approach things and see key elements you have to look for. You can always improve on that and learn new tricks you can use for different problems.
Read CLRS.
Yes please!!!
Nicolai Rathjen will look into it. Thanks,😃
i felt lost after first 5 mins
Same, I understood after watching the video three times. It takes time understanding these new concepts.
I'm still feeling lost, pls call 911
I am a non programming guy.and I understood this!! You are awesomeee!!!!
I have a question:
Wouldn't the *space used to store the return address for function calls in a recursion* outweigh the space used to simply *store the array of integers*?
In this case, wouldnt' the array of integers and no recursion be more efficient in all cases?
That was actually pretty easy.. how do we figure this out in an interview ?
My youtube search says " Horror Movies 2019 " but somehow I landed over here watching algorithms ... sigh.
They are the same thing.
I hope I'm not too late but don't watch vvitch or hereditary, they're overrated
You are doing tremendous job 👏
this is really easy to understand. Thank you
Seems some edge cases wasn't handled well, e.g. N = 4, X={3}, we should expect 0 way will be returned, but it returned 1 way from the above solution.
Nope.. it does return 0.
Ahhh sooo smart!!! xD it's a fibonacci with a different way.
Hi csdojo. Very useful video
literally the best explanation on the internet
The function num_ways_X_bottom_up is memory inefficient for very large n's.
You could instead use a queue to store only the most recent values necessary (or an int array and shift it on every iteration):
[1,3,5] means you only need a queue of 5 numbers, not n.
And generalizing this, the queue size should be (Largest element) - (Smallest element) + 1
The concept is the same as what you showed in the first variation of the problem, when you stored only the last two numbers instead of the entire series.
Indeed. I did a variation of a shifting list from the get go, not really in an effort to save memory, it just seemed like an easier way to code step patterns I worked out on 'paper' beforehand. len() of the new list is the largest value integer in X list, values with indexes corresponding to steps in X are added up and appended to it, followed by a removal of the lowest value first element. Final result is simply the last element in that list after n iterations.
14:19:( Solution to the variation of the problem
)
amazing explanation!
thank you, it's very clever explaining.
how long do they give you to solve this question in an interview?
35 seconds
Awesome. I have a doubt at 3:50, case n=3. Does the case [0,3] possible??
He didn't explain the problem properly, you can only take at most 2 steps.
yes he did not mention that you can take at most 2 steps at a time
he mentioned either you can take a single or a double (2 steps)
I love coding and I love your videos
thanks for the video, I had not found a comment in the comment section that states there is a bug in your code, for the X set of possible jumps (I confess I did not look through too many comments :))
The bug is that you assume that all steps are reachable to begin with and that is true if you assume that 1 is always part of the set X, but in the general case, where X can be any int array (not containing 1 for example) you need to skip those unreachable steps in the for loop, you can either do that with another reachable bool array (that you init only the first step with true) or init your nums array to -1 to all the values apart from nums[0] and in the for loop verify the value you are about to update is not negative.
Hmmm looks oddly familiar to a recursive function I know.... Fibowhat? :]
fibonacci prob.. #cmiiw
You missed the most important part, that is proving that your hypothesis is correct (i.e. that f(n)=f(n-1)+f(n-2) is the solution to the problem). It's just not enough to try out a few sample cases and derive the solution from those, because there could be cases where the solution you think is correct actually is not.
If the set of allowed steps is {1,2} then by definition, the number of ways to get to step n, or f(n), *must* be the sum of f(n-1) and f(n-2), since you can only transition to the f(n) state if you were previously at f(n-1) or f(n-2).
This combined with the base case f(1) = 1 and f(2) = 2 will solve for any n from a bottom up DP approach.
very good description, thanks
Thank you so much for this video.
A small modification for above bottom-up approach which solves all the edge cases (in Python):
def recursive_staircase(n, jumps):
ways = [0] * (n + 1)
ways[0] = 1
jumps.sort()
# you can comment this line if the given jumps were in sorted order
for i in range(1, n + 1):
tot = 0
for j in jumps:
if i - j >= 0:
tot += ways[i - j]
else:
# By keeping break, we can deduce many iterations if once larger j has hit than i
break
ways[i] = tot
return ways[n]
Drake meme:
"Positive integers"
"Natural numbers"
nice one
Very good extended example 👍
nicely explained
Graph theory pliz...make video and trick problem..:)
Nice bro
Super Explanation!!!
This concept was the first thing our professor in the programming class thought us in computer science uni
Hi @cs dojo, i just want to say i've been watching your videos for a while now and i like it; you seem a very skilked coder, but i'm curious has no one ever approached you to be his technical partner in a startup, and if someone does what will your answer be??
Thanks a lot. Sometimes they do, but my answer would be no. I'm just 100% focused on CS Dojo right now :)
CS Dojo well.. Good luck!! 👍🏻👊🏻✌🏻️
We can do this in prolog with a naive implementation that checks all possible permutations of 1 and 2 that add up to the total number of stairs, then returns the total number of those results. It is a lot simpler that way. Takes less time than this to solve.
uberkarthik Bro, i thought the same, you just need to know how many positive solutions has an equation type ax+by+cz=d (in case of N=3)
Coding that is a bit simpler - but SOLVING for a given number would take reeaaaallly long times once you increase the size of N.
I'm late to the party, but I'm proud of this solution: ideone.com/DYVO3g
It's not for i from 2 upto n, but you have to include n . (for i = 0, i
Love the video! It inspired me to make my own channel! I Do website development tutorials and web app tutorials! I really enjoyed the video. It taught me a lot, I aspire to one day help someone with development like you!
Before looking at the solution:
Here is my solution:
A tree where number of children a node can have is the number of possible steps a person can take
A stack with total number of stairs n.
Beast
Genius!
Now explain to a novice!
7:47 my mind stop functioning after this
Easy combinatorial way to think about it, either your last step is a single or double step. In the case it is a single step then you have num_steps[n-1], and for a double you have num_steps[n-2]. Once you see that just write a memoized version of the fibonacci sequence.
Just awesome..Love your videos.