We helped write the sequel to "Cracking the Coding Interview". Read 9 chapters for free

Islands After K Days of Erosion

Watch someone solve the islands after k days of erosion problem in an interview with a Google engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Interview Summary

Problem type

Interview question

Given a 2D grid where 1 represents land and 0 represents water, find the number of islands remaining after K days of erosion. Each day, any land cell adjacent to water becomes water. The challenge involves efficiently calculating how long each land cell survives before being eroded, then counting connected components of cells that survive past K days.

Interview Feedback

Feedback about Verdant Gazelle (the interviewee)

Advance this person to the next round?

Yes

How were their technical skills?

3/4

How was their problem solving ability?

4/4

What about their communication ability?

4/4

Technical: 3 out of 4. I think it’s very important for you to finish writing the code for a working solution, and I think it’s possible you could’ve done this if I accommodate another 10-15 minutes for you to finish writing code, so I don’t think I can rate you any lower 2/4 or higher 4/4 today. For the same reason, I would advance you. Problem solving: 4 out of 4. You have quite strong problem solving, and pretty much came across a working and optimal solution yourself. You’re very structured in your process, and considered runtime up front. Communication: 4 out of 4. I understood what you were thinking the entire time, with a couple pretty minor stumbles that I don’t think are worth rating you lower at 3/4: once when discussing the innerness solution and I misunderstood, and the second when I think you actually meant BFS since that’s what you talked through but actually meant DFS. I think the latter might be a technical point where you acknowledged you might have overlooked if you were going too fast. Things you did well: - You seem to be quite prepared, and you were able to talk through the Number of Islands problem, solution and complexity analysis easily. - As mentioned, your problem solving strategy is strong, where you talked through an initial brute force option with simulation, then came across an optimal and correct solution yourself without much strong direction. You immediately recognized the perimeter/distance search solution after briefly talking about simulation, then refined this solution over 15 minutes. - You considered concrete examples yourself, which was very clear and useful to do. - You were organized in writing out notes in comments as needed. - You balanced working with your interviewer to stay on track while driving appropriately for the level you're targeting. - You were very careful in your C++ syntax to make sure it was readable, idiomatic and correct. Your naming was helpful and you used code modularization when needed. You stubbed out an uninteresting method with sound reasoning. You also mentioned you had good reasoning to spend time writing out types for readability, which makes sense. Areas of improvement: - As you know, the biggest area of improvement is pacing. You spent 16 minutes planning today and 19 minutes writing code and pseudo-code, which is right up against the default time limit for an interview. - You took quite a bit of time to write readable, idiomatic and efficient C++. My advice: - You're quite self-aware, which is good. You mentioned your feedback is now quite consistent across interviews, which means you have a strong signal to go faster. Your time accommodation is very helpful. If your timing today is consistent with your other interviews, then I think you can spend ~3 minutes going faster in planning and most of the time going faster when writing pseudo-code and code while maintaining correctness. It's possible with an accommodation of +15 minutes and if your estimate is right that you could finish writing code within that time, then that would bring you right to your time limit, so to be safe, you definitely have room to save ~5 minutes going faster, or ~10 minutes going faster to have buffer time to go through tests and talk about runtime again. - It would be nice if you didn’t have to write C++ :) You had very sound reasoning about correctness and writing readable, idiomatic, correct, and efficient C++ code. You have good reasoning to go slowly here, and I agree that this is important that there's some balance with correctness and readability and pacing, so I think this is the best opportunity to improve on time. Maybe more practice would help you write readable, idiomatic, correct C++ faster. You had quite a few points where you mentioned you would write C++ a different way, but sacrificed on readability for the sake of time -- you could probably do this more without mentioning it every time. Background context: - Waymo/Google - C++ - L5, L6 - 10 years of experience - Meta team matching - Either too fast, don’t plan or too slow, not urgent - Would go slowly today 16 minutes planning 5 minutes to clarify 9 minutes writing pseudocode 10 minutes writing code +6 You talk through the number of islands problem and solution. +8 I give the question +9 You simulate whole process each day. O(M x N x k). You could start on a shoreline, do a perimeter search. Islands will be number < k. +11 You say you could use BFS or DFS… +14 You wonder if you could use the sum or average of adjacent cells. +16 You consider other examples. +17 You consider the perimeter walk over the innerness solution. +19 You figure out you need a separate solution. You almost walked back out of this, so I gave a hint… +22 You consider exploring diagonally and avoid this. +24 You say the shortest path to the ocean is the distance. This is correct. +25 You mention this was the innerness you were talking about earlier – sorry about that :) +27 You note the time. +27 You say you’ll write some pseudo code. +29 You mention you don’t know how to implement equality and a hash for C++. +33 You consider iterative or recursive DFS, but you did BFS so I mention it. +35 You work on looking at the neighbors with the enqueue, bounds check, visited check +39 You finish writing pseudo code and do a check. I confirm this looks good. +40 You write code. +43 You define types. +50 End Self-review - 10-15m to code, 1 hour accommodation to interview - Tried to use vectors, sets instead of defining structs or data structures. Wanted to define types. - Skeleton in pseudo code - Problem solving: good, described a couple options, simulation and approaches, different paths. - Test cases - More time to work through test cases - Overall okay

Feedback about Immutable Lightning (the interviewer)

Would you want to work with this person?

Yes

How excited would you be to work with them?

