Google Coding Interview With A Normal Software Engineer

let's see how many times i'm gonna say the phrase a google coding interview in this two minute intro what's up everybody how's it going we are all in dire need of a google coding interview it has been far too long since i've made a google coding interview and so in this video that's what we're doing a google coding interview but this google coding interview is unlike a lot of my previous google coding interviews on this channel i am not doing this google coding interview with an international grand master at competitive programming i'm not doing this google coding interview with someone who's won a medal in the international olympiad of informatics no this google coding interview is with a normal software engineer because a lot of you commented in the previous google coding interview videos that you wanted to see perhaps a more realistic performance in a google coding interview and so this is just that i'm joined by kirti she's a software engineer based in india as far as i know he is not an elite level international grand master competitive programmer hasn't won medals of the international olympiad of informatics and so this is going to be a realistic google coding interview we did this google coding interview on a google doc because that's how coding interviews are done at google especially right now even on sites are virtual so they're done on google doc and the question that i asked kirti is a very hard question that we have on algo experts by the way if you're preparing for your coding interviews and you want to get a job at google or any other big tech company then go check out my company i'll go expert go to algox for you and use the promo code clem clem for discount on the platform we've helped tons of software engineers land jobs at google and all other big tech companies and startups and this question is actually a question that i have asked myself at google in a real interview about a year or two years ago and last thing before we jump into the interview we actually did a second google coding interview on kirti's channel she's got a channel where she talks about software engineering and coding interviews so go sell her some love and check that out after you finish watching this google coding interview i will put the link to that google coding interview in the description and in the comments below and with that enjoy the google coding interview so how many times did i say google coding interview oh and try to solve the problem as you watch the video and comment down below how you would solve it oh and in the last 10 minutes of the video we did a feedback session to cover kirti's performance so you don't want to miss that hi kirati how's it going um are you excited for this interview i'm very excited and very nervous okay well try not to be nervous or try to let the nerves uh fuel you into acing this interview and i'm gonna put the timer on the clock now we're gonna have about 45 minutes and i'll let you know you know when we're running out of time or if we have to speeding things up okay so all right starting the clock now so kierke i want to imagine that i want you to imagine that you are about to move so maybe you're moving to a new location and you want to find an apartment that you want to live in so imagine that you have one street and the street you can imagine that it's on a single line so imagine you know a single line here i'm just drawing i'm just typing a bunch of ones to show that it's a single file line and at each at each block in this line there's an apartment so you can imagine that i'm probably going to give you a list a list of blocks street blocks and at each block or each index there's an apartment that you might want to consider living in are you following me so far yeah okay so you want to make sure that the apartment you live in is really good for you and the way that you're going to determine if it's good for you is if the apartment is close to some buildings that you really value so for example you really value or you might really value being close to a gym or being close to the office or being close to the supermarket does that make sense yeah and so i'm going to give you information about at each block whether or not there's a building like an office or like not a school or a gym and you're gonna want to find the apartment that minimizes the farthest distance that you would have to walk to to get to all the buildings that you value so i realize that i've given you a lot of information i'm going to show you a couple sample inputs just so that you get an idea so imagine the first amp sample input is going to be called blocks and it's going to be a list let me put it like this that um has a bunch of objects you know like you know hash tables so to speak and um these objects have all these buildings that map to booleans so here at index zero you can see that there's a gem that maps to false meaning that at block zero there is no gym but there is a school but there is no store at block one there is a gym there is no school and there is no store does that make sense yeah okay and so then the second input that i'm gonna give you is going to be a list of required buildings if i go a little bit lower here i'll put rex requires or requirements and this is going to be a list of strings and this list of strings is going to have the buildings that you value so here you happen to value gym school and store but i could maybe give you just like gym in school or i could give you just gin right it could be any buildings and they don't necessarily have to be in these objects and so here if you value gym school in store that means that you have to find the block that has an apartment and by the way every block has an apartment the apartments are kind of implied to be at every block you have to find the block that will minimize the farthest distance that you would have to go to to reach all of your requirements and so here for this sample input the answer would be index three which would be this one if you want i can highlight it let's say in a light green here this one because for this one the farthest that you have to walk to to get to all your required buildings the gym the school and the store is a distance of one because the school is right here then a gym is one above and then a store is one below okay okay so can they be only three things that is gym school and store or they can be more number of things there can be any number of buildings and the only thing is that in the blocks at each block you will have information about every single building so for example if i were to add here something like i don't know office then you could expect that every block would have a data point about an office whether it's true or false okay and it will be a valid input so i don't have to check whether all four are present or not right yeah you don't have to check whether all four are present they will always be present okay oh okay so at the top of my head if i have to talk about fruitful solution so i can consider each block to be my solution and i can just keep calculating the distance from them right okay so suppose i consider that i my apartment will be here so if so like in this case i can see that there can be multiple things in an apartment there can be a gym as well as a school right yeah yeah so the distance will be zero plus zero like that so uh i will keep calculating the minimum distance as i traverse the array and uh wherever i find the minimum one i can just return that yeah okay and just can you walk me through conceptually like how exactly do you find the minimum distance okay so uh suppose we just suppose the requirement was just gym and school okay so i come over here i have three the number of variables that are there in requirements so same number of variables so right now i am going to keep two variables that is the distance for the minimum distance for gen as well as the minimum distance per school and there will be a result that i will store that will be the minimum of sum of both of them right that is my minimum result that is possible so when i am here so i will have three variables so one will be distance from gym so gym distance then uh there will be school distance and there will be a resultant that this will have the minimum value okay so here since this is false my school distance will become uh 1 and this initially will be some maximum value say we take infinity or in max and so this is infinity and this is zero right then i come over here okay here uh gym is um here gym is true so here the gym distance becomes zero so since i have traveled one distance so it will become sort of the resultant from the previous one plus 1 right so it will be distance of this plus 1 and then i will keep checking whether the resultant has to be updated or not right so the earlier result was max because it was not possible to read uh to reach gem at all here it so at every point i am just seeing the blocks before and not the blocks after that right right so i will traverse the entire thing once and then check so uh but but it is also possible that the minimum can be from my right hand right like instead of from my left hand it can be from right hand as well so probably what i should do is traverse the array twice one from the left side and one from the right side and then check that what is the answer and just before you keep walking uh down that path here to you just to be clear you are looking for the the minimum the minimal farthest distance that you would have to walk to right because so for example like at index three here which was the answer here the farthest distance that you would have to walk to was still one even though there was a school here which was zero you would have to walk one to get to the gym up here and one to get to the store down here does that make sense can you please repeat that point yeah so since you have multiple requirements or you might have multiple requirements you want to minimize the farthest distance or the greatest distance that you would have to walk to because here if you care about gym school and store school is zero distance from this index right okay but jim you have to walk one to go up here and store you have to walk down one to find it here so the point that i'm trying to make that i just want to make sure you you're clear with is that you it's the farthest distance that you have to go to that you're minimizing not just any distance okay so it is not so okay i understood it wrong i understood that it was the sum of the distances it is not like that it is like farthest for anyone that i have to go right yes exactly it's not the same so even though the sum here is like uh i guess two it's not that that we care about it's the farthest that you would have to go to okay so it will be like so i will have to minimize the max of gym distance and school distance essentially uh yes yeah okay that's one way to put it yeah so i have to minimize the maximum value among the requirements does that sound fine yep that i think that sounds good so uh basically i will have and i can have a hash map sort of thing an ordered map so corresponding to each requirement i will keep the maximum distance right so uh and i will minimize that okay so okay so corresponding so okay i have to keep that okay so for the entire array just give me a second for the entire array for each block i need to uh minimize the maximum distance so for this suppose i have to calculate the maximum distance i will have to so that will become order of n square so now brute force will become order of n square so if i have to for this block i will have to check the maximum distance from all the other blocks right similarly for this block i will have to check for all the other blocks so to minimize that to make it order off and i will have to use dynamic programming and store the values that is in a array so if i have see a dp array of distances so this will again be a it will be sort of for of vectors so and vectors will be or the distances the max distances for each of the requirements okay right so it will be like so suppose there are n blocks right so this dp oh okay uh this auto this thing i'm not really caring about it okay okay yeah this caps lock so uh i'll keep a dp array of size n suppose okay and each of them is a vector so it will be vector of a vector of integers say dp and this the entire size will be n and each vector will be of the size so what will be the size of requirements okay say that is in this case and we will initialize the whole thing to some maximum value does this look fine okay right so now as i traverse can i just start writing the pseudo code and then we'll we'll keep discussing if you want but just just uh to make sure i i follow you could you re-walk me through like what the logic you're gonna you're about to write in pseudocode is okay so uh this is the array of vectors that i'm storing right so as i traverse this array for each point i'm going to keep calculating and like i will see all the answers previous to it and update it so if like the maximum uh distance of this school should be the maximum distance of the previous one plus one if it is not present over here right okay so it basically i am calculating maximum distance for each requirement for each uh block in the array yeah does that sound fine yep but how are you doing you you said you're doing that in one iteration uh it will take two iterations i think so one will be uh i'll go from left to right right and one will be from right to left i see okay does that sound fine and i take minimum yeah i think i think i'm following you so if you want you can you can write the the pseudo code that you were going to write okay so i'll just write it in simple terms so i equal to 0 i less than n i plus plus okay so i am traversing the entire array right now and for each element i have to track for for all the requirements right so for n t equal to j equal to zero so j less than m m is the size of the requirements over here right yeah j plus plus and so what i'll do is if it is the first one so for the first one i will update over here so i'll traverse this from i equal to one also can i assume that there will be at least one element or uh should i handle cases when there's just one uh one block or two blocks let's just find that there's always let's assume you know for simplicity that there's always at least one requirement and one block yeah okay so in that case so point j equal to zero so this is for my first block okay so for first block as i go through this so if these are the blocks given to me so if blocks of 0 that is the first block that i am seeing if the element so i am just saying it so can we say that input is given in terms of requirements so 0 1 2 or should i uh save this thing like should i uh like preprocess this thing and save it in uh you know array sort of thing so basically what i'm trying to say is that for block 0 this is requirement 0 this is requirement this is requirement two i see um i had uh the requirements as a vector a string vector but if you if this is simpler for you you can assume that you've pre-processed it to map the requirements to numbers if that's easier for you so would you rather have me write the pre-processing code as well or is it okay to go like this for now let's assume that you've that you've written it so just just to understand you're saying that basically your requirements now look like like this right and here i can just map it to zero one two yeah i'm assuming that you would do the you would do the same for the the blocks like the unordered map here the keys in the unordered map yes so this will be an integer and this will be a boolean so boolean and integer okay that's fine yeah let's let's go with that for now okay so uh if uh my first block has this requirement jth requirement then what i do is i update that distance so dp of so otherwise it will be in max side so otherwise so for this one i update dp of 0 g 2 0 so the distance is zero for this one okay okay uh does the same fine to you till now so this is for the first block yeah so you but you've only done it for the first block yes so for the rest of the block so i'm starting from i equal to 1 i less than n sorry so here so for rest of the blocks what i am doing is so dp of i any ith block and for each j what i am going to do is it will be equal to so i have to find the maximum the farthest that i have to go right so it will be so uh the fathers that have to go so if first of all i will check if that one is true so if blocks of ij that means if it is present over there itself then i can just assign the dp of i j to 0 that means that thing is present over there if it is not present what i do is i check if it was present somewhere earlier right so for this so what was the distance for the previous one plus one it will be right now uh it is possible that we haven't found the previous one so the value will be int max over there so if i add plus 1 it will go out of 1 right so i will have to add a check over here that if dp of i minus 1 j is not equal to in max right then my dp of ij will be equal to so minimum of whatever is the value so if it is max now so i don't have to consider it or if it is 0 then ok so minimum of dp of i minus 1 j plus 1 does this seem fine yeah yeah so uh this is for so this is why i am going left to right right so for each of them i am updating that what is the maximum distance that you have to go right now with this instead of doing this i can do one more thing so i keep this as one m plus ah one instead of m so the last element that i'm going to store will be the uh it will be the minimum of all these values so this is like the maximum distance that i have to go right so i have to minimize the farthest distance that i have to go for all the blocks right so for each block i have to find that so for each dp of i basically i am storing one more element which will essentially be maximum of all of these distances for that block right so when i am calculating this so for each of them right so where is this ending yeah so after each this so dp of instead of this yeah over here i can add so dp of i m will be equal to maximum of so initially it will be okay so for each of them i have to add dp of im as some 0 right so we can assume that at least so i have to find the maximum distance right so if that value is maximum initially only then anyway it will always be max right the answer will always end up being max so i initialize dp of im as 0 and i will make this as dp of i m and dp of i j so whatever value i have calculated if that value is greater then i have to add it so i'm storing the maximum value over here does this make sense yes yep you're updating at each iteration the the maximum men distance of a requirement that you've found exactly right so i have done this when i'm going from left to right but uh the maximum furthest distance can also be from right to left right yeah so i will have to do the whole thing like the same code i have to run in the other direction as well right right so now what i do is now for end i equal to n minus 1 i greater than equal to 0. so i can just copy this whole thing and make some small changes yeah right so odp of im i don't have to update it to 0 now because some value is already there i don't want to discard the value right right so now again for each block i'll check so this will remain same now instead of i minus 1 i'll make it i plus 1 and instead of n minus 1 i'll go from n minus 2 and it should be greater than or equal to 0 and it will be max of this so yeah i think this should work i'm sorry can i just dry run once and check or so do you have any questions or does the same point yeah i was gonna say could you walk me through like let's let's take the sample input that we have above with the gem school in store and we can assume that i guess gym is zero school is one and store is two and walk me through the algorithm you know like basically iteration by iteration just to see that it that it works conceptually right so i'll just store the dp values over here right okay so uh dp so for like 0th value what will be the values initially if uh so instead of writing in max i am just going to write some big number 100 for now right so that will be easier to understand okay yeah or if you want you can even put like um just like an asterisks or like a single character like this okay so for dp of zero so first we'll go through this one so only for school it will be true so it will be something like asterisk zero asterisk and the last value will be asterisk itself okay because the last value you take the maximum of all three of these okay okay so uh also okay so here this is the tricky part i also i haven't uh taken care of resultant which will be the maximum of all of these tp of im essentially so we can calculate that okay just let's first see if the rest is working or not so dp of i1 yeah yeah so i come over here i put dp of im as 0 which is ok so for each block i check if it is true ok otherwise i will add the distance okay so here since this is true this distance is going to be 0 right now this is false so this will be either int max or this plus 1 so this is going to be 1 and the distance of store is going to be this plus 1. so here since it was max only i'm going to keep it max and dp of im is going to be max of these all so since this is asterisk so this will also be asterisk so the maximum distance is infinity itself right now and just here to just um to stop you for one second just to make sure that we're on the same page so here you're applying you're effectively applying this line right this is i just copied the line that you had written yes right and so at the second element you took the minimum at that element which was int max and dp of i minus one at j which was this zero here yes plus one yes so z yeah yeah okay so it was mid so it was min of n to max and zero plus one yes okay that makes sense yeah so now coming to the second element uh so if i am here so here the values are going to be since this is true it is going to be 0 and this is also true so it will be 0 and since this is false it will be a minimum of either into max or into max plus 1 since this is int max so again the value is maximum only so this will again not get updated because the farthest distance till now is still infinity right now if i come over here it will be so here the gem is false so it will be either 0 or it will be there in max or 0 plus 1 so in this case it will be 1 here it is true so school is true and store is again false so this is again infinity infinity okay so for 4 again so this is false so it will max distance will be two here it will be zero so store is wait so zero zero one two three four okay so here uh this is true so what i am going to do is this will finally become 0 and our dp of im will be equal to max of dpf im and dp of ij so what is the maximum value of all of this oh sorry yeah what is the maximum value of all of this it is 2 right so the farthest distance for all of this is 2 in this case yeah right and this is this is this line just again to make sure that we're on the same page it's this line using dp of i which is the next four at m is this value is the maximum of dp of i of m which was um into max because you've initialized it to max correct yeah yeah and then um oh yeah because you've initialized every single value to max is that uh how what this does here no but i also initialize dp of im to zero right so this value right you initialize it to zero down here yeah okay so max of zero sorry so max of zero and dp of i of j um which would be like basically at every iteration you would do max of zero two max of two zero two zero and you end up with two right okay okay so in the second iteration so this answer will remain same and i'm going to start from n minus 2 which is this one okay so i start from here so gen value was initially okay so since this is false what i'm going to do is i'm going to take uh so i'm over here right so it will be either minimum of what is there or dp of i plus 1 j so either minimum of 1 or minimum of 2 plus 1 which is 3 right so in our case we won't update it so this is going to be 1 itself right now since the school is true this will be 0. now again the store distance will either be this or 0 plus 1 which in our case will be 1. does that make sense yeah so now the answer or the tp of i of dp of im for this case will become 1 because the maximum distance is 1. yeah right so in the end i will return the minimum of all of these dpims right so minimum of two one like that yeah right so in this so again coming over here so here gym value is true so it will be 0 and this is also true so it will be 0 since this is false here it was infinity so it will be minimum of 1 plus 1 which is 2 so answer will be 2 over here make sense yep make sense one second just yeah no problem take your time yeah now uh zero so this is okay now either the distance will be one or max of zero plus one so it doesn't matter so this is going to be one so either infinity or two plus one which is three so here it will be three again over here if we come so the gym distance over here was infinity so here it will be 0 plus 1 which is 1 here it is true so it will be 0 so 4 and max of all of these 4 right so now i have to return minimum of 4 3 to 1 2 which will be 1. so this will be our answer gotcha and just to be clear the can you remind me the reason that when you go from right to left you skip the final index what's the logic behind that because essentially i want to see the distances from the right right so this is the right most element so like there is no element on the right so there's like when we calculated from left to right i did not calculate for zero right so i already had some pre-calculation it is similar to that but the since some uh calculation is already done over here i don't have to do it separately just that yeah makes sense okay makes sense and so i guess um as a final few things for the um for the finding the minimum index just walk me through out loud what you would do yeah so you just just i can just keep a result right and here every time i calculate dp of im so i don't have to upgrade the result in the first citation since anyway i'm going to do it again right so my result will be equal to minimum of result and dp of i am so this is when i am going back when i like in my iteration from right to left when i am going back uh i calculate these values so okay when there is just one element this will not work because in that case i am not calculating dp of im at all this will be at least when there will be at least two elements right so when there is just one element n equal to 1 i will have to return the so for this one i should calculate i haven't done dp of im for the first one right so dp of r will be equal to essentially this right so my resultant here i can just re store result equal to dp of i so this is just for the case when there will be one element and plus i mean in the case when there's one element um i i guess i could have specified that maybe the input just always has two elements rather than one because one there's only one apartment that you could go to so it doesn't really make sense uh but good that you that you caught that um could you uh walk me through the time and space complexity of this algorithm yes so uh for each block i am uh going through all the requirements right so if this is so there were n blocks and m requirements so the time complexity will be order of nm over there also and over here also so it is order of 2 into nm which is essentially order of nm and this space complexity is also order of nm since i am storing the requirements for all of them yep ok great and this is um better than the brute force solution that you like alluded to at the very beginning although i think at the beginning you were you were doing the minimum the minimal distance of the sum but you were still alluding to a brute force solution thanks yes were you expecting a better complexity solution or is this okay no this is this is great uh just maybe as a final thing because we we still have roughly 10 minutes here but as a final thing um just out of curiosity like how would you if you if you had to do you see ways that you would improve this code maybe from from a code perspective like because here we sort of did it in pseudocode like part real code part pseudocode but how would you um how would you do this if you had to like write the function signatures and things like that so uh obviously i have not taken correct naming conventions i have just taken ieg and written like not at all professional way so the naming conventions i should definitely change like i have taken vector a vector and i have called it dp which is like when a third person is reading it doesn't really make sense right so maybe i could have named it uh requirements distances and uh like similarly naming conventions but i can say i could have definitely done better oh and return it in better way okay cool well listen kirk i think i think this is great super quick commentary as you're about to see in the last 10 minutes of the interview we did a second coding interview question and in hindsight i think that that was a mistake from me the interviewer because i had already gotten a really good signal about kirti's algorithmic skills from the first question but i hadn't gotten the best signal from her coding ability because i didn't see her code in a sort of production grade formal quality she even told me herself that she would have renamed certain variables and things like that and so in hindsight i think that instead of doing a second question where we only had 10 minutes and i knew that we weren't going to get to the coding part so i effectively just reassessed her algorithmic skills from a conceptual point of view i think that i would have been better off having her rewrite her code in a more production grade quality in a more formal grade quality and that would have given me more signal about her coding ability that was my mistake in hindsight anyway i'm telling you now and enjoy the rest of the interview but we still have roughly 10 minutes on the clock uh qrt so we're going to do something completely different we're going to switch gears um when you're at a big tech company and you're on an engineering team you often care about or almost always care about the state of the code base and specifically that all the continuous integration tests and unit tests that are running in the code base that they're passing right you don't want tests to be failing and sometimes when engineers push code into the main repository they fail they break the tests and so the tests start to fail right does that kind of make sense yeah so what we called it on my team at google was the build and so the build referred to kind of like you know whether the the code in the main repository works correctly compiles all the tests are passing and if everything worked well we would say that the build was green if everything didn't work well if there was maybe like one test that failed we would say that the build was red or there was a build failure okay okay so i'm going to give you some data it's going to be a list of lists of booleans so it's going to be something like let me copy paste something for you here it will be something like this this is going to be question number two and what this is going to represent is each list here you could imagine that the value at a specific index represents like one hour or one unit of time and if there's a true it means that the build is green so here the build was green then the build was green the next hour then it was it was green again so everything was passing and then suddenly it was false meaning it wasn't passing it was broken and then for another hour it was false okay now when this happens an engineering team isn't happy you want the build to be green so you immediately want to go and fix it and so that's why you see that immediately in the next list it's been fixed and it's back to true true true until it goes to false because it's broken and then an engineer has to fix it and you go back to true right okay so we call these these lists here that are effectively like the build is green green green and then suddenly it breaks and then it gets fixed we call that a build run a build run okay and so what we care about as a team is to effectively like minimize the time that it takes to fix build runs right we don't want build runs to be false or to be broken for a long period of time okay so we want to minimize that and um what we care about as a data point is something that i'm going to call a green percentage which is effectively within a build run the percentage of time that the build was green versus broken and so the longer the or the greater the percentage the better it's like for example here in this particular array you can see that the green percentage is eighty percent meaning the build was green eighty percent of the time and then it was broken for twenty percent of the time before it got fixed again okay we want that to be as high as possible and specifically the algorithm that i want you to give me is i want you to to take in this list of build runs okay and i want you to return the greatest number of consecutive build runs that have a strictly decreasing green percentage so it basically tells us the the longest like period of time during which our engineers were increasingly slow to fix broken builds does that make sense yes i have a question how come the uh sizes of the list are different so like are we building different projects all the time or is it because if it is the same projection in the number of hours taken to build it be same or no because you you can imagine that these represent hours so basically it's like okay the for for a single code base the build was green green green and then it broke it broke for two consecutive hours and then as soon as it got fixed again we represent that in a separate like list and so this is all like the same code base effectively but here it's green green green then it gets broken and then it gets fixed so here the green percentage up here is sixty percent and it's okay just about the percentage and uh not about like the number of hours or anything so because yep doesn't matter the number of hours okay okay okay uh any other thing in the question you would like to add or was that it that's it and so we want the the greatest number of consecutive build runs so consecutive lists like this that have a strictly decreasing green percentage and since we are running out of time uh ideally just walk me through if you can come up with an algorithm that solved this conceptually how you would do it you don't have to write any code for now okay since it is supposed to be consecutive so this essentially is a uh longest decreasing the sub array sort of a question right so you have to find a sub array because it is consecutive right so if it didn't have to be consecutive it could have been subsequence and we i could have just said longest decreasing subsequence right and we could have done like a normal dynamic programming over here since this is consecutive there are sub arrays so i can just keep two pointers over here and so there will be two pointers one will be left pointer one will be right pointer so from left to right the percentage should be strictly decreasing or should it be less than equal to condition let's do strictly decreasing okay so if if the so i will move my right pointer and check that okay if uh if it can be added to the answer to the left to right if it is less than the right element that we had earlier then i will just increase the length to 1 otherwise i am going to update my left pointer and then calculate again and i will have a resultant over here does that make sense or should i just uh right and here when you're saying when you're saying from left to right are you you're saying you have one pointer at the left of the main big list so that starts at here yes so the and the left is essentially zero and my right is also initially zero okay so what i do is that if so i will keep doing that i will basically move my right pointer right and then i will check that uh if the percentage of uh right is less than percentage of right minus one because i just moved it right so gotcha okay okay sorry sorry to cut you off guarantee so i i understand now um just how are you going to be calculating the percentages yeah so that i can pre-process and keep so the number of trues and number of falses so it will be number of trues upon number of truths plus falses and 200 right and so would you would you do like a linear search for that oh we'll have to go through the entire list at least once right because to check how many were true how many were false so yeah i'll have to walk through at least once if i tell you that they always start as the build runs by definition are always true and then they turn into fault okay then i can just uh do a lower bound which will return me greater than or equal to or i can just do a binary search that is the lower bound essentially the first place where it was false right right that's all right sort of binary search so uh i can calculate that in log n if n is the size of the list and um yeah so log in to find the percentage so i will have the first place where false came so the ones before that were true and we know the size of the list so we can calculate the percentage right exactly and so then the total time complexity of your algorithm would be so i would have to travel this entire thing once so and so if say m is the maximum size of the list and n is the number of lists so it will be order of n into log m yep okay great um listen kirti we we we're out of time now we're exactly at like 46 minutes um so i think this was this was great we covered at least conceptually so a second question um i think we can jump into the feedback now okay okay cool so i'm gonna stop the timer so for the feedback i'm actually gonna send you a link of the feedback form that we have on our mock interviews on uh algoexpert which is actually like very similar to the feedback that you would get at google so at google there are here i'm basing myself off of google but this is very similar at most big tech companies but at google usually there are these four main categories that you're assessed on right algorithms coding communication problem solving and a few other things but these a few other things are kind of intertwined you know things like how do you handle uh your curveballs or ambiguity or you know were you um was there any moment where you were like disrespectful or you didn't react well to stress or things like that but here we're going to focus on these four main things so i think that's for algorithms i would definitely give you a four which is you know the the best score here because you for not only the first question but also the second question in very little time you came up with the the optimal algorithms to solve the question you basically had no help from me uh in both of them and um you clearly you know demonstrated that you you know how to work with algorithms as well right your dynamic programming was on point binary search you got that right um so really really well done there um then if you want we'll jump down to problem solving before covering the other two because problem solving is often like pretty related to the algorithms and here i would probably also give you um a four for the problem solving and maybe i would hesitate a tiny bit with the three just in the sense of like you know maybe there was room for you know you could have asked a tiny bit more clarifying questions because at the beginning uh you you were going down the path of um minimizing the sum but like that that is personally i don't really find that as that big of a of a bad thing i think you know this was a complicated question as far as like the amount of information i gave you um and otherwise i think you just approached the problem well you know you covered you you talked about edge cases you asked about like you know what if it's an empty array if it has one element you even handled the case with one element um and you you covered a little bit of the brute force solution at the beginning so overall yeah i think that the problem solving was really on point there too so i would give you probably a four there quick commentary so we're about to jump into the coding ability section of the feedback and as i said in the first commentary in the middle of the interview i think that in hindsight i made a mistake as the interview were i didn't get quite as much coding ability signal as i would have liked from kierke and from this interview you'll see that in the feedback here i kind of err on the nicer side i'm a little bit nicer to qrt than i could have been and ultimately in a real interview what i would have done here is i would have left a note for the hiring committee telling them that i didn't get quite the amount of signal about kirky's coding ability as i would have liked to have gotten and for them to just keep that in mind then if we jump into the coding um so for the coding you notice that at the end i asked you kind of like what you would do to improve the code and i think that's important to ask as an interviewer just because i know that you know sometimes um especially depending on your background and like when you're under stress in the interview especially on a google doc you write you know you go with fast variable names like dp especially if you come from a competitive programming background dpdfs but clearly like you said it yourself you would have likely you know cleaned up the code a little bit renamed it more properly um you also asked me about the pre-processing and all that stuff which i i'm very confident you could do so for the coding i would i would go with anywhere between a three and a four you know i i don't think there was anything um really like a red flag and the the one thing that maybe would have made me think it was a red flag is if you didn't tell me anything of how it could have been improved you know if you if you didn't realize that things like dp aren't amazing as naming conventions and things like that but otherwise i think that was fine i guess maybe one one point of improvement that i would maybe have given for coding might be subjective but i think you you're you you did it well because i think your algorithm probably runs perfectly but you you stuffed a lot of stuff in all of your for loops like for instance keeping track of the of the final minimum index distance the result i think um you know that could have been an entirely like separate function um you could have also done you could you could have also separated um some of the like maximums that you're keeping track of in a separate function but like i don't know you know it worked well for you so overall here again i think i would probably give between a three and a four okay that i would say subjective i should have probably mentioned it because so some interviews might probably expect that you know why to increase the complexity by making another function and you know another call and it's just an overhead so but yeah it becomes cleaner like that so it's a it's a trade-off basically which i should have mentioned probably that i could have quoted it like that as well yeah and i guess if you want to take one piece of um feedback that might help you in any future interviews you do it would be that like maybe you can at least tell your interviewer that you're thinking that you could do it in two different ways you feel comfortable with doing it all you know in a single function or in a single for loop but maybe it would be you know easier for readability purposes or for um you know logic grocking purposes to split it up into more different logical units yeah yeah yeah because i guess the last one i'll say here is this yeah in general but this is again this is kind of subjective but for me i find it very helpful to kind of think of how i'm going to solve the problem and you know let's say three different logical steps so here it would be number one you know left to right number two right to left and then number three uh maybe i guess in the right to left with that approach you always update things you know there so that makes sense but then i would have separated out that final step of finding the minimum index in a separate kind of logical unit but again i think overall i think you did you did great there and i think you know we're on the same page given what you just said right now okay um the final thing is communication uh for communication i would probably give i would probably give between a three and a two or like two and a half and three i don't think i would give it two because two is two is a bit harsh i think i would give a three uh the only like reservation i would have about communication is just that this problem is relatively complicated right even if you find the solution really quickly which you did so clearly like the problem itself wasn't that difficult for you it is a pretty difficult problem that has a lot of little you know things to keep in mind you're you're keeping track of the the minimum here but then it's the maximum and you know you skip the last index and you skip the first index and all that and i think that um be you know you could have maybe communicated a tiny bit more and i think that some some interviewers might uh have gotten a little bit more lost personally like my approach is i really want to make sure that i'm understanding what you do so like i'll stop you in the interview just to clarify and you saw that i did that a couple of times um but ideally ideally like you don't have to let your interviewer do that ideally you're the one who's proactive who's like um just to be clear you know this is the line here that i'm using and and what you can do if you don't feel comfortable with that or if you're like you know this seems useless you can ask your interviewer which you did do which you did do so good great job there you can ask your interviewer like are you following me here do you want me to go into more detail as to how i'm getting this or not overall it would probably put you at the three for communication to tally up you know you've got like a foreign algorithms and problem solving three and a half let's say in coding three three and a half in communication for the final score i think i would i would be inclined to give a strong higher you know somewhere between a higher and a strong higher instance you have to make a decision i'd probably give the song higher awesome i can't be hired but yeah i mean yeah again as far as i'm concerned and you know all the viewers can can see in the interview like i think you did you did a great job and especially like it's under pressure you do how do you react to this feedback like did you feel good about it or uh honestly i thought i would get a lower score for uh algo problem solving because communication is my thing so yeah this is the first like this was a challenging thing that okay i have to improve on my communication because i think yeah i could have communicated my approach also little better so yeah that's a good feedback for me yeah and just also one thing to keep in mind is like every interviewer is a little bit different in how they assess you know like what what one person might deem a great amazing communication someone else might score a tiny bit lower but then conversely for algorithms it might be a little bit different like i personally found your algorithm skills like really impressive like you you didn't stumble at any point and you immediately realized kind of the the clever approach of the left to right and right to left thing so i did not expect that thank you so much i'm really happy all right well listen kierty awesome job um if i were an interviewer at google still i would give you a strong hire and um i would i would hope that um you did very well in your other interviews and the hiring committee saw it the same way but any last words for for the viewers i guess most of the people who come uh and do this mock interviews in your channel are competitive programmers so i am not any uh like big high-five competitive programming and good programmer at all so i have a small channel where i make hard questions and explain them in a very simple way so if viewers like that they can just go check it out and give me feedback i would like to improve and help them as well definitely and i'll put your channel um in the description below thank you so much clement thank you so much for having me it was a pleasure that's gonna be it for this google coding interview i hope that you enjoyed this cool coding interview if you did don't forget to smash the like button subscribe to the channel if you haven't already check out the other google coding interviews that we did on kirti's channel in the description and comments below otherwise don't forget to follow me on twitter and linkedin if you enjoy short form written content instagram if you like pixels and otherwise i will see you in the next video

Channel: Clément Mihailescu

Views: 699,261

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 a normal software engineer, google coding interview with a software engineer, keerti purswani, google india interview

Id: rw4s4M3hFfs

Length: 59min 56sec (3596 seconds)

Published: Wed Feb 03 2021