DSA Interview With PhD Student Preparing for Google - Medium Difficulty - Solid Hire

Added: 2026-05-13

[00:00:00]Okay. So, can you give a quick b a b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b brief intro about yourself one more time.

[00:00:04]Sorry about that.

[00:00:07]>> Uh yeah. Uh I'm Yan and I'm a recent graduate uh for our University of Buffalo CS PhD programs. uh I'm focusing on uh uh developing uh robust machine learning algorithm on the data hogenous environment and I uh I have several papers in my PhD study and I also have two internship experience one is at OPPO which is a Chinese famous Chinese self company and I also have another internship at Google and now I'm interviewing doing for uh uh uh Google's air for position which are uh for the you graduate uh PhD level. Yeah. Uh that's my current situation. Yeah.

[00:01:03]>> Okay. Cool. Okay. So, so you can get straight L4 with new grad PhD. It's interesting. Is that like a machine learning role or what type of role is it?

[00:01:11]>> Uh yeah. Yeah. Yeah. Yeah. Yeah. I'm uh yeah. I'm a I'm a uh apply for sometimes like combustion engineering roles.

[00:01:22]>> Mhm.

[00:01:23]>> Okay, sounds good. Okay, so we can get started here. So, I'm going to ask you two problems. Um the first one I think I'm just going to paste the prompt will be easier. Um so, you can go ahead and read it. Um and let me know if you have any questions.

[00:01:38]>> And yeah, we have 15 minutes here. So, there you go.

[00:01:41]>> Yeah. Could I give uh could I have a few minutes to read this and then I will ask some clarify question?

[00:01:48]>> Yeah.

[00:02:08]While you're reading, I'll paste an example as well.

[00:03:04]Yes. So, so that we are giving a functions uh that uh that takes three input mn and a two 2D list sources and what we want to do is that we would uh return a 2D array representing the final state of the grid. So the output are also a 2D integer array.

[00:03:35]Uh right.

[00:03:38]>> Yeah. So you can take a look at the example that I provided as well. Make things pretty clear.

[00:03:43]>> Yeah. Do we change the uh uh 2D integer array in place or we return another uh 2D integer array which represents the final state of all the >> Yeah. Yeah. So if you see in the example, you're not given a 2D integer array input. You're given n M and a sources array and your output array is not the sources array. It's a new one.

[00:04:08]>> Okay, got it.

[00:04:12]So and uh uh so and my other question is that is all the colors I are uh uh positive integers except for the zeros.

[00:04:30]>> Yeah. So the colors will be non zero and they'll all be different. So like in the sources well actually in the sources array two items can be the same color technically cuz like I could have this right as input. Um this is this is legal but yeah all the colors will be non zero. Um and everything else will be a zero. So basically everything in the sources will be non zero and then every other cell should just be a zero starting out.

[00:04:53]>> Okay.

[00:04:55]Uh do we assume that the color cells are four-way connected or the eightway connected? So that tells you in the um >> Oh yeah.

[00:05:05]>> Yeah.

[00:05:06]>> Yeah. It's a four-way connected.

[00:05:10]>> So in this way I think my intuitive solution would be using the BFS to search for the problems.

[00:05:19]>> Okay. So how that work?

[00:05:21]And we would uh we uh we would have a uh BF we would have a BS BFSQ uh uh which are starting to visit from from the beginning of the places that it already has a color.

[00:05:40]>> Mhm. and and for and for each and for each times. I think it what is different from the traditional BFS search progress is that we can uh we are keeping the two uh uh visited set.

[00:06:00]The one visited set is that uh for the sales that have been visited uh already for the previous uh times and the other uh visited another visit set are the current vis set which are the visitor set that uh we are visiting in the current times.

[00:06:22]So but uh for these two sets we treated differently. For the previous visited set uh we don't visited uh uh we don't visit the color anymore.

[00:06:36]>> Mhm. And for the current visited set uh we are uh we are getting the uh we are getting the max of its current and sale colors with the neighborhood spreading colors to update for its current colors. So in this way we update all the uh in this way we use this way to update to visit the orders sales in the uh to the list until uh there were no more sales to visit anymore.

[00:07:13]>> Okay. So you said we're going to have one for like path and one for current and we're going to get a max out of current. Can you maybe walk through what that would look like with the example I provided just so I can understand that a little bit better and then we can talk about like time and space complexity for that. Okay. Yeah. Yeah. Yeah. Yeah. I think for the uh for the input.

