Design Tic Tac Toe: Low Level Design Coding Interview Question

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! 🔥

Use the special discount code of 'HELLOWORLD' to get 20% off!

#gkcs #systemdesign

Reference:

You can follow me on:

[mathematicalninja]

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

[oopsywtf]

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

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

[vennyroxz]

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

[shivamsantosh]

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

[tusharrawat]

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.

[samsang]

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

[shubhambansal]

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

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

[ndb]

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

[chiragchatwani]

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

[venkateshpachigulla]

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

[nemanja.tonic]

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.

[bheemreddyshilpa]

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)

[srikantjenakumar]

I love the way you Speak and Explain in details.

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

[deathstrokebrucewayne]

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

[sushmitagoswami]

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

[dd.c]

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

[sharmanalin]

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