The Legendary Avenger: Hello?
Gustatory Pumpkin: Hey, can you hear me?
The Legendary Avenger: Yes, I can hear you. Hope you're doing good. How's your day going?
Gustatory Pumpkin: Pretty good. How about yourself?
The Legendary Avenger: So far so good. Cannot complain. It's cold in [Location], but isn't it all this. All right, so maybe give me a quick run through of what you're prepping for as well as what you're looking to get out of this before we get started.
Gustatory Pumpkin: Yeah. So I have a coding, I guess, screening coming up at Microsoft. And I just found out today it's actually a level 63 position in one of the software reliability engineering teams. And so I don't really know if that would be a different type of assessment than standard engineering assessment. I have a background more in the infrastructure side and not really on the software development side. And so I'm a bit nervous if this is just going to be like an elite code kind of situation, but that's really all I know is that it's going to be the standard technical screen, as far as I understand.
The Legendary Avenger: I see. Okay, so it's L 63. Sorry. I came in with my collection of junior questions because it was indicated that this was a junior interview. Okay, let me get my understanding straight. So it's L 63, which is senior, I believe.
Gustatory Pumpkin: Right? Yeah.
The Legendary Avenger: I see. Oh, crap. I wish I had prepped better because I don't have a collection of questions for senior SRE here, let me check. Okay, I'll be frank with you. I don't think I'm too familiar with the SRE process. And so, honestly, I was thinking it was going to be a swee interview. And so I'm not really sure if.
Gustatory Pumpkin: And that's fine. We can do that. As I said, I don't believe it's any different, but I don't know. Right.
The Legendary Avenger: Makes sense.
Gustatory Pumpkin: And then I have another one coming up on Friday with Shopify, and this one's supposed to be similar senior infra role, but again, they have a requirement to do a pair programming exercise.
The Legendary Avenger: I see.
Gustatory Pumpkin: Really? Just give me something just to kind of give me an idea of what I'm doing. If I'm failing miserably, then it gives me at least a gauge on where I'm at.
The Legendary Avenger: Totally fine. Okay. So I'll just make sure I also adjust my metrics, because for context, I think you might know that the coding interview typically will be the same across levels, only the expectations will be different. And so, in similar regard, assuming it's a lit code style question, I would expect it to basically be standardized. The only thing that I'll have is high expectations of you. So with a junior, for instance, I would expect that they show me they can think through solutions. They don't have to necessarily do testing or think through all those cases. But given that this is L 63, there's some extra considerations I'll be looking for in terms of optimality, speed of a solution, communication, of which so far you've started strongly, and testing. So those are the bits I'll be looking for, basically just to adjust the heuristics there. But if you're comfortable, feel free to select the language you want to use and I'll basically provide a question for you.
Gustatory Pumpkin: All right.
The Legendary Avenger: Perfect. So, Python. Good choice.
Gustatory Pumpkin: Ruby. Sorry.
The Legendary Avenger: Okay, shoot. This looks very much like Python.
Gustatory Pumpkin: It really does, yeah.
The Legendary Avenger: All right, so this is what we have here. So you're given a zero indexed 2D integer array of size three by three. And what this does, I don't know if you played that game where it's kind of like a bunch of numbers and you have to organize them. The only difference is in this case you might have some cells that have zero elements. And our requirement in this case is we swap the rocks around. And so I'll give you an example with this one. Okay, can you give me a second? My son kind of woke up, but just go through this and then I'll be back in a few. Okay, sure. You got him? Sorry. Okay, he's been saved.
Gustatory Pumpkin: Okay, great.
The Legendary Avenger: So if we look at this, for instance, the one that you have here is zero, which means for us to actually spread all the rocks out correctly, we'll have to pick one from any of them, really. Assuming we had one here, we can pick from that, but it's really up to us. But here, because this is the only one that has extra rocks, we pick one from it and we can either go one, two, three and put it there so that one rock from the two, or we can go one, two, three. And this is to say that the minimum number of swaps we have to spread the rocks out here will be three swaps equals to three. If we cannot perform any swaps, return negative one. Right.
Gustatory Pumpkin: Okay.
The Legendary Avenger: That is if it's impossible. Right out negative one.
Gustatory Pumpkin: All right. And so if I'm understanding this correctly, I'm just going to write in my own words, if that's okay. So I receive in a two dimensional array, three by three. And is it just one of the values represents an empty block or can there be multiple?
The Legendary Avenger: That's an excellent question. There can be multiple zeros. Okay, so there can be multiple sections that need rocks.
Gustatory Pumpkin: Values that signify needing a block are zero. Values that are non zero signify that n number of blocks exist. And I'm assuming that if there's just one block and I move it, then that becomes a zero. And so that's not an acceptable solution.
The Legendary Avenger: Exactly. So for a spread to be considered, at least in this case, for us to have considered the system as being sold, we need to have at least 1 st within the cells.
Gustatory Pumpkin: Got it. So all stones need greater than or equal to one stones in each cell. If all values are not greater than or equal to one, then return negative one. If all values are greater than or equal to one, then return number of moves needed to accomplish task. And each move is a single adjacent cell, correct?
The Legendary Avenger: Yes.
Gustatory Pumpkin: Okay. So two goes up, one goes up, one goes over one. And so that becomes a one. And so when I'm moving everything, it starts as this. And then it will become this. And then it will become this. And then it will become this.
The Legendary Avenger: Correct? That is very correct. Yes, that correctly.
Gustatory Pumpkin: I plus equals one. I plus equals one. And then return I. All right. Okay. And so now is this something where we shouldn't assume that it's always just going to be size 33? Because what if it's a five X five? Or what if it's non square, so it's rectangular? And so need to be careful here to not assume that three by three is the only way to do this. Is that A fair assumption?
The Legendary Avenger: By line two, it's fair to assume that we only need to deal with three by three in this case. That said, if you can design a more generalized solution, I'll be very impressed. That would actually be one of the things I look for in an L 63 person.
Gustatory Pumpkin: Okay. All right, so let's then perhaps first solve for the three X three. And then we can work on figuring out how to make it more generic. And so the first thing I guess we need to have is just a way to test. And so we will say get moves and then input our matrix. Okay. And so get moves of matrix.
The Legendary Avenger: Three.
Gustatory Pumpkin: So that is what we want to do. And so we will do get moves and we'll do a test that fails. Add another zero here. And so this will be negative one. We want get moves of matrix. All right, so I receive this, and let's assume for right now it is three X three. And so the first thing that I'm going to do is I'm going to. Now I guess that we need to worry about any space and size considerations. Are there any constraints or preferences here. Is this something that I should be more concerned with the space? And so I need to perhaps use non dynamic variables. So like not using arrays or hash maps or whatever? Or is this something where I need to be much more careful with the time complexity and just try not to do o of N squared, for example, like nested loops.
The Legendary Avenger: I'll give you the flexibility to approach it, however you would, so long as it's optimal. To be clear, the core goal for me is to one see that you can code, to see that you can think through optimizations. And here's actually a neat trick about it's not just Microsoft, but a lot of other companies. It's not necessary that you even solve the question optimally. Rather they'll want to see that you can optimize the solution. So even if you don't have the most optimal approach, if you can optimize even one section or two sections of your code, typically that's a good sign. And if you can also analyze the complexity correctly, that's usually in your favor. So in this case, choose any approach that makes sense to you and then hopefully you can optimize it even further if it's not optimal. OKAY.
Gustatory Pumpkin: ALL RIGHT. And so again, then let's move forward with attempting to solve this. So I need to first understand how many empty squares there are and how many extra blocks or stones I have, because that's a quick way to understand if we can even solve this problem. And so that can be a quick fail if it doesn't already exist. And so I will do a matrix total stones equals matrix flatten sum. And so that will give me the total amount of stones that are in this matrix. Just note here is that it is an array operation, looping through all the arrays to get the sum. So this is already a zero n operation in itself.
The Legendary Avenger: GOOD.
Gustatory Pumpkin: So next I have the total stones. FOR NOW, I'M JUST NOT GOING TO ASSUME IT'S NINE. AND SO I'LL JUST DO A PRE OPTIMIZATION. Hopefully I don't get in trouble for that, but I will do num stones or num squares equals matrix flatten length. YES, THAT'S RIGHT. AND AGAIN, OPERATION. Now I can have an idea to optimize this in the future, is that perhaps I could join these two operations into one and run a map. Run each map matrix to combine getting squares. Okay, so now I have the total number of stones and the total number of squares. And so if Num squares is greater than total stones, I'm just going to return a negative one because this means that this is an impossible puzzle to fill all squares with given stones. ALL RIGHT. AND SO NOW I SHOULD HAVE. HOW DO I RUN? HERE WE GO.
The Legendary Avenger: I'll say not to worry too much about running, but if it helps you debugging, that's totally okay. Like, I'm also interested in the general approach, but if it helps debugging, that's totally fine.
Gustatory Pumpkin: OKAY. YEAH, I WAS JUST TRYING TO SEE IF THIS WAS ACTUALLY GOING TO DO SOMETHING. Or am I supposed to name it like a main function or something?
The Legendary Avenger: Let's see, we've called matrix here, and it's not we. DO WE PRINT ANYTHING?
Gustatory Pumpkin: ALL RIGHT, THERE WE GO. YEAH. SO THAT'S WHAT I NEED. YEP. ALL RIGHT, SO NEGATIVE ONE. GREAT. ALL RIGHT, NOW I HAVE TO UNDERSTAND THAT, OKAY, I have all of my squares available, and so now I need to move. And so I will find the coordinates of the zeros, and then I will find coordinates of non zeros, the minimum number of moves required to place 1 st in the cell. Now, this one is going to be a bit inefficient because I'll need to understand a lot of different possibilities. Okay, the minimum number of moves. All right, so first I will have an empty squares array and an available squares array. And so I'm going to use these to track which are the areas that I need to move to and which are the areas that need the, that have the available stones. Available stones. All right, and so now I will do a matrix zero to matrix length each I, and then a row equals matrix I, and then zero to row length each to J. And I will. Oh, thank you. Column. If row J equals zero, then I will do empty squares, I, J greater than one. And then we'll do available stones. The location and the number that is available.
The Legendary Avenger: It.
Gustatory Pumpkin: So now I have where the stones need to go, and I have where the available stones are. Okay, now let's do some back of the napkin math here. So if I know that empty square, let's just assume that the single array is zero, two, and I know that available stones equals two. One number is two. Then what I can do is I will. So two minus zero equals two, and two minus I'll do one minus two, absolute value equals one. And then two plus one equals three. And so I know that moving this to the empty square is three moves. And so for one, I can do that. All right.
The Legendary Avenger: Just out of curiosity, so that's on the basis of it being right here, right on line 27. What if I had another one right here?
Gustatory Pumpkin: If you had one right there. Okay. And so that math would be empty. Square would be zero, two. And then the available stone would be at. And the value is two. And so that would just be zero minus zero equals zero, and a zero minus two. Again, absolute value equals two. So moves equals two. And so because of that, let's just make another test for that while we're doing this. And so now what I need to do is that for each available.
The Legendary Avenger: It.
Gustatory Pumpkin: Each available square.
The Legendary Avenger: I'm hoping you can still hear me. Kind of got dropped for a second.
Gustatory Pumpkin: Okay. Yes.
The Legendary Avenger: No problem. Just to do a quick recap here. So what did we say about the case where we have, like, two stones in the origin cell?
Gustatory Pumpkin: So, I did the math. And so the math would still be the same. That if it's here, then this would be coordinate. And this is coordinate two. And so zero minus zero for the X axis is still zero. And zero minus two. Absolute value is two. And so it would be two moves.
The Legendary Avenger: Excellent. So you're using the absolute distances. It's essentially not Euclidean distance, the Manhattan distance. So you're evaluating the differences in X and the differences in Y in absolute terms, and that's basically your distance. Right?
Gustatory Pumpkin: Yes.
The Legendary Avenger: Excellent work. Okay. That makes sense.
Gustatory Pumpkin: And so here, now here's the inefficient part, because it's easy to solve, but it's more difficult to solve for minimum number of moves. But let's solve this so we have at least something working. And so, available squares each. And then I will have empty squares each. Not available squares, and then available stones each. So I will total moves equals zero, and then return total moves. So now I'm going to just do some math and say.
The Legendary Avenger: It.
Gustatory Pumpkin: Here.
The Legendary Avenger: All right. Feel free to diagnose it. That's totally okay. And I know I'm very hands off. Full context. That's basically how they will evaluate it at L 63. They want to see how you even unstick yourself. Basically, yes.
Gustatory Pumpkin: And so, basically what I need is, I need to get to the total moves, but because I'm iterating through this loop multiple times, I need to see which one of these stones is the most optimal stone to move for each square. And so that's why I'm saying I just need to get the appropriate number of static variables here. Or not static, but variables here, so that I can make sure that I'm not overwriting values that I may need in the future.
The Legendary Avenger: All right, so maybe I have a quick question here. So, say we have multiple. Say we have multiple stones that really require filling, right? So we've kind of identified that we could have multiple empty cells. Can we maybe take a step back and try and generalize the heuristic? Like, how will we know which particular cell should feed a particular stone or a particular empty cell? Of the many cells we have that have more than 1 st?
Gustatory Pumpkin: Yeah. Okay. So what I need is, I need to understand which cell has the least amount of moves to fill each empty cell.
The Legendary Avenger: Exactly.
Gustatory Pumpkin: But I also need to track which cell has been decremented so that I'm not turning that cell into a zero. So let's say that if a cell somewhere in the middle had five and all of these were zeros, then that cell would be left with zero. And so that's something that we can't allow. We definitely need to have a few more arrays here. And so we would have.
The Legendary Avenger: Just out of curiosity, what algorithm will that be? So, say I start from a cell. Let's think of a cell XY. And I want to see which of the cells near me or which of the cells closest to me can potentially donate a rock to me or a stone to me. Do you know of any algorithms that will be suitable for this?
Gustatory Pumpkin: I don't know. I don't have the glossary of terms.
The Legendary Avenger: Let's rephrase that a bit. And so if I was to, let's say, start from my current cell, like, think of this particular cell. Cell, let's say, XY, which are the cells I can move to in one move, or which particular cells can I visit with just one move?
Gustatory Pumpkin: Oh, it would be X plus one or Y plus one.
The Legendary Avenger: Exactly. So there are four know. We call it the von Newman neighborhood in our case, but that basically is following the Manhattan distances. I don't know if you know that. You know, there's some types of distances. So there's von Newman. You don't have to use these technical terms in the interview, but in your case, I'm going to give it to you, because I feel like if you just throw this in an interview, typically it stands out there is another type of distance called more distance. So what you just described is referred to as the von Newman distance. And you can look them up? Not distance, neighborHood. You can look them up if you want to verify. Now, with this in mind, are you familiar? Neighborhood. Okay, that's a long word. Okay, so are you familiar with BFS and DFS?
Gustatory Pumpkin: No, I'm not.
The Legendary Avenger: Okay, so this is concept one. So let's just break it down a bit further here. So this is neighborhood types. The second thing we are thinking about here is BFS and DFS. This stands for breadth fast. And the second one is depth fast. Have you heard of these two terms? Right? So as the name suggests, really for breadth fast, you're looking at the breadth. So if I stand right here, or if I stand on one particular spot, who are my nearest neighbors? And then if I go to those neighbors, who are their nearest neighbors, and you are considering all the neighbors, really? So on any particular cell, if I was to look at, let's say, this cell here, cell zero two, then its neighbors are cell zero one and the one below going by the von Newman neighborhood, if I was to go by the more neighborhood, then it will be cell zero here, cell to the left, the cell below it, and the cell diagonal to it. If it was the center cell, I think it's better. Let's look at example on line 25. So I think that's a better one to use. So if I was considering just this middle cell for the more neighborhood, all the cells are actually its neighbors. So if I was just at that particular cell, I can access all other cells with one move going by the more neighborhood. In our case, though, we care about the von Newman neighborhood. So the only cells that are my neighbors by BFS, by breadth fast, such, those are the ones above me, right below me, to my left and to my right. And they use the formula that you described, plus one Y plus one X, minus one Y, minus one X. Right. And so the reason I'm mentioning this to you is because in this case, if I was to just find the collection of empty cells, the cells that need a donation, and I immediately start doing a BFS, a breath fast such, then I can immediately start scanning for cells that can potentially donate to me. You see Where I'm going?
Gustatory Pumpkin: Yeah.
The Legendary Avenger: And so if I just did one scan, then I see, okay, one, this one, this one actually, because it's one newman. So one scan, it's this cell here, this cell here, and then two scans, the middle cell, one here and the one below and this one here. So immediately I know that this cell right here, by the second move, by the second level, by BFS, this cell here should be able to donate to me.
Gustatory Pumpkin: Okay?
The Legendary Avenger: But in this case, that's one BFS move. What if I have multiple cells? That's kind of the big challenge here, right? And what if those cells need some sort of optimization right now? That's why you think of multiple such as can you launch a simultaneous multiple such and then optimize for some form of shortest path? Like, which of the moves that we are deliberating can we use to minimize how many total moves I have to make while doing this neighborhood search? So that's kind of the trick. And in your case, I can tell you're literally doing the same thing, only that you're approaching it from a more intuitive point of view and less of a traditional algorithmic person who's been dealing with this stuff forever kind of view, which I actually like. I like seeing people with that intuition, because to me at least, that shows more intellect rather than a person who's basically jammed lit code in their head. But, okay, given all of this, I don't know if you have any more ideas, and we can proceed to try and solve it. Just take over, given what I've told you, and see if it can help you in any way.
Gustatory Pumpkin: Yeah, I think where I'm stuck is trying to determine the shortest distance without resulting in the value becoming negative. Right. So I'm thinking of a use case where I have something like this on line 25. I changed the middle one to a zero. And so if I did just a naive search, I would take both from here and be left with zero here and left with two here. And so I need a way to make sure that I'm tracking how many stones in each iteration have been taken. Because that searching for the nearest one isn't going to always result in the correct answer if I don't account for that.
The Legendary Avenger: That's an excellent point. And this is where I can maybe throw this at you. And for context, this is exactly why I constrained it to three by three. So, if you were to ask yourself this particular question. If I was to collect all the cells that are empty and collect all the cells that can donate. Right. Or even being simpler, all the donatable stones, basically. So that's the second question. So we need to collect all the cells that are empty and all the donatable cells. Right. Then for each cell, we also have a sense of the distance to pretty much all the other cells. So, in essence, we are asking for what combination of donor and recipient cell, or what combination of all of them will actually give us the minimum moves. And the minimum moves can be computed by the approach that you use, the Manhattan distance. And so, think of it from this perspective. One, we have a collection of all empty cells. This is scan one. Let's say on scan one, let's just actually write all of this here. Scan one, collection of all empty cells, and then scan two, this is collection of all donor, donor cells. And I'll point something out. You don't even have to think of each cell just because it has two or three. You can actually log it in two or three times because it can donate to multiple cells. So in this case, this one cell can donate here. Right? Assuming it was three. That is, assuming it was three, it can donate here and it can also donate here. Now, if you were to record this, in my case, what I can do is just say this cell has three representations. So I know I have. In this case, there are two extra cells, or two extra stones can donate. So I can just say that. So this cell has two possible entries. So it's almost like a lottery. Can I pick from it twice? Can I pick from it once so I can think of it from that perspective? Now, with that, this is all donor cells. All empty cells. Fortunately, this will just be a singleton, or at least in this case, it will only have one. Now, the third question is, I need matches, or I don't know how to refer to them. Is it permutations or combinations? Actually combinations. So we need combinations of donor of donor and empty cells. And the core goal for us is to minimize total Manhattan distance. The Manhattan distance, by the way, is exactly what you're saying. So this is just distance along more, not more Vaughn Newman neighborhood. The opposite distance that considers diagonals is actually called the Euclidean distance. So you can also use that. It's really up to you. So this is kind of the general question we're asking yourself. So if I was to pick this cell, another one in the empty cell. So let's say here I have, let's say ex one. So this is empty, right? And then this is just copy this. Let's call this that E Y one. And this is ex two. E Y two. So say those are our empty cells and those are our donor cells. And then in this regard, you can even generalize this further. Then we say this is DX one. DX two. X one. Donor Y one. Right? And we can repeat that. Say this is donor X two. Donor Y two. Generalize this to ex, let's say N two. Eyn, same case, X-N-Y-N. All right, so with this in mind, what we're looking for are combinations. So what kind of pairings you can achieve? And this has to be pairings. This is something to note. All of these cells here must be paired to at least one of the cells here, right? So we know that's one thing we need to look out for. So all empty cells must be paired to at least one donor cell. That's one thing we know. I don't know why it keeps autocomplete really at a minimum. So let's go stupid simple. What I can do is simply try and randomly assign them. So just make sure you're generating unique combinations of a cell here and a cell here. So it's literally this combination, this. Alternatively, I can also generate combinations or permutations of all the cells here. So I can literally just generate all possible permutations. Of what size of size? Let's call this K. Let's call this size here K. So we can generate all possible permutations. And in that regard, let's actually say this is K. I can generate all possible permutations. So palms of size K and evaluate their distance. So once I generate all the permutations of size K, I can evaluate their pairwise distance to each of the cells here.
Gustatory Pumpkin: Right.
The Legendary Avenger: Do you see where I'm going with that? Yes. And that can be my basis. So if I find any cells, that if I find a combination that minimizes the total distance, that's the combination I.
Gustatory Pumpkin: Need to go with.
The Legendary Avenger: Or that's the result I need to go with. Now the tricky part, as you can tell, permutations are expensive to compute. And it will almost be obvious when a permutation just doesn't work. And that's where DP can come in. You can easily prune the tree, because in generating permutations, you are basically branching out. And the BFS approach I told you about, that's the branching out. So sometimes you'll realize that there is simply a better move I can take. Or if I've seen a better move before, then I know I don't really need to recompute. Like as soon as I know a distance has been exceeded and it's bigger than the minimum I've seen so far, I don't need to consider it again. And so this is where they are pruning techniques. So, considerations to think about here you can prune a search tree. This is when generating permutations. Does this make sense?
Gustatory Pumpkin: Yeah. So when you say prune the search tree, would that be this kind of collective where you're doing effectively, if this is K and this is D for donor, you're actually creating a data set of K times D in size. And so is that what you mean, that you're going to prune that tree, KD tree, or array of all of.
The Legendary Avenger: The distances by pruning the tree, I'm referring to strategies that we can use to avoid going down a rabbit hole when computing distances, and an example here of pruning. So there are multiple strategies you can use to prune in full context pruning, even, right from the word itself, by definition, it's the process of cutting branches on a tree, right?
Gustatory Pumpkin: Yeah.
The Legendary Avenger: So like as a coffee Farmer or something, you go cut the branches of dead branches, stuff that you don't want, taking resources from your main tree. Now, in our case, we know for sure that there are paths we will not want to explore, mainly because they are just not better than anything we've seen so far. So let's say we've started the permutation scan and immediately we find a distance X. Then we evaluate that distance, and that distance is, let's say 15. Then we start evaluating the running sum. So we go to another permutation. We are starting to evaluate the running sum. We realize that for this particular sum, it's already at, let's say 15. Even when we are halfway through the computation at that point, we immediately tell ourselves, yeah, it's never going to be helpful. So we immediately skip that, right? So that could be one way that's an example of not exploring in this case, that's one strategy. Not exploring permutations with larger and mean sum, or mean so far sum, that's one optimization. I'll be frank with you. There are so many such optimizations we can use, and it's really up to us to define how we want to generalize that. But at the end of the day, this is one of them I can think about. Once you start solving the question, you'll actually see more solutions. And I'll do this because I really want to see you solve this. So I'll give you some code to go with. I know this is Ruby, which I'll admit, I don't know much of Ruby, but I'll give you some starter code here and you can use it. So give me 1 second. So I'm just asking chat deputy to provide us some template code that we can use. This, I'm not going to lie, I also use chat deputy.
Gustatory Pumpkin: Yeah, no, it's great, man.
The Legendary Avenger: So this is like some helper code. Feel free to use it. I know the permutation ones can be a bit tricky, but feel free to use this above. So we know their coordinates pretty much. And this is size K. We know it's the size of the empty cells we need to work with. I know you can scan for the empty cells. Now it's your job to build the list of the other cells, the Main cells. So build the list, and then use this kind of function to get those size K permutations. And then from there, use that to actually evaluate those distances. All right, so I'll throw this in here.
Gustatory Pumpkin: Feel free to use it or not. Permutations.
The Legendary Avenger: And if you want to try to just print it just to see how they look like, you can also do that.
Gustatory Pumpkin: Yeah. Permutation of coordinates. Sorry, I'm just trying to understand what.
The Legendary Avenger: Feel free to print it if you want. Just try and print it, and then we can go through it line by line just to understand how it helps us with the solution. All right, so what has that done? So we have this collection of 12345, but what it's giving us is tuples of one. 2231-234-1245 so it's combinations of size two. So in similar regard, if you build the collection of donor cells. So just go in and retrieve all the coordinates of the donor cells, and then generate size K permutations. And by permutations here, we're just looking for different orders, right? Because order matters. With permutations, then generate the permutations of whatever donor cells you have. Now, what that gives you is, and mind you, size K's are actually the total number of empty cells. That's the only bit that you're interested in.
Gustatory Pumpkin: Got it? Okay.
The Legendary Avenger: Yeah. So what that gives you is one, a static list of empty cells, possible places that you can borrow. And then it's up to you to test which of the borrowing patterns gives me the best results. That's literally what you'll be looking for here. So I was going to say at this stage. So let's see. So right here within this loop here, what you're looking for is empty squares and available stones. So as soon as the loops are done, you have two things. You have a collection of empty squares or empty cells, I'm assuming. Right. And you also have a collection of available stones. And here I'll look for something with greater than size one, because that tells us we can borrow from it, which is exactly what you've done. Right.
Gustatory Pumpkin: And so here, should I change this to instead be row of J minus one timeS? And so instead of putting the number in here.
The Legendary Avenger: Save the actual cell itself. Yeah, exactly. IG perfect.
Gustatory Pumpkin: Now I just have the spares and not anything else. Okay. Yeah, I think that'll simplify it a little bit. All right.
The Legendary Avenger: I was going to say, you probably want to have as many spares. So in this case, because our permutation list can contain, we saw that entry where there's one cell that can donate three times. So in this case, you can either use this approach. In my case, I would have used some other approach using, what do you call it, using hash maps to optimize that further. But that's an optimization. A simpler approach will be add it however many times it can donate. That's the brute force approach that we can use here, right?
Gustatory Pumpkin: Yeah, that's what this is doing is it's going to loop through the available times and add that to the array. And so IJ will exist. If this was three here, then IJ will exist twice.
The Legendary Avenger: Perfect. Hence the minus one. That certainly makes sense. All right, so from there, now, you see, as soon as you're out of the loop, the next thing you can do there is use the function we have. So what you want to do is get all permutations. So in this case, I generally don't know, Ruby code, actually.
Gustatory Pumpkin: No, that's fine.
The Legendary Avenger: What you want to do is repeat this process here and say possible, what do you call it? Solutions. Possible solutions here, and just get this off. So you're going to take that and then you're going to check for the possible permutations of what in our case, we know it's of available stones against empty squares.
Gustatory Pumpkin: Length. Yeah.
The Legendary Avenger: Because that's our K, right?
Gustatory Pumpkin: Yeah.
The Legendary Avenger: We can even put that as a K here. Just say K equals whatever value we have here. Now with this, we can now evaluate the minimum distance. So if you come here and initiate this, and this can be, currently it's nil, but you can initiate this as a very large number infinity. I don't know if INF is a thing. Is there infinity?
Gustatory Pumpkin: Yeah, there is, but you have to do, I think like float infinity or int infinity.
The Legendary Avenger: Makes sense. Yeah, let's say, I don't Know, float infinity. Okay, you know what, let's just say it's infinity. Or a million or nine. Nine or whatever the number is. That's a very big number. That is so that every number is smaller than it. Now, the question we need to ask ourselves here is for each and every possible solution. So you loop through each possible solution and evaluate the possible solutions against the empty squares. Because the order of the empty squares is not going to change. You're going to keep it as is. And it's our job to now just test out the different possible empty solutions that we have. Empty squares that we have against the possible solutions that we have. And for each of them, we are just going to compute the pairwise distances. The pairwise distances. So pick a number pick another number, check for the absolute distance between them. And given that we've generated all permutations, we know for sure that we'll find one of them that has a minimum distance, like just the right combination of permutations.
Gustatory Pumpkin: Right.
The Legendary Avenger: You see where I'm going?
Gustatory Pumpkin: Yes.
The Legendary Avenger: All right. You want to write that out?
Gustatory Pumpkin: Yeah.
The Legendary Avenger: Okay.
Gustatory Pumpkin: Here. So I have the total number of moves. I have it here. So empty squares each. So possible solutions. So there's a solution. So for each solution, now, this permutations syntax, it'll do one, two, and then there'll be a two, one, two, and two, three here. And then there'll be a 2312 as well.
The Legendary Avenger: I'll see. How about we print it? Yeah, just try and print it. And let's see. Given our example matrix there, let's see what it gives us.
Gustatory Pumpkin: Okay.
The Legendary Avenger: Because one thing I like at least about doing these interviews is even if we are not able to go pure interview mode, I like making sure that my candidates come out with one approach that they thoroughly understand.
Gustatory Pumpkin: Yeah. It saying min moves. I don't have that anywhere.
The Legendary Avenger: Min moves. Did I print something out? I do not think it's anywhere.
Gustatory Pumpkin: Okay. Now it's just an unexpected end of input. Oh, right here. Okay, so it's.
The Legendary Avenger: All right. So what is that for us? How useful is that for us?
Gustatory Pumpkin: So this is telling me that therE's just two iterations possible.
The Legendary Avenger: All right, so let's even make it more complicated. We know that one example we talked about, so let's do that. And then for the possible donor cells, let's make it that way. So what will that return? Let's just see how that looks like.
Gustatory Pumpkin: That's good.
The Legendary Avenger: So what is that giving us?
Gustatory Pumpkin: So it gives me. And then there's a 10. Zero. Okay, so it is flipping all of them around in every possible permutation of it.
The Legendary Avenger: Exactly. Now the question, let's go back to it. We have available stones. That's the locations of sections that can donate. And we can see can donate multiple times. Same case. I think it's it. Not really sure which one it is.
Gustatory Pumpkin: Yeah. Zero. One can donate, two can donate multiple times. And no, that's not zero. Two. That's 20. And then two, one can donate once.
The Legendary Avenger: Yeah. Although I cannot see examples that have 02103. So I think we might have something wrong. Okay, do you see why that's the case?
Gustatory Pumpkin: Yeah, let's see. Available stones. Permutations of coordinates. Okay, available stones. I have this. And for every. If Row J is greater than one, that's why I replaced it with I here I see.
The Legendary Avenger: K in this case.
Gustatory Pumpkin: Yeah. Because it's I, J. And inside J is K. Yeah.
The Legendary Avenger: All right, let's try that again. Let's make sure it works perfect. That makes sense. That only makes sense to me. Okay. All right. So with that in mind, now we know we need to loop through both the eyes and the possible solutions, I think take over and just get the solution going.
Gustatory Pumpkin: Okay, so possible solutions H. And so then I'll do for each cell, I'm going to wait, not, so I have empty squares. Empty squares is a flat array. And so I should probably flip it around and do empty squares. Each do cell. And then.
The Legendary Avenger: I was going to suggest, given that you will be repeating the process with each empty cell in the empty square, maybe we should have the same thing you have like permutations. So the possible solution. So for each solution. Okay, right. Same thing you have. Exactly. And so once you're in here, so you're doing solution for each, but right here it should be simultaneous. So it should be both the solution as well as the empty square. Because the size of solution here should be the same as the size of empty squares. Right.
Gustatory Pumpkin: Got it. Okay. And so then the solutions. Okay, so then I do zero, two.
The Legendary Avenger: K, and you can still use K because we still have it there as a value.
Gustatory Pumpkin: Okay. Yes. So then for each cell.
The Legendary Avenger: It. All right, here we compute that distance. Yeah.
Gustatory Pumpkin: I should probably just make a method for cell distance here.
The Legendary Avenger: Exactly. That's goodbye. It.
Gustatory Pumpkin: Should return the distance for each cell. And so distance plus equals cell distance of possible, no, of solution and empty squares.
The Legendary Avenger: You.
Gustatory Pumpkin: Then I say if distance is less than total moves, then total moves equals distance. And then I return the total moves.
The Legendary Avenger: Exactly. And I was going to suggest at this stage, you remember that optimization we talked about? So if distance is greater than or equal to total modes. Right. Immediately break. You don't need to keep going. That's one of the pruning things I was mentioning.
Gustatory Pumpkin: Oh, okay. Got it. Okay. It, yeah. So we can do that next. Okay. What doesn't it like? No, imperial conversion of integer into array. Integer into array. What's so 10?
The Legendary Avenger: It's that Manhattan distance computation that's giving us a problem.
Gustatory Pumpkin: Yeah. Zero. I'm passing cell one is a pair. Okay. Yeah, I'm just passing it wrong. So it'd be solution I.
The Legendary Avenger: That's.
Gustatory Pumpkin: Okay. Distance.
The Legendary Avenger: Okay, you can use that too if you want. I provided some extra code down there where on line 64 should be the same thing really, only that I didn't.
Gustatory Pumpkin: Have like a distance. Yeah. My mistake was how I was calling it online. 115. I was passing it the set for the solution, not just the first or not just the I of the set. So I added this.
The Legendary Avenger: I. Oh, I see.
Gustatory Pumpkin: Okay. Distance. I've added distance here. So why doesn't it like distance? Yeah, that should see distance. Okay. This was an old error. I see. Okay. Four. That's the answer. I have a put somewhere that I need to remove.
The Legendary Avenger: All right. I think that's actually the correct answer. So we're good on that. We can try with our original example here. We knew it was one here. You want to try that out, see if it works?
Gustatory Pumpkin: Yeah. Three.
The Legendary Avenger: Heck yeah. We got a three. Good job. All right, so let's take a break, at least from the interview mode. I know, you know, we've gone quite over in terms of typical allocation for time, but thank you. Overall, I'll say it is totally okay, because we kind of transitioned from interview mode into helping each other to look through general permutations, because they're very common subset of questions to be asked, especially by Microsoft. In fact, I'll say this has been the most popular question Microsoft has asked for coding interviews for the past six months. I want to start with you. So, looking back at the interview, you can obviously identify areas where you think you did well and areas where you think you could improve on. So maybe run me through that. So what do you think you did well and what do you think you could improve on?
Gustatory Pumpkin: I think I'm pretty good at kind of communicating and just kind of walking through what the requirements are and identifying relatively early where issues and complexity is going to arise when looking at the problem. And so I feel like I was able to at least demonstrate that I can look at a question and see which parts of it are going to be easy and which parts are going to be the ones where it'll need more time. I think that's about all I can say for what I did well. I think what I didn't do well was finish the development in short order.
The Legendary Avenger: I'll say, don't beat yourself up too much, because I think I mentioned this quite early, almost at minute 39. I immediately pointed out that there is usually two things I will be looking for, and I need to also keep it honest with you. Not all interviewers will be looking for this, but sometimes you'll be lucky. You'll find an interviewer who has that intuition. There's a reason I work for interviewing IO because I'm kind of trained to look for more than just basic solution. I also want to see the ability to think. In your case. I don't know, maybe I can Just ask this randomly. Are you from a standard CS background or did you go to the SRE route?
Gustatory Pumpkin: No. Yeah, I don't have any kind of formal, you know, I did a few Microsoft access courses, things like that when I was in, but like, it was just basic scripting. And then after that I got more into the Just SRE type DevOps work, which I've never been what you would call a formal software developer and never really did any class on algorithms or anything like that.
The Legendary Avenger: And that's totally fine. That's where I tell people it's not about path that you used. At the end of the day, clearly there's also an element of thought. And by the way this solution has panned out. You can tell that you could kind of get there, but there's still some areas that were not as apparent. But overall, you could easily see that you have the intuition as to how a human being should solve this. I feel like that's usually the bit that most people fail to even communicate. And I'll tell you a secret. One thing I dislike about people who have a CS background is, and I'm one of them, so this is also something that I had to give up myself. But because of the emphasis on some of these core terminologies, a lot of us forget to even explain what some of those are like. You might hear me in an interview sometimes just say more distance, or von Neumann distance, or whatever it is, or BFS or DFS. You'll hear people throw these terms and there's a benefit to it, but there is also a loss to it. The loss to it is if you don't have a background with some of this, it's over your head. You're like, what the heck is BFS? What the heck is one Newman? It just sounds like an obstruction. The benefit to it, though, is, if you know what it means, it saves you two minutes of having to explain what you're picking, what you're combining. You're just saying, I'm going to use BFS for this, rather than saying, I'm going to do a level by level neighbor exploration of which I'll save all neighbors into an array, and then I'll look through each neighbor and evaluate them again. You just say it's BFS, and immediately somebody knows what you're saying right now. The reason I'm mentioning this to you is there's a benefit to looking at some of this, and I'll keep it real. You probably won't see them at work too often, but they will eventually show up. Those are the fundamental terminologies and patterns. And if you look at a list such as neat code, let me share this with you. I don't know if you're familiar with neat code.
Gustatory Pumpkin: Yeah.
The Legendary Avenger: But if you're going to do prep, you'll see that he has pretty much all the patterns covered. What he doesn't have is he doesn't have the structures and algorithms listed out. So you'll see the patterns, but you will not see the structures at a high level. That said, if you're to go into, actually, I am wrong. If you actually go into knit code 150, he actually has them. You'll actually see them, the likes of backtracking permutations and all that. They're actually all there. So that's actually really good. He expanded it. So if you just look at the knit code all list, you'll see everything you really need. So there's sliding window, there's the like of stacks. And let's see if I can find the one we've been looking at. I think it was under trees, and particularly we were looking at BFS and DFS. So that should be in traversals under trees. Do we have anything to do with that? I'm just checking it right now. Excellent. This is good. So if you look at the, I don't know, do you have the knit code site open?
Gustatory Pumpkin: If you can.
The Legendary Avenger: So if you go into knit code all and you look under trees, you'll actually see that he has maximum depth of a binary tree. I don't know if he has BFS and DFS, but it should be there. Breadth. Let's see breadth. Okay. He doesn't explicitly list it, but you can kind of see problems that would fall in that category. So an example will be maximum depth of a binary tree that immediately tells you DFS depth first. Such, and the reason I'm pointing this out is you can see how these terminologies come in handy to abstract a lot of logic that you'll otherwise have to explain from scratch. Right now, I'll urge you to familiarize yourself with them. You don't have to do it from scratch right now because I imagine that your interviews are going to approach soon enough. And so you don't waste too much time going into the theoretics, but familiarize yourself with some of these terms. Unfortunately, and I'm not just throwing this in because I work for IIO, they actually have created a guide for us here. So if you actually look it up under the learning center, all these patterns are very in depth articles, of which I was one of the writers, so I do know they were well explained. Okay, so this is an area I'd highly recommend you look into because it will give you guides for pretty much all patterns you would ever need. And they actually also include a curated list of Microsoft specific questions. So it includes both way the loop goes, but also questions that Microsoft commonly asked. Now let's see. In terms of core feedback, you are right. Like, your communication is spot on. I was able to easily follow everything you're saying. I really liked your line of questioning when it came to clarification, which is really good. Now, the one part I'll add you to be mindful of is how long you spend on any particular section. With coding interviews, particularly, you want to, let's say, keep it less than seven minutes with clarifications. So that obviously means minimize, let's say, how much output you're writing. Because sometimes that writing process is what takes up time. So you want to quickly jot down summary points without really being overly exhaustive. You want to run through as many examples as you can, run through that clarification as fast as you can. And this only serves to help you because it maximizes how much time you have with the actual solution. And then there was something I like that you did. You are actually doing complexity analysis on the fly. Do that always because it saves you, especially since sometimes you don't have enough time at the end to actually do the complexity analysis. So what you did was AcTually ReallY Good. LIke AnAlYZE As You Go OR AnalyZE as SoON As You've IdenTified A SoLution. But that Said, this PreemPtS Identifying the Solution Very Clearly. So Make Sure Even before you start To Code, you've Run the IntervIewer through what you want to do. Like, you see what we did here? You can see what I did. I broke down the Steps. And WHile this Is EXtrA Detail Than I would Normally Write In An Actual InteRviEw, this Is Kind of what I Tend to Do. So Write down the General Steps of what you want to Do before you jump into the Code. And for Me, I'Ll give you an Example of How I'Ll do it. So I'Ll say, okay, so I'Ve Identified the Problem here. We have Multiple Cells. We have Multiple possible Donors. So at the Gist of it, I'm looking for Combinations. So in this Case, it's actually Permutation. So I'm looking At Palms of Size, of Size EmPty. So this is what I'Ll say. So, At a Fundamental Level, I'm looking of Permutations of Size Empty that Minimize the MaNhattan Distance. That's what I'm looking for. Given that I'Ll be Generating the Permutations, Then Obviously the Minimum Space Complexity Will be of Size palms, In this Case, Palms K. And under the assumption that all cells Are EmPty ExcEpt One, then this Tells me that I'Ll basically be Checking up All Cells of size N, Where N. And here I'LL say N is EQuals to length Times Width, which is all Cells. And if the IntervIewer wants To know the Exact ForMuLA for Permutations, I'Ll say, I might not have it off of the Top of My Mind Right now, But I know for sure It's a Factorial. So they are Factorial Possible Amutations. Now, with this in Mind, I Know that the Space Complexity Would Also be N multiplied by N At Each Stage. So this Tells me The N EmPtY Cells and All of them need to be Compared Against, Need to be Compared AgainSt All Other possible Donors. So this TelLS Me that this time Complexity Will be old N to the Power Two. And you can think of it from A Very Holistic PerSpective, where imagine Half the cells Are EMPTy and half the cells are donors of just one cell. Then each cell has to pick one from another cell. So that tells me that we'll be scanning all cells against all other possible cells, and we'll do this n times. So it's actually n cubed. So it's n squared, although that's pairway scanning. So it's technically still over N, but it's n to the power two. And then this will be repeated. We get all the distances and we find the minimum. So this is space and this is time. That said, I can potentially optimize this. So if I generate. So here I can say generate bums on the fly. So what I can do here is I can do the scanning as I generate them. So this means I can potentially optimize this to only require of K. Actually, it's of N, where N is the size as we defined it up there. So I can potentially optimize this even farther so that I don't need n factorial. And what I mean by this is, as I generate those permutations, I immediately test. Do you see where I'm going?
Gustatory Pumpkin: Yeah.
The Legendary Avenger: And don't ever save. So this is what I'll do. And you can see that's exactly four and a half minutes. So that's the description I'll use four and a half minutes and then immediately start the solution. And this has gone even into analysis. It's gone into optimizations, it's also gone into the general solution. So if I told my interviewer that, and then I ask, are there any other posts? And here's actually another neat trick. You can always ask your interviewer, does this address the question you have, or do you want me to think more optimally? And the trick about this is, if there's a better solution, typically your interview will tell you, can you think a bit more? So it helps you avoid going down a rabbit hole with a solution if there's a better one to think about. Makes sense? Yes. All right. And let's see, anything else other than that I forgot to mention. And as you can see by the cases I'm throwing up here, there edge cases, you can think of worst cases, best cases. So make sure you're also thinking about how those actually look like. So if you think the performance will be a certain complexity, make sure you're justifying it by giving an example off of the top of your head that would lead to that complexity. So you've seen an example here with me saying, if I was to optimize this to O of N, I'll basically generate on the fly. In this case, the worst case complexity will be where n over two cells are empty and all donors have only one cell. This is like the worst case complexity because it means each cell has to pick from at least one other and they're all different. So if you cite a particular complexity, make sure you also justify it with an example. Does this make sense?
Gustatory Pumpkin: Yeah.
The Legendary Avenger: All right. But other than that, you have the fundamentals. So my general advice will be use the resources I've shared to go through those fundamentals. You don't have to master all of them. Frankly, it will take a while, but be familiar with the core terms so that you're not blindsided by any of them. Two, in this regard, make sure to also justify your complexities. Keep the communication strong. Minimize the amount of time spent, especially on deliberation. Or if you're going to spend a lot of time, make sure you just make it a bang for the buck by also doing analysis as you go, and also proposing end to end solutions. Make sure you prompt your interviewer before starting to code so that tell them the solution you want to go with, and see if they are thinking of a better one before jumping in. This saves you a lot downstream, but other than that, keep practicing. Use the knit code list, use the IIO list that I just provided and keep practicing because that's the only way we get better. And at the end of the day, you clearly have the technical bits checked. You can code, which is good. The rest of it is all problem solving and familiarizing yourself with the core fundamentals in terms of terminologies.
Gustatory Pumpkin: Yeah. So how far away am I right? Because as I said, this is a level 63 interview and. Yeah, and so I. I don't know, like.
The Legendary Avenger: Yeah, go ahead, I'll tell you this. So one of the things about SRE interviews that I know about is they actually would probably give you an easier question than this. So that's one thing I know. Typically it will be easier than this. So that works in your favor. That said, I'm not going to sit here and lie to you. I still think you need a lot of practice. If I was to give you an exact timeline, under the assumption that you are actually crunching, solving about five questions a day, I would say you're probably a month off to cover all the processes that you need. So if I were you, and my interviews, let's say next week or the week after, I'll probably ask them to push it a bit farther so that you practice a bit more. And I would say you probably could benefit from either dedicated coaching. If you want to use the platform here, you can get a person like me curating plan for you to just practice. They throw like a certain pattern of questions and you go through them. Alternatively, if you're okay with south pacing, knit code is an excellent list. I would even invest in Litcode premium and solve the Microsoft questions. You don't have to solve all of them. I would say just solve as many mediums as you can. Definitely solve all the easys. If you just do that, which you can do within a month, it should get you there. And in terms of preparation, I would say use either the learning center here, which is free. The downside to the learning center is it's not necessarily a curriculum, but honestly, it should get you where you need educative. IO is also a good resource. But honestly, I think the explanations on IIO are better. Like, we have engineers who actually interview you. They are giving you a perspective that is oriented towards an interview. So I'll just use this to build the fundamentals with the terminologies and then use those standardized lists to actually familiarize yourself. And I'll give you this spreadsheet that I really like, and you can use it as a self tracker for context. You can time yourself, you can take notes to make sure you're actually knocking off all the patterns that you need. Does that address your question?
Gustatory Pumpkin: Yeah, no, thank you. Thank you for that feedback. Yeah, I've been doing a lot of. What's the site that I've been doing? Have you heard of code signal?
The Legendary Avenger: Yes, I do know code signal. I hate it because it always gets me, but I definitely appreciate what it does.
Gustatory Pumpkin: Okay.
The Legendary Avenger: It's a fair resource, too.
Gustatory Pumpkin: I've been doing that. If I just keep doing that, or should I switch to neat code or lead code, in your opinion?
The Legendary Avenger: In my opinion, I'll use both because there's nothing preventing you from doing it. That said, the one benefit to lit code and neat code is one knit code is actually based off of lit code. So using one or the other pretty much the same. The one benefit is interviewers are lazy as heck. They're not going to come up with new questions.
Gustatory Pumpkin: Okay.
The Legendary Avenger: Which means you're more likely to get a lit code question than you are to get a code signal question in the actual interview. So using lit code, especially if you have the premium account, trust me, you will be surprised. I'll give you a quick tip for meta interviews. All the questions I was asked were lit. Good questions, all of them. And keep that in mind. Those are four interviews, two questions each. Eight questions, and all of them on litcoin. I was stunned.
Gustatory Pumpkin: Okay. All right. Yeah, we got work to do.
The Legendary Avenger: Absolutely. And don't take this in any way. Don't take it hard or anything like that, because I feel like that's the one key thing to make sure you get out of a mock interview. In a mock interview, if you perform too well, it was probably useless. You're already good, right? If you struggled, good. That's the purpose of you needed to iron out your weaknesses. So in this case, we've identified them, work on them, get other mock interviews. In fact, a quick tip I'll even give you is conduct mock interviews yourself. See what other people are failing at. Build that instinct to see what the interviewer could be looking for in you. It doesn't have to be company oriented. Just watch other people solve and see what they're doing, where they're messing up, and then learn from it. Sometimes the best lessons you can gain are from watching others do the same thing. But keep the practice going and you're going to do well. Okay.
Gustatory Pumpkin: Okay. Thank you so much.
The Legendary Avenger: Absolutely. All right, man. I hope you enjoyed this. And, yeah, have a good evening.
Gustatory Pumpkin: Yeah, you too. Bye.