[00:07:38]>> Yeah. Yeah.

[00:07:39]I think that I think that currently for the input uh uh we have the uh we have in in the queue I think we have zero zeros and then we have Q2 I think that's the that's the and that's the uh and that's the starting place that uh we are going to BFS right >> mhm And the uh first past visited I think yeah it would be the uh zero zero and 22.

[00:08:19]>> Okay. So it's going to start out with basically everything that's in our like sources. Okay.

[00:08:24]>> Yeah. Yeah. Yeah. And then for the first BFS the zero zeros I think his neighborhood are the uh Yeah. we directly paste it. Uh the neighborhood are this one and this one.

[00:08:38]>> Mhm.

[00:08:39]>> And uh these are the and these are the place that uh uh we are going to visited, right?

[00:08:48]>> Mhm.

[00:08:49]>> And and then uh uh uh and then because this place uh are not in past visit so that we put it in the one.

[00:09:00]>> Mhm.

[00:09:00]>> And uh Yeah. And yeah because to save time I put an X here means that this is just the state it is current visiting.

[00:09:11]>> Okay. And then uh the two uh and then we have two so that uh we are visiting the place which has the uh we are visiting these two cells right >> and yeah and that's all and that's all for it right that's >> okay so these four cells will be in the current visited you're saying and the past visited will have the 00 and 22 for now >> yeah yes >> sure >> and then uh uh And then we are going to uh visit the next and the next thing is that after this steps end we are adding these two uh four newly uh added uh sales into the past visited set.

[00:09:57]>> Mhm.

[00:09:59]>> And then we are starting to visit for this these four newly added point.

[00:10:04]Right.

[00:10:04]>> I see. So at this point our past visited will basically have like let's maybe have another like a Y or like a P is passed. It'll be like this one, >> this one, this one, and this one. And then your starting ones, right? So these two as well.

[00:10:19]>> Yeah. Yeah. Yeah. Yeah.

[00:10:21]>> And in your queue, you'll have the four that you just went to.

[00:10:25]>> Yes.

[00:10:26]>> Okay. I see. Yeah. I think that makes sense. So you're basically taking the current iteration from the current and adding to past. Okay. And in the current Okay, so in the current if you visit that current, you're allowed to visit the current cell multiple times and you'll just keep track of a max or something something like that.

[00:10:42]>> Yes. Yes. Yes.

[00:10:45]>> Okay. So yeah, I guess can you walk through the Okay, I think I get it. I think this is good enough. So can you talk about um time and space for the solution?

[00:10:53]Um I think that the pie complexity for and the pie complexity for the uh uh the time complexity would be all n times m which uh we are bf we are using bfs to visit every uh every cells at least and at most one times so >> the time complexity would be all n times m And I >> Well, you can visit them multiple times, right? Because like um >> Yeah. Yeah. Yeah. Yeah. Yeah.

[00:11:29]>> Can you No, no. I think I think it's still OM.

[00:11:34]>> Yeah, I think you're right.

[00:11:35]>> Because because in because uh at least we visited four sales from one point in the visit and in the visited queue. So that means that we visited a cell at least four times. So it's still linear of all n times n.

[00:11:56]>> Yeah, I think that's right. Like yeah, I think you can visit a cell multiple times, but it's not going to be like that many. Yeah, I agree with that.

[00:12:04]Okay, so it's okay. So n 10 time m makes sense for time. And what about space?

[00:12:09]I think the space complexity would be also all ent because we kept a set of past or current visited. So uh the and so I think it's still O time M space complexity.

[00:12:27]>> Yep, I agree. Okay. Yeah, feel free to code it. Okay, I would have color. Could I name the function of the sale colors which are >> you call it whatever you want with the MS and the sources.

[00:12:51]So what we need to do is that we have a uh we set which is a set and we have a yeah we have a yeah I think we have a pass set and we also have our which are also empty here and then we also have visit the queue and yeah we have something like the cube of the empty list.

[00:13:23]>> Okay.

[00:13:35]And what we need to do is I believe the first iterate through the cells to find the no empty point and and the non zero colors.

[00:13:48]>> Mhm.

[00:13:49]>> Yeah. Yeah. I think that if uh if sources sources I if it's yeah the second or if it's not equal to the zero we need to do is that we would have the ask you.

[00:14:22]>> So, I think you should take a look at how the sources are is structured again and see if this makes sense like what you're doing.

