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)
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 !!!!!
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.
@@_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 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 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.
Dude, WHERE WERE YOU when I was trying to understand recursion in school? This is the most clear explanation ever. Thank you!
6 лет назад+41
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.
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.
"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
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?
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.
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 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.
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.
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.
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
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
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
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!
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.
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
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!😊👍👍👍
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.
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
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?
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.
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.
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!
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(); }
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.
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])
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.
@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.
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.
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.
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]
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
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
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!
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.
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.
The case of steps by one and two, the number of ways is the (n+1)th Fibonacci number. So in that practical case, there is already a mathematical proven way of solving the problem. The algorithmic is approach is quite nice! Kuddos!
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.
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.
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)
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.
Guess I would just add 2 base cases: if n < 0: return 0 if n < 2: return 1 else: return num_ways(n-1) + num_ways(n-3) + num_ways(n-5) Guess this saves you some lines of code and probably makes it a bit easier to follow. At least I think it's easier this way :)
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.
I made it in javascript, so y'all can test it on the navigator. I used memoization to have a better performance. function numWays(n, x = [1,2], memory = {}){ if(memory[n]) return memory[n] if(n < 0) return 0 if(n == 0) return 1 let result = [] for(let i = 0; i < x.length;i++){ result.push(numWays(n-x[i],x, memory)) } return memory[n] = result.reduce((cont, val) => cont += val,0) }
I don’t see why you wouldn’t just realize this is basically just a recursive sequence and use maths to find the closed form solution. Hell, you can even program in a general solution.
I got it after 15 minutos or so. I even stoped eating. Very enjoyable and funny exercise, I failed at doing the table for efficiency tho. But Ive never study recursivity and I was exited about getting the answer that I blinded myself and didnt see that.
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 :)
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
Programming in the 22. century: Coding expert: Hello computer! I need you to calculate the number of ways you can go from the bottom to the top of a staircase. Computer: As you wish, my master. Are there any restrictions? Coding expert: Yes, thank you for asking! It is only possible to take one or two stairs at a time. Computer: I understand master. There are a couple of possible solutions. May I recommend one that is based on recursion? It is most elegant and fast. Coding expert: Yes, let's take this solution. Computer: Excellent choice, my master. Do you need a calculation for a specific number of stairs? Or should I store the algorithm for later usage? Coding expert: The later. Let's call the algorithm... hmm... Computer: May I suggest "num_ways" master? Coding expert: ... yes, "num_ways" sounds good. Computer: As you wish, master. Is there any more I can do for you, master? Coding expert: No, let's take a break. Computer: Absolutely! You deserve it after the hard work, master. Coding expert: Thanks. And... don't call me master, I'm Phill. Computer: As you wish, Phill.
@@Tehcarp Computers of the 22. century can be whatever you want, a slave ... "yes master, hit me, use me like a dirty little toy!" or a dominatrix as well ... "you are a bad bad boy, now you write the staircase code for yourself like the programmer slaves of the 21 century had to, NOW!".
I tried to solve it without recursions, basically like this (including constraint on allowed steps), illustrating with having n=3 and x=[1,2] - Create a list that includes each allowed step, times the total steps, and remove elements that are bigger than n (if there are any) So list = [1,1,1,2,2,2] - Find all subsets of said list So - {1},{1},{1},{2},{2},{2},{1,1},{1,1},{1,2},{1,2},{1,2},{1,1},{1,2},{1,2},{1,2},{1,2},{1,2},{1,2},{2,2},{2,2},{2,2},{1,1,1},{1,1,2},{1,1,2},{1,1,2},{1,1,2},{1,1,2},{1,1,2},{1,2,2},{1,2,2},{1,2,2},{1,1,2},{1,1,2},{1,1,2},{1,2,2},{1,2,2},{1,2,2},{1,2,2},{1,2,2},{1,2,2},{2,2,2},{1,1,1,2},{1,1,1,2},{1,1,1,2},{1,1,2,2},{1,1,2,2},{1,1,2,2},{1,1,2,2},{1,1,2,2},{1,1,2,2},{1,2,2,2},{1,1,2,2},{1,1,2,2},{1,1,2,2},{1,2,2,2},{1,2,2,2},{1,1,1,2,2},{1,1,1,2,2},{1,1,1,2,2},{1,1,2,2,2},{1,1,2,2,2},{1,1,2,2,2},{1,1,1,2,2,2} - Check for each subset if sum = n, and count positive results - the final count is the answer. Not sure if this is more efficient than recursion or not though. Probably less.
The only reasonable answer to an interview question like this is “thanks for your time, keep your job, bye”. Questions like this are not good interview questions for many reasons. They don’t test the experience or knowledge or way of thinking or anything important. They purely test your presentation skills under pressure. Nothing that you put on that whiteboard will let the interviewers know what you will be like at your job.
If it is the only question they ask I agree, if they ask practical programming questions, it is fair game. Practical programming can be learned with effort, but CS fundamentals require a greater effort.
Guvenc Acarkan Your argument would be correct if an interview lasted an infinite amount of time. In other words, by asking the question in this video, you don’t lose any information on the quality of the candidate, so it can’t hurt to ask it. But interviews are short and finite. And there are far better questions to ask of a potential employee that will give you more relevant information on whether or not they will be a good developer. Wasting precious interview time on this question leads me to believe that the interviewer is incompetent because he’s demonstrating that he doesn’t know an efficient way to analyze a potential employee, and therefore I probably don’t want to work at the company.
Of course the Fibonacci case (where you can take 1 or 2 steps) can be done without ANY iteration because the nth term in the Fibonacci sequence can be expressed explicitly as (((1 + sqrt(5))/2)^n - ((1 - sqrt(5))/2)^n)/sqrt(5). This problem can be solved in one line.
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?
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
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
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
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?
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.
Dude, WHERE WERE YOU when I was trying to understand recursion in school? This is the most clear explanation ever. Thank you!
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.
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.
This is also what they ask their delivery men at the interview to find out which step of porches they will drop off packages.
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
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?
*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.
Ok, but it didnt print "hello world"
T Fierro lol
XDDDD best comment
Lol lol lol
Ha ha ha
🤣🤣
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.
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.
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())))
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?
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.
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.
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
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
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
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!
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.
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
I am a non programming guy.and I understood this!! You are awesomeee!!!!
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!😊👍👍👍
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.
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
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
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
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.
Can we appreciate this guys , how amazing he is ♥️♥️♥️♥️
This is still one of the best explanations I have seen online.
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 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.
Yes. The fast matrix power method can reach O(logn) level for that.
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.
literally the best explanation on the internet
I remember learning similar problems like this in my discrete math and algorithms class.
Man, you are so awesome in explaining things, hats off to your patience in creating this! You're better than paid services!
You're certainly an industry leader and a genius well done!!
Detail level of explanation and optimisation. Very easy to understand . Thanks a lot !
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..
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();
}
Man, I pay internet cost each month for this kind of content? totally worth it
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!
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])
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,😃
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
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.
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.
Congratulations bro on completing 1 successful year on RUclips. Love from India :)
It's not for i from 2 upto n, but you have to include n . (for i = 0, i
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]
One of the best questions you can answer and be laid off too.
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
As a software engineer who's been working for over 7 years, this gave me nightmare.
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
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!
Yiwen Xu the interview would be so impressed if you could solve any basic recurrence in O(1) hahah. EZ job
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
This concept was the first thing our professor in the programming class thought us in computer science uni
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.
The case of steps by one and two, the number of ways is the (n+1)th Fibonacci number. So in that practical case, there is already a mathematical proven way of solving the problem. The algorithmic is approach is quite nice! Kuddos!
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.
I don't know a single bit about coding but I somehow understood this.
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
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)
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.
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)
I'm so happy I did it myself. I actually recognised that it is fibonacci series XD
If we take 1 step 'x' times and 2 steps 'y' times then it's always true that
N = x + 2y ,and
0
That was actually pretty easy.. how do we figure this out in an interview ?
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.
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 taught me a lot CS dojo, I have always been grateful to you. Specially knapsack problem. Hats off
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.
Guess I would just add 2 base cases:
if n < 0: return 0
if n < 2: return 1
else:
return num_ways(n-1) + num_ways(n-3) + num_ways(n-5)
Guess this saves you some lines of code and probably makes it a bit easier to follow. At least I think it's easier this way :)
if x = {1,2} then it is simply Fibonacci series :D
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.
14:19:( Solution to the variation of the problem
)
I made it in javascript, so y'all can test it on the navigator. I used memoization to have a better performance.
function numWays(n, x = [1,2], memory = {}){
if(memory[n]) return memory[n]
if(n < 0) return 0
if(n == 0) return 1
let result = []
for(let i = 0; i < x.length;i++){
result.push(numWays(n-x[i],x, memory))
}
return memory[n] = result.reduce((cont, val) => cont += val,0)
}
You can drop my package at 0 steps
Keep solving problems like this. I learn a lot
Thank you so much sir ! You are great !
In simple words
A[0]
I don’t see why you wouldn’t just realize this is basically just a recursive sequence and use maths to find the closed form solution. Hell, you can even program in a general solution.
I got it after 15 minutos or so. I even stoped eating. Very enjoyable and funny exercise, I failed at doing the table for efficiency tho. But Ive never study recursivity and I was exited about getting the answer that I blinded myself and didnt see that.
This is a math problem that can be solved in constant time with permutations.
@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)
Hmmm looks oddly familiar to a recursive function I know.... Fibowhat? :]
fibonacci prob.. #cmiiw
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 :)
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.
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
Programming in the 22. century:
Coding expert: Hello computer! I need you to calculate the number of ways you can go from the bottom to the top of a staircase.
Computer: As you wish, my master. Are there any restrictions?
Coding expert: Yes, thank you for asking! It is only possible to take one or two stairs at a time.
Computer: I understand master. There are a couple of possible solutions. May I recommend one that is based on recursion? It is most elegant and fast.
Coding expert: Yes, let's take this solution.
Computer: Excellent choice, my master. Do you need a calculation for a specific number of stairs? Or should I store the algorithm for later usage?
Coding expert: The later. Let's call the algorithm... hmm...
Computer: May I suggest "num_ways" master?
Coding expert: ... yes, "num_ways" sounds good.
Computer: As you wish, master. Is there any more I can do for you, master?
Coding expert: No, let's take a break.
Computer: Absolutely! You deserve it after the hard work, master.
Coding expert: Thanks. And... don't call me master, I'm Phill.
Computer: As you wish, Phill.
eye bee-sea Phil is a little soy boy bitch. Computers want you to be a man with them
Programming in the 22 century:
Computer: Stop laughing guys that will be fun! Now listen you, stupid fuck. You have a staircase with..
@@Tehcarp Computers of the 22. century can be whatever you want, a slave ... "yes master, hit me, use me like a dirty little toy!" or a dominatrix as well ... "you are a bad bad boy, now you write the staircase code for yourself like the programmer slaves of the 21 century had to, NOW!".
What a fancy explanation! You made a difficult problem looks like a very easy problem. Thanks a lot
I can now recall why I didn't study this.
I tried to solve it without recursions, basically like this (including constraint on allowed steps), illustrating with having n=3 and x=[1,2]
- Create a list that includes each allowed step, times the total steps, and remove elements that are bigger than n (if there are any)
So list = [1,1,1,2,2,2]
- Find all subsets of said list
So - {1},{1},{1},{2},{2},{2},{1,1},{1,1},{1,2},{1,2},{1,2},{1,1},{1,2},{1,2},{1,2},{1,2},{1,2},{1,2},{2,2},{2,2},{2,2},{1,1,1},{1,1,2},{1,1,2},{1,1,2},{1,1,2},{1,1,2},{1,1,2},{1,2,2},{1,2,2},{1,2,2},{1,1,2},{1,1,2},{1,1,2},{1,2,2},{1,2,2},{1,2,2},{1,2,2},{1,2,2},{1,2,2},{2,2,2},{1,1,1,2},{1,1,1,2},{1,1,1,2},{1,1,2,2},{1,1,2,2},{1,1,2,2},{1,1,2,2},{1,1,2,2},{1,1,2,2},{1,2,2,2},{1,1,2,2},{1,1,2,2},{1,1,2,2},{1,2,2,2},{1,2,2,2},{1,1,1,2,2},{1,1,1,2,2},{1,1,1,2,2},{1,1,2,2,2},{1,1,2,2,2},{1,1,2,2,2},{1,1,1,2,2,2}
- Check for each subset if sum = n, and count positive results
- the final count is the answer.
Not sure if this is more efficient than recursion or not though. Probably less.
The only reasonable answer to an interview question like this is “thanks for your time, keep your job, bye”.
Questions like this are not good interview questions for many reasons. They don’t test the experience or knowledge or way of thinking or anything important. They purely test your presentation skills under pressure.
Nothing that you put on that whiteboard will let the interviewers know what you will be like at your job.
If it is the only question they ask I agree, if they ask practical programming questions, it is fair game. Practical programming can be learned with effort, but CS fundamentals require a greater effort.
Guvenc Acarkan Your argument would be correct if an interview lasted an infinite amount of time. In other words, by asking the question in this video, you don’t lose any information on the quality of the candidate, so it can’t hurt to ask it. But interviews are short and finite. And there are far better questions to ask of a potential employee that will give you more relevant information on whether or not they will be a good developer. Wasting precious interview time on this question leads me to believe that the interviewer is incompetent because he’s demonstrating that he doesn’t know an efficient way to analyze a potential employee, and therefore I probably don’t want to work at the company.
Of course the Fibonacci case (where you can take 1 or 2 steps) can be done without ANY iteration because the nth term in the Fibonacci sequence can be expressed explicitly as (((1 + sqrt(5))/2)^n - ((1 - sqrt(5))/2)^n)/sqrt(5). This problem can be solved in one line.