4/4

How good were the questions?

4/4

How helpful was your interviewer in guiding you to the solution(s)?

4/4

Great feedback throughout, thanks for not giving too many hints and using the barest signals to keep me on track :) I don't think the miscommunication around "innerness" was your fault at all :) Its a good reminder to me to not randomly invent new words and expect others to know what I am talking about :D

Interview Transcript

Verdant Gazelle: Hello.

Verdant Gazelle: Hello. Hello.

Verdant Gazelle: Hi, how's it going?

Immutable Lightning: Hi, pretty good. So we have about an hour, so we'll spend 45 minutes working on an interview question or two together. We'll save the last 15 minutes or so to share feedback, and we'll just use the next 5 minutes for setup. So yeah, I have been at Google for about 6 years, and before that I worked in EdTech for a while. You could introduce yourself if you'd like, or you could just tell me a little bit about where you are in your interview process.

Verdant Gazelle: Yeah, yeah. I am currently— I've been working in robotics and mostly a lot of platform type stuff. Also, I've done a good bit of motion planning as well. I'm targeting a bunch of C++ roles at self-driving car companies. There's a very famous one that everyone's heard of that was spun out of a FAANG company, and they've asked me to do the interview in C++. It's for an L5 role. However, you know, they have a reputation for kind of down-leveling. So I'm hoping to give a little bit of an L6 signal during the interview as well. Um, and yeah, I've got 10 years of experience. I've, I've done successfully in interviews in the past. I team matched at [REDACTED] once, and my, my current employer is known for having a pretty, uh, hard interview loop as well. So I can do it. I just, um, it's always hard, you know.

Immutable Lightning: Yeah, okay, sounds great. Cool. Yeah, that makes sense. Okay, so L5, maybe L6, C++.

Verdant Gazelle: Great.

Immutable Lightning: Let's see. Is there anything you'd like feedback on in particular today?

Verdant Gazelle: Yeah, so one piece of feedback I get is— it's very conflicting, but either I'm going too fast and I don't plan things out effectively, or I'm going too slow and it's not urgent enough. So I don't know if you have any thoughts on that. I, I, I think I'm gonna try and go more on the slow side because it's better to be a little bit slow but have really clear thinking, I think, versus like rushing and, and solving the wrong problem.

Immutable Lightning: Oh, interesting. Okay. That's, uh, yeah, I could, uh, I'll, Note down that, and yeah, I'll keep track of timings and everything.

Verdant Gazelle: Thank you.

Immutable Lightning: Yeah. Okay. All right, I think we can just jump into it. Oh, one more thing. Will you be practicing with the execution environment today?

Verdant Gazelle: I'm not sure. I don't— I think maybe better if I don't, because I believe at [REDACTED] they don't you don't run the code during the interview, right?

Immutable Lightning: Yeah, yeah, there isn't really one. I think here the other difference is you get syntax error feedback, by the way. So it'll be a little bit different, but, uh, okay.

Verdant Gazelle: Yeah.

Immutable Lightning: Uh, yeah, we can try out the execution environment.

Verdant Gazelle: That's good. Yeah.

Immutable Lightning: Uh, yeah, I actually don't think, uh, we can— we don't hit run.

Verdant Gazelle: Okay, cool, cool, cool. Okay.

Immutable Lightning: All right. Okay, I think that's everything, so we can get started. All right. So are you familiar with the number of islands problem?

Verdant Gazelle: Yes. Yes, I am. Maybe I'll just quickly describe it to you.

Immutable Lightning: Yeah. Would that be helpful? Yeah.

Verdant Gazelle: So the idea is If you have, let's say, a 2D matrix and some of the cells are labeled 0 for ocean and 1 for island, you have binary values. The subproblem here is that, let's suppose you are on a cell that is an island, you could do a breadth-first search or depth-first search, doesn't really matter. Depth-first search might be easier, but you search outward from the cell you're on, and you only explore cells that are islands. So if you, if your adjacent cell is a 1, you say this is an island, and then you, you know, you kind of fill it out, and you can add all these cells to your visited set. And then you want to kind of repeat this for all the islands. So in order to find all the islands, you could do a linear scan over the 2D matrix and skip all the ocean cells until you hit an island cell. Then you do this, I guess, like a flood fill to capture the island, mark all those cells as visited, increment your island count by 1, assuming you want the count of all the islands. And so you're in the worst case, you're doing an order n by m scan of the whole map, or that's— you have to do that. And then each breadth-first search is order, I guess, k for the size of the island itself, which would be less than m, so it'll just be order n times m. Yeah, great.

Immutable Lightning: Okay, let's see. I have a— I'm not sure whether you'd like to start with a small variant on that or something different and maybe more interesting. Maybe let's—

Verdant Gazelle: yeah. Okay.

Immutable Lightning: Maybe let's start with something more interesting.

Verdant Gazelle: So—

Immutable Lightning: Sure. We'll use the same grid where 1 is land and 0 is like the ocean or water. And land's up, down, left, or right. So on this grid, we're given an integer k. OK. Where k is the number of days. So what happens is each day, any land cell that is adjacent to a water cell becomes water. So could you find the number of islands remaining after k days of erosion?

Verdant Gazelle: So I'll just give us an interesting example.

Immutable Lightning: So this is after one day. So any land cell that is up, down, left, or right to a water cell. So these land cells will become water after the next day. So—