[00:14:31]>> Uh oh. Oh, yeah. Yeah. Yeah. Yeah. Yeah. I think that we are um Yeah. Yes. The sources are the onedimensional arrays uh which are the Yeah. Yeah. Yeah. Yeah. Yeah. That's >> Yeah. I think >> so that we need to have a uh what we need to do is that we have a empty uh we we what we want to do is that we have a 2D integer array. So we should have initialized it what would be the u which would be the I think that would be the the zero and yeah we should first initialize agreed and then >> Mhm.

[00:15:34]>> build updated if we got it. So what we need to do is that for uh I uh what we need to do is that we have the passi and what we need to do is that we will also append R I CI and we would also update the R I would name it to the other.

[00:16:20]>> Okay.

[00:16:20]>> Yeah. So the next thing is that we use the BFS to visit it. Yeah. Yeah. I think that I'm not sure if the add is the fun function to add something in the set but I think so. Then the next thing we would use the BFS to solve it. So uh we would have while uh while the vic is not empty what we need to do is that uh we need uh we need to have to iterate on the uh range of the shoes of the visitor cues of l of vit.

[00:17:09]Okay, >> in this way uh we are um um we are covering a hop by hops >> and and the next thing we need to do is that we use the B bfs to and update the empty colors in in the next hopper of its recently colored cells. And that is what we do. So that's the so that's what we to do is that I we will pop one in the cube left.

[00:18:02]Yeah. I think yeah what we need to yeah we don't need to have the color eye to close to the we we use the grease to get this cover the color so the color eyes is here >> uh next thing we are and uh next thing uh we are having the neighborhood uh sales of the ICI which we have a pre uh visual people have a direction something like this uh that's so we are uh we are vising the stats the next I to the I class uh we use the direction is delta to get the uh next I and the next CI which is the neighborhood of CI and I.

[00:19:14]>> Mhm.

[00:19:15]>> And then what we uh and then what we need to do is that uh if if uh if max Next see I yeah we first have to see that whether it is inbound so that uh so that if it's not inbound we will continue if not uh is greater than equal to zero and it's smaller And small. Yeah. and and and so we would text CI we would continue because because that means that we don't it is autobound and then another thing if that if uh Next up I next see I next >> that means that this uh this point have uh already been visited before and >> that will also continue.

[00:21:01]>> Okay. Uh then the next thing is that we would add uh we would have the current visited visited set.

[00:21:13]We would add the uh next I next CI.

[00:21:19]>> Mhm.

[00:21:20]And what we need to do is that we uh we need to also update the uh w position which are the next I next CI and equal to the max of with next next I next CI.

[00:21:52]And I using the and of the current color I co Yeah. Yeah. Yeah. Yeah. Yeah. That's true. And that's the thing we are do in each level. And after and after we have uh completed this hops of color update, the next thing we need to do is that we would put the current visit set into the visited queue and we would we would also add the current visited set to the past visited set. So what we need we need to do is that for i set we need uh what we need to do is that we need to con set and we will also append it to the vit.

[00:23:10]Mhm.

[00:23:13]>> Um past. Yeah.

[00:23:17]And and the final thing we need to do is that we need to empty the characteristic set which the car uh set we would have it using empty set. So that's we and that's what we do in eops of color update. And I think the final thing we need to do is that we update the uh we return the grid that all the empty color cells have been updated.

[00:23:51]>> Yeah, I Yeah, I think that that that's uh I think that's almost that seems almost done for the algorithms.

[00:24:03]>> Okay. Yeah, you can review this. We can do a dry run if you want as well.

[00:24:09]Um, >> honestly, like you you kind of already did a dry run of like exactly what you were going to do before, so I kind of get the hang of it. So, I think you can just review it to make sure everything's good and if you think it's good, we can move on.

[00:24:26]>> Yeah, I think it's already good. Yeah, we can move on. Yeah.

[00:24:29]>> Okay, sounds good. Okay. Yeah, because I took a little bit more time in the beginning to ask you to walk through it.

[00:24:36]Okay, so that makes sense. Okay, so let's move on to the second problem.

[00:24:40]Once again, I'm going to paste a description. I think it'll explain it better than I will. Feel free to ask anything and I'll rewriting an example while you're reading through it.

[00:25:17]All right.

[00:25:20]Okay.

[00:25:35]Yeah, it seems complicated. Could you have could you give me a little more time?

[00:25:41]>> Take a few minutes.

[00:26:20]the sort. Okay.

[00:26:29]partition the number into the if k divides n so k is larger or n is larger.

