Python Coding Interview Practice - Difficulty: Hard

Key Takeaways

hello everybody and welcome back so in today's video we're gonna be going through a fairly difficult coding interview question now I've been doing a few of these on my channel let me know in the comments down below and by leaving a like if you guys like this kind of format and what I'm doing and you want more of these videos because I'm always happy to do them the platform that I'm gonna be doing this problem on is called algo expert dot IO this is personally my favorite way to do programming problems simply because and I'll show you when we load this up here it's really easy to have a look at your raw output to see your different test cases to make sure that you got everything correct rather than trying to find you know some questions online doing them not knowing if you got them right having to type in the input this is just much easier it's much faster it's much more convenient they have some structured questions ranged by difficulty so you kind of can work up and around anyways I don't know I like it a lot of these questions you can find online but being able to work in a platform like this helps me focus and just get more done so if you guys do actually want to use this platform there's 85 coding interview questions as well as some other resources on here related to interview prep and just some advice I do have a discount code in the description so it's tech with Tim that'll give you 15% off if you click that link if you are interested in purchasing that and that is an affiliate link so i will get some commission from that so anyways the problem we're gonna be solving today is the largest range problem so this is one of the free problems under the hard section so i've decided to skip this one for now we might go back to it later and what we're gonna do here is just solve this problem so essentially i won't read this whole thing but what the problem is asking us to do is find the largest sequence of consecutive numbers inside of a list now these numbers do not need to be right beside each other so left or right they don't have to be adjacent they just have to exist so in this case it's telling us the largest range of numbers or sequence of numbers inside of this list is 0 and 7 so 0 is the starting point 7 is the ending point that means we know that 1 2 through 6 are all in this list and that's the largest sequence of numbers that we found so how can we go about solving this problem and how can we solve this problem at optimal time the initial solution that a lot of you will probably think of when you hear of a problem like this is why don't we just sort the list now this is OK in some situations but we have to understand and that this is not an optimal solution the reason this is an optimal is because we want our code to run in the shortest amount of time possible and sorting a list already takes n log n time so that's the average time or worse time for sorting a list is there any way that we can do this faster without needing to do a sort well the answer is yes and I'm gonna bring up my drawing tablet we're gonna get into the solution but I'm gonna go through for this problem then we'll code it out and we'll talk about exactly how it works so the way I'd like to start by explaining a problem is just breaking down what the problem is thinking about some trivial solutions to that problem how we kind of use that solution to find the answer and then adapting that to find a more optimal solution so in this case we're gonna do a quick example or I'll just write a few numbers here there's gonna be random different from what we had before just to one to zero why not something like that and we're just gonna see you know how would we go about solving this well as a human what we're gonna do is just look for you know the largest range of numbers and in this case we can tell it's gonna be one two three four zero right we know that that's the range how can we do this in computing really easily and really fast well a really easy way to do this is to start by just sorting all the numbers so let's say we sorted all the numbers and we go one two three four there's a zero here in my bad 711 well now we can tell why this is so much easier because since all the consecutive numbers are beside each other all we need to do is start at zero loop through the list until we get to a point where there's no consecutive number so right here take all of these store them save them be like okay this is our current longest range and now we're at seven and now what we can do is loop through and find a range from seven and just keep going until we've gone through all the numbers and we've determined what the longest range is pretty straightforward pretty easy I'm sure you know most of you guys could come up with how to solve that so let's erase this and that's fine but the issue with that solution is that runs in n log n time because we need to actually sort the list first and well that just takes a lot of time is there any way that we can do this without sorting the list well I'm gonna walk you through my kind of solution which is also the solution that the algo expert guys use in and you can see it here and we'll code it out second that goes runs in linear time it doesn't require actually meaning to sort the list now the way that we do this is using something called a hash table now a hash table in Python is the same thing as a dictionary but I'll just call it a hash table here because that's kind of the more formal term for it what I'm gonna start by doing is loading all of these numbers into a hash table now think to yourself why I might do this while I write out these numbers why do I want all these numbers in a hash table what's the point of doing this like why why am i doing them all so what am I going to use is the key well in this case I'm going to use zero as starting out the key as the value for all these keys in my hash table and ask yourself why I might do something like that why would I use the number zero or maybe false or maybe true why might I use that as the key well the whole point of storing all these numbers in the hash table is oh one time lookup now what I mean by that is trying to find if any element exists in a list is gonna take you oh and time the reason for that is because you need to look through all the different elements in the list to determine if a specific element exists however looking up an element in a hash table runs in O one time and that's exactly why we're gonna use it because what I'm gonna do is simply start at a number go left and go right from that number so go 10 go 12 and just count how many times and how far I can go until I reach a point where none of those numbers are in my hash table now I know you're still confused right now we're gonna go through obviously a detailed example and explain it but what we're gonna have kind of in our program is we're gonna be keeping track of a left and a right now the left and the right are gonna keep pretty much say with the left number in their sequences and with the right number in our sequences we're gonna adjust these to reflect the largest range as we go through these numbers now we're gonna start with left equals zero and right equals zero if you guys at the very beginning our largest range is just one number which is the first number in the list and that's merely because we just don't know we haven't looked through it yet that's a default value so what my kind of algorithm is what I'm gonna do is I'm going to look at each number in the list so we're gonna go through end times through the list and what I'm gonna do is I'm going to create a left pointer and a right pointer which are equal to the numbers directly above and directly below left so in this case 12 and in this case 10 and I'm gonna continue branching this out so to the left and to the right until I reach a point where the numbers here are no longer in the hash table or don't exist in this list right so the basic algorithm is look to the left look to the right so I'm gonna look to the left and I'm gonna see if 10 is in my hash table now in this case I go through I look at my hash table about a1 lookup time it doesn't take any time at all and I don't see 10 so what I do is I say okay we can't go left from 11 there's no more numbers left in the sequence from 11 let's go right and let's look at 12 well now we're looking for 12 and obviously we look in this hash table we don't see 12 so what do we do we say okay we can't go right and what this means is now we've visited 11 we've looked at 11 and we've determined that the largest sequence that 11 will be a part of is gonna be just itself and the reason we can say that definitively is because if there was a 10 or if there was a 12 then we would have found it we would have seen it in the hash table and we would have been able to determine that okay potentially 11 could be in a longer sequence but here since there's no 10 of there's no 11 no matter what the largest sequence that 11 can be in is itself so what we do now is we go down here to that our hash table we find 11 and we mark it with low 1 simply saying that we've looked at 11 so far there's no point in looking at 11 again we've already done now this isn't super important for 11 but you'll see whether you mark this a second that would go to 7 and what kind of speed through this now because I think you're getting the hang of it and we'll do the same thing we're gonna look left so for sex we're gonna look right for 8 now in this case we don't find either of them right so same thing here what we're gonna do is well we know that 7 cannot be a part of the sequence so what we're gonna do is Mark a 1 now I forgot to mention what we're doing with this left and right variable up here well essentially what we're gonna do is when we kind of go left and right we're gonna check if that left and right distance is greater than the current left and right that we have so in this case obviously 0 0 the difference between them is 0 so any two numbers left and right are gonna give us a larger difference so in this case when we you know had 11 with our first number we would actually say that the left is gonna be 11 and the right is gonna be 11 because that's largest sequence that we currently know which is just 11 we get to seven same thing so seven is the same length sequence as 11 we know that there will never be two sequences of the same length of the max sequence but I can either decide to leave these as 11 or I can put them as 7 I can change that variable if I wanted to a set but anyway so let's go to 3 now and explain how this works so now we're at 3 we've already looked at 11 we've already looked at 7 we've determined that those are not a part of a longer sequence than just themself and what I'm gonna do now is do the same thing from 3 I'm gonna look at 2 and I'm gonna look at 4 but in this case both 2 and 4 actually exist in my hash table so here I can see 4 exists and I can see that 2 exists so what I'm gonna do is since I actually exist I'm gonna mark them as the fact that I've seen them and I'm gonna say that currently now at this point in time you know my left value is gonna be 2 and my right value is gonna be for my temporary laughed at my temporary right value is gonna be 2 and it's gonna be 4 and the reason that's gonna be that is because that's currently where I am on the left and that's currently where I am on the right and that's the current sequence that we have 2 3 4 right ok so now we say okay well we found 2 we found 4 so let's try going both ways again so let's try going to 5 and let's try going to 1 well obviously we know 5 doesn't exist so we're gonna end on that path there that means 4 will stay as our right element then we're gonna look at one well now we look at our hash table we find one so what do we do we're gonna mark 1 so we're gonna say we've looked at 1 let's mark it so we do that and then you know our left now is gonna be at 1 because that is the current for this left point we have and we say ok well let's not stop at 1 let's keep going let's go to 0 okay let's look for 0 well we found 0 it's down here so what do we do we mark 0 we give it a 1 let's do that and then all this left to mark is 3 after that don't essentially you know we can't we're gonna go we're gonna look for negative 1 we're gonna see negative 1 doesn't exist so we'll end we're gonna mark 3 is the fact that we've seen it so let's do this now and now what we're gonna do is we're gonna go to the next number so all this you know we can cross that out we've just done three we've done seven we've done 11 now it's time to do 4 but the thing is we don't need to do 4 because we've already determined that 4 is a part of a sequence we've already determined from looking at 3 that 4 is a part of a sequence so we don't need to do 4 so what we're gonna do is check if 4 is marked as 1 if we've seen it if it's a part of a sequence already and if it is well what we're gonna do is skip it and same thing with 2 we're gonna check you know is this a part of a sequence it is already we have it marked it has a 1 so let's skip it and then we're gonna look at 1 we're gonna say okay well one that's in there it's marked as a 1 so what we'll do is we'll skip it same thing with 0 and now we're at a point where we've determined that the longest range is actually the left value of in this case I guess 0 and the right value of what was it before and that is our longest range now you might be getting a little bit confused on how we're calculating the longest range but essentially all we're gonna do is from each number go as far left as possible consecutively go as far right as possible consecutively we're gonna keep track of what the furthest left and the furthest right point was so in this case you know we had 0 and we had was it 4 we're gonna calculate the difference between them in this case which is 4 so 4 numbers in that sequence we'll compare that against what our current max left and right value is and we'll say if that sequence is currently greater that we have will replace our greatest sequence with that and we'll keep going through all the different numbers using this hash table to look them all up in a 1 and we'll be fine now some of you might be like well this seems like an N squared algorithm where we have to look through all the numbers and then what we have to do is go left potentially unlimitedly and write potentially unlimitedly 2n right well the whole thing here is this actually runs in linear time and the reason it runs in linear time is because every time we see a number we mark it in the hash table so we will only actually ever evaluate a number one time because every single time that we look at it even from you know going left and going right that's only ever looking at it once because when we get into the for loop and we're the you know trying to evaluate 2 and trying to evaluate 1 we see that it's already marked in the hash table so we don't need to do any operations for it so we can be certain that this algorithm will run actually in perfect Oh n time every time because well we don't need to do evaluations on the numbers that we've already marked and you know we're only gonna mark and numbers so that's essentially how that works so anyways that is kind of dissolution now let's actually get into programming and I know this was long but I want to make sure that you guys really understood how this worked and why this does run in O n time as always leave questions down below and let's get into coding it now okay so I made this code box full screen I'm hoping this is readable enough for you guys and let's actually just start coding the problem so essentially we're gonna follow that algorithm that I explained we're gonna create a hash table to start we're gonna go look at every single number in our list we're gonna look to the left and to the right of that number we're gonna see how far we can go we're gonna mark the numbers in our hash table and that will actually ensure that our algorithm runs in O n time we'll keep track of the furthest left and for this right point in the largest sequence and then we'll return them so what do we need to do to start well we need to create a hash table so I'm gonna create numbers equals this and I'm gonna say X colon zero for X in array now what this is going to do is simply create a new entry in our hash table that has the value 0 and the key whatever the number is for every number in our array so we'll do that then I'm gonna set up some left equals right equals 0 variables here so left equals 0 right equals 0 you can do this in Python it's kind of like a fancy trick to keep track of what our current longest sequence is or the left point of our longest sequence and the right point of our longest sequence okay and now what we're gonna do is we're gonna look through every single number in our array so we're gonna say 4 number in array and the first step to check is have we already evaluated this number is it already a part of a sequence or doesn't need to be a value at it's still so we can check that and very basically will say if numbers number equals equals 0 in only bad case will we actually evaluate the number otherwise if this is not true that means that we've already seen this number when we've gone left or gone right from another point and there's no point in evaluating it again because we know that you know going left to right we're gonna reach the same sequence again because we've checked that already so we're gonna say if you know if it's not been evaluated what we need to do is go as far left as you can from it and go as far right as we can from it and keep track of those values so I'm gonna say left underscore count cools in this case we're actually gonna do number minus one for me to say right underscore count equals number plus one now what I'm gonna do is go as far left from this number as I can looking it up in the hash table each time and then I'm gonna go as far right and keep track of that so to do this I'm gonna say Wow left underscore count what's it sorry actually my bad here ya know well left underscore count in numbers so this is a lookup in the hash table just seeing if it exists again this will run into a one time so let's actually write that down so that we remember oh one okay I don't know why the brackets aren't okay that would make sense anyways so while this number is in numbers what we'll do is simply decrement the number and mark the number in numbers so we'll say numbers left underscore count equals one then what we'll say is the left underscore count - equals one so continue to the left as far as we can now once we reach a point where we get out of this loop we actually just need to add one to left camp the reason we need to do that is simply because when we start by subtracting one and we don't necessarily know if this number is automatically gonna be in left count and at the end we subtract one again to see if the next number is gonna be in numbers or in our hash table so we need to just add one at the end to make sure that we're not saying what an extra number exists in our sequence when really it does not anyways you guys will see that in a second okay so that's the left aspect of it we can actually copy this and do it with the right aspect but I feel like it might be faster just type it will say well write on your score count and numbers then we'll say numbers oops this and I guess I need a colon so we'll say numbers right underscore count equals one and then right underscore count plus equals one if I could type properly and then we'll say write underscore count - equals one and this needs to be plus equals one as well you guys can tell a little tired this morning apparently I keep forgetting all this basic stuff okay and I have this cursor in the wrong book okay so anyways there we go we have write count and we have left so what we've done down just so everyone's on the same page here is we've initialized two variables left count and right count our left count is gonna go left or right count is gonna go to the right again keeping track of the consecutive numbers from whatever number we're at so let's say we're looking at the number four in our array we're gonna check is for marked have we looked at for you in our hash table we haven't okay so we'll set up our left count to be start at 3a right count to start at five and now we're gonna check is three in numbers if it is what we'll do is we'll mark that number and then we'll check now if two is in numbers then we'll keep doing that right as soon as we break out what we'll do is say okay well we checked two two wasn't in the number so let's just add that left count back up one because that's the last number that we knew for sure was in the range right now same thing with the right count we're going to check if in this case five is in numbers if it is we'll mark it will add to the next one then we'll check if six is in otherwise what we're gonna do when we break out is just subtract one so we have the correct range now what I'm gonna do is actually set the largest range aspect here so I'm going to say if right minus left is less than in this case right underscore count - left underscore count and I'm actually gonna do a less than or equal sign here and we'll talk about why in a second I want to do that then what we'll say is right goes right underscore count and left equals left underscore count and then we will simply return at the end here an array with left and right so now I know what kind of ended this you know kind of fast here I'm sure some of you guys are probably still figuring out what's going on but essentially this is all that we need to do to actually make this work now we'll run through it one more time you know with an example here but let's talk about this part what this is doing this is gonna check to make sure that the current range that we've just found by going left and going right is larger than the last previous range that we had kept track of so in this case the first time you run this this will always be true because obviously you know your number won't be marked that you're looking at so the first number won't be marked then what you're gonna end up doing is say that left equals right and these will be the same value if there's no you know sequence from the first number all right so if you say left less than or equal to then what we're gonna do is keep track of all these sequences so maybe we find a sequence of length two maybe that sequence has the numbers one two in it will say left equals 1 right equals two we know that how many numbers are in that sequence by subtracting the right pointer from the left pointer so in this case gives us 1 and then we check if the current sequence we found is greater than or less than that sequence and that's pretty much all that we need to do and in that case we mark right and we mark left and there we go and yeah I'm fairly certain that that's all that needs to be done I'll check to make sure and yeah I'm gonna go ahead and say that that's okay so let's actually run this code so let's how do I get inside a full-screen mode okay so run code give it a second and we can see we pass all these test cases so let's compare it to what solution they had so their solution is very similar so you can see they have a best range nums longest length I think they've made it a little bit more complicated than it really needs to be to be honest on in terms of the way that they programmed it but I mean you know you guys can be the judge whether you like my version or their version better anyways that is the problem now if we look here we can see some of the hints that it was trying to give us so you can use a hash table which obviously we did iterate through the input array once storing every unique number in hash table which we did then optimal space time complex the O n time o n space and that's exactly what we're doing because well we're keeping oh and space here well we need this hash table for every number in the list and then for here this is simply o n we know that this will ever uh never only run n times so in theory we could say this is n plus n and obviously that's gonna be 2 n which is gonna simplify to n so anyways that has been it if you guys do like I'll go expert honestly I'm telling you guys I've used this I'm really not just trying to sell you a product this is a great platform if you want it take advantage of the discount code it is the link in the description and I will be honest with you guys this a platform has been getting more expensive if I go to the purchase it used to be $77 it's 85 now and I can only imagine in the future it will continue to rise in price as they add more questions as it seems to be that whatever how many questions they have they charge one dollar for each question so anyways that's has been it I hope you guys enjoyed if you did leave a like subscribe and let me know what you guys want to see in the future