**一堆網路教學，我覺得不錯的都有放上去**

2022/9/19

###### 參考

Google Coding Interview With A Normal Software Engineer

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

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

【隨便年薪千萬台幣?】揭秘加州軟體工程師每一個級別的薪水細節

**一堆網路教學，我覺得不錯的都有放上去**

2022/9/19

其他文章:M