[00:26:45]So k can't be larger. Um so like you basically need numbers of k that divide n. So a bigger number wouldn't right like like basically n mod k needs to be zero.

[00:27:02]>> Okay.

[00:27:19]the possible divides one and three.

[00:27:27]So in in the example we are return four, right?

[00:27:31]>> No. So you would return three because if you pick one then you have to have chunks of one element that you're allowed to rotate and you can't rotate one element, right? Like one element can only stay in the same place. So with one you couldn't make this sorted. It's not possible. with three this entire thing is a chunk and then you can rotate it left and then that would give you a sorted array.

[00:27:56]>> Does that make sense?

[00:27:57]>> So yeah. Yeah. So that we can only so that we can only rotate uh we can only rotate within chunks. Yes. And okay. Got it.

[00:28:26]Let me see.

[00:28:35]I think I think the and if we first start from a simple condition for k= q1.

[00:28:59]>> Mhm.

[00:29:04]And in this And in this way we would And in this way um uh whether uh uh whether it can uh be Yeah. I have one question. Could it possible that there were no case satisfying this condition?

[00:29:28]>> Yes, that is possible. There's the answer could be zero. Yes.

[00:29:32]>> So that in these conditions we would return zero, right?

[00:29:36]>> Yeah. So I mean you could take this 312 and instead of 312 you can make it like what 321 or something. Is that possible to sort? Uh I don't think so. But whatever. There's got to be a way to I think this is not sortable, right? This would be uh yeah I think this would not be sortable because if you rotate left you would get one 32. So yeah basically if you have any if you have 132 this wouldn't this would never be possible to be sorted. So I guess this is an easier example. Let's say you had 132 um one would obviously not be possible and three would would not be possible as well because you can't like move elements around in the chunk. You can only rotate the entire chunk right. So this would be zero.

[00:30:21]>> Okay. Okay, got it. So we would f I think that we would first check for the condition for the k equals to one, right? I think this uh this this integer uh is rotatable only have the condition that it could be something like up up and down >> it would be down down.

[00:30:52]>> So I see >> with k equals one actually if you think about it you can only rotate like you have chunks of one. Yeah.

[00:31:00]>> And you can't rotate a chunk of one because a chunk of one rotated is the same thing. So for K equals one, it would have to be sorted to begin with to give you >> Yeah. Yeah. Yeah. Yeah. Yeah. Sorry.

[00:31:10]Sorry. I mean that K equals to N. Yeah.

[00:31:12]Yeah. Yeah. K= to N. Yeah.

[00:31:15]>> Yeah.

[00:31:17]>> And then it would be the and it would be something would be uh to broaden. And then uh if this kind of array and up up up up up up up up up up up up up up up up up up up up up up up up up up up up up up up up up up up up up up up up up up.

[00:31:31]>> I see. So you're basically saying there's one like like it keeps going up and then it drops once and then it keeps going.

[00:31:39]>> Yeah. Yeah. Yeah.

[00:31:40]>> Okay. What if it just keeps going up forever? Like it's all >> Yeah. Yeah. Yeah. That's also possible.

[00:31:46]>> So what would be the case that wouldn't make it possible? I guess to make it more clear.

[00:31:51]>> Yeah.

[00:31:56]I think that um I think that the I think that the number of the non the number of non descending the number of the non number of no descending should be less or equal to one and >> the number of non-escending so descending is this >> yeah Yeah. Yeah. Yeah. Yeah. I think it's not ascending. Yeah. Yeah. It's not >> ascending. Okay. I see.

[00:32:27]>> Then it should be less or equal to one.

[00:32:30]And if it's equal to the zero, if it's equal to the zero. Okay.

[00:32:37]And if it's equal to one, we would check that whether this one is the lowest. uh whether the uh whether the descending uh whether the descending descending I is the lowest >> in the entire array.

[00:32:55]>> Yeah. Yeah. Yeah. Yeah. In the entire array. Yeah.

[00:32:58]>> I see.

[00:33:01]I think that makes sense. Okay. Okay.

[00:33:03]So, this will tell you basically if a chunk is sortable, right?

[00:33:07]>> Yes.

[00:33:08]>> Okay. Now, what happens if you have multiple chunks?

[00:33:11]>> Um Let me see.

[00:33:20]>> A multiple chunks is that >> yeah like let's say you have multiple chunk like so I guess I'll give you two cases. Let's say you have multiple chunks and one of them isn't sortable and then you have multiple chunks and all of them are sortable like what would you do for either one?