Verdant Gazelle: Oh, very cool.

Immutable Lightning: We'll return 4 islands with a K of 1.

Verdant Gazelle: And every day erosion happens once, and then after K days we'll see what we have left.

Immutable Lightning: Is that right? Yes. Yeah, that's right.

Verdant Gazelle: Hmm, hmm, hmm, very interesting. Let me think about how I might wanna do this. So one thought I have is, let's, maybe you can, you can, if on the 0th day, You start on day 0, and what you could do is, well, a really simple way to do it might be to like simulate. So then you have the whole map, and then you like iterate over the whole thing k times. So that's like an n times m times k, and then you simulate the whole process. You simulate the erosion, and then you do an n times m island search that we discussed earlier, island counting thing. I think there may be a slightly simpler way to do this where you don't have to do it k times, you could maybe start on like a shoreline and maybe do like a, like a perimeter search around the shoreline, and for all the cells that are adjacent to that, you, you count them as 1, say. Then you go 1 ring in, and then you mark all those as 2, all right, these are now the cells that are adjacent to 1s, get— become marked as 2, and then the cells that are adjacent to 2s on the inside get marked as 3, and so forth. And so, um, the number of islands you have will be the number of groups of cells that have a number greater than K, because any cell that has a number less than K will get eroded by the time K comes around. And so then you can do an island scan, and your island is the same as the island scan I described at the very beginning, but instead of 0 and 1, you're looking for like values greater than K. So you would— any group of cells that are adjacent to each other that have a value greater than k will be an island that survives past k days.

Immutable Lightning: That sounds pretty good.

Verdant Gazelle: Um, what does the— yeah, so I'm imagining you could do this in— um, let me think about this for a second. If I were to This is— I think you can do this like ring perimeter walk in order en or order— say the size of an island is i, you can figure out the distance from the shore per cell in order i time. Um, and, um, this perimeter walk is a little weird. I think it might cause some problems. Ah, you might be able to do something with like a breadth-first or depth-first search perhaps where you have— well, you don't know where you're going to start. That's the thing. It's not like you can say, find the center of an island. That's a little tricky as well. So then you, you know, you could try and do like some kind of, hmm, what would be a good way to walk up from the shore and hug the shore? What kind of exploration would that look like? Let's say you do a linear scan, you're seeing all zeros, and then you find a one. So now you know you're on an island. You also know this is adjacent to the ocean because you're linearly scanning. So you just were on an ocean and you now you touch land. So you know this is a shoreline and it's marked as a 1. And so how do you follow it? How do you sort of hug the left, let's say, and do a If you were to hug your left side, you would do a clockwise walk around and stay as close to the ocean as possible. It's a bit strange because you're only going up, down, left, right. So if you would— you wouldn't actually be able to do this. For example, let me— you wouldn't be able to do it as like a ring walk trivially. For example, let's say you have this example here, sorry, 1, 0, 1, oh, 1, 0, 1, 0, right? And you do your linear scan starting from here, and then you end up here. You would actually, you would go down, you would go left, you could check left, right, and then you have to go down, and then, I guess you could check if, hmm, so all the cells are marked 1, which is not giving us any particularly useful information at the moment, 'cause it would be cool if maybe they had different values. Say, let's say, Hmm, hmm, can I do something like the average or sum of my adjacent cells or something like that? Let's say for a given cell, for this— oh, this is interesting. So for this cell, if any one of these happened to be 0, then this would, you know, be a 1. But since all these are 1, this becomes a 2. This is what we end up with here. The reason I know it's a 2 is because it's surrounded by 1s. So if it had— even if it had another 2 here, say, and a 1 here, something like that— oh, I think I'm getting somewhere. So it's like a cell's value is +1 the min of its adjacent, the cell's, uh, cage, I guess, or cell's innerness, like how inner it is, is the min of, is, uh, 1. Plus min innerness of all adjacent cells. Does that seem right? Am I kind of on the right track here with this thing? Maybe not. No, let me think about it more. So is this plus 1 the min of all adjacent cells? I mean, in this case that I've drawn, it is, but maybe I could draw something different. What if we had something like this? I guess this, there's not really, these are all gonna be 1 'cause they're all on the shore. That's not that interesting. What if I had something like this? Uh, right. So this is technically an island. All of this is one island because they're all connected. Oh well, this one is not. Okay, like this. So this island has like a pool of water in it. What do we do about that? That's an interesting case. Is that something I should be concerned about?

Immutable Lightning: Yes, actually, that does look like this example.

Verdant Gazelle: Which one, sorry? Are you near the top here? Yes.

Immutable Lightning: Yeah, yes, it does.

