[00:01] down one of the most common low-level design interview questions together. For low-level design is an interview type that focuses on object-oriented design. what classes you need, how they interact, the actual implementation of
[00:17] the methods that make things work. And so, as far as fang goes, at least Amazon. It's common at Microsoft. It's common at Netflix. Usually for more junior roles, but it does sometimes show up for senior level roles as well and
[00:31] up. Um, it's also really common in different parts of the world. So much of India and Asia in particular, companies based there or even the offices of fang companies based out of India or Asia love to ask low-level design questions
[00:43] oftentimes even regardless of the candidates's level. Um, so what we're common beginner low-level design questions out there, which is design a connect for game, right? And my hope is that this is going to serve as an
[00:56] introduction to this type of interview for those of you who may be new to it. answer the question in an interview as interviewer, would be looking for at each step along the way. Uh, I guess
[01:10] be new to the channel, I'm Evan. I'm a former staff engineer at Meta and the current co-founder of Hello Interview, where Hello Interview is a platform that helps software engineers just like you prepare for your upcoming interviews. We
[01:22] got tons of content here on system design, ML system design, low-level code behavioral, you name it, as well as the ability to practice or do mock mentorship, salary negotiation. Basically, a one-stop shop for
[01:36] upcoming software engineering interviews. And the overwhelming majority of all of this content here is free. So head over to the site, check it out. Uh if videos aren't your thing, then don't worry. We have a full written
[01:49] going through today, which is going to show you all of the trade-offs, all of the code, all of the decisions, as well as each of the implementations in their going to stick to pseudo code in the video here today. So that'll be linked
[02:03] in the description. Uh let's get after it. start designing the system. So, that first step was the requirements. And so,
[02:16] design interview. You're super nervous. You sit down. You enter the Zoom call and you find your interviewer waiting for you with the following prompt. On Connect 4 game where players take turn dropping discs into a seven column six
[02:30] row board. And the first to assign four of their own discs vertically, horizontally, or diagonally wins. Right? This is the prompt that you're greeted with. Now, for anyone who maybe hasn't played Connect 4, just really quickly,
[02:42] like. Users take turn dropping the discs. You want to arrange all of yours in four, either vertically, horizontally, or vertically, horizontally, or vertically, horizontally, or diagonally, right? Um,
[02:56] now one of the most important mistakes, most common mistakes that I see they start the interview is they get this prompt and they immediately start into implementation. And this is a problem for two reasons. First, you
[03:10] exactly what it is that you're going to build. So, you're not on the same page with the interviewer yet. But second, and maybe equally as important, is that evaluating you on what's called your problem analysis. And so they want to
[03:23] and you can turn it into something concrete, a concrete set of requirements against. And so spend a few minutes up front doing exactly that. And you're going to want to ask some questions to to clarify this with your interviewer.
[03:38] like, well, what questions should I ask? And I think the way to do this is to think about three primary categories. The first is primary capabilities. So lock gosh lock lock down the capabilities of the system. The second
[03:53] is error handling. Determine how you're supposed to handle errors, where errors appear. And then the third is define some scope boundaries, what's in scope and what's out of scope? And so we'll run through this quickly. I don't need
[04:05] to kind of roleplay this too hard, but for primary capabilities, you might ask do players interact with the game? Do they just specify a column number and might say, yeah, that's exactly right. Right? They drop it, it goes to the
[04:18] lowest available spot. Okay, cool. You confirm the main action, right? Then you might say, "What are all the ways that a game can end? Is it just the four in a row, vertical, horizontal, or diagonal, or are there draws?" And this is a
[04:31] might say, "Yeah, that's correct. If the if the board fills up and nobody gets four in a row, then it's a draw." Okay, great. Now, we know draw conditions are in play, right? And so, we might move on to ask about air handling. This could be
[04:44] a disc in a column that's already full, what should we do? Should we return an error, an exception, just ignore it?" And they might say something vague like, don't let invalid moves break the game state." And then you might say something
[04:58] like, "What should happen if a player tries to move out of turn?" And they would say, "Same thing. Just reject it cleanly." So now we understand where the it into a column that's full. You can't move out of turn. Pretty clear. And so
[05:11] then you'd want to understand sort of where are the scope boundaries of the scope? And so you could ask a question like, are we designing this to support a single game at a time or do we have multiple concurrent games going on at
[05:23] especially for an earlier stage candidate, junior or mid-level, I might one game at a time. And then you could say, what about, you know, what about the UI? Is the UI in scope, for example? Uh, and they might say, no, that'll be
[05:37] focusing on just the backend class design here. So, excuse me. forth with your interviewer, you're going to end up with a pretty clear set probably taking notes as you go. And so, this is what you'll want to end up
[05:51] I'm going to copy and paste because you guys saw how awful my typing while you guys are watching is, but you might end up with a final set of requirements that write this on your shared screen with your interviewer. And that's that you
[06:03] have two players who take turns dropping discs in a seven column, six row board. that this falls to the lowest available row in that chosen column. The game ends either by having four in a row in either of the three directions or it's a draw
[06:15] when the board is full. We know that invalid moves based on our questions are turn or moving after the game is over, of course. And then we can even outline keep ourselves honest. If throughout the design we ever try to touch about talk
[06:28] well, we know we agreed with the interviewer that's out of scope. So, we should try to avoid that. But now we have a concrete set of requirements and we can start to move on to the next steps in our design.
[06:43] requirements in hand and the next step in our delivery framework is to move on just figuring out what objects we actually need and how they're going to interact with each other. These becomes the classes in our class design. And so
[06:56] and I think this is really formulaic and and and a good suggestion, uh, is to looking for the nouns, looking for the things that stand out. And so in our case, we have two players, okay? We'll probably need to model players, right?
[07:11] That drop onto a board. Okay, we probably need a board, right? And then the game ends. Well, clearly there's a a game here. There's a game orchestrator, right? So you're pulling out these nouns. Maybe you're listing them as you
[07:25] go. And in our case, what we'd end up with is we obviously have that game game logic. It's going to hold the board and hold the players. And then we have the board. It's going to manage the grid state, the disc placement. It's going to
[07:40] know how to check if columns are full, whether discs should fall, uh whether care about whose turn it is or who's winning. That's the job of game, right? It's just it's just the board. And then there's the player. And this is going to
[07:54] game. It's probably going to be a simple data holder with just a name and a disc Like you could write this, you could not. I think with foresight we realize this is probably just going to be a simple enum or something. Um, but it is
[08:08] a noun. It is a thing in the game and it's going to be important. So maybe you want to write it down there. Now, uh, this was pretty simple for this design, interviews, this can be pretty complex. And so it's worth taking this time up
[08:22] front in order to think thoroughly through this so that you don't end up you get to your class design. But in any case, you can always come back and you nothing that you write here in the interview is concrete. It's really just
[08:36] allowing your mind to step into the process uh linearly so that it's able to build this design up from its foundation as opposed to having to jump right in cold, which ends up usually being a failure state for candidates.
[08:54] can now use those entities in order to move on to our class design. And this is where things start to get more fun in an actual interview. Um this is where we actually get to decide what data each class holds and what methods it exposes
[09:07] to the outside world. And we're defining its interface basically. And so something candidates often uh struggle with is deciding which class is responsibility of the game? What's the responsibility of board for example? And
[09:21] the most important thing to remember is that each job each class should have a clear job. And so when requirements change, you should be able to point to without touching the others. That's really the key here. And so for us, when
[09:34] of the board as just the dumb physical object like the actual board in the table. It doesn't know about players or whose turn it is. It just knows that a disc can go here. It knows whether there's four in a row. its only job is
[09:48] grid physics and placement rules. And so if the grid size were to change from 6x7 to 8 by 8, for example, or the win condition changed from four in a row to five in a row, only the board class would need to update. And then game on
[10:02] referee. It's one job is game flow and orchestration. It knows whose turn it is. Is the game over? Who won? It uses board just as a tool. And if we added an players or any of that, then only game changes, right? See how clean that
[10:16] separation is? And so the board handles one thing, the game handles another. Neither bleeds into the other's responsibilities. And this principle is important. It actually has a name. And it's called SRP, the single
[10:28] of the most important design principles that you'll use. Uh, and it applies to almost every low-level design problem that you're going to see. So you don't You don't necessarily need to say it in an interview, but it's a principle that
[10:43] you should keep in mind when you get into class design. Um, and it, as I said, shows up in just about every single low-level design interview. Um, okay. But with that in mind, let's get back to our exact problem here and
[10:56] recommend that you approach this class design is that you start uh from the top down. So, we'll begin with our game class because it's our orchestrator. It's our primary entry point. it's what other users, classes, whatever will will
[11:09] games interface, then we can work our way down to the board and down to the player. This will keep us focused on the public API instead of getting lost in the implementation details early. And so for each class, what we can do is we can
[11:23] simply go through the requirements and derive both the state and the behavior starting with game. So in designing the class design for our game class, we can start by looking up at our requirements and going line by line and pulling out
[11:36] on state right now and then we'll work on methods in a second. So what does the game class need to track or need to know? We have two players take turns dropping discs into a seven column six row board. Okay, so the game needs to
[11:50] track two players. A player one, which is a player, and a player two, which is going to be a player class. Um, it also needs to track whose turn it is as well as the board itself. So, current player, that's going to be whose
[12:06] turn it is. And then the board itself, which is going to be a board class, which we'll define in a second. And then we have the game ends when either we get the four diagonals or the board is full. And so, the game needs to track some
[12:19] sort of game state like is it in progress? Did somebody already win? Is it a draw? And so when it comes to tracking state, we actually have an interesting decision to make. I see some candidates who use multiple boolean
[12:32] flags. This is often like their reflex is to do something like is over bool has is to do something like is over bool has winner has winner. Gosh, I'm such a bad typist while you guys are all watching. I'm so sorry. Um
[12:45] guys are all watching. I'm so sorry. Um or is draw bool, right? And now if you do something like this, the problem is that you end up with three booleans which give you eight possible combinations, but only three of those
[12:57] it's in progress, one or draw. So you can imagine something where it's like is over is true, but has winner is false and is draw is true. Like this isn't a valid combination. And so you're relying on yourself or any future programmers or
[13:11] accidentally set these conflicting values. And that's bad. And so a better approach and how you would usually model state in these multi-state games or multi-state designs is to use an enum with three values. And so you could have
[13:27] game state as an enum which has just something like in progress maybe one and draw. And now you can only ever be one of those three valid combinations. Now, importantly, and you guys might be
[13:42] thinking this, if you want to be able to know who won at any point, well, you figure it out. That's one possibility. But oftentimes, you also want to put that on the player here or on the game here. And if you do that, well, now you
[13:56] have two things that in theory could get out of sync because you could have in game state as in progress, but the winner as a player. That's obviously not one, but this be null. that's obviously
[14:10] advanced, but there are languages like Rust, Swift, even TypeScript where you state itself. So that this is actually impossible. Um, but for the interview context, especially when you're writing in pseudo code, this simple enum plus
[14:26] You'll just have to trust yourself to keep just these two things um consistent or in sync. And as I said, this is really even just a cache of what the board can tell us about who ended up winning by us just reading the discs on
[14:41] the board. So it might be that you don't even need this altogether. So if you're looking at me and thinking, "Okay, Evan, that was a a lot of talking, like what's interview?" Um, I hate to break this to you, but there's no right answer. What I
[14:56] interview is that you can weigh these trade-offs. you can make a reasonable decision and a reasonable justification and move forward. So, any of the things exception of the three boolean states would be sufficient for me in an
[15:08] interview and I'd feel pretty good about it. All right, let's let's come back to Um, what else do we have? Moving after the don't need anything there. The player gets four discs. So looking back at it,
[15:23] I feel pretty good that this is the the complete state that we need to model um for our game. So once we have our state, we want to then move into the behavior the actual functions that we're going to need to define. And so we can now look
[15:38] at the actions the outside world needs to perform. And every single one of those methods should correspond to again what are the concrete needs within our requirements or our problem statement. And so if we come back here, we have
[15:50] players take turns dropping discs. Okay, so we're going to need some sort of a I'm going to actually denote these like this just for private. Doesn't matter. This is a semantics thing, but something I like to do. You can do it either way.
[16:04] Um, and so we're going to end up first, let me put a constructor. You're going player two. That's how a game is going to start. Then based on what we just said from the requirements, you're going to have a make move. This is going to
[16:18] have the player making the move and the column that they're dropping it in. And then maybe we either return a boolean or we could throw here based on our earlier in case we try to make an invalid move. We could either return
[16:30] false or have the boolean. Uh the next thing is that we reject moves that are out of turn. Right? So moves should be rejected cleanly if they're out of turn. And so we need to have some way to know whose turn it is. Maybe that's internal,
[16:45] but we have a Why are you trying to give me suggestions? Right? We got the get current player. This is just our getters here. No big deal. And then we're also going to have the get game state. More getters. Easy. Uh get winner in case we
[17:01] want to return this. Again, this could be by just reading our winner state could be by iterating over the board again and finding which disk won. And then we need to be able to potentially get the board. This would be uh if
[17:14] somebody wants to be able to render the full view of the board like whatever person is responsible for rendering the UI. But given that it's out of scope again that one is optional. So the most important thing is the constructor and
[17:27] private methods that will help us do that. Right? This is the overall class design for game. Now, before I go any further, I want to can already hear you guys in the comments screaming and saying, "What
[17:42] about UML?" And I have a little bit of a hot take here, but I feel passionately that this is an accurate take. And that's that look, UML is incredibly outdated and it isn't actually used at any major tech companies. Microsoft
[17:55] themselves actually even removed UML tooling from Visual Studio back in 2006 zero. You know, an indication that nobody's using it. And so UML was software engineering where you were inspecting uh where you weren't
[18:10] inspecting and running code as regularly or it was more expensive to do so. And these in some sort of a diagram in order to help people review whatever was valid back then. It's not now. And so what that means in your interview is that if
[18:25] your interviewer is asking you for UML, then it's either out of habit or some academic training rather than an actual real requirement. And so if it comes up, here's my concrete suggestion to you. Ask them whether a simplified class
[18:37] notation like we've done here um is sufficient. And in almost every single case, they will say yes, that's totally fine. Right? In most cases, they are totally fine with it. They also know that memorizing UML symbols is a total
[18:51] waste of time and energy. And so feel confident here. Feel free to tell them that. If they say for some reason, no, I need UML. I personally would probably UML semantics. It's not something I've ever used in my work." And I know that
[19:03] it's actually a pretty outdated form of of modeling classes. Um, and if they probably not a company that you want to work at to be honest, but it's unlikely that they do. So whether or not you need to learn a UML, my thoughts are no and
[19:17] that what you have here should be more than sufficient. Now, let's move on to class. We're going to take the exact same approach where we look at the requirements in order to define first the state and then the methods. And as
[19:29] we know our board class is part of the game state. And so game is going to be to think about the things that game is going to need to know about our board. Okay. And so we can start looking at our requirements and we see that we have a
[19:45] seven column six row board. And so the board needs to know how many rows and columns it has. And so it's going to have rows as an int. It's going to have columns as an int. And in our case, this is 6 by seven. But maybe it changes in
[20:01] the future, right? So we're just making this extensible here. And then what else do we need to know? We need to know that a disc falls right to its lowest available place. That was one of the questions that we asked them. Also, if
[20:13] the board is full that it's a draw. Um also that if a player gets four in a row, then they end up winning. All of this is telling us that we need to kind of track each column in a row. We need to know about the grid state itself. We
[20:26] need to know where the uh the current disks are on the grid. And so this screams to us that we need to actually track a grid. And the question then is what is the grid made up of? Well, it's a it's a two dimensional array of
[20:39] two-dimensional array? And so what I see a lot of candidates do is they do this. They create a two-dimensional array of players so that you can know which players are in each spot. And I put a question mark here to show that it's
[20:53] nullable. Right? For some slots in the grid, there is no player. And this is this, to be honest, I'm okay with it. And it's not the end of the world. It's totally fine. But what you'll notice is that this is in part sort of violating
[21:06] that single responsibility uh principle that we were talking about earlier. And that you don't actually need to know all about the players here. the grid only needs to know about what disk is there really like what disc color. And so what
[21:18] testable as well is that we end up creating a disk color enum which just has two colors maybe red or blue and all that the board needs to know is what disc colors are in each spot and then game can figure out which player that
[21:33] corresponds to and thus which player won and all of these sorts of things. Right? little bit more true to SRP but like I said you can go either way. Okay, I preference here, but that's what I'm going to end up doing. And so now we can
[21:47] look at trying to define our methods. And if we do this, these are the methods that the board is going or the game again is going to need to call. And so the first thing that g the game might need to figure out based on us knowing
[22:00] that dropping into a full column is invalid, right? Or moving out of turn is invalid. It's going to need to know, well, can I place this? And so given a column, can I place it? And what should
[22:13] it return here? Well, given a column, can I place it? We'll say that it returns the boolean. Then game can decide what to do. Return an error to the user, throw, render something in the UI for whoever is handling that, right?
[22:26] disc falls to its lowest available row and you end up dropping them, right? And so we need to have that place disk function. This is when a user calls make move. What do they do? Well, they check,
[22:38] can they place it? And then they actually try to place the disc. And so this will take the column that they're placing it on as well as the color. And return value here unknown. And we'll come back to it in just a moment as we
[22:51] learn more. Just continuing to go through here. We it's a draw. And so the game is going to need to be able to make that decision. And so we should expose to the game then is full. It should be able to check
[23:04] this. And that's going to be a boolean. And then maybe the last one here is that a player gets four discs in a row. Well, then they win, right? And so the board, the game needs to be able to call the board and say, did somebody win? We can
[23:18] call that check win. And so what should check win have? This is where I'll come is that it just has a color. Basically, you say check, did this player win? The this, then we would look at the entire board in order to try to figure out if
[23:34] they had four in a row. This is totally doable. It's fairly reasonable and there's nothing wrong with this approach. But what would be smarter is can win is immediately after they place
[23:46] a disc. That's what changed the grid state. So after they place a disc, then whether or not they win would mean that that newly placed disc has to be a part of that for a row. And so rather than checking the entire grid, what we can do
[23:59] checking the entire grid, what we can do is we can tell uh the game class right which row this place disc fell into. It already knows the column. We can tell it how far it fell in terms of rows. So return the row the disc lands in
[24:14] or negative one maybe if we we couldn't place it for some reason, right? Just to for check win, what we can do is that we can pass in the row and the column of can pass in the row and the column of the newly placed disc so that it knows
[24:28] this grid checking the diagonals, the horizontals and the verticals. Okay? And so there's a very strong chance that you did not realize this in class design. And that is so fine. Like in class design, you could have done place this
[24:43] boolean. And then you could have had this as just a color and a boolean. And implementation, you might figure this out that it would be more efficient and change. Just given that this is a YouTube video and people might be
[24:56] stopping the video at this point, I want to be careful to just kind of be correct as I go. Um, but know in the actual game, you can be pretty fluid. And then after here, you have some private methods. Sure, the get row, the getters,
[25:08] going to write all of these or put them all um perfect, but you know, get cell, whatever. Maybe you want to have these um just as internal to the board class, matters when you're doing the the class design is that you expose the public
[25:24] far less important, and I more or less just put them here for completeness. So encapsulates all the grid math and the wind detection. The game uh doesn't know how to scan for four in a row. It just asks the board and updates its own state
[25:39] accordingly. Now we've done disk, we've done game, we've done board, we sort of we needed to create that enum. Now we just need to do player. And so what is a time here. Player is super straightforward. A player just needs to
[25:54] know what color they are. And that's going to be a disc color. And then maybe going to care about. Obviously, that's out of scope for us, so who really cares? But like maybe it's got a string. And then it's just going to expose some
[26:06] public getters here like get name, right? or get color discolor string. Nothing to it, right? No time to spend no reason to spend time there. So at this point, we have the class design and then we can move on to
[26:21] class design and then we can move on to our implementation. said in the beginning, uh this can be majority want pseudo code, what we're
[26:36] going to do. Some want real code. So, I want you to just talk through it even uh just ask them, ask your interviewer what kind of detail they're looking for. Hopefully, your recruiter even told you up front, but as you get into your
[26:48] that I want you to take. I want you to first start by defining maybe I'll put this as a comment as well. I want you to start start by defining the core logic.
[27:01] numbers. You'll see me do this in a second, the core logic of the actual consider the edge cases. And interviewers love when you consider edge cases. So you want to make sure that this is something that you always do.
[27:14] progression. You'll understand what the method should do and then all the ways in which it could break. And when you get into implementation, typically the that they want you to implement. You don't have time in a short interview to
[27:26] implement everything. And so in this interview, the ones that they usually obviously the most important one from game. So game.makemove. Uh they also usually want to see the board.place disk. It's an interesting
[27:41] one. And then check when because it checks all of those conditions, right? about this problem, the ones that they want to see you implement. And it's the here together as well. And so as you're implementing, just remember you're
[27:55] thinking about writing clean code. Avoid all the cleverness. Avoid premature optimizations. That's a trap that I see candidates fall into so often. But let's go ahead and let's start with our games. make move. And so we have game
[28:08] uh and then we have our make move where make move if we come back here took in a player and a column and returned a boolean. So it's going to have a player and it's going to have a column and I'm going to come in here and I'm first
[28:22] going to do what we said we should do starting with defining the core logic. So I'll say what is the core logic? The core logic here is that we are going to place the disc. We're going to try to place the disc. We're going to check if
[28:36] placing that disc means that somebody's won. If so, or maybe if not, excuse me, then we'll check for a draw. And then we will switch turns,
[28:49] right? And then we'll return. So, that's the happy pace. When place the disc. We check if they won. If they didn't, we check if overall there's a draw. We switch turns. And then we return. I don't even need to add that.
[29:03] And then what are the edge cases? Where can things go wrong here? Well, the edge cases would be what? That the game is already over. You can't place a misk right? It could be that it's the wrong player's turn. That won't work. If the
[29:19] person trying to place it, it's the wrong turn. It could be that the column to place it somewhere where it can't be placed. It could be that the column is full. And so if you're watching this and
[29:32] based on what you said about single responsibility and and proper a part of game." And you're right. So I'm kind of going to note that to I'll make sure that board does these checks. Um, but as it pertains to game,
[29:47] state is already over or whether it's the wrong player. And so we can come in here then to to try to actually implement this. And what start with just the happy case. So, I'm going to place a disc. So, I'm going to
[30:02] say boardplace disk and it has a column. And then we but it takes their color. So, I'm going to do that. And then what did place disk
[30:14] return? Place disc we said would return the row. I'm going to say row equals the row. I'm going to say row equals that. And then I'm going to say if You can write pseudo code however you want. You can see my pseudo code looks
[30:26] Python E, but it really doesn't matter, right? Do whatever works for you. You're your interviewer. No interviewer cares about the type of pseudo code you write. There is not even an agreed upon style of pseudo code in the industry. Um, so
[30:39] I'm going to do board check when on the row and the column, right? I have the parameter. I have the row because we returned it. Remember that was a decision that we made earlier. And if that's true, then I'm going to change
[30:51] the state to one. And I'm going to change the winner to the current player. Cool. What's next, though? If it's not true, we said that we need to check if this was a draw. So, I'm going to say else if the board is full, well, in this
[31:07] case, my state equals my state equals draw. Um, and then otherwise, right? So, if we won, game over. If it's a draw, game over. If it's not game over,
[31:22] player. And so my current player would be that if the player equals player one, then now it's player two. Otherwise, it's player one. Just a simple turnary
[31:34] player one, now it's player two. Otherwise, it's player one. No big deal. true because we said that make move returns a boolean to whether or not we we're successfully able to make the move. Okay, so that's my happy path.
[31:50] it. Let's not think about those edge failure conditions? Well, if the game is already over and so I need to say if the already over and so I need to say if the state does not equal in progress, then
[32:03] state does not equal in progress, then we should return false. And then if the equal the current player and we have current player state, remember current player is state. So, if the player does not equal the current player, I'm also
[32:18] going to return false. Um, but then I said that I was going to offload these to the board. And so, I'm assuming that place disgrow
[32:36] disc. Um, and I'm going to also return false in that case. One important thing to discuss here, and some of you might be thinking about this, doesn't this stink? Why are we returning booleans? Shouldn't we be throwing errors? Um, and
[32:50] You're totally right to call that out. In this case, whoever's working with the UX or the UI is going to just they're not going to know what type of error the user like, there was an error, and that's maybe not a great experience. And
[33:03] so, because we defined that as sort of out of scope and this is an interview and I'm I'm kind of shortening things here, maybe this is fine. But if you want to be totally complete and I would appreciate a candidate bringing this up,
[33:15] then maybe you actually return some appropriate error status here. Like maybe this returns some object that has like success and message. And in each of these you can actually then return false and you know game not in progress or
[33:32] maybe it returns an enum so that the the user knows what or the the caller knows what to do with it. Um, the reality is you don't know what the caller wants here. And so I would just raise this if I was an interview. I'd raise this to my
[33:44] important. I know it could be something else. I've sort of taken like a a cheat code here by just returning false or true because I don't know what my caller wants, but it would probably be some sort of an informative error message and
[33:56] they would appreciate that. I think that's more than enough for them. Um, want the full error states, you can obviously put them. So just reviewing this again, our core logic is in place. We place a disc. We check a win. We see
[34:09] edge cases are handled. Game over current player as well as any issues with the the the columns being full or the wrong index. This looks like a pretty good implementation to make move. We can move on then to the next key
[34:23] code implementation for is going to be from our board class and it's going to be uh place disk. So we can scroll down here. class if we look up at our class design, we
[34:38] can remind ourselves it takes a column and it takes a color and it returns the int of the row that it landed in or negative one. So we have the column,
[34:50] the column and the color. Okay. And so we'll take the exact same approach. We'll just define what the core logic should be and then we'll define what our error conditions should be. And so the core logic here is that we want to find
[35:03] the lowest empty row so that it can uh you know for that column so that it can fall to the lowest empty row and then we want to place the disk basically update the grid state and we want to return
[35:18] return the row it landed in so we know where to span our check out from as we talked about earlier. As for edge cases, these should be the same as what we have here. We already determined that they were edge cases apart of the board.
[35:31] Right? So the edge cases are the column index is out of bounds or the the column index is out of bounds or the column is full. Okay. So if we then come in to try to implement this, we can start with our core logic. And the first
[35:46] lowest empty row for that column, let me paste this ASI in it so I can help you guys visualize this. This is our grid, right? So we just have a grid, a array
[35:58] of rows, okay, where each one of these is indexed at zero. So 0 0 is our top top left hand corner. And so if somebody told us they wanted to drop it into two, check here, then here, then here, then here, then here, then here all the way
[36:12] here, then here, then here all the way up until or if we found um you know, an place our disc. And so that means that we start at the rows minus one because
[36:24] variables that in this case is going to our instance variables which is going to be six. And so we start at rows number one since it's zero indexed and we just work our way up. And so in pseudo code what that might look like is for row
[36:38] where rows [cough] row equals rows minus one down to zero just have a for loop of that nature. nature. uh then we can say if the grid and we do
[36:52] rows first with that row and that given column which was the input if it's null then what we want to do is we want to set the grill or the grid with that row and that column to the disc color that was input right and we want to return
[37:09] that row if we don't then maybe we return negative one so there's our happy case pretty straight straightforward core logic. Nothing really to it. Now, if we look at those edge cases, then we could either just kind of offload this
[37:24] that. Yeah, let me do that. So, I'm going to say if the column is less than zero or the column is greater than greater than or equal to board.get calls,
[37:39] calls, right? Then in this case, we can return our negative one. And then what's the other condition? Well, if the column is already full. And so that's the logic that we can just offload to the helper.
[37:51] We already had a helper about cam place. So if you remember, we can just have if boardcam place column. And this is really useful to do column. And this is really useful to do this kind of offloading um in in a
[38:04] this like correct, right? It's nice to have uh you know designs that are simplified in this way. Um, it's like correct programming, but it also just implement that class or implement that method, excuse me, that function unless
[38:18] basically you saying like this one is easy. I don't really need to do this one. If you want me to, I will, but I can kind of just place it that simply. So, with that in place, we have our core logic. Easy enough, right? We work from
[38:30] the grid all the way up until something is available and we place it. Uh, and we return these negative ones or errors as we discussed earlier based on our two edge conditions. Last but not least, we can implement what is really the most
[38:42] interesting function maybe here. Board.check win. So if we come back to our board, we can do check win. And what did check win take according to our class design? Check win takes the row,
[38:54] row and the column, this is the disc that was just placed because again, we just placed rather than looking at the entire board and the color. And so here,
[39:08] [cough] excuse me again, we're going to define our core logic and then we'll define whatever edge cases we need to be aware of. And so for our core logic, we just need to check for four in a row. Check for a row in all four directions.
[39:24] we just have horizontal, vertical, and diagonal? Well, there's two diagonals, right? because you can win horizontally, you can win vertically, and you can win to the left. And so there's actually four there, and that's important. Um,
[39:39] and then obviously we're going to return true if found, false otherwise. So that's the core logic. The edge cases would be if either row or column becomes would be if either row or column becomes out of bounds or the one given to us is
[39:53] out of bounds, then clearly we'd return false. And if you ended up giving us, false. And if you ended up giving us, you know, seven, uh, column seven, row six, it's out of bounds. Nothing we should do with that. Um, what if they
[40:05] gave us row and column? What if this was blue and they gave us row and column 35 or 53 and it wasn't blue here. Well, we should return in that false in that case
[40:17] should return in that false in that case too, right? So if the cell at row column doesn't match color of the disk then also return false. Those are our two uh edge cases error cases that we want to handle.
[40:32] So let's go ahead and now implement it. This is the the more interesting first thing is we want to figure out how we can check the winds in each of these that we're going to start with a disc. That disc could be placed here. And what
[40:46] we want to do is basically count how many of that same color are to its vertical, how many are above it and below it? For diagonal, how many are up left. And for the other way, up and to the left and down and to the right. And
[41:00] then we get to sum those up and see if it if it's four. And so what we can do is we can define first the directions that we move. And so the first thing that we would have is that we could move zero in rows but one in columns. And
[41:14] that would mean that we are going over horizontally. We're staying on the same row, but we're moving one over on the column, right? So this would be that we've gone over one. Maybe let me do this to be clear. So this would be a
[41:27] horizontal check. And then we can also have one zero. And this would of course be the vertical check, right? Because this would mean that if we're right here and we went over one row, we went up one row and we
[41:44] didn't change columns, well, we're checking vertically then in that case. And then we also have one one. This would mean that we go up into the right or I guess in our case because we're increasing, excuse me, this would really
[41:57] be down and to the right. Uh so this would be the uh what did we call this? Diagonal. Is that how you spell it? Okay. And then which is basically you're going in the other direction which would be that. So
[42:13] other diagonal. So those are our directions. Those are the ways that we need to move. But we also need to move like the opposite of those. So again if one is going to take us in this direction. We also need to look over in
[42:27] that direction there. Okay. So let me show you how we can do that. So we can show you how we can do that. So we can say that for all of the directions to that we should move and the directions of the columns that we should move
[42:39] indirection. So we're going to iterator over this. The first time that we iterate over it, we need to move our row by zero. We need to move our column by happening there. Let me remove that for better pseudo code. And then our count
[42:53] is starting at one. And then our count is going to increase based on our count in that direction starting at the row and the column that starting at the row and the column that we're currently at. Moving up by the
[43:08] the amount that we need to for the column checking for that color. And so this is move in one direction. In the is like moving to the right. Okay. And we're going to implement this function
[43:21] in a moment. We're going to offload it for a second. And then we need to look in the other direction. And so we can do this same thing. this same thing. We can do this same thing, right? Count
[43:33] in direction. But in this case, we want to go in the opposite direction. And so in the case of our horizontal check, this would mean that our column is actually negative one. And so we're moving looking this way. So our first
[43:46] check is going to move to the right. Count how many are to the right. Our are to the left. We're adding those to our total count starting with the disk which we already know is the right color. And then if the count is greater
[43:59] than or equal to four, then we can return true. If we got out of this whole thing and we didn't find it, then obviously we're returning false. So make this make more sense, let me go ahead and also implement what would be a
[44:15] private method here of that get direction. And so that's get row get column the direction that we need to move in the rows the direction of columns and then the color here. And so you have your count starting at zero.
[44:28] How many do you have? The row that you need to check now is whatever the need to check now is whatever the current row was plus [cough] excuse me how much we need to move either one step in either direction or zero.
[44:42] The column same thing column plus our DC. And then what do we check? We just check if the row is greater than or equal to zero. This is just our simple bounds here that we always need to check that
[44:54] we don't go outside of the grid. And our row is less than the board.get rows. Okay, easy enough. Just did we get outside of our bounds and C is greater outside of our bounds and C is greater than zero. C is greater C is greater
[45:09] than or equal to zero because zero was in play here. And the C is less than board.getc columns. Right? just again are we in the board and then most importantly that the board.get cell that we're at of this R and C the one that we
[45:24] we're at of this R and C the one that we moved to right equals the color. So if all of that is true then we are still in the board we haven't exceeded the board and as we moved over one we are still that same color and as a result we
[45:37] should increment the count and we should also then move over once more. Right? So we can move our column or our row and our column by one more each. And at the end of that we can return our count. And so what is this doing? It's starting
[45:52] walking its way over in just one direction because we defined that direction that it needs to go. And so the overall one does this twice. It then it walks over in the other. So in the case of the diagonal, it walks that
[46:05] way and then this way. Sums up those counts if they're greater than four. counts if they're greater than four. Hurrah. Okay. So that covers the the core logic. And then the edge cases, of course, our rower columns are out of
[46:18] bounds. Well, we should probably just check that right up front. I'm going to copy this because it's the same code. And that's just if it's this, then I'm And that's just if it's this, then I'm going to return false. And also, if
[46:30] board.getell of that row or column does not equal the current color, as we said in the second check, then I'm also going to return guys to see here is not watch me write code. I actually hate that you guys are
[46:44] type this. The interesting thing is I want you guys to see how uh systematic right? How easy this can be by just going step by step. If you've built your functions, you understand the core logic and the edge cases for each, then you
[47:00] logic, you can implement the edge cases, and everything becomes pretty Um, one other thing that I want to call out here is that some of you are probably thinking to yourself, why didn't he use the strategy pattern? And
[47:14] article, which is going to be linked in the description. But let me let me paste actually what the strategy pattern could look like in here for you guys. Uh,
[47:26] unfortunately, this is this is in Java, but I think you guys can still get the do is that they implement some interface of a wind checker. And that interface has one function to check. And then they
[47:39] implement a horizontal wind checker, a vertical wind checker, a diagonal down, a diagonal upright. And in their check win, what they do is that they have all of over each of them checking them. And if any of them return true, then of
[47:52] course uh the check win should resolve to true. And so I didn't even implement these. I stubbed them out. But you can see how many lines of code this is. And something I see in so many low-level design interviews. And if you take
[48:06] anything away from this video, maybe it's that I want you to take this away. That the most common mistake candidates make is that they just shove patterns unnecessarily into problems because they want to show off to their interviewer,
[48:18] And what it leads to is just ridiculous overengineering. Like why do I need to pattern for each of these four strategies when a there's no conceivable
[48:30] There's no other direction that you could even move on a grid, first of all. And B, in order to check this, it's just 10 lines of code. Why blow everything up like this? And so, maybe this is kind of my own itch that I'm passionate about,
[48:45] speaking correct within software engineering. And it's a symptom of these low-level design interviews where we've taught these patterns in object-oriented design um so excessively that candidates actually lose sight of what they're
[48:59] supposed to really be doing. And so don't be that guy or girl. Don't shove that you're right. If you want to show them that you understand patterns, do this. This is a senior level thing to do. You could say here, hey, I could
[49:13] could have a pattern or I could have an implementation for each of the different check directions and then iterate over those check directions um in order to determine whether someone has won. But the reason I'm not going to do that is
[49:27] because there's no really conceivable option for those wind checkers to change and their logic is all so similar to each other. And so there's no reason for me to blow up the complexity of this implementation just to fit in a pattern
[49:40] unnecessarily. If you say something like that, your interviewer will be some reason your interviewer is not and they say, "No, I want to see you shove a go ahead and you can implement the pattern. And again, I don't [snorts]
[49:54] Maybe not a company that you want to work for. Um, but I also understand that adapt and and we all want to get those jobs. Um, but nonetheless, there's the
[50:06] functions. If you want to see these implemented in your language of choice helper functions implemented as well, again, written breakdown, uh, you can again, written breakdown, uh, you can see all of that there
[50:22] level, your interviewer might might now ask you a couple follow-up questions to Depending on the company, as I said, level, how hard the question was, you is already pretty long. And so, especially if you're junior mid-level,
[50:36] this point, you're all done. If you're senior up and you want to stick around a little bit, I'll be complete and just walk through what the top three extensibility questions for this particular LOL design interview usually
[50:48] different board sizes, how you would add an undo or a move history, as well as So, if we start with just that first one, this is really straightforward. How would you support different board sizes? If my interviewer asked that, I would
[51:01] say, well, that's actually really straightforward. Nowhere aside from in the class definition would we have hard-coded six and our seven? Yeah, whatever. Um, so all that we would do is add this guy. I actually just added it
[51:15] constructor which takes in our row and our columns and as a result now we have you want it to be because nowhere else in the code did we hardcode that six or dynamically checked based on the number of rows and the number of columns when
[51:30] would just naturally grow and everything else would work. Perfect. Our code was extensible. So my answer here would just be update the board constructor to take
[51:43] be update the board constructor to take any and it'll work and it'll work easy. For that next question, how would you add undo or move history? Um then this one's a little bit more involved. Undo is pretty common. It's a pretty common
[51:57] follow-up question for these sorts of games. And this is testing how well you had a clean separation between your orchestrator or game class and your state or your board class. And since all moves are flowing through that game make
[52:10] move function, you already have a single choke point where you want all of the introduce some history. I would basically say something along the lines of this. I can add it here. This is just directly out of the uh uh out of the the
[52:28] description. So I would say undoss belong in the game because game controls the lifestyle, the turn order and when state changes and then I just keep a move history stack such that each time a move succeeds, we push a small move
[52:41] record containing both the player, the row and the column. And then when we want to undo, we just pop that last move off. We clear that cell on the board and we revert the current player. This is essentially what would need to happen.
[52:53] So, let me show you just quickly what that might end up actually looking like. like a move which just tells us the player, the row, uh, and the column that actually took place. And then within our game class, we would add something like
[53:09] this. If we come back up to our game class, come back up to our game class, right? We would add something like a move history. We would add something like a move. Oh,
[53:21] I put that in the wrong place. We would add something like a move history which has a stack of those move objects. And then within make move, we're going to push to that stack. Okay, let me remove it just because I'm going to link this
[53:34] and I don't want you guys to see the kind of incomplete state there. But what that would end up looking like is that in terms of changes, we'll have game with that. And then when it came to that make move function that we had earlier,
[53:46] it's going to now look like this. all the things we did before. Remember, we place the disc and then we're going to push that new move um onto the move history. And so then what the actual implementation of undo last undo last
[54:02] move would look like would be as straightforward as this. We would say if return false. That's our edge condition. We'd pop off of our move history in
[54:14] order to get the last move. And then we could revert the board to clear its state. So board would now need to expose some clear cell which just takes the last row in the column and obviously removes that cell. It would probably
[54:26] check like are there cells above me? Can I even remove this? It probably has some condition checks there. But we won't go that deep. And then simply change the current player. This could be that turnary like we had earlier. Um or
[54:39] actually no this is even better. Right? We have the last from the move. So we can put the player back. uh and then put the state back to where it needs to be. Uh something like this in case there was a winner. This is a simplified version.
[54:52] need in an interview. Usually when they're asking about extensibility, wanting full implementations. Again, what I did here is probably even more than you would want in an interview. Like it would be sufficient to just say
[55:05] this, right? Read this thing out. That's kind of good enough. But I wanted to more about what I meant here so I was a bit more complete. And then last but not least, we have that how would you add a computer opponent? And so this one's a
[55:18] little bit interesting because it's mostly outside of the state u or outside what this follow-up question is usually testing is whether or not you can extend outside of your current class design. So without like ripping up your game and
[55:33] your board implementation as it is. So you might say something in effect like you might say something in effect like this. Let me again paste this in. rules exactly as they are. Game and board. Nothing needs to change. You just
[55:49] introduce some small bot component or bot class that looks at the current board and then returns whatever column it wants to use. Now, we didn't kind of do this game drive logic that was outside of our scope. So, the the
[56:04] current game drive logic would look something like this. uh would look something like would look something like sorry
[56:18] You would have while the game state is in progress get the current player and in progress get the current player and then their column equals you know wait then their column equals you know wait from the UI to get input. Basically this
[56:31] go back and forth between the current players. you would get that input and then you would do gameake move current column. This is how our game class would be used or called and again something like this. This would be
[56:47] sort of the drive engine. And so the only thing that would change here is only thing that would change here is that maybe you would create some class bot engine which has a choose move and how it chooses the move your interviewer
[56:59] obviously you could have some sophisticated ML thing here or you could board. It doesn't really matter. But then the only way that that little thing then the only way that that little thing changes is it becomes now this. And so
[57:12] also instantiate this bot. And you simply say if the current is a human player, then you know do it from the column else choose the move from the bot and you go from there. Your actual board and game didn't need to change at all.
[57:27] and game didn't need to change at all. And that's sort of the key here. Um, if I ask this follow-up question, one thing I see candidates often do is that object-oriented heavy approach and they'll create a player interface.
[57:40] They'll create a player interface and it'll have a human player and it'll have it'll have a human player and it'll have a bot player, right? where the choose move for the human player reads from the UI and the choose move from the bot
[57:54] player um chooses it, you know, however we decide to choose it, randomly or otherwise. Um, this is fine. I don't mind this. I think that this is totally okay. Um, I don't know. I'd argue that maybe the
[58:07] the the simple bot engine approach that we have here is even a better design just because a human player doesn't do anything. It's just data. And so making the player an interface adds this abstraction without actually adding any
[58:20] value. Whereas keeping player as just a simple data and separating uh you know simple data and separating uh you know its identity from making decisions makes I think in my mind pretty clear. Um and if you had reason to believe that there
[58:32] would be other types of players a human a bot and what else? I don't know. I can't think of it off the top of my head. But in any case I appreciate either approach in an interview. As the interviewer I don't mind one bit. So
[58:44] interviewer I don't mind one bit. So feel free to do either one. in the framework all the way through to extensibility. Hopefully you feel like how you would answer this question and more importantly the framework that we
[58:59] would use to walk through low-level design interviews of any question or any takeaways I want you to have is that these interview types don't have to be sequentially and you follow the framework, it really follows a natural
[59:13] progression that's easy to build off of. And so long as you remember to keep things simple, to not uh over inject patterns in order to show off in places you're going to do a fantastic job in your interviews. So, this was the first
[59:27] low-level design interview that we've put on this channel. Um, let me know there was anything that was confusing or if you don't like the flow or the progression. anything, any feedback, any tips, we'll continue to evolve these to
[59:41] make them as useful as possible for all of you. And um most importantly, best of luck with your upcoming interviews. You guys are going to do great. Take care.