[00:33:37]>> Yeah. Yeah. I think that first we we first and check two conditions. Uh the first condition is that whether the inch part is sortable.

[00:33:48]>> Mhm.

[00:33:48]>> And the next condition we need to to check is that whether uh each neighborhood chunks are in ascend are in are in ascending order. That means that the next the minimum of the next chunk should be larger than or equal to the maximum of the previous chunk.

[00:34:09]>> I see. Okay. Okay. So it's like two parts. So basically you check within the chunk and then you check neighborhood chunks. Okay. Okay. Yeah. So and you also need to get like integers of K, right? Like you need to figure out like what numbers of K to use. So bringing this all together, what would be the time and space complexity of the entire algorithm?

[00:34:28]Um I think that uh um uh for example if we have if we have if we have m integers which are uh divisible by uh which divides n and and in this way we would check u uh we would uh check whether it is sortable. in m times and for each for for each k we check it choosing the n time complexity >> mhm >> so that the total uh so that's the total kind complexity would be o n * m as the kind complexity and I think that the each and the and and I think that in each algorithm we run it and without and with using the constant extra space. So that's I think the space complexity could be 01.

[00:35:34]>> Mhm. Okay. So coming back to the factor part. So you said like n has m factors.

[00:35:41]How long does it take to get the factors of n and do you know roughly what like how many that can be like worst case? Um I think that I think the easy the the and I think that it would be the and and if we want to find the MS uh what we need to the time complexity would be the square root of and the square root of n because we only need to check the first square root n part of the n because at least the one divisor should be less or equal to that >> right okay so you're saying it takes square root of n time to get all m factors and then yeah I guess how many factors can there be roughly?

[00:36:24]>> Yes. Yes.

[00:36:26]>> And you mean how many factors could be have of the n?

[00:36:30]>> Yeah. Like if I have a number n how many factors can it have like worst case roughly?

[00:36:35]Um um it's I >> don't know.

[00:36:48]>> Okay, it's fine. I guess to give you a hint, you're you're doing the square root algorithm, right? So for a square root that gives you factors.

[00:36:55]>> So can it be any bigger than the square root?

[00:37:01]>> Oh, no, no, no. This is couldn't be uh >> right like for every square root value you're checking it can be one or two or zero. So it's basically like worst case you know like two times a square root or something.

[00:37:13]>> Yeah. Yeah. Yeah. It sounds because it it can at least gives you it can at least gives you two factors uh and the square root and the n divide square.

[00:37:26]Yeah. Yeah. I think that's could be at most square root of n. Yeah.

[00:37:30]>> Okay. Yeah. Uh I think we have enough.

[00:37:33]You kind of talked about everything. Um so I think we can talk about or not talk about but um what's it called? Uh we we can code it now and we have about 15 minutes or so.

[00:37:44]>> Okay.

[00:37:45]And then we would have to define of uh we would have defined of the uh return integer ding the sum of all the uh sum of sort of and what we need to do is that we have the numbers and that's the only thing we have uh yeah so we guess the length of Um, and what we need to do is that and then what we need to do is that um and for I and what we need to do is that and we have to We have two arrows and what we need to do is that if yeah we don't we don't need to have one to the to so what we need to do is that we we check if n equals to I = to zero and what we need to do is that sort of yeah we uh uh would define a sortable K functions which would be the K and uh uh and the the numbers.

[00:39:40]I will write this function later.

[00:39:45]So now equals to the I equals to the I and what and then we and we would write this functions and then we will define this.

[00:40:06]>> Yeah.

[00:40:07]>> Yeah. Yeah.

[00:40:10]of sortable.

[00:40:14]>> Okay. So, you're basically just going through the numbers, checking if it's a factor, and then if it's a factor, then you are checking if it's sortable >> and then you're going to make a helper.

[00:40:22]Got it. Makes sense.

[00:40:23]>> Yeah. Yeah. Yeah. Yeah. Yeah.

[00:40:32]Because nobody's here. We just let you have an eye.

[00:40:38]So that so that I think the I is the uh I is the yeah let me see I is the chunk number or I is the uh the chunk size and I think I is the >> looks like it's chunk size for you.