Verdant Gazelle: Yeah, yeah, yeah, it does look like that example with the pool in it. So, so the pool is also eroding everything around it. That makes sense. Okay, cool. So the pool isn't treated any differently. It's also ocean, basically. So it would erode Similarly, that's good, that's good. I think that keeps things more straightforward. So maybe this min-earnest thing is not that useful. I was thinking maybe it's like a, like a dynamic programming where I have this subproblem of like min. I won't, maybe I'll put this in the maybe not down here. And then maybe this ring walking thing that I was talking about earlier, maybe that's more like on the right approach or I'm kind of like, walking and every time I explore a new cell, if it's a land, I can like check the adjacent cells around me and then make a decision based on that. Well, hmm, if it's— it's not just what the value of the cell is, it's also if I visited it or not, I think. Well, no, that's not quite right either. Hmm, I think If I do a linear scan, find the boundaries of all the islands and mark them like with the different numbers or something like that so that I can know that— because what's, what's tripping me up right now in my mind is you can't— when since they're all marked as 1 in the initial state, you can't necessarily use that information since there are— you can't tell off the bat. If let's say instead the, you know, you had your oceans were marked with an enum for ocean and your island cells are marked with an enum for island, then maybe I would like copy the map once in n by m time and I would, then I could choose, then I could leave the, like, the ocean could be like infinity or NaN or like max int or something, or some, some, yeah, -1 or something that would like really separate it. And then I would, and then all of the unvisited island cells would be some other enum. And then when I hit an island cell, I would mark it as 1 because I know that I've linearly scanned and know it's adjacent to the ocean, and then I can explore outward. And if, if it's unvisited, I can add it to my queue or stack, and then I pop it off. And then, hmm, no, I don't think that's helping me at all, actually. That's an interesting thought, but no. Was I on the right track? I—

Immutable Lightning: yeah, I do Thank you. It is help— like, it is hard to store this information in the same grid in place. So I think you're right that this is helpful.

Verdant Gazelle: Maybe useful copy the grid represented differently.

Immutable Lightning: And I think you're like— I think calculating the perimeter how you did is helpful.

Verdant Gazelle: Like the ring?

Immutable Lightning: That makes sense. Yeah.

Verdant Gazelle: Okay, cool, cool, cool, cool, cool. Okay, okay. How would I— Hmm. The reason I'm hesitant— I appreciate the hint. I'm just trying to figure out this tricky bit here where you have this sort of, you know, jagged edge. I want to be able to— I want to be able to mark this as a 1 and then— oh, well, let me copy it first. So, when I copy this over, copy it into my new data structure of some kind, we'll call this one So this is a— we have an ocean cell, which is an O, and then we have a land cell. Wow, this looks like a 0 and a 1. That's funny. Something like this. And so what will happen is I do my linear scan and I get to this O, I get to this L, and I know right off the bat that I'm on the, adjacent to the ocean, so I mark it as such. And let me copy this. Make sure. So then from here now, This is the interesting bit. I want to explore the ring. So if I were to check my left adjacent, I would say that's ocean. I'm not going there. Up, there's nothing. Right is ocean. Down, that's something I can explore. Um, and I could— if I were to try and explore diagonally, I think it would just confuse things a bunch because Well, would it? I think so. I'd rather not explore diagonally, I think. Um, so then when I explore this cell, I pop it, I put it on the stack. This is the only thing I have on the stack. Um, I, or Q, and then I pop it off. And so now I'm looking at this one. I'm contemplating it. How do I know what it is? Well, I know I have land on this side and land on this side and land on this side, unvisited lands. And I have a 1, um, and I only have lands. So that means I can— it's the minimum of the un— of the minimum of the visited adjacent set cells plus 1. No, that's— oh, I think so, actually. Yeah, the minimum of the Because suppose there's actually like a bunch of land here, right? It doesn't actually matter because I came from this, so kind of greedily I got here first doing a DFS. And so even if there's like hella land over here— oh, but what if I got— see, what if I get here? What if I actually got here from Here, say, what if this is actually a 4, right? I've been like doing like a depth-first search or something. And there's like a, there's like a, I have, it's hard to draw this vertical line, but above this, I have a narrow isthmus of like 1, 2, and 3 with ocean on both sides. So I have 1, 2, 3, 4. And then I get to this cell here. And oh, that wouldn't make sense. These would all be 1 because they have ocean next to them. There's no way this could be a 4. That literally doesn't make sense. Okay. Okay.

Immutable Lightning: Okay.

Verdant Gazelle: So I think what I was saying makes sense. The shortest path to the ocean is going to be what sets your number. Any longer path to the ocean is irrelevant. So by doing kind of like a greedy depth-first search type of strategy, I am really incrementing the adjacent cells. And even if, you know, let's, okay, so let's, let's go back to what I think I'm on the right track actually. So this, I'm back here, I'm considering it, I have unvisited cells on either side and a 1 above. So I'm going to mark this as a 2. Then let's say I went down, I could have gone left, I could have gone right, but let's say I went down. If I had gone down first, because, you know, we don't know what orientation we're going to be in, right? It's not obvious that this will be oriented this way. So if I happen to go in this direction first, I'll look at the adjacent cells, I'll immediately see ocean. So I know this is a 1, even though this is a 2. And then if I happen to go to the— this side first, same story there. Now if this were— let's say this was a land here, this was a land here, this was a land here, right? When I approach, and then maybe let's say this is a 1 and this is a 1, then when I get to this 2 and I explore to this side here, I would say I have an unvisited cell on this side, a 1, a 1, and a 2. 2, so I'm gonna call this a 3. So, hmm, is that right? No, because—

Immutable Lightning: oh wait, yes, yeah, with that, with this ocean, yeah, or with this.

Verdant Gazelle: No, unfortunately, because this is a 1, right? So then, oh yeah, 3, this has to be a 2. So it wouldn't— I would look at It's not that— I would look at the minimum value of my visited adjacent land cells and increment by 1. Yeah, that makes sense. I think maybe this was right. Minimum of visited adjacent lands. Is 1 plus the minimum of visited adjacent lands. That seems to make sense to me, but if you— yeah, yeah, maybe.

