Amazon Coding Interview Question - Recursive Staircase Problem

[@CSDojo]

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)

[@vaibhavaren3217]

very nice video,learnt new things :D Thankyou so much :D :)

[@vaynegod2273]

Once I saw the pattern i realized it was Fibonacci immediately, really cool to see other real world fibonacci patterns, thanks cs dojo! :D

[@mayankagarwal4545]

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

[@rahulpandey6478]

CS Dojo can i contact you

[@kevinjad4506]

CS Dojo will the interview questions b such easy?

[@MrBartolomeo22]

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

[@_VeritasVosLiberabit_]

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 KZbin tutorial or a Stack Overflow post.

[@MuffinMan0521]

+ Nicolas You have no fucking clue what you're talking about.

[@christianjamesguevarra6257]

@@_VeritasVosLiberabit_ moronic sheeple

[@_VeritasVosLiberabit_]

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

[@thespicycabbage]

@@_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

[@codinginflow]

Me: Just take the elevator Amazon: You're hired

[@preddy09]

Yup, hired for the warehouse job

[@codinginflow]

EasilyFallsForClickbait 😂

[@architadesai7876]

What if there's cut off 😂

[@danyeun01]

EasilyFallsForClickbait im pretty sure all of the warehouse work in amazon is handled by robots

[@christianjamesguevarra6257]

@@preddy09 yep but then they whine about people not "thinking outside the box" lol

[@technbyond8144]

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

[@ytg6663]

Why

[@technbyond8144]

@@ytg6663 Because I didn't figure out that was a fibonacci sequence. Once you find out the pattern, it's easy to code.

[@ytg6663]

@@technbyond8144 so, are you placed now ?

[@technbyond8144]

@@ytg6663 Nope 👎

[@ytg6663]

@@technbyond8144 why, what now

[@SeanUnkown]

*Amazon:* Write a function that solves this problem *Me:* Goes to Stack Overflow *Amazon:* You're hired

[@ankitmathur4u]

Is this really true? :)

[@adityapawar4937]

@@ankitmathur4u Nope. Companies like Amazon, Google, Microsoft want their candidates to think and figure out the logic of the problem by themselves.

[@thomasmcbride1645]

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.

[@uthoshantm]

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.

[@hungvunguyen8929]

thank you for giving us some hope!

[@utari90]

i needed to hear this for various reson xD

[@jeyaramt9066]

How to apply for ur company?

[@sarahb8147]

Dude, WHERE WERE YOU when I was trying to understand recursion in school? This is the most clear explanation ever. Thank you!

[@Monotoss]

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.

[@440s]

Ok, but it didnt print "hello world"

[@OrenjiMochi]

T Fierro lol

[@tenshix1649]

XDDDD best comment

[@navarivkapais1943]

Lol lol lol

[@khan2850]

Ha ha ha

[@SriRam-og8fk]

🤣🤣

[@ninjanerdstudent6937]

This is also what they ask their delivery men at the interview to find out which step of porches they will drop off packages.

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.

[@ochism1]

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))}

[@mond2440]

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.

[@mond2440]

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

[@Tips4Tat]

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

[@rousseau327]

This thread is a pretty clear demonstration of theory vs. experience lmao

[@ashirog1622]

Can do with a bit dp+matrix

[@ljdelight]

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.

[@AnythingBros]

Please do more coding interview Questions!! Your awesome btw

[@fleisch1992]

*you're

[@mohmreski46yh32]

Really, do you understand the optimal way in the last minute? Or u just said that bcos u don't understand

[@jeremiahtassinari1743]

"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

[@jeremiahtassinari1743]

@Karan do you know if you'll go to heaven when you die

[@VishalPatel_imvishal]

@@mohmreski46yh32 hahaha was thinking the same. Good point

[@deanroddey2881]

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.

[@Kyrelel]

Dynamic Programming or, as we used to call it back in the 80's ... Programming.

[@reggiefrank]

Actually this technique was originally named dynamic programming, and it's programming means tabular math instead of programming a computer.

[@netbotcl586]

Dynamic programming was invented by Bellman before the invention of the first electronics computer.

[@TheHighborn]

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.

[@IlyaGazman]

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

[@abduallahmustafa1029]

it is fiboonacii series?? brillient way to solve problem...

[@sanjarcode]

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.

[@mhdmart]

@@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?

[@teamkilla4313]

The base case is different. fib(n) is 1 for fib(1) and fib(2), fib(0) is zero

[@baileymorgan9986]

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.

[@ricardofranco7419]

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!

[@mastersabo7751]

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.