[00:41:04]>> Yeah. Yeah. Yeah. is the chunk side. So that so we have the chunk surface and the number of chunks equals to the I and= to times I so that we first we first need to the check side for J R for J and number of checks which is the first thing we need to check that is sortable and um we also have another help some function is that and whether it is sourceful in chunks we define uh >> okay >> we define and other functions. So that uh this functions would be the uh uh this function would be the um this function would be the yeah the sub chunks here you also have the sub sub chunks and the sub chunks would be from the I think this J times size chunk X and the J + one time size minus one.

[00:43:05]So J times trunk size and then J. Okay.

[00:43:08]Got it. Okay.

[00:43:09]>> Yeah. Because that's the open interval.

[00:43:11]So >> that makes sense. Yeah.

[00:43:12]>> Okay. So we first check that is and if the sub chunks and if the sub chunks and if the ch and if the sub chunks is sable if it's not so if it's not sourceable we directly return false >> return false and then the next thing we have is chunk If uh current uh current chunk max current chunk which would be the minimum of sub maximum of sub chunks >> sub chunks and this one would be the minimum of sub chunks.

[00:44:15]Uh that's a sub current check means and if J is greater than one but we need to we need to check if current it's in ascending order so that the current if the current chunk mean is smaller than the previous chunk max next what we need is that we would directly return for us.

[00:44:53]>> Mhm. And then we will also update it pre max pre which we will and after it's the check box and check which are the current we move to the next iterations.

[00:45:36]Yeah. Yeah.

[00:45:38]>> So, I think you just need a comma here instead of the period.

[00:45:42]>> Yeah. Yeah. Yeah. Yeah. Yeah. We will have a comma here.

[00:45:49]>> Okay.

[00:45:51]Okay. So, and then you're going to make the sortable function as like another help. I see.

[00:45:55]>> Yeah. Yeah. Yeah. Yeah. Yeah. We will have sort of a chunk.

[00:46:05]>> Yeah.

[00:46:08]We are sub chunks. So that what we need to do is like build to have a um local equal to and number of uh number of number of dots you zero. So that's what we need to do is that for I in for Don't want to confusion with the other loops for any range of the length of the sub chunks.

[00:46:49]>> Mhm.

[00:46:52]>> Chunks minus one if up. So that it means that if sub chunks if sub chunks air plus one is smaller than the sub chunks we need to do that the number of will be class by one and the code equals to the sub and L + one and and we use it to update it until the minus check and if the number of D equals to zero we would return and if the number of DS is equals to one and the load of mean are equal to the minimum of the sub chunks and in these two conditions we will also return true and the rest of conditions will return for us. Yeah.

[00:48:15]>> Okay. So basically the local min is none to start off but then if there are no drops you just hit this case. So you don't use it at all and if you do use it then it would be like somewhere.

[00:48:27]>> It it wouldn't be none so it would be somewhere. I see. Okay.

[00:48:30]>> Yeah.

[00:48:30]>> Okay. It looks good. Okay. Uh anything else?

[00:48:34]>> Um no I think that that see that seems that that seems Yeah. Yeah. That seems okay. Yeah.

[00:48:44]>> Okay. Um so for this one let's actually do a dry run. Maybe you could take another example um and we can see how that would work or you could use the current example up to you. But yeah.

[00:48:58]>> Yeah. Yeah. Yeah. Yeah. I think that I would use uh uh yeah I would use the current example of the uh three one two. Yeah, I would use this examples. And uh in this way we first we first uh use the conditions of k equals to one.

[00:49:23]>> Mhm.

[00:49:25]>> And in these conditions because for the size one uh we for the each software functions I think because for the one there are uh we don't run anything into the uh we don't run anything into the loop of the ms number of them always equal to zero. So that the uh for the piece one and chunk is always sortful and then uh the first chunk the first the min would be first three and three.

[00:49:59]>> Mhm.

[00:50:00]>> And but for the next one the one is that and it's mean and max will be the one one because y is smaller than three. So that we uh we don't think that it is chunk uh so that we don't think that it is chunkable >> and so we would return and so this would be uh this would be not chunkable and for i= to 1 for k = to 1 not chunkable not chunkable >> mhm >> and for k= two because two doesn't divide three So uh we don't get to check it not checkable and the final thing we want to check is clear equal to three and then example the number of and the number of DS would be would be one >> would be one and and the number of and because we we we only have one chunk so that we just don't need to uh check whether it is sortable inside the whole chunk. So for the big chunk the number of down equal to one and the local minimum I think because only one part they have a down so the local minimum and it is also equal to one which is the minimum of the one and minimum of the big chunk so that we have when k equal to three it is chunk work.

[00:51:36]Mhm.

