Acing Google Coding Interview as an 18 year old High School Student

[Music] what's up guys as you might know Artie I'm a competitive rammer and competitive parameters are the best that yes you've guessed it right solving algorithmic problems especially those from coding interviews if you don't know what competitive programming is then be sure to check out my channel to learn more about it so in this video I did a mock Google phone coding interview with Clement Clement is an X cool engineer and X Facebook engineer and a co-founder of algo expert he has a YouTube channel about software engineering and he also made another mock interview video on this channel which simulated an on-site whiteboard coding interview with a harder problem so be sure to check it out his channel by the way if you don't know what Jaco expert is be sure to check it out because it's an online platform they'll prepare you to ace coding interviews go to the algo expert Ohio - tmw and use the promo code tmw to get a 15% discount on your purchase be sure to LIKE and subscribe and enjoy the rest of this video hey William how's it going everything's fine how about you good I'm excited for this second interview that we're doing here are you excited yes I am alright so we are gonna put 45 minutes on the clock and I'm gonna start the timer now and then I'll give you the prompt sounds good yep I'm ready to start okay starting the timer now so for this interview we are gonna work our way through at least a couple maybe a few different problems that are that are all sort of related and we'll start out with something perhaps simple that you might already be familiar with but imagine you have a binary tree so I'm gonna paste here an example binary tree that's rooted at a node with value 1 we define the depth of a node in a binary tree as the distance from that node to the root node or in other words how many edges you have to traverse upwards to get to the root node from that node to like the depth of the node with value 8 here would be 3 the depth of the node with value 1 would be 0 as the root node does that make sense yeah so I want you to write a function that is gonna take in this particular binary tree for any binary tree and it's just gonna return the sum of all of the node depths in this binary tree okay so in what form will the binary tree be given so so imagine you've got a class we've got like a be a binary tree node class if you want you can just call it node and it's got a value property a left property and a rights property and the left and right ones are gonna point to the child nodes or like the null value and the value property is gonna point to an integer okay so the some of the paths if so call this son that's and then I'll be given to root right yep so OH what I'm going to do is I'll keep out the f first thing I need to do is find that that's of all of the nose so in order to do this I'll just start a DFS from the top node and then in the DFS function I'll pass in the node and also the death of the current node okay then each time each time I go down one level I increase the test by one so okay so and so so for each node when I DFS on to the node I'll know that that's one node and then what and then in the DFS function I also add the depth of the node to a global variable called answer okay so guess I'll just write the code now yep sounds good so I've cancer and then initially the answer is zero and then we also want to we can answer in time and gladly do our DFS and we start from the root node and the root know starts from a depth of one so he called DFS call up DFS root 0 then our DFS function note you and I we have that's the node okay so once you have the death of the node we'll know the depth of note U is here so we'll just add it to our answer okay and then we also needed DFS to the left and the right all children is there any so first thing I need to do is check if the left and right children actually exist so in in C++ I think I can just do this oh by already yep okay oh this should be a reference so and you don't have to stop sure and then if the left child is not note then I'll do a DFS on the left child you know add one to the test because that that's the distance from the root in pieces i1 and yep do the same thing for the right child and yeah this looks good to go okay yeah I think this this would work on on the binary tree so this was sort of like the the introductory problem here now let's assume we wanted to up things a little bit wanted to increase the the the amount of stuff that we're looking for so here you calculated the sum of all the node depths in the tree rooted at one right yeah now let's try to write a function that is going to return the sum of all of the sub trees in this binary tree in the in the input binary trees all of the sub trees sum of deaths so like in this for this particular binary tree your function your some deaths here would return I think 16 that would be the the answer right now imagine we were also looking for the some of the depths of the binary tree rooted at to the binary tree rooted at 3 rooted at 4 at 5 at 6 so of all of the sub trees and we want to add all of those node depths ok and the answer for this so for the second problem let's call it prompt number 2 but we're using the same input binary tree for the sake of the example the answer would actually be 26 you do you are you understanding how I'm getting or computing this 26 oh yeah let's just like go through I'll just like calculating myself just to be sure okay so something would add to as as a 6 and such for you that 3 has 2 that makes 20 forward and just up she would ask for has 2 so so it totally adds up to 26 yeah I get what is it yeah yeah how about I'll just move this part to the top sure yeah mmm ok so think Oh since like a tree is like kind of a recursive structure I think maybe if we calculate the sum of thefts in the sub trees of 2 & 3 you might be able to use that information to calculate the sum of deaths for the entire tree tree that one ok ok let's consider what happens to the that's when we move from we Mahony moved a root from 2 to 1 so when you move from 2 to 1 the depth of all that's of all 5 nodes in the subtree of 2 are increased by 1 okay okay so and then somebody thing happens for the sucker you adapt D so when we moved a room from three to one all nodes in the subtree of roots three are increased by one yep okay so in order to get the new some of depths we can take the old some of deaths of the left subtree add that to the oldest some of deaths of the right subtree and then in order to fix the fact that we moved a route to one we should add we should add to that the total number of nodes in the left subtree and the total number of nodes in the right subtree okay okay so in my DFS function oh I might say so for my DFS function I'll return two things so um I'll just make up hair is so DFS and I know you and then I don't know if I need to test right now so I'll just leave it just leave the parameters like this right now so so for the peridot returns so the first element the pair will store number of nodes in sub C and then the second element of the pair dies returned will returned some of that's in the subtree at you okay okay and then and then so let's initialize the result in the BFS function so so initially the pair so the number of nodes in the subtree of you if we don't consider the left subtree and the right subtree then we only have one node which is u itself so number of nose starts at one and then the sum of deaths will start at zero if we only consider the node U and after this we'll consider the left and right subtrees if they exist does it make sense so far yep okay so so now we'll add the sum of deaths of all of the nodes in the left subtree of U so let's call this P child and this will be returned from the DFS function when we for for the left child okay and then and then we add the sum of deaths of all nodes in the left subtree so initially we add the original deaths but then there were gional attempts to get increase it get increased by 1 so the total increase is the number of nodes in the left subtree yep q doctors we add the organelles already know yeah there was you know some of that and plus the increase which is just the number of nodes then that will give us the new sum of deaths when considered by the left subtree of U and we also need to update the number of nodes in the subtree of U so do that we just add the number of nodes in the left subtree of you is this far right this part does it make sense so far yep and so now to support the left subtree and we basically do the same similar thing for the right subtree I think we just need to change this yeah I think it's all right now so this DFS function will return oh yeah and you also need to add it to the answer so store story total variable called answer and then after I calculate the sum of the deaths for the subtree of you I had that sum to with the answer so add the second value of the pair okay right this is for DFS now for the entire program I'll just have something similar to the one before this call some death and then node starting from the roots yeah bicep answer to zero they call the DFS function for the root and then I care and answer and yeah it just looks yeah this looks pretty much it can you just quickly walk me through the example here at the top conceptually like if you were to run that function okay so so first of all the we call it the FS on the roof and then the DFS on a route calls like all these so all of the children and so the first notes that return any values are the bottom those so yeah the leaf-nosed eight nine six and seven they don't have any left child left children with my children so they'll just return to pair one zero so these three and five oh yeah inside yep okay and then after that let's look at four and three so four and three they initially start at 1 0 then when we look at the left sub-tree oh let's look at left sub-tree so they the second value of the pair is added with the both values in the subtree so one is added and then the first audio of pairs added with just the number of nodes in the subtree which is 1 and then that's when we process the left child I'll just once you process the left subtree 1 0 becomes 2 1 and then yep prosit survive such becomes 3 2 so the value of the pair returned by 4 & 3 is 3 2 yeah okay so now let's look at no.2 no.2 also starts out with 1 0 and after the looking at the left subtree which is 4 ohh firstly added to the second value of the pair we add both numbers so comes 5 and then you also add the number of those so then comes for now we move on to the right subtree I suck she is five so for the second value yet we just add one and for the first value we also add one so the Perry turned by a subtree two is five six yep and just to make sure the last thing before I think we can move on here can you ReWalk me through how you got the five here okay so in order to update the second value of the pair after yep after like a processing the left subtree I add the sum of thefts of the left surgery and the number of nodes in the left subtree so left sub G is 4 right so the sum of that is 2 and the number of nodes is 3 so I add 2 plus 2 which is 5 into the sum of that yep ok cool so listen I think I don't think we need to walk through the rest of the of the tree I think we we we have the idea here let's move on to something completely different ok oh yeah can you hear me oh I can you repeat the last sentence yeah so I said I said I think we can we can stop going through this example I think this makes sense and let's move on to something completely different okay sure so let's do I'm actually gonna copy paste another example I want you to imagine that we had or actually you know what let's let's just work off of this binary tree we can just work off of this one so we have this binary tree here we've we've so far been able to calculate the depths in the binary tree the depths and all the sub trees right now what if we wanted to calculate the distance of every node not to the root but to another node so for example I would give you like the node with value 3 and I would probably give you the root node of the binary tree as well just so that you you have the entire structure and I wanted you to return the distance or the sum of the distances of every node in this binary tree to the node with value three or two whatever you know second note I give you okay so each node will have a different value right value is in like the the integer value yeah but you could imagine that I would give you the axial reference to the node oh okay but so as an example like if we were to call this function with the root node as like the target node you know there's a target node the the the answer that you'd be looking for would be the the no deaths just uh your your first question right the distance of every node against the root node and you sum up those distances but now what if I give you as the target node like another node not the root node so the function will look like this like this yes yep okay and the root in our case is always like with the example that we had above is always gonna be one for the node ID in yeah the the root node in our example is always gonna be the the node with value 1 okay okay so and I think I need to think I need to maybe I need to pre calculate some information for use of it knows like maybe okay one DFS won't be enough so I'm just wondering can I do can I create like more am I allowed to like add new variables into the node class totally well let's allow that okay so so first thing is and you could you can almost assume that like to your question if you wanted to you could you could first transform this entire tree into a tree that fits you or that you prefer right and then you kind of do whatever you want to do okay so I'll just now I'll just each node will have left right however you value and then you'll also have a also calculate the sum of bests in the subtree of each node so okay I'll just call this sum that and nobody calculate this sum of deaths and you said she can do can use why I just did up here and so that would be our first DFS is to calculate this value sum of deaths in each sub tree for each node okay oh and then for it does for the second part I'm actually I'm actually just going to end up calculating the sum of distances to each node and not just a target node so um what I'll do is I'll start from the root node I know I know the sum of distances to the root node like and that'll just be the sum of deaths and yeah I just need you know wait wait actually okay I'll change this not some of that but just the number of nodes in each subtree okay okay so so I'll say I noticed some of distances for the for each node 2 1 and if I know that then can I figure out the answer for no 2 or note 3 instead and the answer is actually yes because what we'll do is let's say that let's say that the current value is X and then in order to modify to sum of distances notice that when we move the target node from node 1 into mono to all nodes inside the subtree of no.2 or have the distances decreased by one yeah and then all notes outside of the sub C of no.2 or have the distances increased by one yep all right so so so in this case some some businesses from for target no two can bypass as sum of distances from one - number of nodes in sub C of two because all these nodes have their distance decrease by one and we just add the number of nodes outside sub C - since they're the sense they object in distance is increased by one okay okay so so in the second BFS I'll do is every time I've every time I call from a parent to a child I'll use this these two pieces of information to update the sum of the distances and in this way once I DFS onto a certain node I will note that knows sum of businesses to every other node now can you walk me through your logic for this sorry I understood what you just said um and I understood how you found this the son of distances for two but can you walk me through this same logic for like another node in the tree like for instance let's say we went in with a node with number five as the target does can you walk me through this logic okay so so first we so DFS will like first go to one and it will go to two then I'll go to five so so now you know what does it go from what to go from 1 to 2 we already have this formula and now we need to go from 2 to 5 and we can use a similar formula as well so sum of distances for 5 is equal to sum of distances for two - number of militants judging 5 plus member very odd nose outside subtree size and I see so you're you are basically when you find a node like node five you you go to its you treat its parent as the new like root node kind of and you apply that that function on that parent node mmm okay he didn't just to clarify for for this for here some of the distances five um okay let's say we had gone with fire with eight so imagine I'm gonna type out something here and I think we had done some of this of eight what would you what would you do here I just let's just look at it's all so first of all the DFS well the FS will visit all nodes and then yep well eight is the only one we care about so how only goes through knows one two four and eight so when DFS from node 1 we have this value Rd and then and then what this sorry from one week DFS to two and then using this formula we can calculate the sum of businesses for two and then then from two we DFS to four and I using a similar formula we can find the sum of distances for four and then starting from and then we DFS on to note a now we find that node a is the target node that we want so then we just then we'll set the answer to the sum of distances for eight and the formula would be some of this on for - number of nodes in subtree in subtree there would be no subtree here oh they'll just have those just be like no yeah they'll be sub feet eight it was just be the node eight right okay and then plus number of nodes outside your subtree which would be no nine Oh Ashley bead and like the entire tree except for eight so in fact I'll write this formula or you write this formula clip so so if total number of nodes then some distances for some node u equal to the sum of distances for its parent - the size of subtree of node u plus the number of nodes outside the subtree and we know that total number of noses and so in order to find a number of nodes outside the subtree can just do and - s of you gosh oh gosh okay right so you are you are adding not only the the right subtree of the parent but also all the other number of nodes because they all they all have like one more distance to the sum of distances of four yeah exactly or the parent rather gotcha okay okay um just so let's try to code this out okay so start with dancer then for the first so in the first DFS I'll calculate this the sum of no the number of nodes in each subtree and also the sum of distances for the first for the first node so let's see so this copied a function from above so we get the pair from the FS one root and then the FS one will be pretty similar to this okay so so yeah okay we don't need to modify anything in here except alcohol also oh yeah by the way uh I need to remove this answer because that's not what we're looking for and I also need to get that the size of the subsea so I'll just represent the size of the sub tree with SC and I'll and I'll set that to and that's equal to the first element of the pair so after that do you follow along so far yep yep so after that first I can find n which is the number of notes and animals just be number of of nodes in the root sub tree and then okay then I'll just write this various return answers and then we do the DFS two and we maintain the sum of distances for each node and we also just set the answer to the the sum of distances for the target note when you find it so DFS two starts at the root and then sum of distances for the root is just P dot second it's just the sum of that that's because it's a root and then you want to find our target so I'll pass that in as well okay so here I have DFS - it's in the current node takes in just some of businesses for not--you and then also gives me target and then the first thing is if if we if we find out know you as a target then our answer is just the sum of distances for the current node so I'll just check for that then I'll set the answer to the sum of distances and then and then given the information for given the sum of distances for node u we now want to find the sum of distances for its left child and it's right child and we also want to DFS on all nodes in the left subtree and the right subtree so just do this for the left subtree first okay and so in order to find new son this I use the formula back there so it's the sum of the distances of the parent - the subtree that the size of the subtree of the left check of the left child plus yep never of knows outside of the subject which is just n minus the size of the subtree then after I find the new sum of distances I can call the FS 2 on the left child is this part good so far yep okay and then I just do the exact same thing for the right child as well and yeah this should be it cool okay so can you walk me through let's copy let's maybe copy the example mmm um let's copy it down here you copied it at the bottom of the doc can you walk me through but like go let's go through the axle code and walk me through what I've been looking for you know the the distances to four can you read before can you repeat that sometimes it in there was some of it so yeah yeah so can you walk me through all of your code and let's assume that the target node had been like four all right um oh should I go through the fs1 as well because he kind of went through that not BFS oh yeah not the FS one just the main function here and then and then DFS - okay so DFS 100 I caught the FS one get n is equal through the first element of the pair which is just on nine and then also find that sum of distances for one is second all other pair which is it was 16 right yes but so so this is where for DFS 1 are you not using your are you using the solution to your to the first problem or to the second problem oh I'm just I rewrote the DFS one just it's similar to the one for the second problem where I returned a pair and the first element of the pair is the number of notes and the second element of the pair is the sum of deaths okay and but but for but the sum of deaths are you doing aren't you here doing the sum of all of the depths it's the sum of deaths in the subtree of you okay and but you and this the sum of so you wouldn't be sixteen it would be 26 with what you wrote here no or am i am i not following correctly it's not the sum of the deaths of all sub trees is just the sub tree for node 1 okay and here you're doing so in here you're doing P P dot second plus or equal P child dot second plus P child odd first but why are you doing plus P child odd first then here uh in order to update the I think it helps if we look back at there's no closure so and there's no code in order to find the or to find the sum of that's for all sub trees I add the P I've had the second value of the pair for all knows you but then yeah but then here I'm only considering here for P I'm only considering the pair returned by the root oh I see okay you only return you don't you don't add them all up is what you're saying yeah yeah okay okay and so I received this information from DFS one and that's when I start going to DFS too so I do it on node one first and the first summit distances is just 16 and then and then and I pasinetta which is note 4 and this will give me the new sum of deaths new summer distances you'll send it to so it goes to the left child it processes the love child forget to and then set it to 16 - the size of sub G 2 which is 5 and then plus n minus 5 but plus 9 minus 5 this total of 2 15 so yeah just hold up to 15 and then after I find the new sum of distances the FS 2 is called on no to with with the sum of businesses of 15 and targets the same and in this DFS for the left child the news from up distances is calculated to be 15 minus the sum of distances inside sub C for this know the number of nodes inside sub C 4 which is 3 and I add n minus 3 which is 6 and this totals up to 18 yeah yeah and then and then the FS 2 is called on note or with value of 4 18 and 4 and here I have the if statement and sees that the know the current node is the target no so answer is set to 18 and then all all the nodes are called by the DFS to function but I'm just showing like 1 2 and 4 because it's the only one they're the only ones that we care about for this yeah and you would return at this point but in theory would go to or it could go to all the nodes like if your dad like node 7 as the target then it would have told that is what you're saying yeah well my code is actually returns so it was still cool to go to all of them but then it doesn't matter if it visits often all right yeah there's no need to return preemptively um okay and can you walk me through the complexity analysis of the solution okay so for DFS one so for DFS one we the structure is all right so for DFS one just basically go through each of the nodes once so yep the complexity is linear time and then this is and then for DFS too we also go through each of the knows exactly once so it's also a linear time yeah and you're not you're not doing any other like costly computations and times cuz you already have them computed values right yeah I store to sum of a story does sizes of the sub street in the nodes are T and inside the FS 1 yeah and so from a from a space complexity point of view what's it what is this gonna look like is this I think it's this the size of a subtree count as extra space I believe so if you're if you're adding if you're gonna be storing extra values you'd be storing like an extra values basically yeah so that would be all of an extra space yeah and then the the recursive calls are kind of disregarded the because of this and and that's fine um ok and I guess here like um yeah I think that's I think that's it we can we can end here William with like three minutes on the clock roughly ok so that's a perfect perfect timing so where you go through different floor yeah let's do debrief so first of all and you did amazingly well uh-huh spoiler alert just like in the in the first coding interview um so this this coding interview I went with kind of a different approach where I gave you multiple problems that kind of worked on top of each other we're not even kind of like really worked on top of each other in a real coding interview I would have for most candidates only expected to go through the first two problems I would not have expected to go through the third problem you kind of knocked the first two problems out of the park the first one is very trivial the second one is actually quite a bit more complex than the first one but you still got it really quickly and then the third one the third one I think is an extremely difficult question that I would not expect again a candidate to take I as a nail so easily it's also like very hard to to grasp there's a lot of like mental stuff so it's very impressive that you did that without a whiteboard all that to say like just on a Google Doc all that to say that algorithmically you did amazing your communication skills were also really good I didn't get lost at any point in time except that here with the the DFS and that was mainly my mistake because I didn't follow the the lack of adding to the answer or in the second yes I sorry the one that you copy pasted here yeah yeah you you don't add up to the answer here but yeah it's a great job from that point of view and then for the for the coding I also don't have any any criticism like I would have to look hard to find criticism I think you did everything was readable and I think it was good that you thought of I think that you did a very good job I guess going back to this is a combination of the communication and the coding you did a very good job of asking me well what's the structure of the nodes then asking me am I allowed to mutate the structure of the nodes because that's not necessarily evident right some candidates will think that they're not allowed to do that and then it makes the problem a lot harder so yeah well how do you feel that the the interview well I felt that yeah definitely felt that I did pretty well so I'm really happy to hear about your commentary yes your comments as well and I'm curious actually like did you did you struggle with that third problem at all oh okay so let me think so so the first part was like well once I knew I could modify the structure of the note then like I think it was I think I could get it but I just didn't know that details exactly like I I already had the structure of the solution line so remember how I told you about how I was going to start with a DFS on its time from you know I didn't go down yeah I know yeah but then I didn't think the details clearly so initially I said that initially I said that the extra information that I would store in each node was the sum of deaths but later as I think as I wrote out the formula I realized that it wasn't the sum of deaths and it was just the size of the subtree right and I saw that here when you kind of like near the at the top of the doc when you corrected yourself on that yeah um I've done like very similar problems before so I kind of knew the I kind of knew what solution I that would work for this problem but I just had to figure it the details out right right well once again I mean fantastic job this was a pretty different coding interview than the one then the first one we did tonight the first one we did had to do with like graphic reversals this one was freeze but cool yeah great job yeah I think so coming on my channel is there anything you would like to say just that you are like an absolute monster at algorithms and coding interviews or coding problems you know harder ones than the typical coding interview problems we did another coding interview on my channel I would highly encourage everyone to go check it out very different genre and well I've already spoiled it a little bit but just go watch it you won't regret it and that's it okay thank you by the way there's an alternate solution to the third problem in the interview so basically what you could do is you could just recreate a tree so that the root is that the target node and it might be easier in some ways but using this alternative solution you can only find the sum of distances to two target node and not all those so yeah my solution still useful in some way so thanks for watching and I hope you've enjoyed the video and be sure to check out my other videos and subscribe

Channel: William Lin

Views: 2,060,974

Rating: 4.9199853 out of 5

Keywords: tmwilliamlin168, competitive programming, coding interviews, William Lin, algorithms, mock google interview, mock coding interview, google kickstart

Id: -tNMxwWSN_M

Length: 48min 57sec (2937 seconds)

Published: Sun May 03 2020