Design Tic Tac Toe: Low Level Design Coding Interview Question

[@oopsywtf]

Please - A few more of this LLD questions ! This is awesome

[@mathematicalninja2756]

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

[@gkcs]

Congratulations 😁🍻

[@abarag8]

Congratulations. Which company asked this?

[@chembetikarunakar814]

@@gkcs how to do this project please give source code link and other docs

[@sushmitasingh8352]

Hh

[@jaishreeramjaanki]

the interviewer itself watch this video 10 minutes before interview...

[@devcybiko]

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.

[@arv_sajeev]

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.

[@nemanja.tonic87]

@@arv_sajeev Yeah, but if N > 3, then you have more than 2 diagonals, so this algorithm won't work.

[@arv_sajeev]

@@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????

[@HimanshuYadav-uh4oz]

@@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.

[@vennyroxz]

Please do more of these low level design coding interview questions.

[@samsang8971]

The design and O(1) algorithm is really elegant! Thanks

[@shivamsantosh6111]

Just commenting to appreciate how you hit undo twice when explaining the undo requirement… genius

[@srikantjenakumar]

I love the way you Speak and Explain in details.

[@gkcs]

Thanks!

[@godlesscherryTV]

Channel 10x'd in 3 years, well done !

[@tusharrawat8768]

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.

[@shubhambansal5487]

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

[@someshgangwar4013]

@gauravsen I haven't meet a person like you which explain all concept in such a easy way

[@HELLOWORLD-ry9ds]

You are the king of HLD and LLD

[@rashidsiddiqui4502]

amazing content sir

[@sushmitagoswami2033]

I think Gaurav is the only youtuber who focuses on the actual problem deeply and make the videos crisp instead of focusing on peripherals

[@gkcs]

This is the best compliment I have received in memory. Thank you Sushmita, what is praised is what I strive for consistently. Cheers 🌟🌟🌟

[@sushmitagoswami2033]

​@@gkcs You deserve it! Truly.

[@ndb70]

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???

[@gkcs]

Oh God, yes! Thanks for pointing it out! This is what happens when you don't test your code properly 🙈

[@iitgupta2010]

@Jiren Jin No, check he already put a condition on player = player ==0? -1 : 1;

[@omshankar4862]

Why can’t we have players as 1 and 2? No negative and abs hassle!

[@ALLINONETV1]

I also got same doubt..... Looking for related comments. Finally got...

[@nemanja.tonic87]

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.

[@gkcs]

That's true, thank you 😁

[@venkateshpachigulla]

When this video was posted, the subscribers count was 47k, now subscribers count is 436k. Awesome.

[@logic_master950]

Bhaiyaa, I am a Big fan of your tutorial . Thank you so much 💓💓💓💓. From BD

[@chiragchatwani9124]

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

[@gkcs]

Will pick it up soon 😋

[@shreyanshtiwari5384]

thank you O(1) approach for winner is a really good one

[@RexZShadow]

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.

[@bheemreddyshilpa1710]

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)

[@gkcs]

Are you sure?

[@deathstrokebrucewayne]

Can I hope for chess's low-level design anytime soon? Probably more LLDs

[@d.cc07]

Loved this video..waiting for the chess video..

[@gkcs]

😁

[@ankushrodewad]

This approach makes it very convenient to add new features!

[@amulyakishore]

'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.

[@avikchowdhury6933]

very elegant solution. Loved it.

[@jackburgdoerfer5955]

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.

[@gkcs]

N is the size of the rows

[@rahulsharma5030]

Where can i find code link for this?

[@krishnaidamakanti1644]

Thank you very much for your help.. Just wanted to know which tool your are using for illustration of hand writing?

[@gkcs]

It's ArtRage 😁

[@krishnaidamakanti1644]

Thank you for your quick replay..

[@59sharmanalin]

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

[@LT-js2yk]

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.

[@vipingupta1567]

explained very well. Thanks Gaurav for the video

[@bostonlights2749]

High Quality Stuff!!

[@adithyabhat4770]

Love your videos, helping a lot to me

[@gkcs]

Glad to hear that!

[@RY-it3de]

Hey this Tic Tac Toe code is not in the repo you linked in the description

[@SHIVAMTIWARI-zu4ht]

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

[@viks599]

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

[@sarthakgrover1850]

Thanks for the video sir, Can you make more videos of low level design? It would be very helpful.

[@amanranjanverma]

You are awesome. Just awesome.

[@gkcs]

Thank you!

[@nirleygupta1537]

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?

[@aleyummusic]

Don't see the code on github?

[@tattvabodhaka6140]

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 ?

[@gkcs]

Nope.

[@tattvabodhaka6140]

Thought so, thanks ! It would anyway be of the same order . I’m new to LLD, not a CS Guy lol

[@randomcomments1738]

hey Gaurav what is the best programing language for a beginner like me start learning?

[@gkcs]

Python perhaps.

[@ShaliniNegi24]

very nice explanation.

[@yelururao1]

Thanks.it's awesome..Please do more low level design questions

[@stephyjacob1256]

Great job. Please make more such video on LLD and HLD.

[@srikantsingh8867]

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

[@safakhan8177]

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.

[@Royceroni]

But then how do you determine if its a tie?

[@AZHARSAMEER10]

Nice video, please make more videos on LLD and using design patterns in designing some real world systems

[@bostonlights2749]

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

[@amishsharma7578]

Thank you for the video sir. I just want to ask that which IDE you are using?

[@gkcs]

It's IntelliJ Idea 😁

[@paramgandhi5768]