[00:51:37]>> So in this way we would return sweet.

[00:51:41]>> Okay. Yeah. Yeah. I think this makes sense. So we're right at time. So let's stop. So how do you feel you did? Um yeah.

[00:51:50]>> Uh yeah, I think I'm okay. Yeah. Maybe a little messed up in the in in the definition of the CH size or the or the Yeah. Yeah. the the the number of inside or the an outside chunk and also have a little of messed up in the number of factorials.

[00:52:16]>> Mhm.

[00:52:17]>> And maybe because there was some time complex there was some time complex conraints and a little of and a little challenge for the whole problems. Maybe a little nervous in the code in the coding of and a little nervous in the coding of the and in the in the code and in in the coding and explanation of the codings maybe. Yeah.

[00:52:45]>> Yeah. But overall I think it's fine.

[00:52:48]What do you think?

[00:52:49]>> Yeah. So I think so I'll just break it down what I had. So I think for the first one like I had an approach that wasn't like yours but I think your approach is actually better like the the simple way to solve the first one would be to sort the sources um by biggest and then in a tie you would always just like visit with the bigger number first um which would actually be worse time complexity I think because you need to sort and like sources could be the whole grid. Um so I think your solution is actually better. that. So I was like, I need to understand a little bit what you're doing and make sure it makes sense. Um, and I think it totally makes sense. So I thought this was really good. Um, and then yeah, so for for the first time I basically gave you like a five out of five for problem solving.

[00:53:32]Um, but you had some bugs.

[00:53:36]Uh, and so basically the main things I said is you asked about something that was in the description. So it's like a small thing, you know, you were like, "Oh, is it eight or four?" Um, and it's in the description. So ideally you don't ask for things that are there because then then it's like you're not reading the problem carefully. Um and then you yeah you add a bug here as well. So basically for the directions like >> you want to you want to go >> plus Yeah. Yeah. Yeah. Yeah. Yeah.

[00:54:02]That's >> but I think it's like a very easy uh it's like a very easy thing to fix. So it wasn't like the worst. Um, so I basically said, yeah, I gave you a four out of five for coding because you had a small bug and then a five out of five of problem solving. For context, I think three is like lean higher. Basically, like you passed the bar to get an offer, but if anyone did better, then like, you know, give it to them instead. Um, I think ideally you go for like a four or five and you basically got a four or five in every category for the first problem. Um, yeah, I think like some small improvements like I said, you know, the coding could have fixed the bug. Also, you had some like syntax stuff, but it's like not the biggest deal, especially I don't know how codepend works now. Maybe you have to have like types or something, but yeah, I don't really care. Um, and then yeah, so basically for the first one quite solid. Um, for the second one, I think also quite solid. I think the only small things are yeah, you didn't know like the time complexity exactly and I had to like hint you a little bit, but it wasn't the worst. You got most of it. um and you came up with basically the optimal solution. Like I think there's like two ways you could do it. One is keeping track of min maxes. One is um taking the uh checking if the chunk is sortable and then just actually sorting the chunk and just compare the entire sorted array to like the sorted array and see if it's the same. Um I would have accepted either one, but you came up with a better one because keeping track of minmaxes means you don't need to sort.

[00:55:30]So that's good. Um and then you did have some small code things once again. So like here you never initialized um prejunk max so it's not there at all.

[00:55:42]>> Then the bigger one is there is actually an edge case you didn't catch. I think out of all the people I asked no one has gotten it so far.

[00:55:49]>> So let me just show you. Um if you have something like this basically you're checking for like one drop and the min is like your smallest thing. So in this case your min would be the one but this is not chunkable. Um because it would be like 1 4 3 5 6 is the order. Um so the so the main thing you had to do was you had to actually compare the last element to the first element and make sure there's no drop there as well.

[00:56:11]>> And then if there's only one total then it would work. Does that make sense?

[00:56:14]>> Yeah. Yeah. Yeah. Yeah. Yeah. Yeah.

[00:56:15]Yeah. Yeah. I forgot. Yeah. Yeah. I forgot to.

[00:56:18]>> And then you and then you wouldn't need to see like where the min is like as long as there's one drop total. If if it was completely sorted if it was like 1 2 3 4 5 or whatever um then there would be only one drop total anyway. Okay. So, as long as there's one or less like overall, then you're good. Um, so I basically said I gave you a four out of five for the problem solving because you had the small maybe like four and a half out of five because you had the small like time complexity thing, four out of five for coding because you missed an edge case. Um, and didn't initialize some stuff. Uh, and then yeah, I think the only other thing was maybe you can improve the speed a little bit better.

