Design Tic Tac Toe: Low Level Design Coding Interview Question
ฝัง
- เผยแพร่เมื่อ 27 ก.ย. 2024
- Low-Level System Design involves designing a system's components before implementing them in code. It is used to define how the objects and interfaces in a system will interact with each other. It also defines what state and behaviors will be present in each object.
An Interview question on LLD(Low-level design) usually has a data structure like a Rate Limiter or a Cache as a question. We are expected to design its #interface and keep the object open for extension but closed for modification (Open-closed principle). Design Patterns could be very useful during an interview and can simplify interactions if applied correctly.
The low-level #SystemDesign allows us to define #DataStructure for Caches and the implementation of their algorithms. It also acts as an Object level API contract, which engineers can implement straightforwardly.
Looking to ace your next interview? Try this System Design video course! 🔥
interviewready.io
Use the special discount code of 'HELLOWORLD' to get 20% off!
#gkcs #systemdesign
Reference:
en.wikipedia.o...
docs.microsoft...
refactoring.gu...
You can follow me on:
GitHub: github.com/Int...
I was asked this in today's low level design interview. Funnily enough, I just watched 30 mins before the interview. Nailed it xD Thanks man
Congratulations 😁🍻
Congratulations. Which company asked this?
@@gkcs how to do this project please give source code link and other docs
Hh
the interviewer itself watch this video 10 minutes before interview...
Please - A few more of this LLD questions ! This is awesome
Nice video, but shouldn't the condition to detect the winner be if (abs(rowSum[row]) == n || abs(colSum[col]) == n || ....)? In other words, shouldn't you take the abs value of rowSum, colSum, diag and revDiag instead of taking the abs value of n???
Oh God, yes! Thanks for pointing it out!
This is what happens when you don't test your code properly 🙈
@Jiren Jin No, check he already put a condition on player = player ==0? -1 : 1;
Why can’t we have players as 1 and 2? No negative and abs hassle!
I also got same doubt..... Looking for related comments. Finally got...
The design and O(1) algorithm is really elegant! Thanks
Just commenting to appreciate how you hit undo twice when explaining the undo requirement… genius
Thanks for this overview! very helpful and not overly bloated. Been looking up this low level system design question for my interview soon but so many of them seem to over complicate the problems so much. Like you have very limited time during an interview and stuff they show just is not realistic in that short period of time.
I'm concerned that the OP is doing "premature optimization." Since TTT is only a 3x3 matrix, the difference between O(n) and O(n*n) is immeasurable. (eg: O(3) vs O(9) is only 3x and in real terms is not significant). Also, the refactoring of the loop is a good idea, but in this case could be done even more simply. I would be more inclined to refactor the massive 3-if "guard" at the beginning of the function. I might even argue it's unnecessary since this is an internal method and nobody should be passing illegal values here. If an illegal value is passed, you should let it fail organically and let the parent (calling) method handle the exception.
The OP says your code should be clear. This solution is completely UNclear. All you need are 8 comparisons (one for each winning position) and you're done. And this doesn't even check for draw.
Also, if you're going to extend this logic to larger board games, this idea of keeping the rowSum, colSum, and diagSum will not work in chess.
The big mistake here is putting the logic for the RULES of the game in the BOARD. The rules belong in their own class. The BOARD should only keep track of the model.
This is a classic example of thinking locally about the solution and solving for just the problem at hand. If your goal is to grow this into a larger AI - this is the wrong path.
The constructor here for Tic tac toe, takes a parameter N as the size of the matrix. Maybe he didn't mention it but his intention was for a TTT where size of the matrix can vary.
@@arv_sajeev Yeah, but if N > 3, then you have more than 2 diagonals, so this algorithm won't work.
@@nemanja.tonic87 didn't get you? N here refers to the number or rows / cols in the N*N matrix. I think there can only be 2 diagnols between each pair of opposing corners? Am I missing something????
@@nemanja.tonic87 your point is valid but that can be extension of this as with n > 3 will lead to some advancement in rules and conditions to be check. For this one he just consider 3*3 game of board.
Great video Gaurav, One point is at least we need to return draw if 9 moves have been exhausted (though I'm sure there would be ways to optimise deciding draw before 9 moves too), we can keep a counter if it becomes 9 we can signal a draw with let's say by returning any number -2 or +2 or anything other than -1,0,1
We can also use a stack to store moves that will be used for undo operations and if the stack size becomes 9 we can say that we have a draw.
Amazing video for LL design. Didn't know we could make finding winner operation in O(1), before watching this video.
I tried to implement Tic-Tac-Toe game using the min-max algorithm, and kept the same code for 'move()' function, to get the winner in O(1) after making a move.
But I was able to beat the computer everytime.
Started debugging my code/logic of min-max/finding winner...and all other helper functions I wrote.
After a day of effort, I figured that the bug is in 'move()' function itself.
You said it right in video, but wrote different code.
Correct condition to check if there is a winner should be:
if(Math.abs(rowSum[x]) == n || Math.abs(colSum[x]) == n || Math.abs(diagSum) == n || Math.abs(revDiagSum) == n).
Great video as always. Thanks.
Good one. Another minor correction in the edge case check. if (player != 0 && player != 1) should actually use OR operator for "Invalid player condition" if (player != 0 || player != 1)
Are you sure?
@gauravsen I haven't meet a person like you which explain all concept in such a easy way
'rowSum[row] == Math.abs(n)' is incorrect. 'n' is always positive; it's rowSum[*] which can become negative. So it should be 'Math.abs(rowSum[row]) == n'. Similarly for colSum and the two diag sums of course.
Channel 10x'd in 3 years, well done !
Loved this video..waiting for the chess video..
😁
Nice overview , I enjoyed the video.
Other Important thing in oo design is interaction between objects.
How player actually makes the move. What sort of interface will be used by player?
How can board module be tested. Do current apis provide such modularity
What if tomorrow there are four players ? Will interface change like the make move method
If player makes a move then is it behavior of player. What if tomorrow I want to use ai as player. Now board state will be passed to player also , will the api change for that
Hey this Tic Tac Toe code is not in the repo you linked in the description
Thanks for the video sir, Can you make more videos of low level design? It would be very helpful.
This is amazing! Thanks a lot Gaurav for a well explained, fast-paced video.
One QQ - why can’t we have the states as 1, 2, 3 as opposed to -1, 0, 1? Then we would not need to use abs.
No, then row, col and diagonal sums wont be equal to n
But then how do you determine if its a tie?
I think Gaurav is the only youtuber who focuses on the actual problem deeply and make the videos crisp instead of focusing on peripherals
This is the best compliment I have received in memory. Thank you Sushmita, what is praised is what I strive for consistently.
Cheers 🌟🌟🌟
@@gkcs You deserve it! Truly.
You are the king of HLD and LLD
Thank you very much for your help.. Just wanted to know which tool your are using for illustration of hand writing?
It's ArtRage 😁
Thank you for your quick replay..
This approach makes it very convenient to add new features!
Don't see the code on github?
amazing content sir
Thank you so much for the amazing explanation.. but while voting for tic-tac-toe I was thinking it would be Player vs CPU instead of Player vs Player. I know it will become complex but can you do it?
Hey Ashish, I have made lots of videos on AI. You can start here:
th-cam.com/video/KU9Ch59-4vw/w-d-xo.html
Hello, Not from the point of view of the interviews, but for designing a solution for a problem in general, How to approach the problem?
For example, at 4.33, you said whenever you make a move, you pass in a Move object. My question is how was it decided that passing a Move object as an argument would be better?
Designing an OO solution in real life is not straightforward and it takes many iteration to come to a good solution. You can certainly prepare for the interview problems but you can not prepare for the problem you are gonna face tomorrow at your day job! It would be good if you can make a video about the thought process of solving the problem, how to iteratively make a solution better and overall attitude to approach a problem.
Thanks! ♥️
Thanks for the feedback Anand 😁
I passed in a move object since it encapsulates an action. Too many params in a method which seem related to each other is an anti pattern.
You are right, but this is in context of an interview. In general, the job requires us to constantly refactor and redesign the codebases we have. As the requirements shift, so does our code.
I could try to touch on that topic, but maybe some other day. 😁
@@gkcs waiting for that day! Hahaha. Thank you so much ♥️
BTW, Are you gonna take part in FEB19 starting today?
@@9429963654 I will have a look at the questions. Wondering if I should post an editorial later... 😛
@@gkcs Do post one. Whatever you explain goes directly into the brain!🌝
@@9429963654 what is feb19?
Great work. One question, which whiteboarding software do you use to present your session?
ArtRage with a Wacom board.
very elegant solution. Loved it.
Nice video. But the return values don't match what was being said at the start of video. The explanation says return +1 if Player 1 wins but the code says " Player == Player==0 ? -1:+1;" Please let us know if this is right
Great video Gaurav. Regarding the diagonal concept to check if we only make a move at the diagonal, how to extend this solution if the board is uneven(not a square matrix) or a square matrix of size nxn with n unknown?
The solution can extend to take all (m+n) diagonals, in case that is considered a win. Maybe the case in a non square board.
N has to be known to us for checking a victory. It is necessary for a tic tac toe game to be defined 😁
@@gkcs Thanks for your reply. Looking forward to the chess video
here abs() function should be on rowSum[row] and colSum[col] instead of having it on n . Eg. abs(rowSum[row])==n. Nice Explanation Overall
Thank you for the video sir.
I just want to ask that which IDE you are using?
It's IntelliJ Idea 😁
can someone send me the code of this question, i cannot find it in the link given above.
If we are not saving the game state and you cannot resume a previous game. Should the winner logic be moved to front end and may be sync up only moves or state of board from backend for network drops?
I have just learnt c++, and the internship I applied too has system design too, how should I learn it from the start?
Thanks.it's awesome..Please do more low level design questions
Please do some more low level design questions
With how many years of experience can we expect these kinds of questions in interview?
Nice Video, very informative!! I just had one query how we can say returning zero from MakeMove method will be a Game draw scenario as for that we need to be check other conditions as well such as board should be filled up with players moves . If you could clarify on that point would be really great. Did I misunderstood anything there?
thank you O(1) approach for winner is a really good one
Thank you for the video Gaurav. Could you please add code link.
Also, how a player is going to decide which move to play to win?
You need a minimax algorithm to find the best move: th-cam.com/video/KU9Ch59-4vw/w-d-xo.html
Great stuff Gaurav! Can you cover a video that goes over location services like Uber or Yelp?
I have it on my list of videos to do 😁
Hello, I am in 1st year B.tech CSE. By what time will I be able to understand your videos and what are the things that I need to learn :/ I like your way of explaining and can only understand the theoretical part of videos.
In a couple of years, you'll be doing a lot of projects and working on your algos. It will all fall in place then 😁
For the timing, what skill set should be my main concern?
A problem with this is a lot of the complex design you do early on in the problem is not implemented when you actually write the code
Bro, I think your link doesn't points correctly or code doesn't exists. Can you recheck and attach the correct link ?
Awesome video.. please made Low level design for chess game :)
Great video! Have you ever played ultimate tic-tac-toe? I can't imagine that being asked in an interview but that can be a really challenging question to solve.
Ref: en.m.wikipedia.org/wiki/Ultimate_tic-tac-toe
I have heard of it. Sounds good though :)
Where is the chess design question? I couldn't find it anywhere.
It's yet to be done :)
you are not checking for draw
Can somebody explain me why there are not enough tutorials on low level design. Searched entire web and found only a few vaguely done videos
get.interviewready.io
@@gkcs Best 4k ever spent
Great video, very helpful. Please share the code link.
very nice explanation.
Hi Gaurav,
All the videos are very insightful. thanks for these. Great help. Can you take up a video on Twitter Notification, basically I was wondering, how notifications can flow almost immediately to say millions of followers within seconds as soon as a person tweet?
Thanks Vivek!
You can check out the Instagram interview video for the notification and user feed ideas 😁
The repo does not contain the code for tic tac toe
First. :D And thanks Gaurav. I was waiting for this video. :)
😁
The ground work of low level design is to make better design decisions which can mitigate risks when developer starts to implement code.
Where is the design decision?.
Really it's not necessary to show the code at design phase. But you should be able to show the conceptual design.
Try to review SDLC( Software development life cycle)
Next: Master Slave Architecture (Y)
The poll results were NoSQL. So that's coming out next.
You can vote on the next poll coming after the video 😁
what about a case like -
0 X _
X 0 _
_ _ X
Payer X has made his current move in (2, 2) and colSum condition will be true, but player x is not the winner. Please correct me if i a m missing something
You are. Recheck the winning condition.
@@gkcs Its correct . Rechecked the condition . Colsum is summing the all rows for same column
Which writing pad do u use bro?
Huion
Waiting for the code link.
Code Link please.
Please add the link to code
Where is the code?
Can we design chess ? .. BTW explaination is great ( as usual )
Thanks Yash!
Chess design will be fun. Let's finish another topic before we get to it :D
Nice
Thanks!
close to 50k!!!!!!!!!!!!!!!!!!!!!!!!!
Yes!
class TicTacToe {
int rows[];
int columns[];
int diagonal;
int anti_diagonal;
/** Initialize your data structure here. */
public TicTacToe(int n) {
rows = new int[n];
columns = new int[n];
}
/** Player {player} makes a move at ({row}, {col}).
@param row The row of the board.
@param col The column of the board.
@param player The player, can be either 1 or 2.
@return The current winning condition, can be either:
0: No one wins.
1: Player 1 wins.
2: Player 2 wins. */
public int move(int row, int col, int player) {
int add = (player == 1) ? 1 : -1;
rows[row] += add;
columns[col] += add;
if(row == col)
diagonal += add;
if(row + col == columns.length - 1)
anti_diagonal += add;
int size = rows.length;
if(Math.abs(rows[row]) == size || Math.abs(columns[col]) == size || Math.abs(diagonal) == size || Math.abs(anti_diagonal) == size)
return player;
return 0;
}
}
Thank you!
🔥
Fire!
Gaurav Sen appreciate your videos bro. I am an SDE1 at Amazon and it’s nice to see another person’s opinions on these subjects and sometimes learn new things about architecture. I don’t have a CS degree so you helped me brush up on a lot of concepts.
public class TicTacToe {
private int[] rows;
private int[] cols;
private int diagonal;
private int antiDiagonal;
/** Initialize your data structure here. */
public TicTacToe(int n) {
rows = new int[n];
cols = new int[n];
}
/** Player {player} makes a move at ({row}, {col}).
@param row The row of the board.
@param col The column of the board.
@param player The player, can be either 1 or 2.
@return The current winning condition, can be either:
0: No one wins.
1: Player 1 wins.
2: Player 2 wins. */
public int move(int row, int col, int player) {
int toAdd = player == 1 ? 1 : -1;
rows[row] += toAdd;
cols[col] += toAdd;
if (row == col)
{
diagonal += toAdd;
}
if (col == (cols.length - row - 1))
{
antiDiagonal += toAdd;
}
int size = rows.length;
if (Math.abs(rows[row]) == size ||
Math.abs(cols[col]) == size ||
Math.abs(diagonal) == size ||
Math.abs(antiDiagonal) == size)
{
return player;
}
return 0;
}
}
"Elo" is just pronounced eee-low
It isn't an acronym
Are you hear to teach or to learn buddy?
First Comment 😅😅
Wow!
You could have done better explaining how you arrived at the requirements. It seemed like you already knew the solution and reverse engineered the problem.
public class Solution {
static int[][] grid;
static int n;
static int[] rowSum;
static int[] colSum;
static int diagSum;
static int revDiagSum;
public Solution(int n) {
// Initialize your data structure here.
this.n=n;
grid = new int[n][n];
rowSum = new int[n];
colSum = new int[n];
diagSum = 0;
revDiagSum = 0;
}
public int move(int row, int col, int player) {
// Write your code here.
int element = player==1?1:-1;
grid[row][col]=element;
rowSum[row]+= element;
colSum[col]+= element;
if(row==col){
diagSum += element;
}
if(row == n-col-1){
revDiagSum += element;
}
if(Math.abs(rowSum[row])==n || Math.abs(colSum[col])==n || Math.abs(diagSum) == n || Math.abs(revDiagSum) == n){
return player;
}
return 0;
}
}
Please do more of these low level design coding interview questions.
Semantic Error! In the line where you are checking for winner, you should take absolute value of rowSum[row], colSum[col], diagSum and revDiagSum rather than abs(n). Correct me If I'm wrong
You are amazing man I had done tic tac toe as hobby project. But this is insane. Please please Make chess video. Thank you for this channel
Will pick it up soon 😋
Can I hope for chess's low-level design anytime soon? Probably more LLDs
Where can i find code link for this?
Thanks for the video! I would just add that your O(1) solution only works for 3x3 boards, but the rest of your solution provides flexibility in terms of size (you take the size n as the constructor parameter). If someone passes n which is greater than 3, it won't work.
That's true, thank you 😁
I have one doubt, we are returning 0, 1 or -1 indicating who is the winner, but where are we ensuring that the game has ended?
Why can't u try a job in google?
Do I want to? 😛
There can only be a winner after Atleast 3 moves of a player (so the win check can come only after 5 initial moves of both players combined Atleast ), will taking this into consideration reduce computation significantly ?
Nope.
Thought so, thanks ! It would anyway be of the same order . I’m new to LLD, not a CS Guy lol
Love your videos, helping a lot to me
Glad to hear that!
High Quality Stuff!!
hey Gaurav what is the best programing language for a beginner like me start learning?
Python perhaps.
This was awesome! Thanks. I'm not sure if I am right but why would it be n^2 to search the board? There's a constant/fixed amount to search.
N is the size of the rows
You are awesome. Just awesome.
Thank you!
Like always a nice video indeed.
What if someone asks you to make it in a scalable way?
Means it can be a m x n board and u need Kx’s or Ko’s to win?
Also I see some redundant data structures used. For example whose move is it can be computed easily by current board status rather than holding an extra variable.
The original approach of O(N) time would work there too.
Yes, the player can be decided by the board itself. Good point. 😁
@@gkcs would it be feasible to traverse all possible states and store them in a lookup table?
@@nilspin For 3x3, yes. For anything else, no.
Even the 3x3 needs reflections on x, y and diagonals removed for efficient storage.
I'd much rather use a minimax algorithm to find the best move, if that's what you want.
Another issue with the approach.
There are possibilities where all boxes have not been exhausted but no possible winning streak would be possible. In other words game is headed towards a draw no matter what. Shouldn’t our algorithm be robust enough to detect that situation and declare draw before hand. I have a design which takes care of all such scenarios.
May be I will blog about it and share a link.
@@NikhilKumar-vb8ym can you please share the code if available ? Thanks!
I love the way you Speak and Explain in details.
Thanks!
Hey can you help us to understand IRCT ticket booking module LLD . How trains and station are mapped and train listing is filter between two station
When this video was posted, the subscribers count was 47k, now subscribers count is 436k. Awesome.
I think you made a mistake in code, we need the abs value of rowSum right,as abs(n) makes no sense.
Bhaiyaa, I am a Big fan of your tutorial . Thank you so much 💓💓💓💓. From BD
Good explanation .
Shouldn't it be Math.abs(rowSum[row])==n ?
Hi!
How do you make the video? The drawing of the tic tac toe and writing on the white screen. Which software is used?
Thank you
has Gaurav shared the code?I can't find it
What if n is passed as 0 to constructor?
can you post the code link..
My mind is in Not Responding mode.