Design Tic-Tac-Toe

Design Tic-Tac-Toe

What is this problem about?

The Design Tic-Tac-Toe coding problem asks you to implement a game on an $n imes n$ board. Two players take turns placing their marks (1 or 2). A player wins if they complete a full row, column, or either of the two main diagonals. You need to implement a move function that returns the winner (0 if no winner yet).

Why is this asked in interviews?

This is a classic "Medium" question at companies like Apple, Microsoft, and Amazon. It tests whether you can optimize a simulation. A naive solution checks the entire row, column, and diagonals for every move ($O(n)$). An optimized solution should determine the winner in $O(1)$ time, which evaluations your ability to use "Counters" to track game state.

Algorithmic pattern used

The Simulation design pattern with Counters is used here. You don't actually need to store the $n imes n$ board.

1. Maintain two arrays: rows[n] and cols[n].
2. Maintain two variables: diag1 and diag2.
3. When a player moves at $(r, c)$, increment the count for that row/col/diag if it's Player 1, and decrement it if it's Player 2.
4. If any counter's absolute value reaches $n$, that player has won.

Example explanation

$3 imes 3$ Board.

1. Player 1 moves at (0,0): rows[0] = 1, cols[0] = 1, diag1 = 1. Winner: 0.
2. Player 2 moves at (1,1): rows[1] = -1, cols[1] = -1, diag1 = 0. Winner: 0.
3. Player 1 moves at (0,1): rows[0] = 2, cols[1] = 0. Winner: 0.
4. Player 1 moves at (0,2): rows[0] = 3. Winner! Returns 1.

Common mistakes candidates make

• $O(n^2)$ Check: Scanning the entire board for every move.
• $O(n)$ Check: Scanning only the specific row and column of the move. This is better but still not optimal ($O(1)$ is possible).
• Diagonal Logic: Incorrectly identifying which cells belong to the anti-diagonal (it's where row + col == n - 1).

Interview preparation tip

This problem is a masterclass in "State Reduction." When an interviewer asks you to design a game, always ask: "Do I need to store the whole board, or just the summary of the board?" Summary-based designs are almost always more efficient.