Immutable Lightning: Yeah, I think you were— yeah, sorry, I think I thought this was different, but this makes sense.

Verdant Gazelle: Yes.

Immutable Lightning: Okay, I think you're—

Verdant Gazelle: I'm glad I walked through it. Yeah.

Immutable Lightning: Sorry about that. Yeah, I think that this makes sense.

Verdant Gazelle: No worries. Cool, cool, cool, cool. So before I jump into— well, how much time do we have left? I've spent a good amount of time. Maybe we should talk—

Immutable Lightning: I think you— Yeah, let's see. You have like 8— let's stop at the 45-minute mark. So I think we still have plenty of time.

Verdant Gazelle: Yeah.

Immutable Lightning: Cool, cool, cool.

Verdant Gazelle: So then what I want to do right before I jump into coding, a little bit of pseudocode is always helpful, especially because we're doing C++, you know, it can get hectic. So what we have here is first maybe a linear scan. This is like the outermost loop here. And well, first actually we have a copy. Oh, actually, do I need to copy? Yeah, I think it's useful to copy maybe just, hmm, yes, I think it would be useful to copy so I can mark the cell as visited instead of having to track a visited set, or this is a C++ thing. If I wanted to make an unordered set of visited nodes, I would have to implement a point struct with like a cell xy struct. Totally fine. However, to make it work with an unordered set in C++ is quite annoying. You have to implement like this like very, very complicated hash thing. It's not overloaded for you automatically. And I've never been able to successfully memorize how to do this. So I don't know if I want to do that in an interview. So maybe having another structure instead. So I might define my cell, copy into my custom matrix, which is gonna be cells like this, something, you know, n by m, and then my cells will be defined something like, It doesn't even need to keep track of its x, y necessarily. Maybe I will, because if I want to pop them onto a stack or something. So, it has a row, it has a column, it has a is visited, and then it has a is land. And then finally, there's a, Like to immutable, like I will write the, what should we name this thing? Earlier I was calling it innerness, then I can call it like distance from the shore or something, or—

Immutable Lightning: I think that's a good name, yeah. Distance.

Verdant Gazelle: Distance, yeah, from shore. If I get tired of typing all that up, I'll call it distance. Yeah, something like this seems reasonable. And then the loop, we have a linear scan, so that's going to be like a for, you know, row, for row in rows, and then for cell in row, and then if cell is land and not visited, also, then, and do distance exploration for a given cell, let's say. And then I also— so now let's see the def do dist exp is going to look something like, uh, you get to the cell, um, and then also the matrix itself, the, uh, my, my matrix, my, uh, uh, we'll call it, why not, uh, map, whatever. And then, um, if, uh, how's this going to work? So I have this max, min, sorry, min visit adjacent lands thing, and I have a DFS. So what I'll do is the way DFS works, we'll do it with a stack. Um, you could also do it recursively. Do you have a preference on that? Um, so I think stack— oh, sorry, go ahead, go ahead, go ahead.

Immutable Lightning: Is that right?

Verdant Gazelle: Like, Oh, I'm— is that right? Meaning? Or do I want to like— sorry, let me think about that. Yeah. So are you, are you, are you asking if this portion here is not quite right?

Immutable Lightning: Oh, no, no, I think that's right. I mean, in calculating the distance, was that DFS or was that actually BFS?

Verdant Gazelle: Let me— it's a good point. That's a good point. If I were to do a DFS, I would have— oh yes, there is a problem with DFS, and I really appreciate you for pointing that out. With the problem with the DFS is you kind of go in a straight line and you just kind of like explore in one direction and you're doing the min of visited adjacent lands and all the adjacent lands are unvisited. So you just like, yeah, 1, 2, 3, 4, and you're like, I think what you happen to be—

Immutable Lightning: yeah, what do you happen to be doing was BFS.

Verdant Gazelle: DFS, you're absolutely right.

Immutable Lightning: DFS.

Verdant Gazelle: Yeah. Perfect, perfect, perfect. Thank you. Thank you. So we have a queue, then we need to have a queue. This is the frontier, I'll call it frontier and equals cell. Maybe I'll do cell.dist equals 1. Cell dot, well, I'll mark it as visited in my loop. Then while frontier If cell— no, then I'll do cell.visited, and then here's another function I need to write is this is a min_adjacent_dist function. This is going to look something like— so, for the adjacency, I have some kind of— This is to the right. This is to the left. And then— or this is up and down, sorry, because it— look up a row, look down a row. This is to the right and this is going to be to the left. And so I like loop over these, you know, adjacent equals these, and then for adjacent, I then, you know, loop over these, loop over adjacent, add adjacent to cell, bounds check, you know, it's in the matrix, don't try and, exit the matrix. So that would be like greater than or equal to 0, less than or equal to cell, less than or equal to matrix size, height, width. We would do a is adjacent. If is adjacent visited already, you know, then ignore it, skip. Adjacent that are visited and skip adjacent that are ocean. Oh, sorry, well, I'm not skipping here, I'm actually doing a min here. So into my, I need to have a small array here of values, this vals, equals a little array. And then if adjacent is not visited and land, vals.append. And if it's ocean, I do need to be aware of that as well. If it's not visited land, or ocean. So, I'll append zeros in here if they're ocean. If it's unvisited land, I ignore it, and if it's a visited land, I will mark it as such. And then, you know what, maybe— oh, I don't care to mark the ocean cells as visited. I don't think that matters since I'm just going to linearly scan over them anyway. It doesn't affect the order of of the whole thing. But yeah, once I do that, then I can do loop over min adjacent distance. I'm going to return after this loop. I'm going to return, and then this val is going to be defined over here, actually outside the loop. Return 1 plus min Vows. And then so, while frontier cell, if mark the cell is visited, then I want to add adjacent unvisited lands to the queue. So, We would use a similar thing here to, you know, look at all the adjacent things and add them to the queue. And I will do this, cell.dist equals min adjacent dist. Cell matrix, something like this, I think. Let me walk through this once.