I have just learnt c++, and the internship I applied too has system design too, how should I learn it from the start?

[@anand_undavia]

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! ♥️

[@gkcs]

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. 😁

[@anand_undavia]

@@gkcs waiting for that day! Hahaha. Thank you so much ♥️ BTW, Are you gonna take part in FEB19 starting today?

[@gkcs]

@@anand_undavia I will have a look at the questions. Wondering if I should post an editorial later... 😛

[@anand_undavia]

@@gkcs Do post one. Whatever you explain goes directly into the brain!🌝

[@blasttrash]

@@anand_undavia what is feb19?

[@Shruti68-b9j]

Many thanks..Very useful video.Waiting for many more useful videos down the line

[@gkcs]

Thanks!

[@varunupadhyay3836]

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?

[@gkcs]

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 😁

[@varunupadhyay3836]

@@gkcs Thanks for your reply. Looking forward to the chess video

[@ps36452]

Great work. One question, which whiteboarding software do you use to present your session?

[@gkcs]

ArtRage with a Wacom board.

[@shaahidbarodawala]

can someone send me the code of this question, i cannot find it in the link given above.

[@ngneerin]

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

[@gkcs]

get.interviewready.io

[@mathematicalninja2756]

@@gkcs Best 4k ever spent

[@rakeshthapachhetri7427]

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

[@gkcs]

Yes.

[@NikhilKumar-vb8ym]

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.

[@gkcs]

The original approach of O(N) time would work there too. Yes, the player can be decided by the board itself. Good point. 😁

[@nilspin]

@@gkcs would it be feasible to traverse all possible states and store them in a lookup table?

[@gkcs]

@@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.

[@NikhilKumar-vb8ym]

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.

[@taranjitkaur9036]

@@NikhilKumar-vb8ym can you please share the code if available ? Thanks!

[@ashishmasih2250]

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?

[@gkcs]

Hey Ashish, I have made lots of videos on AI. You can start here: kzbin.info/www/bejne/gYacdJtrbpJnrNk

[@souvikghosh5668]

Saved to watch later. Next video on Netflix, KZbin concept would be great..

[@gkcs]

I'll try my best!

[@shankarsundaram5513]

Please do some more low level design questions

[@omshankar4862]

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.

[@shubhshah4192]

No, then row, col and diagonal sums wont be equal to n

[@aliasal129]

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

[@jayeshudhani99]

Bro, I think your link doesn't points correctly or code doesn't exists. Can you recheck and attach the correct link ?

[@abhiraj9990]

has Gaurav shared the code?I can't find it

[@madhavgaba7617]

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?

[@PrateekSaini]

Good explanation . Shouldn't it be Math.abs(rowSum[row])==n ?

[@poojachugwani5201]

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?

[@gkcs]

You need a minimax algorithm to find the best move: kzbin.info/www/bejne/gYacdJtrbpJnrNk

[@gauravpareek3783]

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?

[@arjunsharma456]

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; } }

[@mistersir]

Thank you!

[@shradheytripathi7564]

First. :D And thanks Gaurav. I was waiting for this video. :)

[@gkcs]

😁

[@sahilk335]

Awesome video.. please made Low level design for chess game :)

[@sayobaid]

Which writing pad do u use bro?

[@gkcs]

Huion

[@rajivranjan6268]

Where is the chess design question? I couldn't find it anywhere.

[@gkcs]

It's yet to be done :)

[@xordux7]

Tum dhanya ho 🙏

[@adithyakashyap64]

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

[@jrajesh11]

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?

[@sarthakCompro]

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.

[@arnabkundu4541]

With how many years of experience can we expect these kinds of questions in interview?

[@mohitmotiani6879]

Great video, very helpful. Please share the code link.

[@rishabhjoshi948]

Next: Master Slave Architecture (Y)

[@gkcs]

The poll results were NoSQL. So that's coming out next. You can vote on the next poll coming after the video 😁

[@sj8065]

Great stuff Gaurav! Can you cover a video that goes over location services like Uber or Yelp?

[@gkcs]

I have it on my list of videos to do 😁

[@lovkush5257]

Nice

[@gkcs]

Thanks!

[@abhijitkumarsinha]

Harkirat Singh - 95 subs . I guess he is the one we all know 15:11

[@gkcs]

Hahaha, I hadn't noticed that!

[@harishs7951]

What if n is passed as 0 to constructor?

[@ritankarsarkar9394]

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.

[@gkcs]

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 😁

[@ritankarsarkar9394]

For the timing, what skill set should be my main concern?

[@swaramjagtap]

The repo does not contain the code for tic tac toe

[@nkalra0123]

can you post the code link..

[@01VAR]

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

[@gkcs]

You are. Recheck the winning condition.

[@01VAR]

@@gkcs Its correct . Rechecked the condition . Colsum is summing the all rows for same column

[@VivekVardhan22]

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?

[@gkcs]

Thanks Vivek! You can check out the Instagram interview video for the notification and user feed ideas 😁

[@pramodroy8137]

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

[@gkcs]

I have heard of it. Sounds good though :)

[@learn-ws3rf]

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; } }

[@shrutigoyal600]

Waiting for the code link.

[@dasvidaniya8412]

Can you please create a system design for banking system

[@gkcs]

I could try 😁

[@udeshkumarganesan7040]

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)

[@shauryachopra3388]

Please add the link to code

[@amritrai3336]

I think you made a mistake in code, we need the abs value of rowSum right,as abs(n) makes no sense.

[@gmmkeshav]

you are not checking for draw