Design Tic-Tac-Toe
On this page
Problem statement
Design a tic-tac-toe game for two players on an
n × nboard.move(row, col, player)places the player's mark and returns the winner after that move:1or2, or0if nobody has won yet. A player wins by filling a whole row, a whole column, or either diagonal. Moves are always valid (the cell is empty and the game isn't over). Follow-up: the board isR × Cand a player wins withkmarks in a row in any direction.
A small design question that rewards thinking about what to store. The obvious answer rescans the board; the good answer keeps a handful of counters so each move is O(1). Original problem: LeetCode 348 (subscription). The R × C, k-in-a-row version is the same idea as Connect Four.
Example

TicTacToe(3)
move(0, 0, 1) -> 0
move(0, 2, 2) -> 0
move(2, 2, 1) -> 0
move(1, 1, 2) -> 0
move(2, 0, 1) -> 0
move(1, 0, 2) -> 0
move(2, 1, 1) -> 1 # bottom row is all player 1
KInARow(rows=4, cols=5, k=4)
moves by player 1: (3,0), (2,1), (1,2), (0,3) (player 2 plays elsewhere in between)
the fourth of them returns 1 # a rising diagonal of 4
Constraints (assumed)
- 2 ≤ n ≤ 100; at most n² calls to
move. - Follow-up: 1 ≤ R, C ≤ 1,000 and 1 ≤ k ≤ max(R, C).
What this question tests
- Asking what the next query needs and storing exactly that, instead of the whole board.
- Small but exact index rules: which cells lie on the main diagonal (
r == c) and the anti-diagonal (r + c == n − 1). - Choosing a different approach when the rules change (k in a row on a rectangle), and saying why counters no longer fit.
Questions to ask first
- Are moves always valid? (Here: yes. Otherwise check the cell is empty and the game isn't already won.)
- Do both diagonals count? (Here: yes.)
- Is the board square, and is the win the full length? That decides counters vs a local scan.
- Should
movealso report a draw? (Here: no; you could add a move counter.)
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.