Immutable Lightning: We have running out of time, so we need to be a little bit quicker.

Verdant Gazelle: So copy into my custom matrix cells, linear scan, do distance iteration. So this is a— let's make sure the depth-first search makes sense, right? So while the frontier has things in it, call this frontier, add adjacent unvisited lands to frontier. Then for the current one that I just visited, I do this min adjacent thing. And yeah, I think this is it here. What do you think? That is—

Immutable Lightning: yeah, I think so.

Verdant Gazelle: Cool. All right, cool. Okay, so then let's get into it here. What I'm gonna do is I'm gonna define my fruct. So if I stop talking for a bit—

Immutable Lightning: Oh, sure, yeah.

Verdant Gazelle: So we'll say en, oh, equals 0, call equals 0, um, bool is, is returned, false. Bool isLand, and then dist— sorry, dist— int dist equals 0. And is there anything else I was missing from this? rowWasVisited is land, dist. And then I'm also going to, you know, make myself a little helper function here, static. Oh, you know, You're outside. I'm going to call using matrix equals vector int— oh, sorry, vector of vector of int. So that's just because I don't like typing vector vector over and over again. This is the input matrix. And then using my matrix is going to be equals vector vector cell. And vector is not included, and this should be at the top of the file, but I'll just do it here for now. And so now we're going to do a Let me stub this out for now since I'm running out of time and I wanna focus on the more interesting bits, but we have a matrix copy input matrix. This is going to const matrix of input raw matrix. I'm gonna copy this into, Yeah, you can imagine it's like two nested for loops, two nested loops, init_cell and init_cell with row and column. There's also some like, you know, you do like std::fill or something like that. You get your various C++ things to deal with the matrices. Returns a nice matrix for us. And then, so we have our matrix, and then let me maybe write this— this part is interesting, it's worth writing down. I will do this— what I will do is I will additionally define a another struct. Oops, sorry, where am I here? This struct is adjacent or— hmm, you know what, this might be a little bit easier to do, and I kind of want to actually write this code myself. So what I'll do is I'll call this a— hmm, I didn't make these— I should have made these unsigned ints first of all, so let me do that. And then I will actually define this as a separate thing because I, I do prefer that. This is adjacency, um, and this is an int, and it'll be row and int col also. And then what I'm going to do is, uh, I'm going to have an array adjacency that has 4 elements. These are the adjacents, and this is going to have a 0 or 1, 0, a negative 1, 0, 0, comma, 1, and 0, -1. Okay, so then I can loop over the adjacents with something like this.

Immutable Lightning: We can go over to the 50 mark.

Verdant Gazelle: Okay, thank you. Thank you. Yeah, I appreciate that. Okay, cool. So I've got my array here. I'm going to loop over it. It's complaining about something that I did in here. I wonder what it is saying. Suggest braces around initialization of subject, fix available. Not sure what it's mad about here, but I will leave it as is because it's some kind of simple C++ syntax error that should be fixable with relative, it should be easy to fix, not a real algorithmic thing here. Okay, cool, so now the interesting bit, let's loop over Let's do this minAdjacentDist, the innermost part, and build up from that. So I have a uint min— oh, I'll do that one for you— minAdjacentDist. And this is gonna take a const cell and a const my matrix, not the input one. And what we were going to do is— let me actually copy my pseudocode down here so I don't have to keep scrolling up. So what I'm gonna do is, Windows, can't hide some of these panels, I'm like a very small viewport here. But so here, let's see, min_adjacent_dist. What I'm gonna do is I have my adjacencies, so I have values. So I'm gonna make a small vector of uint. And I would use like, you know, I would actually do something like this in like real code. I just wanna point that out. This is not real code. Really good practice here, but just for the sake of this, vector uint this or vals, we'll call it since that's what I was calling it earlier. Then for const, what did I call this? Adj in, in adjacency.

Immutable Lightning: Nice.

Verdant Gazelle: If we'll say, we'll call this cell equals, it's actually gonna be constructed and it's gonna be a.row. This is also not ideal syntax here. I apologize again. This is a bit of an abusive notation, but I'm just going to do it for the sake of this interview,.row plus ads.row, and.col equals cell.col plus ads.col. And now we could do our bounds check. So since I used unsigned integers in the cell, this makes the bounds checking slightly easier. What I can do is if adjacent— so I don't have to check the 0 case, I just have to check if it's greater than matrix.size here, or if— because it overflows. If it's a— if I got less than 0, it will overflow to be a gigantic absurd number. And if the adjacent cell is greater than matrix[0].size, then continue. We were out of bounds, don't bother with this one. And if it's not visited— if it's not visited and land or ocean, then we will append. If Matrix adjacent cell dot row, matrix adjacent cell— oh, sorry, not dot. And this I'm going to rename this to like possible. So, let me do this. This is not correct here. It's a little bit— it's getting ugly there. So, the const, because I passed in a const thing. Const app. This is the actual JSON. Oh, it shouldn't be const. I'm going to— oh no, this is const. I'm not editing anything here. If adjacent cell equals matrix possible cell dot row. Oh, I'm sorry. Possible cell dot row. That's a little bit more readable. If adjacent cell.isLand and not— oh, sorry, and adjacent cell.isVisited, both there.