[@kylemacarthur9863]

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?

[@abeyjoseph6381]

I am a non programming guy.and I understood this!! You are awesomeee!!!!

[@jf3518]

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.

[@forgotaboutbre]

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

[@ts4gv]

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.

[@raynanwuyep4102]

Its been 2 years but, Can you show me how you did it?

[@shaikzillani6106]

Man, you are so awesome in explaining things, hats off to your patience in creating this! You're better than paid services!

[@DarshanSenTheComposer]

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!😊👍👍👍

[@mfrdbigolin]

I solved both under five minutes, not a hard question; list compressions (available on Python, Haskell and other languages) were used, my recursive solution is below: def solve(n, xs = [1, 2]): if n < 0: return 0 if n == 0: return 1 return sum([solve(n - x, xs) for x in xs]) Turning this into an iterative solution (as shown by the video) should be trivial.

[@hemantupadhyay1554]

Same question was asked to me and in exam, i was trying to remember permutation & combination formulas.

[@harshith3062]

which exam

[@hemantupadhyay1554]

@@harshith3062 one of the IT company written test

[@Amirkolo]

literally the best explanation on the internet

[@hihey229]

We did this in semester one of CS, on "Fundamentals of programming". Amazon, here I come

[@RaitisGrandovskis]

you wold be surprised how many cs mayors have forgoten or never understood this. However, it doesn't mean they are unproductive at work.

[@simaonunes]

This solution is very simple to understand and also does the job with constant space and O(n) time: a = b = res = 1 for i in range(2, n+1): res = a + b a = b b = res return res

[@haval00]

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

[@peg13579]

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())))

[@cbuster7]

I remember learning similar problems like this in my discrete math and algorithms class.

[@DrunkGeko]

This concept was the first thing our professor in the programming class thought us in computer science uni

[@mayankgupta2543]

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.

[@chris7056]

Beast

[@sameerali8293]

Genius!

[@AaronBrand]

Now explain to a novice!

[@qwarlockz8017]

This is still one of the best explanations I have seen online.

[@cepi24]

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

[@sayeedchowdhury11]

Shouldn't the case for going from step 0 to step N directly be added? Or that direct jump isn't allowed?

[@antonyndungu5514]

You're certainly an industry leader and a genius well done!!

[@GRLDT]

Isn't this a coin change problem? Instead of counting how many possible ways to form a nominal from the coins, but it's counting how many possible ways to get up the stairs from how may steps we can take, right?

[@alirezabeitari2821]

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!

[@ujjvalkapoor6067]

For that question you can refer to geeksforgeeks article..

[@tung6796]

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

[@jayanthsai400]

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]

[@ilanaizelman3993]

It's not for i from 2 upto n, but you have to include n . (for i = 0, i

[@kitko2652]

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.

[@nndd8585]

Nope.. it does return 0.

[@antonyvilson8973]

You taught me a lot CS dojo, I have always been grateful to you. Specially knapsack problem. Hats off

[@pilpelbarkan]

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.

[@TngMutantNinjaTroll]

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.

[@ShanmugamChinnappaiyan]

Detail level of explanation and optimisation. Very easy to understand . Thanks a lot !

[@Shubham_Singh_India]

Congratulations bro on completing 1 successful year on KZbin. Love from India :)

[@anime23973]

A naive solution will be O(n^(size of X)) - with X containing the possible steps like ur {1,3,5} what will be the complexity with the DP solution ?

[@dibyankamahto6238]

Amazing teaching style and love the way you go through the thought process while writing them down so seamlessly. Thanks for creating this content.

[@alexandrucosminvlad9338]

Maybe I'm missing something, but in case of num_ways_X_bottom_up(n), if i is 2 and j is 3, wouldn't that result in an evaluation of the if statement in the second for loop to be -1, and therefore it will break the algorithm? So for example, if you pass an argument of n set to 3, it will go through first loop, and while reaching i = 2, it will always fail in the second loop while evaluating 2 - 3 = -1, even though n = 3. In the initial num_ways_X(n) that would not represent an issue, as the if statement checks against a fix value for n while subtracting i, whereas in bottom-up method the i is going from 1 to n.

[@india1727]

My youtube search says " Horror Movies 2019 " but somehow I landed over here watching algorithms ... sigh.

[@tongwu8467]

They are the same thing.

[@zhkq]

I hope I'm not too late but don't watch vvitch or hereditary, they're overrated

[@anildusarlapudi8476]

When n=3, why can't [3,0] is another way to reach top?

[@starquake7061]

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.

[@CSDojo]

Not yet. I'll put it in my list :)