[00:56:51]But overall, I'd say this was quite good. I think if you took a Google DSA interview, I would be quite like I have decently high certainty that you would pass. You know, maybe like 80%. Um, you know, this wasn't like extremely ridiculous like like I would be crazy not to hire you, but at the same time, this was this was quite good. Um, like much better than average, much better than, you know, like a lean high or whatever. Um, so yeah, I think this was quite good overall. Some small things to work on. Like I said, you know, make sure your code's correct. Make sure you don't miss edge cases. Um I yeah, things like that. Um and then and then yeah, read the problem a little bit more carefully. But most of these things are like very small. Obviously speed. I would say the stuff I ask typically is a little bit harder than what you will get on average because I ask two problems on a pretty time constraint time. um like most of the times you might you might get like one problem might be slightly harder but you'll have like 45 minutes or you'll get two problems but they'll might be like a little bit easier or whatever. So I think if you you did quite well here and I think yeah once you do your like actual Google one I would be uh quite you know I would feel pretty confident that you would do quite well. Um yeah do you have any any other questions or is that kind of clear?

[00:58:04]>> Yeah. Yeah. Thank you so much for your comment that's valuable for me. I only have one question. Do do you have any suggestions for me to do further improvement?

[00:58:16]>> Yeah, so further improvement um I mean I guess obviously figure out what environment you're going to code in.

[00:58:21]Like I think in Google use a Google doc so they don't have any syntax highlighting, right? Like so you're not going to see like here there was like syntax highlighting of things that were wrong. So that you can't really improve.

[00:58:32]Um, I think the main things is so really common issues when you can like clearly hit the bar for passing. Make sure you read the problem carefully. Make sure you know exactly what it's asking and don't solve the wrong problem. If you need to take a few minutes, you know, that's fine. Um, and then and then obviously in your dry run try to catch like maybe try to go a little bit more in depth of like your code and try to catch your bugs. So maybe write write down some of the variables, things like that because like if you have an uninitialized variables, if you just write down some of your variables, you'll realize like, oh, I forgot this variable. Um, also ideally, yeah, try to like look for edge cases a little bit harder. But honestly, if you have, you know, like an interview coming up soon, I think the biggest things is just like rest and try to not be nervous and like all that kind of stuff over than over like cramming problems. I think you're in like a decently good spot. Obviously, you know, it's not a it's not guaranteed. you can get asked some absurdly hard stuff, but if you get asked that absurdly hard stuff, like you're like there's not much you can do, you know. Um, so yeah, I'd say there's there's not too many areas to where I could clearly see like this was a problem. Um, maybe maybe some small things as well is like have a little bit better variable names, a little bit more descriptive so you can like debug a little bit easier. Um, because you had some stuff that was like rii, vq, you know, like whatever. is kind of like a little bit unreadable. Um, so I would say that uh and then make try to make your solutions as simple as possible. Um, but yeah, I don't I don't see any glaring I don't see any glaring issues. Um, so yeah. Does that make sense?

[01:00:10]>> Yeah. Yeah. Yeah. Yeah. Yeah. Yeah. This makes sense. Yeah. Yeah. Yeah.

[01:00:13]>> Okay. Yeah.

[01:00:14]>> Cool.

[01:00:17]>> Yeah. Yeah. Yeah. Thank you so much for your interview and uh also thank So um also thank you so much for uh uh for putting some challenging problems in my interview and yeah in this way it's a way to drill but yeah yeah it's >> yeah I try not to find Google tagged ones. I don't think these are Google tagged because usually when people interview for a company and they ask me to find tag problems they mostly have done it and then I don't want you to just like repeat what you've already seen. Uh it's kind of a waste of time.

[01:00:47]So but this will be pretty similar too.

[01:00:49]Like I think out of all the things I think Google asks the hardest questions or something. So I think asking something pretty hard is pretty good.

[01:00:57]>> Yeah. Yeah. Yeah. Yeah. Yeah. Yeah.

[01:00:58]Yeah. These people these two problems I think I have not and done it before and I and other problems I'm thinking and c it just in time. Yeah.

[01:01:12]>> Okay. Cool. Well yeah catch you later if that's that's that's it.

[01:01:16]>> Yeah. Yeah. Yeah. Thank you so much. And thanks so much for ti.

[01:01:20]>> Yep. Bye.