Immutable Lightning: I do think, I do think actually it would be better for us to talk about feedback now rather than Okay, continue here. Yeah, yeah, yeah, yeah, yeah, of course. Alright, so. Hmm. I think I do have a question before I continue with feedback first. Do you— is your upcoming interview like it isn't the C++ but is that an option or is this? Like, or is that—

Verdant Gazelle: It's not an option, no.

Immutable Lightning: No. Okay.

Verdant Gazelle: It's not. I would much rather be doing this in Python. I mean, I write C++ every day, but yeah, we're very serious that every— all of the self-driving car companies I've interviewed at, um, and robotics and platform, every single interview at— last year I was interviewing, my current job that I interviewed for, uh, the place that I'm really targeting, Also [REDACTED], [REDACTED], they all require C++.

Immutable Lightning: Oh, okay.

Verdant Gazelle: Yeah, yeah, it's unusual.

Immutable Lightning: So this is not— Yeah, this is crazy.

Verdant Gazelle: I agree.

Immutable Lightning: This is— Yeah. Okay.

Verdant Gazelle: How much, how many characters I have to write is bonkers.

Immutable Lightning: Right, right, right. Okay. I was just wondering.

Verdant Gazelle: Okay. All right. Yeah.

Immutable Lightning: That's good context. Okay. Okay. So I, I actually usually ask candidates this. Could you could you do like a brief self-review of how you think you did? And I just wanted to, yeah, I think it's helpful, you know, for candidates to just hopefully understand how they think they did and that it matches how I think you did. Yeah.

Verdant Gazelle: [Speaker] I would say, I think if I had like 15 extra minutes to just code, I think I could have a pretty decent thing working. At least 10 minutes even maybe, you know? But the one good thing is I am getting, I have requested, accommodation on time because my typing is really slow. I had to relearn how to type because of wrist pain. I have an ergonomic keyboard. I'm still, you know, I, yeah, it has, it's a much smaller keyboard, so I don't have to stretch my hand out as much. So I will be given extra time during the actual interview. So I have an hour instead of 45 minutes for the whole interview. That will, yeah, you can see my typing is not very fast and I think maybe I wonder if like, so on a previous interview I got feedback that like I tried to do everything using just native C++ vectors and sets and tuples and pairs and stuff. And I got feedback being like, hey, you should actually try and define some structs, define some data structures. It makes it a little bit more readable. I'm sure if you've seen C++ code where You know, it's all pairs and like, it's like a set of vectors of pairs or something that it, it's so unreadable. It's like, what is.first? What is.second? That, that, that has messed me up in interview before. So that's why I kind of spent some time defining the struct up here. Mm-hmm. Uh, defining this array so that I'm not looping over some like weird thing. Um, and I, you know, I left this blank because I knew this is just like tedious, annoying for C++ code. Um, and I figured if I get the skeleton— I got the skeleton of the, uh, um, breadth-first search in pseudocode. That's, that's kind of the easy part. The hard part is kind of this, like, what am I, what am I doing the math on? What is the actual number that I want to get and how do I want to set it? So I figured maybe let me focus on that. Um, and so Yeah, I think if I had maybe 5 more minutes to finish this part and then 5 minutes to write the actual frontier exploration in the breadth-first search, it would have been good. And then I think in terms of problem solving, I think that was good, right? I kind of explored a few different options. I talked about simulation, I talked about, I tried to go through a different couple different paths and then there was a little bit of a misdirect there, miscommunication, misdirection.

Immutable Lightning: Yeah, sorry about that.

Verdant Gazelle: Which is no, no, no, that's not your fault. I think it's good that we were able to clarify it. I think that's actually maybe good signal as well on the communication side. And so yeah, and then, yeah, and then I think I worked, you know, I came up with a few test cases to try and think through the problem, which is useful. If I had more time, maybe I would have had time to step through one of these test cases and like, you know, explore how it actually works.

Immutable Lightning: Uh, I would say overall probably like a okay, but not terrible. Yeah.

Verdant Gazelle: It would have to, maybe it would be up to the interviewer. Like some interviewers would be like, didn't finish the code, no hire.

Immutable Lightning: Right.

Verdant Gazelle: And some interviewers would be like, oh, you know, I like talking to him.

Immutable Lightning: So, uh, yeah, I think.

Verdant Gazelle: Yeah, so funny.

Immutable Lightning: I think, like, I think I agree with, like, the problem solving there. Like, you did really well there. And then I think you did warn about— you did give me a warning about going slow today. And, like, I think you're right. Like, you wrote out the pseudocode, and that was kind of the hard part. And then I think I can believe that you can write the code for this, for the pseudocode. Yeah. And I think you're right that there is probably room to go faster here. And I wonder what you would have done if you chose to flip it. And I wonder what your other mode is where you go really fast.

