Amazon Coding Interview Question - Recursive Staircase Problem
Вставка
- Опубліковано 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
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 UA-cam 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
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
*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.
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
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?
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
You taught me a lot CS dojo, I have always been grateful to you. Specially knapsack problem. Hats off
This is also what they ask their delivery men at the interview to find out which step of porches they will drop off packages.
Man, you are so awesome in explaining things, hats off to your patience in creating this! You're better than paid services!
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!😊👍👍👍
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.
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.
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
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?
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..
Dude, WHERE WERE YOU when I was trying to understand recursion in school? This is the most clear explanation ever. Thank you!
Thanks a lot for all the hard work you put in to make these videos. It's really helping me a lot.
Amazing teaching style and love the way you go through the thought process while writing them down so seamlessly. Thanks for creating this content.
You're certainly an industry leader and a genius well done!!
This is still one of the best explanations I have seen online.
Keep solving problems like this. I learn a lot
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.
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.
Best ever explanation for this problem.. Thanks .. Please do more such interview problems.. You are really getting into the depth of it..
Thank you for this video. I was stuck in a similar problem. This helped me!
I remember learning similar problems like this in my discrete math and algorithms class.
Thank you so much sir ! You are great !
Detail level of explanation and optimisation. Very easy to understand . Thanks a lot !
love the way you presented...im totally new to programming and i can easily understand this video...expecting more videos from you..
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.
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.
Congratulations bro on completing 1 successful year on UA-cam. Love from India :)
Can we appreciate this guys , how amazing he is ♥️♥️♥️♥️
Ok, but it didnt print "hello world"
T Fierro lol
XDDDD best comment
Lol lol lol
Ha ha ha
:)
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
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.
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?
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!
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
What a fancy explanation! You made a difficult problem looks like a very easy problem. Thanks a lot
great vid YK. keep the tutorials going
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
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
literally the best explanation on the internet
I am a non programming guy.and I understood this!! You are awesomeee!!!!
Amazon hires a guy to build a scalable rest based web api and he can't do it because they hired a guy that was really good at solving recursion algorithms which ended up only being used in 5% of his job. "Hey since you are a god at computer science theory surely you can pick up full stack development skills instantly".
Guys who can solve this without cheating and checking the solution before the interview, are usualy better. If I have to hire a guy who cannot solve this kind of problems and a guy who can solve, assuming I have the budget, I'll hire the guy who can do it.
What does the guy who solves it off the cuff look like when he can't and has to do research and learn something new? Being good at finding solutions and learning to implement them is a skill. I've met tons of people who don't "know how to Google". I'd take the person who is better at researching, learning, and adapting over the person who knows a solution offhand, because the limit to the one who can learn is endless.
Full stack development is a cake walk compared to advanced algorithm and CS theory. I've never met a person who understands advanced CS topics that can't pick up full stack in a few weeks but I've met plenty of so-called full stack developers that can't understand algorithms and write inefficient code because of it.
Well, it takes time, but these companies hire based on talent and are willing to develop people.
Some companies ask applicants to know Haskell. Some of these companies don't even use Haskell, but they know it's a filter. If you know Haskell, you are more likely a better coder than those who don't.
That doesn't mean you can't be good at coding if you don't know Haskell, just that the probability is inferior. The same way stronger people tend to be above a certain stature and weight, but it doesn't necessarily mean shorter/leaner people can't be stronger. Yes, it has some relation, but not an implication.
ughhh i hate people who do not even know basic data structure... waterfall of loops and ifs...... also they usually do not understand principles such as OOP or FunctionalP as well. they just shove code from stack overflow :P
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
You are amazing man, Thanks for yours videos.
Best explanation. Great job! Thanks for the effort.
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
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
Thank you for the video and all efforts!
Very nice explanation! It took me awhile to understand.
I'm so happy I did it myself. I actually recognised that it is fibonacci series XD
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.
very good description, thanks
Hi csdojo. Very useful video
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?
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
You are doing tremendous job 👏
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())))
Ahhh sooo smart!!! xD it's a fibonacci with a different way.
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.
I love coding and I love your videos
beautifully explained!
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!
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,😃
this is really easy to understand. Thank you
Luv u CS dojo
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]
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.
Interesting problem and pretty good explanation. However, it is not efficient if the number of stairs is large. There is a closed formula for the Fibonacci numbers. It was published by Leonhard Euler in 1765 but seems not to be well known. For details and derivation see the book "Concrete Mathematics" by Graham, et. al.
Using phi = (1+sqrt(5))/2 and phih = (1-sqrt(5))/2 the formula for the nth Fibonacci number F(n) is
F(n) = (phi^n - phih^n)/sqrt(5)
Of course F(n) are all integers so the floating point result must be rounded to the nearest integer.
Very good extended example 👍
I can now recall why I didn't study this.
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.
Great tutorial your explanation was easy to follow.
This concept was the first thing our professor in the programming class thought us in computer science uni
That was actually pretty easy.. how do we figure this out in an interview ?
Nice bro
now i understands how dp works thanx cs dojo
amazing explanation!
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.
Graph theory pliz...make video and trick problem..:)
thank you, it's very clever explaining.
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.
The fact this video has 500k views makes me question whether programming is flooded or not.
I m not a programmer but i am watching this just to see the logic behind it so.
Not a coder just watching out of curiosity.
Just watching for fun
The world has 7 billion people fyi.
Not even close to flooded lol. The demand for engineers outpaces the amount of CS grads by a ratio of like 10:1. In the US at least.
Drake meme:
"Positive integers"
"Natural numbers"
nice one
the way he iterated through so many versions of the function and reached the last one was sick
Thank you so much for this video.
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
14:19:( Solution to the variation of the problem
)
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.
nicely explained
You can drop my package at 0 steps
Hmmm looks oddly familiar to a recursive function I know.... Fibowhat? :]
fibonacci prob.. #cmiiw
Got it in about 10 mins, thanks for the challenge.
Python:
def num_ways(N, n=None, count=None):
n = n or 0
count = count or 0
if n == N:
count += 1
elif n < N:
count = num_ways(N, n+1, count)
count = num_ways(N, n+2, count)
return count
Another obvious optimization is that the list of legal ways is likely to be relatively small. So sort it first. Then, in the inner loop, once i-j < 0, you can break out and not do any more, since the rest are going to be invalid.