Python Coding Interview Preparation - For Beginners

Key Takeaways

hello everybody and welcome back so in this video I'm going to be kind of continuing an ongoing series where I solve some programming problems and do some coding interview preparation now for any of you that don't know if you're going to try to get a job at any high tech company maybe Google Facebook any kind of the name-brand companies then you're going to have to pass a coding interview and they're notoriously difficult personally I don't feel as though I am even ready to go for the coding interviews so I've been practicing on a platform called algo expert now this is a paid platform and what I'm gonna do in this video is go through some of the free questions with you guys to give you an idea of how this platform works why I personally use this platform I've been using it for about two months now and if you guys are interested in purchasing this and actually using this there is a discount code in the description full kind of transparency here if you do buy this I will make money from this it's like I think I make like 25 bucks or something for every time someone purchases this so I'm being transparent with you guys but personally I've been using this for two months I highly recommend it and I think it's 80 let's see how much it is it's 85 dollars so I mean if you guys really are trying to get into a high tech company you just want to practice your coding skills I can tell you this is one of the best ways to do it and I know I messed with a ton of different websites before personally this is my favorite and has a ton of stuff on here like interview tips where you can actually watch videos of this guy who will give you you know some interview tips tell you what it is you need to do to really land the job and then data structures apparently is coming soon anyways they've been adding a bunch of stuff to this since I've been using it but today what we're gonna do is solve the nth Fibonacci problem so I'm gonna click on this one it's a free problem I'm not even signed in to my account here and we're gonna go through and solve it I'm gonna talk about my solution notice that this was one of the easier questions so I would recommend you guys try to solve this first you can either do this on the website just by hitting the link this is a free question again so you don't have to pay for it to do it and you guys will see how to go through this kind of how the website works and how everything operates alright so what is the problem we're gonna solve well the Fibonacci sequence is defined as follows the first number in the sequence is 0 the second number is 1 and the nth number is the sum of n minus 1 and n minus 2 numbers write a function that takes in an integer n and returns the nth Fibonacci number ok so here's an example so for any of you that don't understand kind of how this works the sequence goes essentially like this you have 1 1 are they your first or sorry zero-one-one those are your first three numbers in the sequence where that's one that's two that's three I believe then you have two and what how you get two is you add the previous two numbers then you get what is it three because you added two and one and then you get five and then you would get eight and you can see that we're kind of exponentially increasing upwards so essentially it's asking us to find a solution I'll zoom in on this you guys can actually read my code to this problem you guys can see there's actually some hints here I don't want to read them because I'm gonna try to do it without the hints but if you're stuck you can use those you can save your answer by hitting this thing and then you can actually just test it by hitting run code and it will tell you if you failed or passed these test cases and then down here is actually an explanation of how to do this we're not gonna watch that because I'm gonna explain it to you guys but for all these questions there is explanations so let's go ahead and get started so this is actually a recursive problem now we don't necessarily need to do this using recursion but we are going to I'm gonna do the trivial solution first and then I'm gonna show you a better way of solving this that runs in a faster time so essentially whenever we're solving something recursive what we need to do is determine our base case and then our other case now we could have more than one base case but essentially what a base case is is a solution that we know the answer to so when we call nth Fibonacci on this number like five we don't actually know the answer to five but we don't know what the fifth number in the sequence is what we do know though is what the first second and third number in the sequence are they're these numbers right 0 1 1 so what we can do is simply write in this Fibonacci thing what we know to start so in this case if n is less than or equal to 3 actually sorry if n equals equals 1 return 0 if n equals equals my guess is less than or equal to 3 return 1 because we know that that's the number in the sequence now how do we calculate it if it's not one of these two values well this is where we get into the recursive part what we need to do essentially is calculate the previous value and the previous value before that and add them together well the logical way to do this is to return the get end Fibonacci of n minus 1 plus you get and Fibonacci of n minus 2 now you might be like well how is this gonna work if we don't know what these values are well essentially what's gonna happen is when we call this return statement we will call the function get nth Fibonacci and look for an answer from it now if it doesn't know any of these answers well it's gonna go back again and try to find the answer to whatever that sequence is that we call it so if we call with four well obviously that's not here then what's gonna happen is it's gonna return three plus two so get nth Fibonacci of 3 plus two obviously we know the answer of three and we know the answer of two which is 1 which is gonna return to a then 2 which would be the correct answer now if we're gonna call 3 what would happen here actually I'm gonna get my drawing tablet out to do a little illustration but then I'll show you how this works ok so I've got my drawing tablet out here now and I just want to explain to you how this code works before I actually run it and show you really how this works and you can see obviously here this is highlighted green I just tested to make sure I wasn't misleading you guys but I was fairly confident in that answer so I just won't explain how this little piece of code can actually generate this sequence that we're talking about here now essentially the way that this works is just using very basic recursive principle now hopefully you guys know about recursion but if you don't I'm gonna kind of explain what that means but essentially recursion is just calling the same function within that function so if I ever make a call in here that calls the function that like we're making the call from that's known as a recursive call which is exactly what we've done here so essentially I'm just gonna draw kind of the stack or like the trace of what this is gonna look like so let's say we call an Fibonacci of 4 so we'll just call it we'll just say like we want to calculate the value for from ends Fibonacci well is 4 equal to 1 no is 4 equal to 3 or less than 3 no it's not so what do we do we return this recursive sequence now what is this recursive sequence actually going to give to us how does this work well we need to start by evaluating this so we need to get the nth Fibonacci number of n minus 1 now well what is that well n minus 1 is obviously gonna be 3 so we can write 3 here we know get fib is gonna be 2 so and we know based on the sequence that that should technically give us the correct answer is the value of three plus the value of two in the sequence will give us the right answer okay well how do we get three well what happens as we come here we do the end Fibonacci of 3 and we see that it is less than or equal to three so what we do is we return one right so what we do then is we say that n Fibonacci here is equal to 1 we'll add a plus sign now what we're gonna do is we're gonna get the nth Fibonacci of 2 well how do we get the nth Fibonacci of 2 we come here we see that it is indeed less than 3 I don't know why my circle is so messed up there and what we do is we return 1 so we get 1 now 1 plus 1 equals 2 so our answer is returned from the forth sequence as the value 2 which is correct because obviously 0 1 2 3 but if we could go 1 2 3 4 which is gonna give us the answer of 2 and that was a pretty trivial example of how this actually gives us that answer for 4 but let's try getting the answer for 5 and how can we do 5 because Phi will be a little bit more complicated so we're looking for 5 we'll put our 5 over here so what we're gonna do on our first call here is we're gonna return to get Fibonacci of 4 and the get Fibonacci of 3 well what is the get Fibonacci of 4 well if we run that what that actually is equal to why can I not erase this one second if we run that well it's not less than 3 it's not less than 1 we actually need to return this whole statement again so what I'm gonna do is just draw a branch to illustrate that when we call get Fibonacci of 4 what we actually end up returning is the well I'm just gonna say get fib just to shorten the function name but it's the same thing so the get fib of 3 plus the get fib of 2 right because when we call for well 4 comes up here then we're gonna do the 3 and then we're gonna do the 2 so we need to return that first so we're gonna kind of dig deeper in there and figure out what those smaller answers are to build our way up into the bigger answer so let's erase this so we have get fib of 3 plus get fib of 2 now when we called this what do we get well we know that 3 is 1 and we know that 2 is 1 so our value here is 2 so the get Fibonacci of 4 now actually it's 2-2 right that's our answer for that part now what does the get Fibonacci of 3 well that's 1 so we have 2 plus 1 and then our answer is equal to 3 so you can see that when we call something and we don't have this trivial base case as the answer what we do is we have a recursive call which means we call the function again twice to get the two previous values now if when we call that twice we still don't know the answer to that we call it another two times and another two times and another two times until eventually we reach a case where we know the answer which is our base case and then we return all those values upwards to get our final answer and that is kind of how recursion works now if you want to really see how it works what you can do is put print statements inside your recursive function so that you can kind of get an idea of when it's actually being called and how it's being called but that is pretty much the answer now because some of you guys are still here what I'm gonna do is actually explain to you why this is kind of slow and another way that we can actually do this not using recursion now what's actually gonna end up happening when we do this and some of you may have realized is we're gonna calculate the same numbers a lot of times so let's say we do this get Fibonacci call here and we call it with five and four so gebben on G of five get Fibonacci of 4 well they calculate the Fibonacci of 5 we need to know that calculation of Fibonacci of 4 but here we're calculating Fibonacci of 4 again so what we're gonna do is calculate the Fibonacci of 4 in this call and we're gonna recalculate it again in this call now obviously as we kind of go up higher higher higher higher in numbers this is gonna mean we're doing a lot of calculations at the same time so multiple time so we don't need to be doing that what we can actually do is use a for loop and a hash table to make this a lot faster so I'm gonna run through that solution quickly and if you guys understand that solution I'm gonna assume you probably don't need to lengthy explanation so let's go ahead and get started now first of all I'll just show you that when I did run these test cases so run code we do get perfect answer which means you know I've done this correctly but let's do in a different way now and just say how we can solve this a little bit more efficiently so I'm gonna say calculated equals and a new hash table in this case a dictionary whatever you want to call it okay so sorry I said I was going to calculate this using a for loop but I'm actually still going to do this recursively but what I'm gonna do is just change something so we actually store all of the values that we've already calculated in a dictionary or a hash table and then pass that through every time to our function and just reference that hash table to see if what do you call we've already calculated that value so the way I'm gonna do this is just say calculated equals and I'm gonna set this as an optional parameter just so I don't have to do anything globally because I don't want to do that I'm gonna say it's equal to a blank hash now what I'm gonna do is simply say if n in calculated return calculated n now what this is gonna do is simply look in this hash that we have here in this dictionary I'm just gonna keep calling it different words apparently and see if we've already calculated this value if we have if there's anything in here we'll simply return that so what I'm gonna do is actually start by setting 0 : first I guess we're gonna say 1 : 0 2 : 1 3 : 1 because we know those values so these will all like always be calculated pretty much and we'll pretty much say that if it's not in calculated what we're gonna do is return deep get and fib of whatever it is or sorry not return we're gonna say calculated N equals get Fibonacci number of n minus 1 plus get and fib of n minus 2 then what we're gonna do is return calculated n now the way that this is going to work is essentially say if we've reached a point where we know the calculation of this will return it but if we don't what we'll do is we'll store that calculation and we'll actually need to pass calculated here every single time otherwise this won't work like that so we'll pass calculated it through as the new parameter because now we've changed it we've added a key to it and we'll store that value so we'll say you know and Fibonacci of index 5 or whatever in the sequence is equal to this so that means anytime now from one of these previous calls that we call this value will actually get the answer immediately returned to us rather than having to do another recursive sequence which means that this can run much much faster so I mean if I run this code you can see that we're still passing everything is still working but if you actually look at the time that it takes to run this on a very large number of n then this will be much much faster than if we do it the other way around because we're storing those calculated values so anyways I think I'm probably gonna leave it here because I assume that most of you understand how this works if you got this far in the video and you're still going obviously this guy down here can explain everything to use 31 minute video going through the solution for this get Fibonacci there's even a go to code walkthrough where he explains everything that he's gonna do you can even see his solution I think which is right here so he had the same one for me to start but I mean you know we just sped this up a little bit by doing something and restoring the values so anyways that that has been it for this video if he doesn't want to practice along on this platform you'd like to purchase this I do have a discount code below I think it's for 10% you can go to algo experto slash tech with Tim and I will give you the discount for this site