Tic-Tac-Toe in a Coding Interview: Clean Object-Oriented Design and an O(1) Win Check
3 views
"Design tic-tac-toe" appears in both coding and low-level design interviews. The basic game is trivial, so interviewers use it to see how you model classes, validate moves, and, in the classic follow-up, detect a win in constant time on an n x n board.
Clarify first
Ask: Is the board always 3 x 3 or n x n? Is the win condition a full row, column or diagonal? Two human players, or a player against a computer? Do we need undo? Those answers decide how much structure you need.
A simple class model
- Player: id and symbol ('X' or 'O').
- Board: size n, a grid, and methods place(row, col, symbol) and is_full().
- Game: the board, the players, whose turn it is, the status (IN_PROGRESS, X_WON, O_WON, DRAW), and make_move(row, col).
Keep rules in Game and storage in Board. That separation is what interviewers look for, because it lets you swap rules (for example Connect Four or "k in a row") without rewriting storage.
Validation
make_move should reject moves when the game is over, the coordinates are outside the board, the cell is occupied, or it is not that player's turn. Raise clear errors or return a result object; say which you choose and why.
The O(1) win check
Checking a full row, column and both diagonals after every move costs O(n). The well-known trick keeps counters instead:
- rows[n], cols[n], diag, anti_diag, all starting at 0.
- Player X adds +1, player O adds -1.
- After a move at (r, c): rows[r] += v, cols[c] += v; if r == c, diag += v; if r + c == n - 1, anti_diag += v.
- If the absolute value of any updated counter equals n, the current player wins.
class TicTacToe:
def __init__(self, n):
self.n = n
self.rows = [0] * n
self.cols = [0] * n
self.diag = self.anti = 0
self.moves = 0
def move(self, r, c, player):
v = 1 if player == 1 else -1
n = self.n
self.rows[r] += v; self.cols[c] += v
if r == c: self.diag += v
if r + c == n - 1: self.anti += v
self.moves += 1
if n in (abs(self.rows[r]), abs(self.cols[c]), abs(self.diag), abs(self.anti)):
return player
return 0 if self.moves < n * n else -1 # -1 means draw
This uses O(n) memory and O(1) time per move. It assumes moves are valid, so keep the grid in Board for occupancy checks.
Follow-ups
1. Undo: store a move stack and subtract v from the same counters.
2. k-in-a-row on a large board: counters no longer work; scan outward from the last move in four directions, which is O(k).
3. Computer opponent: minimax with alpha-beta pruning for 3 x 3, or simple heuristics (win, block, center, corner) to explain quickly.
4. Multiplayer online: game state on the server, moves validated there, and updates pushed over WebSockets.
Presenting it
Start with the class diagram, write make_move with validation, then offer the counter optimization. Interviewers reward the habit of separating concerns and stating complexity before being asked.
If design questions make you lose structure under pressure, Linkjob AI (https://linkjob.ai) gives real-time help during job interviews and technical interviews, so you can keep your explanation organized as the interviewer adds follow-ups.