Tic Tac Toe

Classic Board Game

Design a two-player Tic Tac Toe with move validation, constant-time win detection, a draw rule and a scoreboard that follows many games.

Overview

Two players take turns marking cells of a 3 by 3 grid. The first to fill a row, a column or a diagonal wins; a full grid with no line is a draw. Everyone knows the rules, so the interviewer spends the time on how you split the work between classes, how you validate a move, and how you detect a win without scanning the whole board.

The problem is a warm-up, but it separates tidy designs from tangled ones fast. A tidy design has a Board that only knows about cells, a Game that only knows about turns and rules, immutable Players, and a Scoreboard that learns about results without the Game knowing what a scoreboard is. A tangled one puts everything in one class with a nest of if statements.

A strong answer also shows the constant-time win check: keep a signed counter per row, per column and per diagonal, and test only the four counters the last move touched. Then it shows that the same code plays a 4 by 4 board with no change but a parameter.

Scoping the problem

Before writing code, ask these questions; each answer changes the design a little.

Board size fixed at 3, or N by N? — A parameter costs nothing and shows generality — N by N, default 3
Two players only? — More players need a list and a turn index — Two: X and O
What happens on a bad move? — Return false, or raise; the turn must not pass — Raise, and the turn stays
Track results across games? — Adds a scoreboard and a way to tell it — Yes
Undo, replay, an AI opponent? — Each is a follow-up with its own design — Follow-ups, not the core

Core entities

The Board does not know whose turn it is or what a win is. The Game does not know how a cell is stored. That split is the Single Responsibility Principle in a form an interviewer can see in ten seconds.

Win detection in constant time

Scanning the board after every move is O(n²) for an n by n board. Counters make it O(1). Keep one signed counter per row, per column, and one for each diagonal. X adds 1, O subtracts 1. A line is complete when its counter reaches +n or −n, and only the counters of the last move's cell can have changed.

The trace runs the first game of the demo: X plays (0,0), O (0,1), X (1,1), O (0,2), X (2,2).

X (0,0) — +1, 0, 0 — +1, 0, 0 — +1 — 0 — continue
O (0,1) — 0, 0, 0 — +1, −1, 0 — +1 — 0 — continue
X (1,1) — 0, +1, 0 — +1, 0, 0 — +2 — +1 — continue
O (0,2) — −1, +1, 0 — +1, 0, −1 — +2 — 0 — continue
X (2,2) — −1, +1, +1 — +1, 0, 0 — +3 — 0 — diag is +3: X wins

Scan the whole board — O(n²) — none — Fine for n = 3; the first thing most people write
Scan only the row, column and diagonals of the last move — O(n) — none — The natural middle step
Signed counters (the code) — O(1) — 2n + 2 integers — Works for any n; undo means subtracting

Telling the scoreboard

The Game keeps a list of listeners and calls on_game_over(game) on each when the status leaves IN_PROGRESS. Scoreboard is one listener. A display, a logger or a matchmaking service would be others, and Game would not change for any of them. That is the Observer pattern, and the point is the direction of the dependency: Scoreboard knows Game; Game does not know Scoreboard.

Game holds a Scoreboard and calls its methods by name — Game holds anything with on_game_over
A second consumer means editing Game — A second consumer is one more append
Game is hard to test without a Scoreboard — Game is tested alone; the demo passes a Scoreboard only where it is checked

What you will be able to do

Split the problem into Board, Game, Player and Scoreboard and say what each one does not know.
Validate a move at the right layer and keep the turn from passing on a bad move.
Explain and trace the O(1) win check with signed counters, and say how it generalizes to n by n.
Use a frozen dataclass for Player and say what it buys.
Add a scoreboard as an observer and explain why the dependency points the way it does.

Functional requirements

Two players, X and O, alternate turns on an n by n board (default 3)
play(row, col) places the current player's mark; an off-board cell, a taken cell, or a move after the game ends is refused and the turn does not pass
A move that completes a row, column or diagonal wins; a move that fills the last cell with no line is a draw
The game reports its status (in progress, won, draw) and the winner
Listeners such as a Scoreboard are told when a game ends and count wins and draws across games

Non-functional requirements

Win detection is O(1) per move through signed line counters
Board size is a parameter; no code names the number 3
Player is immutable (a frozen dataclass), so a game cannot swap marks mid-way
Game does not depend on Scoreboard; consumers register as listeners
Every rule is covered by an assert in the demo, including each kind of invalid move

Interview questions

How would you support a bigger board, or a rule like four in a row on a 6 by 6 board?
Why not check for a win by scanning the board? It is only nine cells.
Where do you validate a move, and what should happen on a bad one?
How would you add an unbeatable computer player?
How do you add undo?