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