[@ThePhoenix107]

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

[@NicolaiRathjen]

Read CLRS.

[@Rupi_Kat]

Yes please!!!

[@Rupi_Kat]

Nicolai Rathjen will look into it. Thanks,😃

[@tylersanders2388]

I thought most major tech companies were looking for people who could solve these things in O(logn) time so I looked at this problem for an extremely long time before giving up. Your runtime is like O(n*x) which is a more reasonable time.

[@ziqichen5902]

Yes. The fast matrix power method can reach O(logn) level for that.

[@Arkngthunchsturdumz]

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.

[@MrHenryG123]

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.

[@user-account-not-found]

One of the best questions you can answer and be laid off too.

[@pietart3596]

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?

[@BruinChang]

The reverse labeling is not straightforward to me. How can we quickly find new ways to sort the data in algorithm problems? Thanks a lot.

[@qwarlockz8017]

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.

[@usenthilsmail2007]

I was thinking about a Tree with depth traversing.. tree root at zero, has children 1,3,5 in this example. Tree depth can be ((total-no-of-steps / smallest step possible)+1). Then start traversing in unique paths, keep adding the value to the sum till you reach sum == total-no-of-steps. if you happen to cross total-no-of-steps then discard that tree path.

[@uberkarthik]

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.

[@habibullah-ki7ok]

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)

[@ABaumstumpf]

Coding that is a bit simpler - but SOLVING for a given number would take reeaaaallly long times once you increase the size of N.

[@danhorus]

I'm late to the party, but I'm proud of this solution: ideone.com/DYVO3g

[@paoloesquivel7430]

Wouldn't it be nice to also pre-check whether the generalized problem is even soluble for a given pair (n, x)? For instance, trying to get to the top of a 5,000,000-step staircase (n=5e6) is impossible if your only allowed move is to climb by x=[4,999,999] steps at a time. May save a lot of time and heartbreak. Pre-checking seems like it would require an O(len(x)) algorithm that just checks whether, for any x_i in x, n modulus x_i == 0.

[@beatalert123]

That was actually pretty easy.. how do we figure this out in an interview ?

[@girishbalaji8058]

Classic pattern of fibonacci numbers - just that it starts off with 1,2,3,5,8...etc. Hence, num_ways(n) = num_ways(n-2)+num+ways(n-1)

[@GurdeepSabarwal]

14:19:( Solution to the variation of the problem )

[@machavaramakhil6656]

@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)

[@arkprince9413]

i felt lost after first 5 mins

[@mryup6100]

Same, I understood after watching the video three times. It takes time understanding these new concepts.

[@brondchux]

I'm still feeling lost, pls call 911

[@mohsendp]

My one liner solution in Javascript. You can give it a try in your browser's console: var sumWays = (n, steps, pos=0) => steps.reduce((acc, step) => acc + (pos + step > n ? 0 : pos + step === n ? 1 : sumWays(n, steps, pos + step)), 0) sumWays(4, [1,2,3])

[@tayern3927]

how long do they give you to solve this question in an interview?

[@belina65]

35 seconds

[@lakshmitelukunta]

When N=3, why there is no path directly from 0 to 3, similarly when N=4, why there is no path from 0 to 4, and 0, 3, 4. Can someone please explain this one to me.

[@workonline8831]

Awesome. I have a doubt at 3:50, case n=3. Does the case [0,3] possible??

[@JaySiggz]

He didn't explain the problem properly, you can only take at most 2 steps.

[@YourComicc]

yes he did not mention that you can take at most 2 steps at a time

[@8ballpoollivestream369]

he mentioned either you can take a single or a double (2 steps)

[@jesperat]

If we are looking for all possible combination to go up, aren't we missing in n=4: [0,3,4],[0,1,4], etc?

[@aashay1709]

I'm so happy I did it myself. I actually recognised that it is fibonacci series XD

[@CTT36544]

Method 1: dynamic programming (a very "CS" way); Method 2: generating function (a "combinatorics" way). Use the first method if your math knowledge (in combinatorics) is so-so; use the 2nd method if you know some basic combinatorics and want to make your life easier!

[@ASager30]

Yiwen Xu the interview would be so impressed if you could solve any basic recurrence in O(1) hahah. EZ job

[@all88899]

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

[@cagriypr115]

I don't know a single bit about coding but I somehow understood this.

[@nahianalhasan5151]

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!

[@therishabhdhiman]

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.

[@poon1104]

