Medium Google Coding Interview With Ben Awad

what's up everybody how's it going today i am joined for the second time by the one and only ben awad we are doing a second mock google coding interview if you remember a few months ago we did an easy google coding interview where i had been reverse a linked list and invert a binary tree today we are doing a medium difficulty coding interview because that was a pretty easy one and ben are you feeling good i'm feeling a little bit nervous i haven't seriously thought about algorithms or linked lists in a couple months so i don't know what to expect listen i think this one is going to be fun either way whether you struggle or not it's going to be a good learning experience for you and the viewers so let's jump into it we're gonna have roughly 45 minutes on the clock we're going to be using the algo expert mock interview shared workspace user interface for this interview by the way if you're preparing for coding interviews or systems design interviews or machine learning interviews then check out my company i'll go expert go to expert.ion user promo code clem clem for a discount on the platform then in a real google coding interview the interviewer wouldn't be shilling their product in front of you so i'd be on google docs right now yeah um we'll probably move to google docs for the for the hard google coding interview that we do in the future but okay ready i am ready and willing all right the clock starts now at roughly 56 minutes i see on the on the stopwatch so we'll go roughly until about 10 minutes so then i want you to imagine that you have a black and white image so the black and white image consists of pixels or rather it's represented by pixels and these pixels are either black or white now the representation of this image is going to be in the form of a matrix which is a two-dimensional array and that two-dimensional array only has the numbers zero and one one represents black a black pixel and zero represents a white pixel so for example if you look on your scratch pad here do you see this two-dimensional array that i pasted yep so that might be a sample input that represents the black and white image now you are going to be tasked with removing all of the black pixels that are not connected to the border of the image so when i say connected i mean two pixels that are or two or more pixels that are either horizontally or vertically adjacent and if they are not connected to the border then you have to remove them and the reason that the function that we have here is called remove islands is because we're going to call these blocks of black pixels that are not connected to the border we're going to call them islands and so you want to remove them so i'll give you the sample output for the input that i gave you here this would be the sample output here and it might not look like much here but i'll show you another thing this array that i'm paid that i'm about to paste here this shows all of the islands that we removed so you can see that between the sample input and the sample output we removed this island here that had one one we removed this one that had another single one and then we removed this one that had two connected ones and none of these four islands here or sorry three islands rather there are three none of them were connected to the border yep so okay so it's not diagonal too it's just left right up down exactly so you might notice that in the sample input if you scroll back up there's a one in the top left corner the one here in the second row second column we removed it even though it's diagonally connected to the top left corner because diagonally just doesn't matter right i i think i get it now and i know how you're supposed to solve this i'm supposed to come like create a graph of all the ones and then i can see which one is not connected by doing i mean i guess i could do a depth first search but i kind of like that that feels too algorithm heavy i kind of want to just like do a for loop and see if i can do it without creating a graph slash i forgot how to do graphs too so okay my initial thing is i want to for loop here and i think okay so my the first thing i thought was like all right i could do one pass to identify all the ones on the edge i assume the matrix is going to get really really big right that's the idea and so i can't like yeah so this ideally you want to be too slow to like so this was my first thing this is a slow version right so i take the outer ring and i do the inner ring and then the innermost ring you know what i mean so i would do like so this one has three levels the outermost level and then two but that's going to be too slow actually what would that be okay can i do it to start don't worry like yeah don't worry about about optimizing the solution all right all right i'm gonna go really slow then all right so this is going to be um so i need to store the ones that are on the edge so i'm gonna call this edges and i'm trying to decide if i want to make this a dictionary i think i do and i think the dictionary how this is going to work is i'm going to store like 0-0 true zero one false actually i'm trying to decide yep so how this is how this is working is this is going to be the rows this one's going to be the columns okay and what does true and false represent true means it's an edge false means it's not an edge so then i'm going to we're going to for loop and actually i could probably do this oh i can actually do this very fast too because then when you say not an edge you mean not on the border or you mean um okay yeah yeah i see what you're saying so yes it's not on the border and it's not connected so what i'm starting at the very very so like the very left side the very right side the very top the very bottom that's what my first loop is going to touch okay and i'm going to say whether it's a one okay so true true means it's a one and it's an edge and then i'm gonna and then i'm gonna do that again on the second ring and do it again on the inner ring okay this sounds really drank but this may be really jank so we're gonna start here though because i actually don't know why i'm starting here but we're gonna start here all right so four i n matrix this should be for rho and do i want to enumerate let's enumerate a numerate so enumerate should give me the index and then the value oh now the real question is does enumerate i think the first one is the index let's let's do a little test okay um running code yeah failed give me output though if you clicked arrive but you should see it okay perfect i did it right yeah so i just want to make sure this was literally the index and this is literally the row and it did look great and just uh ben i i don't mean to interrupt you in the in the middle of your thought process but when you say you're going to be going through these inner rings i understand that but walk me through how like what do you do when you're at ring number two like the the second inner ring like how to what information from the first ring is gonna suddenly be relevant to you um well i know based on the outside ring which ones they're touching okay and so i'm gonna use the computed edges this is actually gonna be recursive i actually don't need a for loop here because the okay this is really hard to say in words what i'm doing can you see my cursor um in the scratch pad yep i do so like i'm literally going to touch this row yep then i'm going to touch this diagonal column then i'm going to touch this diagonal column then i'm going to touch this so that's what my first pass is and then my second pass is going to be this yep this this and then this yeah so the sort of like perimeters of the squares yeah there we go i got that so that that's not that's my jank algo but but again it's like let's say you are at i don't know this one you see this one here right in the second uh row what do you what do you do from here because you see that it's so one how does this sort of like help you get to the outside you want i have i have everything stored in edges right yep so i'm going to look at my edges map and i'm going to say is this an edge is this an edge is this an edge well actually it doesn't help me downwards wait is this actual trash then oh i'm gonna have to do this backwards oh this is disgusting actually this doesn't work at all you're right good thing you're stopping me now i was gonna go down a really bad path it's not necessarily not necessarily bad but like there might be some you know quirks about it that make it you know not really lead you to the outcome you want all right am i literally just going to compute a graph all right screw it we're going to compute a graph this is just a graph problem why am i using this so what walk me through what you meant by a graph because you made it sound like like a graph was super complicated but but walk me through it alright so this is what i'm thinking graph wise is i'm just going to basically i want to see which like the ones that are touching each other and yeah i don't care about zeros here all like my first thing to compute the graph is just going to be the the the edges are ones that are adjacent basically yeah and that's how i'm going to compute my graph and then after i compute my graph i mean that's not too bad i suppose all right let's start there this is the right approach i'm pretty sure so we'll just do a graph i didn't want to touch graphs because graphs are a little gross slash i like forgot we're gonna like do graphs on the spot here okay um so do i want an adjacency list i think i do oh you know what this is a matrix i bet i'm supposed to use the graph representation of a matrix but i totally forgot how that works so we're gonna do an adjacency list so that's gonna be a little jank all right so we're going to loop um i still care about this 4j [Music] call actually this is going to be value and and sorry ben i again don't mean to interrupt you because i know you're in your thought process but the graph what are you going to use the graph for so like let's say you have a graph that yeah what maps like one one two to its connected ones or something how does that help you um basically i'm going to do a depth first search of every graph um and then because so like that's the other thing right these are all disconnected graphs so there's going to be an array of graphs i guess now that i think about it so for each graph i know if it has like a one that's on the edge and then i know that entire graph is connected so e each graph represents effectively one cluster of ones yes or or one island i see so like this oh let's go up to the top so like this would be an island or would be part of the graph you yes that this entire block thingy here would be an island this would be an island minus the zeros and then for each island i guess you're right why i don't even technically have to do depth first search i just know that the entire island is good maybe this problem is actually easier than i thought because it's actually okay okay i think i know what i'm doing closer now because i know if at least one like item in the graph is an edge then the entire thing is good slash right so all i'm looking for is a graph where none of the ones are um edges and then i remove it that's all i'm doing okay i see and so just to re-clarify when you're saying the word graph here you're effectively saying like a cluster of connected ones or a group of connected ones right so yeah my graph is connected ones okay and how are you representing them like here you have an object like what what are you storing or dictionary in python what are you storing in that so so adjacency lists i remember there's something like this they have some key and then they have the list of edges that's all i remember so i think what that means in this case is this is going to be an index so like zero zero for example because that's going to be like where one of the ones is yeah and then it's going to have a list of all the edges oh you know what i guess this is not this is a so i was thinking of directed graphs you know where it's like one edge points to another i guess in this case they're connected both ways so i have to actually set it up both ways we'll we'll set it up like that but anyway so like actually let's take this one down here since zero zero isn't connected anything so in this particular case how what i'm thinking of representing this as is we have zero 1 2 3. so that's going to be 3 0 points to 3 1 and also points to four zero okay so that's what i was planning on representing at my adjacency so i have two questions for you here okay one do you think that you need to create this adjacency list or do you not already have a graph within this matrix just by nature of having like a two-dimensional array um you're 100 right that i probably don't have to make an adjacency list specifically because you're asking me i did i know i definitely don't need to make an adjacency list okay enough that that was perhaps a bit of an obvious question but i suppose like what you wrote here right three three zero pointing to three one and four zero you have that all right right this is a graph you you gave me a graph i just have to remember how to use a matrix graph well how how when you are at this one the three zero sorry i haven't highlighted it this one three zero you can access three one and four zero directly right right i mean okay we could we could technically do like a little depth first search at every okay why don't we do that okay that's kind of spicy okay so like every time i hit a one that's on the edge i depth first search it that's what it might that might be a little bit that but that might be all you need exactly that might be all you need right yeah okay okay let's start there then and to be clear it's it's not that you don't need a graph it's that you already have a graph i already have graph yep okay good you're right thank you for reminding me how to use magic graphics matrix graphs i i don't remember them at all okay so so yeah so i'm going to literally depth first search every time i hit a one is my plan okay so sorry i'm gonna go back i literally had the enumeration already set up i don't know why i did do i care about a new braid anymore i think i still do all right if value is equal to one sorry i've been in elixir land they put due at the end okay yeah i was like is this some new playthrough no i don't know i caught myself okay so we got value is a one this is where i'm going to depth first search and so now what i need to think about is i already know whether it's an edge here really what i care about is seeing all i don't i don't care that this is a one actually i care about if it's a one and it's an edge then i want to do my depth first search so actually that's what i want to do and again wait to use the terminology because edge is like terminology and graphs right right say edge you mean you mean border here yes okay border as well as used instead okay so yeah if i find a border one that's when i start depth first searching um and we'll call this border islands okay that's probably a better name all right so now i need to detect if it's a border and i know it's a border if i is equal to zero or if i is equal to the length so actually let's create a new function up here def is border beautiful crap i'm gonna put dues everywhere all right we'll do pass and the only thing that defines whether it's a board or not is the two indexes i and j so that's what we're passing in so is border i j all right so if i is zero or i is equal actually we need to know the length of the row so row length call length okay and it's going to be row length so what i was trying to decide there for your millisecond was whether this was zero based and i should minus one here but we're going to minus one when we pass it in i think okay sure we're going to return false and obviously we do the same thing with call which is j so if j is equal to zero or j is equal to call length by the way are these always square matrices uh no they are they can be rectangular but they can't be weird shapes okay so it's correct to have a two different row and call lengths yep okay all right so this is going to be the length of row and this is going to be the length of oh you know what i'm being a plug i think so this is so iterating through that that's going to be a row okay so it's going to just be matrix length now i actually think i'm supposed to inverse these this is yeah i i need to decide whether i am switching these two or if i'm keeping them the same yeah this is this isn't the most interesting part of the code so yeah like here yeah should be matrix matrix and and here i think i do believe you have off by one errors since you did your oh i'm gonna minus one yeah okay yeah yep um so if that's the case i actually think that's fine now um so now i do so now i know this is a border island so i can stick this in here if i want to um i don't remember how to use f strings actually i think i do can i can i just do like this some python people are going to laugh at me to be honest i have no idea i would personally just do like i dot string or or str parentheses i don't even know how you convert things to strings um i think i think this is the right syntax but i'll play it safe and we'll do that okay i'm gonna trust that this works and i guess we'll find out later if we can run the code no yeah this one this one definitely works all right it's gonna be true that's gonna be my border island um and now i need to find everything it's connected to and tell it it's a border island as well all right so we'll create a new thing up here um we'll call it rec for recurse and i need to pass in the matrix we're going to be i j oh my gosh i have to pass in my border islands too we're about to find out if things are passed by value or reference in python i think i'm gonna be fine though um in python you are passing by um you you're passing the actual entity okay i i thought i was gonna be okay but you never know these days you're not making copies of border islands at least not right now i want to make sure like when i put in some values in here that you know that actually retains because we're going to do stuff with border islands later and then we're going to print out border islands just to make sure i'm remotely on the right path here and then let's do my recursion all right by the way super quick pause then i'm just restarting my camera if you want to do the same okay okay i'm back to being good i'm back to being good as well carry on with the interview okay yeah um now i just basically need to look up left right down and if any of those are ones i stick it inside a border island so um i guess here's how i know we're done if you know what i'm not going to do it like that i'm trying to decide how i want to do error detection all right this is going to be my i hate when i do this all right so basically i need to do this right oh we're going to do like this actually so 0 1 these these are all my steps so i'm gonna do four steps um that negative one have you seen this before by the way no i'm not sure what you're doing all right so these are all the different um i guess you'd say like up left right and down so so here just in the interest of time uh ben why don't we do because here you're basically grabbing all the neighbors right right why don't you just like write a i don't know get neighbors function but you don't have to write it immediately because i know this is like the annoying tedious part of the thing um basically they're clement i'm gonna for loop this and we're gonna be like four step and steps and we're gonna like you know neighbor here is gonna be matrix oh whoa i've never seen this yeah so yeah you need to and i i'm gonna get real crazy here i don't know if i can destructure this actually should i make this tuple i think you can destruct you can do stress can i destruct your arrays too i actually i don't know i don't know maybe do them tuples if you want i think you can oh yeah okay i i think i just broke okay i just broke your editor i'm gonna just refresh real quick okay i'm gonna refresh as well all right all right i'm back well minus one that all right we go actually screw we'll do it nice and big all right yeah so we're basically here um so here we're going to say um i x uh jx for you know what's being changed in steps and this is going to be new i is ix plus oh that's so kind of you wait no no i have to destructure like this then right yeah am i tripping okay i think even before you had to do that but just keep keep writing what you're doing okay um i x plus i new j it's like that and then um i have to do it up here is okay i showed you an is out of bounds function nah we'll just write ourselves we're just we're plowing through if n is equal to if i is less than zero or nj less than zero or n i is greater than the length of the matrix um yeah yep no actually minus one yeah i may be having off by one or i think mj is greater than matrix i'm gonna like do the assumption that there's at least one row in this i think that's a safe assumption sure we'll let that slide for now yeah i will let this slide okay okay well i can add like a little if statement at the top if we need to wow this is a beef if statement look at all the stuff you're making me do okay so that's that's why you do another that's how you do a helper function like you suggested earlier sure but i'm just in the mode you know okay so we're gonna continue if that's those are all bad okay um and uh now we get our neighbor which is equal to new i new j and then if neighbor is equal to a one then we're going to stick it in border islands and we're gonna do our dot format new i new j and then we recurse again yo this is a nasty problem new i new j matrix border islands okay oh i was literally about to save the html page there okay so that's wreck i'm trying to think if we need to return anything from rank i don't think we do i think we're actually just good here okay let me we'll pull that down all right i want to just run this and actually see what border islands prints i don't think we have an infinite loop because i have if statements in here this becomes part of the island yeah okay i'm gonna run the code okay um i failed the one and oh it doesn't like key error 14 um oh this is oh you're right i didn't put true you see what i did wrong i didn't put true online online where are you there you are oh right because you're storing in a dictionary yeah maximum depth exceeded are you kidding me i definitely thought i was gonna be oh you know what oh that's so disgusting we have a cycle you know that's what we have right yep because you are revisiting the same yeah the same neighbors ben all right so i should just see if it's already in the border island so if nay and if new i okay wait so border oh right right so this is i should build my key so if key in border islands then i recurse right so you're basically using the border islands as the same like both as a sort of um already visited data structure and as your border islands exactly all right i think we're good i looked at it and there's stuff in it it kind of looks right so every time i come across the one and it's not in border islands i'm just gonna kill it so so if value is equal to one and not um in border islands not so we have to build our key dot format i j yeah um that means matrix i j and i'm just making it a zero right and wait why am i returning an empty thingy am i not recurring matrix or is this like an in place you said yeah you should do it in place and before you run your code because i think you you finished your for loop here before you run your code why don't you just like let's re-walk through it once to just see like are you confident that if you run it here it will it will work right okay so this is like top level what we're doing here so one i'm keeping track of everything that is a border that's what i'm storing my little border islands and then we're looping through the entire matrix until we come across a very important value which is one and that it is a border because those are the only things that we care about and one if we know it's a border we're adding it to our border islands but then we like once we have made this a border we then have to check all the ones that are borders next to this and so that's why we're you know doing recursion and then we recurse this is my little algo to check all the different neighbors instead of doing four if statements you can do this and you do a for loop it's my preferred method i really should have stuck this this this by the way could just be wrong we'll see in a second um but we're just making sure that like if we're on the edge we don't go over or sorry if we're on a border we don't want to step over the matrix and get a problem yeah um we're just checking if the neighbor's a one and if it is then we know it's next to a border we're sticking in our border islands and then yeah we recur again if we don't have that key already is that right though yeah no i think that's good i think that's good i'm pretty happy with that and then after i've stuck everything in border islands i know all the borders and so i'm just killing the ones that are not in borders by reiterating through the entire matrix exactly and then this is literally just how i'm this looks a little weird but this is just how i'm getting the key of border islands okay and perhaps if you want uh then again before we run the code because in a real interview you you might not be able to run the code if we were like in a google doc why don't we try to cause i i do think that your algorithm seems sound why don't we try to clean this up a little bit because you said there are a couple places where you could maybe just like clean it up okay okay okay and it might make it easier to debug after uh he's getting a little bit worried he's not confident in my code all right so we'll do um we'll add once for this beefy thing here which is just like is safe is outside matrix is basically what i'm asking it um and you could say new i new j matrix are the values that i'm passing into that oh ben you're you're killing me with the with the inconsistency with your is border parameters that are basically the same as as this well you know why i'm doing that right so i don't have to rename it because i have new i here and new eye there you know i don't i don't know my highlight okay i actually kind of do it i think i can do like percent all right i don't know if your percent vim thing works all right just just for you okay it won't take that long you're overwriting words in in a single like you're doing some sort of vim magic here yeah yeah that's the beauty of m right there so i think this is now is outside matrix we're gonna return true okay return false and then is nice as auto completion um new i new j and then we're going to pass in our matrix so if it's outside the matrix we're going to continue that looks good i really hope i don't refactor and just ruin my code even more and then we'll add one other thing this is going to be um border island key so this is for generating the key for the dictionary okay and i'm going to just be passing in ij and all it's going to do is it's going to return dot format rj okay and then we can now get rid of this bit if we wanted to okay and you can probably uh use it also down there yep and basically every actually i probably shouldn't search and replace it oops there we go i saved the file again and yeah okay i think that's that cleans it up quite a bit i mean we don't need this none of these comments were remotely useful i can kill those okay yeah i'm i'm pretty happy with this i'm just running it i just ran it okay looks like there's an issue with your code are you kidding me i told you this is a god of refactoring yeah you forgot a colon no this one what line was it on line 25 okay and just a colon after that yes yep yep okay so um oh i got some right okay you're getting you're getting 11 out of 15 so this is actually the worst possible situation it is actually you'd actually rather get them all wrong all right so one thing that you can do is if you look let's click like for instance test case number one click view outputs side by side and you might be able to see the diff of where they are different oh what the heck this just like took over my full screen okay i see um oh this is such a weird view alright so the left is oh i got rid of that one interesting all right all right i've had enough of this view i assume i just hit escape you can just close the tab it's a new tab okay so there there is there must be some small bug in your code why don't we why don't we just go back through it like why i i bet no i think i know it it's probably something i i'm wondering if it has to do with this one what line uh on line eight i wonder if i janked this one up all right so length of i matrix um if it's greater than that then it's a problem okay okay this is just for kicks okay okay so what let me just see if there's a pattern to the things that i got wrong so the first one i got wrong is it was missing on the left side and actually it was missing down to our hotel in the in the first one in your codes output you you remove the few ones that were connected to a border for whatever right which means my and and notably it's they're in the inside of the border like they're not on the outer level which means there's something wrong with my recursion that's that's why i like immediately went to my recursion thing it's like the left and bottom now if we look at like test case number four um i'm going to go to the disc because it helps me so our codes output you removed two one you removed um yeah again that was connected in the middle yeah i did it basically just a straight rookie mistake here um so you see how i literally i i'm not i'm not i'm only recruiting like i'm only doing recursion once i see what my problem is it's on line 29 31. okay you see how i literally stick the key in border islands and then i ask if the key is in border islands not so this is this is always false i'm never done yeah so that was just a pleb move really what i want to ask it is um what do i want to ask it i i mean i should really do i think i should do it up here in the neighbors if neighbors is equal to one and um we're gonna move key up here and not key and border islands so i think i just need to move up my thing i think i always recurse here all right i'm feeling good yeah i just jammed it yes because you were you were checking the visited in the wrong place you have to check the visited immediately when you check uh that it's a one but not when you're not after you've already set it as visited otherwise it will never recurse down that path right yep so i basically uh my my case for not doing recursion i need to check in a different place up here higher up yep okay well listen then we're there in the we still have like about eight minutes let's just do a couple more things like are there any places where you think that you could again clean up the code like if you were looking at it you know just to see um i mean i could probably think of a better name for border island key though i mean it's pretty deep like it's decent i'm like i'm happy with it border islands i probably could give a better name um as far as like i don't know this is pretty i'm pretty happy with my work here yeah this looks this looks decent yeah this wasn't like a trick question or anything um no yeah i mean i'm just i'm just going over the code now one of the things that for me like is striking but it's a small thing is just like is border and as outside matrix have the exact same or they in my opinion they should have the same function signature because like you're doing very similar actions whereas here oh yeah yeah i just decided to put matrix in there yeah yeah one or the other to me works better um right i could i could i could have just done this here for example yeah so let's just show them real quick so i could have done this and then i well this is going to be gross now let me undo uh row length and i basically do what i did to compute the row length inside of it just a little bit it would just be one of the matrix um minus one yeah no you still have to do yeah yeah i equals you know my brain's fried after doing way too much thinking and we did matrix zero here i think that's all i needed minus one again oh right right good catch and we'll get rid of this one of me wait one of the matrix okay actually you know what i this is i got like two caught on my little graph theory kick because it looked like such a graph problem i should just treat it like a graph matrix and pretended i knew how those worked yeah i mean it's funny because like if you if you just take a step back here just for the like i guess the feedback that i'll give is like you your very first intuition was correct like this is a graph problem to some extent and you are traversing that graph with the first search that's like the most intuitive way to to solve the problem but you don't like just because it's a graph problem doesn't mean that it needs to be like complicated you already have the graph and traversing a depth for search is just going through the neighbors up left uh right and down i guess uh one question that i that i could ask you is like what is the the time and space complexity of your algorithm and do you feel like there's a way to optimize it are you comfortable with the solution um there may be a way to optimize it because we're literally doing recursion on every one but i think it's pretty good so i mean one we're doing o of n squared because we're going over the entire matrix and then yeah inside the matrix and there you go um why why another oh sorry sorry i just meant to put one yeah and then inside the actual so like we're calling this rec function inside of double for loops so we then have to compute whatever the space complexity of rec is which i'm pretty sure it's some logarithmic thing we're doing a for loop of steps so actually that's constant um i'm not sure how i mean okay the worst case scenario of recurse is we do the entire matrix again like we like we do the entire matrix exactly so you so basically and since you have your visited checks right your you check if it's in already a border island and you don't revisit it you're actually never going to revisit islands multiple times right right oh i guess so okay okay so i loop through this like let's pretend these are all ones all right it's not really easy i was gonna do a search and replace but that's one one one one so this is what i'm thinking about is if the matrix was entirely a sheet of ones right yep so i would mark the like the outer thingies as no i'm pretty sure we would still i'm pretty sure this is like we're multiplying this times an m or n at least because we're going to be recurring and when we do recursion we're going to touch every one yes but only once the only thing is like maybe to make this more clear what you could do here but this is purely for to make this overwhelmingly clear here you could say like on line 41 you could say if um how do you check if it's in border if bored i guess let me do this if border island key ij if border is in border islands then continue and you will you will only like you would start at the top left corner right you would mark this as a border island you would recurse through the entire matrix because let's say they're all border islands and then for every single other one you just skip them like you you would traverse through them once but you would skip them immediately on line 41. so it's like a plus and and then we just kill the that and then you kill it and then figure out the second loop here 46 to 49 same thing um you're just reiterating once through the entire matrix but that's like fine so it's like two times nm which is just it simplifies to the same thing what can be tricky about this type of algorithm to come up with that space complexity or time complexity is like like you said in the recursion here um depending on where you put your your check to not like re-recurse you might feel like you're doing way more work but even there at most you're just revisiting four neighbors but then stopping right so it's like at most for every key you're doing another four extra operations it's always gonna be constant that's constant with the input exactly yeah that's good all right well listen then i think we made it in time good job um i think that like uh yeah good job i mean at the beginning there was a little bit of like confusion and i gave you a few hints to to lead you in the right direction um thank you for holding my hand but i i think i still think that like i think you had you had the right intuition and um the code this is like a relatively difficult thing to code out in full um and it's certainly more difficult if you can't run the the you know input output um but you had very few sort of like genuine algorithmic mistakes except that one recursion that one recursion thing without yeah this would have been hard to catch without running it yeah the thing like the missing colon on the if like we that doesn't matter well yeah that's uh yeah but and everything else was with sound this was the only thing and that would have been tricky to to catch would have been interesting like you know if we had we been in a google doc i would have had you you know walk through line by line and maybe we would have caught it there um but yeah good job so did you watching it did you catch this by the way um when when we were doing it no i didn't catch it immediately um but i maybe maybe i would have caught it if we had kind of like walk through it theoretically if we're both in google docs you could have just thought i did it right too so i kind of who do you need that it it can't happen but again we would probably have spent a little bit more time um looking through it but yeah it to some extent it can happen that's why it is very important though to to communicate and i would have had you like walk us through a couple of examples like walk you through the sample input and to be honest the sample input would have failed right that was one of the four test cases that failed right so we had we walked through that line by line uh or you know you had like run the algorithm on that it would have failed so i mean this one's kind of disgusting to do manually because it's just so fat it is yeah it is but you can you can just try going at like the islands right good ones you would have probably seen that like from this one you'd have gone there and then you you would have seen like oh wait i'm not like based on my code if i if i hit this this will always be true and i'll never visit it you know yeah but cool all right that concludes the medium difficulty mock uh google coding interview ben um overall here i think like if we were in a real coding interview i'd probably give you some somewhere between between like um i don't know a leaning higher or higher something like that um like there there weren't any you know huge like mistakes so even even though i was like totally in the wrong direction at the beginning that's this was enough like i recovered enough to get leaning higher i would say like leaning higher because like you know and i would have to go through like the rubric um i could go through the rubric right now of mock interviews we have a rubric but like let's put it this way algorithmically i did give you like a decent amount of hints and you were going down a few paths that seemed yeah i was really looking to get like you know borderline pass at most so again like i think leaning higher is probably the fair you know i tend to be i tend to be a little bit nicer so i don't want to like you know i don't want to be i don't want to be like strong no higher but this is not a strong no higher this is a leaning in my opinion so either a leaning higher or a leaning no higher again the reason is like the algorithmically i think you were you were in that middle thing of like uh you know if they're if they're four scores you were probably like in a somewhere between a two and a three because i did give you quite a few hints and i was gonna make an adjacency list yeah and the adjacency list i don't think would have brought you anywhere at least not in the way you were doing it um coding wise i think you were able to transcribe your algorithm into code very well and you were able to clean it up where you know when it made sense so coding wise i would give you between like a three and a four four being the the maximum um communication wise i'd say you were pretty good at communicating again at the beginning maybe not i had to push you a little bit to kind of walk me through the adjacency list and all that and like the edges and border you got to be careful with that right if you're talking about edges in a graph like you know that can be confusing but so communication probably between like like right around a three and problem solving i think your problem solving was pretty good you know you you did like think about how you could go through a graph how you could um you know depth first search um you added a little bit of color by saying that some of your algorithms were trash which i don't know if that would be super appreciated in a real interview but you know you like my steps thing though right that was that was really nice your steps thing definitely wowed me and so that pushed me over you see the steps thing is what pushed me from a lot from a leaning no higher to a leaning higher okay excellent i'm going to keep that in for my next google docs but seriously again in all in all honesty i think that you did a pretty good job and um to anybody who's watching especially for someone who as far as i know you don't really do like you have you don't practice coding interviews these days um yeah no that's why i was like i don't remember adjacency matrix things at all that's why i was like let's put this in a list um but yeah so um good job and uh maybe we will do a third interview that will be of a hard difficulty so to speak uh another time cool all right hope you all enjoyed that uh we are about to do a react interview on ben's channel he's going to be interviewing me for an intermediate level or medium difficulty level um react interview so wish me luck the link will be in the description in the comments below and otherwise don't forget to smash the like button subscribe to the channel if you haven't already follow me on linkedin and twitter if you enjoy short formatting content instagram if you like pictures and i will see you in the next video

Channel: Clément Mihailescu

Views: 369,776

Rating: 4.9020386 out of 5

Keywords: google coding interview, google coding interview questions, google coding interview preparation, coding interview google, coding interview, coding interview questions and answers, mock coding interview, technical interview with a google engineer, algorithm interview questions, real coding interview, google software engineer interview, google coding interview with ben awad, ben awad, medium google coding interview, intermediate coding interview, medium coding interview

Id: 4tYoVx0QoN0

Length: 51min 27sec (3087 seconds)

Published: Thu Jun 10 2021