Design Tic Tac Toe: Low Level Design Coding Interview Question
HTML-код
- Опубликовано: 30 янв 2019
- 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.org/wiki/Low-lev...
docs.microsoft.com/en-us/dotn...
refactoring.guru/design-patterns
You can follow me on:
GitHub: github.com/InterviewReady/Low...
Please - A few more of this LLD questions ! This is awesome
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...
The design and O(1) algorithm is really elegant! Thanks
Channel 10x'd in 3 years, well done !
This approach makes it very convenient to add new features!
@gauravsen I haven't meet a person like you which explain all concept in such a easy way
I love the way you Speak and Explain in details.
Thanks!
Just commenting to appreciate how you hit undo twice when explaining the undo requirement… genius
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.
very elegant solution. Loved it.
Great job. Please make more such video on LLD and HLD.
explained very well. Thanks Gaurav for the video
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.
Nice video, please make more videos on LLD and using design patterns in designing some real world systems
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.
Thanks.it's awesome..Please do more low level design questions
Love your videos, helping a lot to me
Glad to hear that!
High Quality Stuff!!
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.
Thanks for the video sir, Can you make more videos of low level design? It would be very helpful.
Many thanks..Very useful video.Waiting for many more useful videos down the line
Thanks!
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 😋
You are the king of HLD and LLD
Bhaiyaa, I am a Big fan of your tutorial . Thank you so much 💓💓💓💓. From BD
Please do more of these low level design coding interview questions.
amazing content sir
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
Loved this video..waiting for the chess video..
😁
thank you O(1) approach for winner is a really good one
very nice explanation.
Saved to watch later. Next video on Netflix, RUclips concept would be great..
I'll try my best!
Can I hope for chess's low-level design anytime soon? Probably more LLDs
Please do some more low level design questions
You are awesome. Just awesome.
Thank you!
When this video was posted, the subscribers count was 47k, now subscribers count is 436k. Awesome.
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.
Thank you Gaurav! Really appreciate your work and explanation on the LLD problem. One question, the comment above the move function says "@return winner +1 if first player, -1 if second, 0 otherwise" , but it seems the program is doing the reverse.
Awesome video.. please made Low level design for chess game :)
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?
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 😁
Great video, very helpful. Please share the code link.
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 😁
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?
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...
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
Thank you for the video sir.
I just want to ask that which IDE you are using?
It's IntelliJ Idea 😁
Great work. One question, which whiteboarding software do you use to present your session?
ArtRage with a Wacom board.
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
'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.
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:
ruclips.net/video/KU9Ch59-4vw/видео.html
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..
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
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
Great clarity. But one question, should we not have a From and To position in the move function? As we need to subtract for the ‘From’ position and do an add for the ‘To’ position?
Tic Tac Toe is not chess, a move here is adding O or X on the board, not literally moving from one position to another.
Good explanation .
Shouldn't it be Math.abs(rowSum[row])==n ?
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
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
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 😁
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: ruclips.net/video/KU9Ch59-4vw/видео.html
Nice
Thanks!
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?
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
close to 50k!!!!!!!!!!!!!!!!!!!!!!!!!
Yes!
Where can i find code link for this?
Hey this Tic Tac Toe code is not in the repo you linked in the description
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
I have just learnt c++, and the internship I applied too has system design too, how should I learn it from the start?
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!
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 :)
Tum dhanya ho 🙏
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 😁
But then how do you determine if its a tie?
🔥
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.
With how many years of experience can we expect these kinds of questions in interview?
Hey Gaurav , I am following your videos for quite a some time now. I want to ask you ,how do we prepare for the system design questions for the interview ,I mean seeing your videos everything seems so trivial and easy but doing it on your own is what is important .
Can you tell me any protocols/steps to follow so as to make a good design or any book you may refer.
Thanks for the feedback 🙂
My videos are to help people learn interview/work related material. Practice and perseverance they have to bring themselves.
I think interview preparation sites and solving competitive coding questions is a good way to practice problem solving.
System design is something we can learn with colleagues. You can check my recent Quora answer for some tips 😁
write your own software. no two ways about it. Tell yourself here's a compiler and here's a text editor. I'll not use any libraries and build all abstractions on my own. Slowly through making mistakes you'll get frustrated with your own functions/class designs and you'll slowly learn to realize what changes you need to make to make yourself a happy developer. Since it depends on usability and different people use systems differently, your designs will be specific to your use case. It's more art than science, really.
@@nilspin That's a tough but good point!
@@gkcs just read on Quora , found it helpful Thanks
@@nilspin I think you are right it is more of a art
has Gaurav shared the code?I can't find it
hey Gaurav what is the best programing language for a beginner like me start learning?
Python perhaps.
Don't see the code on github?
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
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
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?
Which writing pad do u use bro?
Huion
First. :D And thanks Gaurav. I was waiting for this video. :)
😁
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?
Can you please create a system design for banking system
I could try 😁
What if n is passed as 0 to constructor?
can you post the code link..
If we are playing tictac toe on nxn board then we only have to determine the winner if the moves count of a player is n or greater than n
Yes.
Waiting for the code link.
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
Bro, I think your link doesn't points correctly or code doesn't exists. Can you recheck and attach the correct link ?
Where is the chess design question? I couldn't find it anywhere.
It's yet to be done :)
Please add the link to code
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?
The repo does not contain the code for tic tac toe
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
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)
Code Link please.
Where is the code?
Please make a chess game design video
Sometime in future 😁