Python Coding Interview Practice - Difficulty: Medium

Key Takeaways

hello everybody and welcome back to their Python coding interview question today we're gonna be doing a medium question from algal expert dot IO which is personally the website I am using when have been using to prepare for coding interviews I have coming up I'm actually gonna be doing a really exciting video soon where I'm going to be doing a mock coding interview with the creator of this website I believe his name is Clemente or Clemente I don't know exactly how you say it I'm gonna butcher it but you guys will see that coming up soon so if you're excited about that leave a like but anyways the reason I use this platform is not just because you know I get paid to use it which I don't by the people that own this is because I actually really like the way that kind of information is presented and how easy it is to quickly go on the website and start practicing your coding skills you guys know for me personally I'm very busy the last thing I have time to do is search online to find all these different questions and then write my own test cases for them and do it in a Python window on my computer and try to see if I'm correct here and you guys will see as we go through it's really easy to save your answers you can mark them as in progress you can change your language you can get some hints like you would get in the regular coding interview you can set a timer you have test cases you know immediately if your codes working or not and that's kind of what you're paying for when you use this platform so if you guys do want this it really is a great resource I wouldn't recommend it to you if I didn't mean that and I've used tons of other platforms and even people have tried to pay me to promote theirs and you know I have stuck with this one so there's 10% discount code down below but let's get started with this question which is River sizes now River sizes this I'm gonna zoom in on this and we'll read through this last video I didn't really go through the question extensively and some people got confused so let's make sure we really understand this before we dig in so you were given a two-dimensional array matrix of potentially unequal height and width containing only zeros and ones that just means you know this does not have to be uniform length and width it could be way longer than it is height wise anyways each zero represents land each one represents predator river a river consists of any number of ones that are either horizontally or vertically adjacent but not diagonally numbers of adjacent ones forming a river determine its size write a function to return all of the river sizes represented in the input matrix they do not have to be in order okay so essentially the way that this works is we have these ones here which represents our rivers and the way that you can kind of think of a river is any ones that are touching each other form a river and the rivers can be in owls and they can go all around and they don't just have to be straight lines which is originally what I thought when I read this question so essentially for like these ones are rivers so the one on the left side I'll zoom in maybe a bit more so you guys can see so this one and this one are River this one this one this one this one and this one are River and they form this kind of El structure like that so how are we gonna go about solving the solution I'm gonna bring up my drawing tablet we're gonna walk through I'm gonna explain my solution then we'll code it out here and kind of figure out how this works all right so this is an example of what our input matrix might look like now I want to start by just identifying the rivers here so you guys understand which ones they are so we're gonna say that this is a river right here so all of the red underlines I'll do some different colors so we can see here I'm gonna say that this green is a river right here and then let's pick another color let's go with you know purple we'll say that this one is a river right here so essentially what we need to do in our code is write some function it's going to be able to look through all of these different ones its input matrix and determine the length of all these rivers so in this case we want to have you know three for this one we want to have five and we want to have five for this other River that goes like that so how can we do this well there's only really a few ways about going to do this that make practical sense and we're gonna want to use a graph traversal algorithm to do this and I'm gonna do this in a depth first search way and I'll kind of explain how that works and what that algorithm is as we go but just think about how you might you know approach this problem it's one thing if all you need to find is rivers that go horizontally and vertically that's actually fairly easy because you can just check every single horizontal row every single vertical row and do kind of some comparisons and store the rivers you've already seen but when we do this and we can have you know chains that look something like that as a river how do we do that well what I'm gonna do is a depth-first search process now if you don't know what depth-first search is essentially it's kind of looking for a path through a graph so it's a way to traverse a graph to find the longest path kind of first whereas if you're doing a breadth-first search way you're going to iteratively kind of and Edwards so anyways we're gonna start and this doesn't it doesn't matter this is the one but we're gonna start by looping through every single position in our matrix we're gonna loop through each row and each column and just look at every single position that's gonna be a kind of our first process what we're gonna do is when we get to a position we're gonna see if the element at that position is a 1 if it's a 1 that means we found you know the start or maybe possibly even like the middle of a river and what we're gonna do is try to find any river that's attached to it so like the longest river or whatever river is attached to this one we're gonna try to find that and figure out what the length of that is so how do we do that well when we find a1 we found you know okay this is a start of a river or something like that what we need to do is look at all of the neighbors of this one and determine if there's any ones beside it because that would be the rest of the river right so we're gonna look up we're gonna look right we're gonna look down and we're gonna look left now obviously we can't look left and we can't look up because there's nothing there so we won't look in those positions but what we can do is look here at this zero and look here at this one now let me just erase all of these so that we have a cleaner thing here so what we'll do is we'll look at this zero and we'll say okay so is this a zero or is this a 1 well obviously it's a zero so that means there's no river kind of going this way on the right side we don't need to continue doing anything past the zero we'll just stop there next though what we do is we look at this one and we say okay so we have one we have another one so our River now is of length two we've seen both of these ones they're part of our River so what I'm gonna do is actually mark the fact that these ones have been discovered that we've looked at them that we've seen them because currently we have a river of length two that contain these ones we want to make sure that when we look through you know later on in the sequence of this program we don't reconsider these ones so I'm gonna create a kind of a set over here in think of it as a hash to the think of as a set it doesn't really matter I'm gonna store the position of these ones so I'm gonna say okay so I've looked at this one it's in position what position is it zero zero because that's the position in the matrix right so we say that's 0 that's 0 and I'm dot dot that should be one two three four five and then one two three four Oh oops oops this ship for okay so let's say that goes to four and we'll do the same thing here to position four so let's say that is you know position zero zero so we mark that we say we've seen that one already now same thing with the one we look at this one so okay that's the one let's mark this one what's that position that's actually gonna be position one zero because we're gonna read from the row and then the column after that and the reason we do this is because when we get to this next one what we're gonna do is continue the process of looking at all the neighbors of this one trying to find if this River expands or goes anywhere else so what we're gonna do is well we're gonna look up we're gonna look left we're gonna look down and we're gonna look right but now you can see where an issue might occur if we look up we're gonna see the same river that we've already seen right and well we don't want to count that River because we've already seen it we've already marked it we already know it's part of our River and we really shouldn't go back to it and start looking in all the different directions from that River so what we do when we look in all these different directions do we say okay well if we look in this direction and we find a one that hasn't yet been marked that we haven't seen in this set here only then will we consider so in this case when we go here we can see that this isn't marked yet so we'd consider it now what we're gonna do from here is consider all the neighbors that aren't marked so in this instance we'll look at this one because this is you know one of the neighbors of it and then same thing from this one we're gonna look in every position we're gonna look for any ones that aren't marked so we won't look here because that's marked obviously so what we'll do then is we'll go to the next one then same thing here we'll go to the next one continually marking all of these positions in our list so in this case we're gonna mark position 1 1 we need to mark position 2 1 I think and then we need to mark position what should this be 2 - I think that's the correct position yeah so we'll go to 2 marked and then this now has made up our first River we've marked all these positions and while we've been doing this we've been keeping track of the length of that River I don't know what I just wrote there which I'm gonna say is a fine right so the length of this river is 5 so we've kept track of that as we've gone through and found all these ones now we'll add that to one of the rivers that we found which is 5 ok so we did that we looked through all of these so let me erase the let's talk about the next step that we're gonna do so get rid of all this all that okay so now we already looked at this one so we found all these other ones from this one that are connected to it we've marked all of those now we're going to move to this next position which is a zero since it's a zero we don't need to consider anything because there's obviously no river there same thing here we don't need to consider it same thing here don't need to consider it now we hit another one so what do we do alright let's reopen up this set here let's start by marking the fact that okay we've considered this our current River length is 1 we've looked at this one what position is this in that's in position 0 4 so we'll mark that now what are we gonna do we're gonna look left up right down right so we look at all these we realize that ok obviously to the left is a zero we don't need to look at that down what's that oh it's a 1 ok so let's look at that alright one looks up looks left looks right looks down sees ok well this one's already marked we're actually gonna mark this one that we've seen it so what position is this that's position 1 4 then we say ok let's go to the next one which is this one let's mark it what's this one well this should actually be 2 4 and now our current River length is 3 there's no more else that we can go because those are all zeros obviously so we stop we add 3 into our list of rivers so now we have a list of let's say what is it 5 & 3 so 5 comma 3 and now we can continue the process so where do we left leave off well we had looked at this one already so now we'll go to the next one we'll look at this one oh wait this is a one okay so did we start the process again no we don't the reason we don't start the process of looking for other rivers is because we've marked this one and we can see that position should actually be 1 0 which is right here so we don't even bother considering it we'd go to this one same thing it's already in our set so we don't need to look at it because it's already part of a river 0 that's a 0 we don't look at it 0 we don't look at it 1 ok well that we've already looked at it's a part of the set don't look at it and you guys get the process 0 don't look at it one don't look at its in the set 1 don't look at it 0 don't look at it 1 it's in set we don't care all of these obviously we're not gonna look through until eventually we hit this one say ok it's a 1 it's in the set so let's consider it and then we're gonna chain go all the way here look at all these ones mark all these ones notice that you know that's another River add five then we're at the end here so we just returned that list and this is exactly what we're gonna do and this is the process that we're gonna follow so I hope that makes sense I've dug into it pretty in-depth I've talked about it for about 10 minutes kind of this depth-first search approach which is kind of what this is we're just looking through all of the neighbors of all these different things and kind of traversing the graph now it's time to apply this in Python it's a little bit of an advanced algorithm but try to stay with me and you know try to write it yourself first and then you come back again I'll go expert you can use this question for free so you guys can actually go to algo expert on and perform this question on the website for free you don't need to sign in or pay for it to do it because this is a free question then obviously if you guys like it you can take advantage of that discount and use some other questions let me put away some of my stuff and we'll get here and start coding all right so let's start coding this problem now I'll make this fullscreen I hopefully this is big enough for me for you guys let me know in the comments if it's too small actually it will go fullscreen on everything here okay there we go all right so what's the first thing that we need to do well we need to create this kind of set that we're gonna keep track of all of the marked rivers in and we also need a list that we're gonna keep track of all the river lengths in that we discover so what I'm gonna do is I'm gonna start by creating a set which is we're gonna call marked so this look keep track of all the rivers we've already seen and now we'll keep track of I guess rivers that we've seen in a list what we're gonna do next is what I've explained and I'm just gonna follow kind of the algorithm that I explained to you guys in the following page we're gonna loop through every single position in the matrix so starting from the very top left going to the very bottom right we're gonna say four row in range the length of matrix like that then we're gonna say for call in range B Len of matrix like this and then row like so now the reason we're doing this is because this is going to essentially tell us you know how long each row is because we know these might not necessarily be the same in terms of length and width so for each row in our matrix we'll figure out how long Rowe is and then loop through every single position okay so now that we've done that the first thing that we need to do is we need to look at the current position in our matrix so our row call position we need to see if that's a 1 and we need to make sure that we haven't already looked at it in the market set so to do that we're gonna say if in this case the matrix and we'll say row call equals equals 1 and in this case we'll say row call not in marked so if that's true which essentially again means you know it's a 1 and it's not in the mark set what do we need to do well we need to start looking at all the different positions around it so what we're gonna do is start by essentially saying our current River length is equal to 1 at the current moment we found one which means this river has length 1 what we're gonna do next is actually set up something that I'm gonna call a stack and I'm gonna set up our actually sorry add this position to mark now we'll talk about what this is gonna do in a second so I'm gonna say mark dot add and I'm gonna add row call which is essentially saying okay we're going to put this position that we've seen in the marked set so we know not to look at it again what I'm also gonna do is add row call in to my stack now if you guys haven't seen stacks before I'll briefly kind of go through how they work but it's a fairly simple data structure this is gonna allow us to do kind of a depth-first search of this all the ones that we can find attached to this river so what I'm gonna do now is say well stack I'm gonna say current equals stack dot pop and we'll talk about what this does okay so what this means is essentially while stacks so if there's anything in our stack because what we're gonna do is every time we find a one that is neighboring the current one that we looked at we're gonna add that to our stack which we're gonna call here so that we can look at all of the neighbors of that one during the next kind of iteration of this searching traversing process so what we do is we're gonna say the current like node the current one we're looking at is gonna come from the end of the stack so whatever we pop off that's what it is going to come from the end so in this case when we start we'll just get this row column which is the first one that we have that's one we're gonna look at what we're gonna do next is get all the neighbors of this and then look at all of those neighbors and see you know one of those neighbors are they ones are they zero should we look at them should we add one to our current River life do we see another one that's adjacent to it what do we do so what we need to do to do that though is create a function that can give us all of the neighbors based on a current position in our matrix so what we're gonna do is say define get underscore neighbors if I could spell neighbors correctly and I don't know if you spell it Oh urs or if it's o RS but we'll just go with this for right now because why not and what this is going to take is a position and the matrix what we're gonna do in here is essentially find what the position of the left neighbor the top neighbor the right neighbor and the bottom neighbor is so to do this is pretty straightforward we're gonna start by saying y comma x equals position which is just gonna decompose this topple for us and essentially tell us the two components of it so we can use those independently and now what I'm gonna say is if X is greater than I should say greater than 1 greater than or equal to 1 what we'll do is and we'll create a list here we'll call it NS which just stands for neighbors we're gonna say NS dot append and in this case we're gonna do X or say Y X minus 1 now this is going to give us the left neighbor so we can put a little comment here that says left and why am i doing comments in Java I've been reading too much Java next what we're gonna do is check the so that was left neighbor will check the right neighbor so we'll say if X is less than and in this case we're actually gonna say is the length of matrix 0 minus 1 now the reason we're doing this is because we're going to add 1 to X so we need to make sure it's less than whatever the length minus 1 is so that we don't get an index error so we'll say NS dot append Y X plus 1 and I will do the same thing for Y so if Y is less than or sorry not less than greater than or equal to 1 then what we'll do is NS dot append and we'll say Y minus 1 X and then same thing with the other component so if Y is less than the line of matrix minus one because that'll give us the Rose NS dot append and in this case it should be y plus 1x now we'll simply return that list so return an S and that will give us all of our neighbors okay awesome so I think that makes sense so far so now what we'll do is get all the neighbors of this current position so to do that what we'll simply say is okay and actually we'll say neighbors Y not equals get underscore neighbors of position which is actually going to be row call and matrix awesome so now that we do that we're gonna have a list stored in here of all the neighbors so what we need to do is look through all these neighbors first of all see if there one see if we've already looked at them or not and if we haven't then we'll do is add one to our current River length and then add that to the stack so that we can look at all these neighbors again and again and again and kind of traverse through all of these and I'll dig into it in a second so what we're gonna do now is say for n in neighbors so this again will give us those positions I think I need an H there I do now we're going to say is if N or actually I'll say Y x equals n just so we can decompose this and make it a little bit easier so we'll say if matrix yeah if matrix y x equals equals 1 and y x not in marked which essentially means we haven't looked at this river already then what we'll do is we'll add it to mark so say marked dot add Y X will say cur underscore River underscore length plus equals 1 because this is another component of the river that we found so we need to add it and then finally what we will do is add it to the stack so it's a stack dot append and if I could get the right symbols here we will append Y X now the reason we're doing this appending to the stack is because we need to add that one and I think I can go back to my drawing example maybe this will make things a bit clearer like okay well this is an absolute mess now but if we're here right and we find this other one well we need to add this one to the stack back so that we can look at the neighbors of this one next right and then whenever we find another one or maybe there's two ones we add both of them to the stack so that we can look at all of their neighbors during the next iteration when we pop things off the stack now I know this might be kind of confusing to some of you guys if you haven't seen an algorithm like this before we're actually almost done so what we're gonna do now is essentially once the stack is empty we're gonna add to the rivers list so we're gonna say rivers dot append current River length Soaker underscore River underscore length and then at the very end of our program will return rivers now that should actually be it I'm just gonna do a quick glance of my other screen I do have the solution up right now to make sure I haven't absolutely butchered it and it looks like we're doing all right and yeah that should actually be it so essentially the process is right loop through every single position make sure that the position we're looking at is either one and it's not marked if that's true if it's a one it's not marked we'll say okay so we're gonna look for a river now attached to this one it has a current River length of one it's we're gonna add it to the marked list so we don't look at it again we're gonna create this stack that starts just just having this position then what we'll do is we'll pop that off the stack which actually means remove this element set it equal to current then what we do is we're gonna say neighbors equals get neighbors row call matrix so this actually should be current my bad guys this shouldn't be wrote call the reason it needs to be current is because we're gonna actually change the neighbors we're getting based on the thing we just popped off the stack so sorry this is current matrix this will give us all of the neighbors for that specific position and assuming I didn't mess up this function that should be alright then what we're gonna do is look through all of the neighbors essentially say okay let's break down their components let's check if this neighbor is a one so if it's a one in the matrix and if it's not yet marked what we'll do is we'll add it to the marked set we'll set current River length plus one because we just found another one that's a part of this River we'll add it to the stack so that we can then look at all the neighbors of that one and see if there's any other you know rivers that are extending and going off finally once that's done so we don't have nothing left in the stack that we found the end of the river what we'll do is append the current River length then we will return rivers now returning rivers will just return this final list this is a little bit of a messy coat but let's run this and see if we've done all right or not so let's zoom out run code log into run code okay so I'm gonna log in and run the code and then let's see if this works okay so we passed now I would like to say that I actually just had to copy the code like my solution back in here it's the exact same as what I wrote but you might notice some variable names are a little bit different because for some reason it deleted my code when I signed back in to run the code anyway so there we go we passed our outputs are good and I mean we can see them can have a look at the raw output here saying how long it ran in and we can have a look at these test cases to see you know what we were tested up against and if that actually worked we'd also write our own test cases if we want to inside of your tests like you can modify them and if we have a look here we'll have a look at our optimal space-time complexity so we have owh time owh space which is actually I believe what this algorithm runs in so if you guys want to challenge yourself leave a comment down below and tell me if I'm right or wrong on the space-time complexity of this algorithm I'm trying to get it centered in the page here so that we can have a look at all of it but does this that I've written here run in owh time where W is the width and H is the length of our matrix I'm gonna go on a limb and say yes it does the reason I say that is because obviously these two loops are gonna be WH right then what we're gonna do in here is we're only ever gonna execute this a maximum of W times each times because we're adding all these things into our marked set and looking up an element in a set takes a one time on average it can take longer to find if it's in there but on average takes a one time so what's gonna happen is this will only run a maximum of WH times so technically we would have to WH is our maximum amount of runs that we can potentially have because in combination of all these loops the some of that will be less than WH so we can remove that constant and then have WH as our running time complexity now in terms of space what we're using is well essentially a set here that could potentially have maximum WH elements for every single element being a river so one massive River is the entire matrix that's possible and then rivers here well this can have I mean in theory it can have as many rivers as are actually in the matrix so that's gonna give us two WH for space but since again we can remove that constant we'll have WH for space and that should be good I'm sure someone can come up with a reason why this might not run in WH why am i running like WH squared or something like that but if you can that's awesome leave a comment down below and I think that has been after this video as always if you guys enjoyed make sure to leave a like you know always get a 10% discount on algo expert using the code I have in the description and with that being said I will see you guys in another video