Verdant Gazelle: Oh yeah.

Immutable Lightning: What does that look like? You just spend less time planning or writing pseudocode?

Verdant Gazelle: Yeah, I wouldn't have written the pseudocode probably. And then, oh, interesting. Okay. I think, I mean, in this case, I, I kind of, I landed on the right approach upfront, which is lucky. Mm-hmm. And so I could have maybe just blasted through it, but more likely there's some trick somewhere I didn't think about, or like, ah, I see. I would have maybe like gone with the DFS and then like run through it then, or like I would have maybe, you know, during this like plus one plus min, there would have been some trickiness where like I didn't think about like, is it visited, is it ocean? And I would have like, uh, coded up something that doesn't really work.

Immutable Lightning: Right, right. I think that, right, like you mean the balance with correctness is quite important.

Verdant Gazelle: Yeah.

Immutable Lightning: Uh, I think I do agree with that. There is some balance, uh, and maybe there is— yeah, you know, maybe there is some in between, between you going very fast and then this, um, this process to do the planning. Like, you, you did take, um, a good amount of planning, and maybe some of that was like the clarification, like, like 5 minutes probably for the— for clarifying what you meant by the enness. Uh, so, um, like, that planning did seem good. And then for the time that you took to write some pseudocode. That, that did take a while. That was like 13 minutes. I, I think that it was all like correct, which is very important and good. Like you, you did the like, especially like when maybe this is an example, like for the neighbors traversal, like you made sure to check the bounds and yeah, make sure you're visiting land or ocean or using the checks properly. That was definitely important. Man, I don't know. Yeah, I think that there is some balance here though. Like, ideally, I think what your plan was is like, yeah, you have the pseudocode and then translating it is fast. But these checks just took quite a—

Verdant Gazelle: took up so much time.

Immutable Lightning: Yeah, there was a lot of typing, which is why I was wondering about the C++ thing. And then, yeah, like you did spend a considerable amount of time that you've also pointed out to define the types. Like you, I think you understood that that took some time, but you also have a reason for doing that.

Verdant Gazelle: Mm-hmm.

Immutable Lightning: I, I mean, okay, so I took some like timing for where you are, and it— that is really great that you have an accommodation for more time. I think you ended up spending most of the time writing pseudocode and code though, like 16 minutes planning is kind of reasonable. Maybe it is closer to the maximum of like 20 minutes. So maybe there, maybe there is an opportunity to go like just a little bit faster in the planning. And then in the writing, but I think most of your time is spent writing pseudocode and code. So if you can find a better balance.

Verdant Gazelle: Yeah, because with an hour, then that is, uh, that's like 5 minutes intro, 5 minutes questions at the end maybe.

Immutable Lightning: Yeah, so that's 25 or 35 minutes to write code and pseudocode.

Verdant Gazelle: Mhm.

Immutable Lightning: I guess that that was doable. Maybe like, when did you start? 27. I guess you might have time to finish.

Verdant Gazelle: So, I don't know.

Immutable Lightning: Yeah. I, I think, uh, I mean, yeah, the thing is like when we stopped, I believed you, like, I think you can write the code for this, for the pseudocode. Yeah. Uh, and then it's just about the testing, having time to test too.

Verdant Gazelle: So, right. Um, I know it's, you know, I, I'm choosing to put myself in this position where I'm like targeting these like super like in, you know, popular, popular companies and I understand that, like, you know, there's gonna be some, like, I have a family and I have a full-time job and there's, I'm competing with someone who is just grinding [Platform Name] 40 hours a week. So it's gonna be tough.

Immutable Lightning: Yeah, I think that you're fine. I think, right, right. Yeah. Like the problem solving is really sound. Um, so just the second part of the writing code is just, um, difficult. Like, you've done the— I think it sounds like you've done the preparation you need, um, and just practicing how to find the balance between writing the pseudocode and code faster in C++.

Verdant Gazelle: Tricky. Um, okay, cool.

Immutable Lightning: Um, anything else I could help with?

Verdant Gazelle: Uh, um, no, I, I really appreciate that. I You know, I think I'm glad that the feedback has been sort of consistent. It, you know, it matches with my internal model, and at least I have kind of an understanding of where I'm at. And practice, practice, practice. Yep, that's, that's got to be the name of the game. And hopefully, I don't know if there's anything else you think maybe it was just some other like very minor thing you noticed that maybe you were calling out or something to consider?

Immutable Lightning: I wrote down a lot of notes about the details, so—

Verdant Gazelle: Okay, cool.

Immutable Lightning: I don't know if there's anything there worth sharing. I mean, I think, I think you're right. Like, you are pretty self-aware, which is really good. And then, yeah, just figuring out how to either, yeah, practice and write code faster would be your best improvement. All right. Well, good luck with your interviews.

Verdant Gazelle: Great. Thank you so much. I really appreciate your time. I know.

Immutable Lightning: Of course. Yes.

Verdant Gazelle: You know, it's very grateful that anybody would be willing to do this to help others out. It's really nice. And thank you.

Immutable Lightning: Like, you're a good person.

Verdant Gazelle: Yeah.

Immutable Lightning: Really good luck in your interviews. Looks like you'll— you're doing great. Yeah. Take care. Have a great rest of your day.

Verdant Gazelle: You too. Bye-bye. Bye.