I only watched the problem description part and did the problem honestly. I knew right away the first solution is similar to recursive fib. DP for optimization in fib problem is a common notion anyway. The generalization of X took me several minutes to figure out. The key idea is not all combination has a solution. For example, if X = {3}, then N=1,2,5,7... will have 0 solution.

[@moshiurrahmanmoshi]

if x = {1,2} then it is simply Fibonacci series :D

[@mahipalpurohit3387]

If we take 1 step 'x' times and 2 steps 'y' times then it's always true that N = x + 2y ,and 0

[@cskcsk6370]

W.r.t this video, the author has done a good job of explaining the problem and solution approach. In general, though little off topic, rather than just teaching procedural programming, we should try to teach and evaluate on design and OOP concepts too. I would rate a person much higher, if the person starts by first defining a "StairCase" class, even if it just contains only one method to find ways to climb stairs. That would give me a better picture about the candidate. I would trust that person to build much more critical pieces of functionality.

[@modusponens1094]

There's usually one more step, which is to work out the closed-form solution using the golden mean for the number of paths, making the dynamic program entirely unnecessary (for the Fibonacci sequence, it's on the Wikipedia page). Similar forms are possible for other linear recurrences. Hard to beat an O(1) solution. Math FTW.

[@MuffinMan0521]

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

[@emmanueloverrated]

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.

[@PabloEdvardo]

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.

[@dilutedexcitement]

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.

[@a-j.2002]

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.

[@jeanmuyuela8112]

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

[@latifk9999]

I found a solution that's kinda overkill. For N steps, the answer is: (N choose 0) + (N - 1 choose 1) + (N -2 choose 2) + .. + ( Ceil(N/2) choose Floor(N/2) ). So for example, N = 6, we have: ( 6 choose 0 ) + ( 5 choose 1 ) + ( 4 choose 2) + ( 3 choose 3) ( 1 ) + ( 5 ) + ( 6 ) + ( 1 ) = 13 You could also use the closed form expression for the Fibonacci sequence. Possible combinations for N steps is basically the Nth Fibonacci number. That was a fun problem :)

[@SurajSingh-tz1wr]

Hello CS DOJO!!! I am an engineering student(IT) and I will be in my final year from next month. I want to be a software developer And believe me I love writing code.Your videos has helped me a lot and I am now 100% focused on my coding study on my own. However I am facing a problem regarding to data connectivity of forms using phpmyadmin. Even my lots of friends are feeling the same way. So please if it's possible Can u make a video regarding data connectivity using phpmyadmin in detail? It would be a great help from u. If it's possible so plzzz do reply. 😃

[@rohan0103]

3 years after this comment, how are you doing?

[@nickyetti93]

@@rohan0103 im curious too lol. Im in my first yr currently and skipped classes today to learn recursion , been up from 5:15 amnd now I'm here.

[@DinnerIsDelayed]

The way I got is was to divide the number of stairs by “jumps”. What ever the whole number was is the number of ways. FOE EXAMPLE {1,3,5} Num of stairs =9. ALL 1’s count as 1 way, 9/3 =3 ways , 9/5 = 1 way, AND If 1 +3+5 = 9 then that = 1 way (it does in this case)

[@dressr3270]

I can now recall why I didn't study this.

[@naveenkr5992]

Hey sir I believe you sees this. I watched the video you uploaded on may 26th 2018. At timestamp 4:00 you are a bit mistaken I believe. Actually theres 4 ways to get from 0 to 3. { [0,1,2,3] , [0,1,3] , [0,2,3] , [0,3] }

[@vishalchauhan9832]

Thank you so much sir ! You are great !

[@maximgoncharov551]

I didn't see the whole video and the solution, but for me it was interesting to solve this problem. In java it can be done with one line of code: private static int numWays(int numSteps, int...hops){ return Arrays.stream(hops) .filter(hop -> hop hop == numSteps ? 1 : numWays(numSteps - hop, hops)) .sum(); }

[@TheZiZaZo]

Hmmm looks oddly familiar to a recursive function I know.... Fibowhat? :]

[@ryannathaniel8060]

fibonacci prob.. #cmiiw

[@bbekg]

I didn't understand the problem with variation. When there was no variation, in code we had "if(n==0 || n==1) return 1;" but when variation we have only "if(n==0) return 1". So, Why not return 1 when n==1? Somebody please help me.

[@shubharora2172]

You can drop my package at 0 steps

[@ferri12321]

I think you shoud check if the position in the array is empty at the same time that you check if n-i is greater than 0, because not always you will have a 1 in the array and you may have cases where there is no way to reach a certain stair. i.e. {2,5} your code will break at i = 6 trying to access a non existing element of the array