Tic-Tac-Toe LLD: The Warm-Up Interview You Should Never Lose

"Let's start with something easy — design Tic-Tac-Toe." That word, easy, is a trap. The interviewer isn't testing whether you can build Tic-Tac-Toe; they're watching how you build it — whether you invent six classes nobody needs, whether you scan the whole board after every move, whether your game object can be driven into a nonsense state. The warm-up is where habits show.

So let's build it the way that earns the follow-up question: with the recipe, a deliberately tiny cast, an O(1) win check that makes interviewers sit up, and a state machine that makes illegal play impossible. You and I will have the whole thing — testable and complete — in a few hundred lines of reading.

Let's start nowhere near a computer

You've played this game on the back of a notebook a thousand times. Notice what you actually tracked while playing: whose turn it is, what's drawn in each cell, and — without ever thinking about it — whether anyone has three in a line. Nobody re-reads the whole grid after every move; your eye just follows the line that the latest mark extended.

Hold onto that instinct. The naive program re-scans the board after every move; the good one does what your eye does — checks only the lines the new mark touched. We'll turn that into the cleanest trick in this article.

Where this little game actually matters

• Interview screens. Tic-Tac-Toe, Snake & Ladder, and the parking lot are the standard "can you structure code at all?" filters.
• It's Connect-Four and Gomoku in disguise. The same design scales to every grid-line game — only the line length changes.
• It's a tiny state machine lesson. The discipline that keeps a finished game from accepting moves is the same one that keeps a parking ticket from exiting unpaid.

Step 1 — Functional requirements (sentences first)

What the game must do, as plain sentences — the functional requirements:

• Two players take turns placing their symbol on an n×n board (3×3 by default).
• A move must land on an empty cell inside the board.
• A player wins by completing a full row, column, or diagonal.
• The game is a draw when the board fills with no winner.
• The game can report whose turn it is and the result.

That second sentence is two rejections in one: a move off the board, and a move onto an occupied cell, are both refused — loudly — rather than silently overwriting. The whole game is small enough that the edges are the design.

Step 2 — Non-functional requirements

At class level the non-functional requirements are different words for the same idea — how well, not just what — and for a game this small they're what separates the warm-up you pass from the one you ace:

• Correctness. A move must be in-bounds and on an empty cell; turns must alternate; a win is any full line — row, column, or either diagonal; a full board with no line is a draw. Every one of those is a place to be wrong.
• Performance. The win check must be O(1) per move — bumping a few counters — not an O(n²) re-scan of the whole board every turn. This is the optimization the interview is actually fishing for.
• Extensibility. Board size N (3×3 generalizing to N×N) and the win rule (full line vs. k-in-a-row) are parameters and seams, not constants baked through the code.
• Testability. A move is a pure transform of game state, and a game is a deterministic sequence of moves — so any position is reachable by replaying moves and assertable on its status.

Listing them is the easy half; the design only earns them if it fulfills them. Here's the contract — each requirement and the mechanism that keeps it:

Every trade-off below is chosen to keep one of these.

Step 3 — Nouns → classes (fewer than you think)

The nouns: game, player, symbol, board, cell, move, result. A rookie turns all seven into classes. Look closer:

• Cell — a value in a 2-D array, not a class.
• Move — it has no lifecycle here; it's the argument to a method.
• Player — we track nothing about players except whose symbol plays next. An enum.
• Board — tempting, but it would own nothing the game doesn't already own. Folding it in keeps one source of truth.

That leaves one class and two enums. Saying why the cast is small is worth more than the cast itself: a class earns its existence with its own state or its own lifecycle — the same test the recipe uses for tables.

Which structure — and why. The board is an n×n array indexed by [row][col], not a map of coordinates or a list of cells — direct O(1) addressing is what makes both the move and the win bump cheap, and sizing it by n is the Extensibility seam from Step 2 (a hard-coded 3×3 grid would weld the size into the type). The player is an enum, not a class, because we track nothing about a player except whose symbol plays next — and an enum's two values are exactly the two states turn can hold, so an illegal third player is unrepresentable (Correctness). And the per-line tallies are kept as plain counter arrays — one slot per row, per column, and per diagonal — because that's the structure that turns the win check from a scan into a constant-time bump (Performance); we'll earn that in Step 6.

Step 4 — Verbs → methods

The verbs: place a symbol, report turn, report result. All of them need the board and the turn — so they all live on the game:

public Status play(int row, int col);   // current player moves; returns the new status
public Symbol currentPlayer();
public Status status();

One deliberate choice: play takes only coordinates — the game knows whose turn it is. Letting callers pass a symbol (play(X, 0, 0)) invites the bug where X moves twice. An API that can't express the illegal thing beats an API that validates it.

Step 5 — The status is a state machine

Same move as every LLD: the result isn't a string, it's a fixed set of states — and a finished game throws if you poke it:

if (status != Status.IN_PROGRESS) {
    throw new IllegalStateException("game over: " + status);
}

Two lines, but they're the difference between a game object and a bag of fields. Every illegal sequence — moving after a win, moving twice into one cell — dies here or in the bounds check, loudly, at the moment of the mistake.

Step 6 — The win check: from scanning to two array bumps

Here's where the warm-up turns into a real conversation. How do you know the last move won?

The obvious answer: scan all winning lines. On 3×3 there are only eight:

Honestly? For a fixed 3×3 board, scanning eight lines is fine — say that out loud, it's true. But the interviewer's follow-up is already loaded: "now make it n×n." Scanning becomes O(n) per move (or O(n²) if you scan everything), and your eye never needed any of it.

The senior answer: remember the notebook instinct — only the lines through the new mark can possibly have changed. Keep a counter per player for every row, every column, and the two diagonals. A move bumps at most four counters; any counter reaching n means its line is complete:

int s = turn.ordinal();
cells[row][col] = turn;
movesPlayed++;
 
rowCounts[s][row]++;
colCounts[s][col]++;
if (row == col) diagCounts[s]++;
if (row + col == n - 1) antiDiagCounts[s]++;
 
boolean won = rowCounts[s][row] == n || colCounts[s][col] == n
        || diagCounts[s] == n || antiDiagCounts[s] == n;

O(1) per move, O(n) extra memory, works unchanged for 3×3 or 30×30. This counter trick is the single most quotable thing in the whole problem — it also happens to be the standard answer to the LeetCode "Design Tic-Tac-Toe" question.

Step 7 — Patterns?

Run the cheat sheet question: what varies? Nothing — two human players, fixed rules. So: plain code, and saying so is the senior move.

But know the follow-up before it comes: "add a computer opponent." Now something varies — how a move gets chosen — and that's a textbook seam:

public interface MoveStrategy {
    int[] chooseMove(TicTacToe game);   // human input, random, minimax…
}

Name the seam, don't build it. Pre-building strategies for a two-human game is exactly the pattern-stuffing the warm-up exists to catch.

Step 8 — Trade-offs (each one keeping an NFR)

The last column is the discipline: every choice keeps one of the promises from Step 2 — that's what designing to the non-functional requirements looks like.

Growth — when the rules change, not the scale. Tic-Tac-Toe doesn't grow by adding machines; it grows by changing the rule. The first knob is n (the counters already absorb it). The next is the win condition: full-line gives way to k-in-a-row (Gomoku), where the counters lose their grip on adjacency and you switch to a directional run-scan around the last cell — O(k), still touching only the new mark's neighbourhood. Same instinct as the counter trick itself: look at what the last move changed, never the whole board.

The complete implementation

package dev.fiveyear.tictactoe;
 
public enum Symbol { X, O }
 
public enum Status { IN_PROGRESS, X_WON, O_WON, DRAW }

package dev.fiveyear.tictactoe;
 
/** n×n Tic-Tac-Toe with an O(1) win check per move. */
public final class TicTacToe {
 
    private final int n;
    private final Symbol[][] cells;
    private final int[][] rowCounts;     // [symbol][row]
    private final int[][] colCounts;     // [symbol][col]
    private final int[] diagCounts;      // [symbol]
    private final int[] antiDiagCounts;  // [symbol]
 
    private Symbol turn = Symbol.X;
    private Status status = Status.IN_PROGRESS;
    private int movesPlayed;
 
    public TicTacToe() {
        this(3);
    }
 
    public TicTacToe(int n) {
        if (n < 3) {
            throw new IllegalArgumentException("board must be at least 3×3");
        }
        this.n = n;
        this.cells = new Symbol[n][n];
        this.rowCounts = new int[2][n];
        this.colCounts = new int[2][n];
        this.diagCounts = new int[2];
        this.antiDiagCounts = new int[2];
    }
 
    /** Plays the current player's symbol at (row, col); returns the new status. */
    public Status play(int row, int col) {
        if (status != Status.IN_PROGRESS) {
            throw new IllegalStateException("game over: " + status);
        }
        if (row < 0 || row >= n || col < 0 || col >= n) {
            throw new IllegalArgumentException("off the board: (" + row + ", " + col + ")");
        }
        if (cells[row][col] != null) {
            throw new IllegalArgumentException("cell (" + row + ", " + col + ") is taken");
        }
 
        cells[row][col] = turn;
        movesPlayed++;
 
        int s = turn.ordinal();
        rowCounts[s][row]++;
        colCounts[s][col]++;
        if (row == col) {
            diagCounts[s]++;
        }
        if (row + col == n - 1) {
            antiDiagCounts[s]++;
        }
 
        if (rowCounts[s][row] == n || colCounts[s][col] == n
                || diagCounts[s] == n || antiDiagCounts[s] == n) {
            status = (turn == Symbol.X) ? Status.X_WON : Status.O_WON;
        } else if (movesPlayed == n * n) {
            status = Status.DRAW;
        } else {
            turn = (turn == Symbol.X) ? Symbol.O : Symbol.X;
        }
        return status;
    }
 
    public Symbol currentPlayer() {
        return turn;
    }
 
    public Status status() {
        return status;
    }
}

And a game from the notebook margin:

TicTacToe game = new TicTacToe();      // 3×3
 
game.play(1, 1);   // X takes the center        → IN_PROGRESS
game.play(0, 0);   // O takes a corner          → IN_PROGRESS
game.play(0, 2);   // X
game.play(2, 0);   // O — one move from winning column 0!
game.play(2, 2);   // X eyes both diagonals — but O blocks each at a corner.
                   //     Still IN_PROGRESS.
game.play(1, 0);   // O completes column 0       → O_WON
 
game.play(2, 1);   // throws IllegalStateException — game over: O_WON

The interview corner

Clarify before you code: Fixed 3×3 or n×n? Two humans, or do we need a computer player? Is undo/replay in scope? Each answer halves the design space — asking them is itself graded.

The follow-up ladder, in the order interviewers climb it:

1. "Make it n×n." The counters answer it — O(1) per move, already built above.
2. "Win is k-in-a-row, k smaller than n." The counters can't see adjacency — switch to the directional run-scan from the warning above (O(k) around the last cell). This is the one variant the full-line trick genuinely can't handle.
3. "Add undo." Store the last move; decrement its counters, flip the turn back. The counters make undo O(1) too.
4. "A server hosts thousands of games." No statics, no singletons — a game is an object; the server holds a map of them (the rate limiter registry shape).
5. "Add a computer opponent." The MoveStrategy seam from Step 7, now justified — random first, then minimax with a depth cap.

Mistakes that fail the round: a class zoo (Board, Player, Move, Cell); rescanning all lines and having no answer to "now n×n"; letting callers pass the symbol so X can move twice.

Where to go from here

The shape, pocket-sized: a tiny cast, an API that can't express illegal moves, a status that's a state machine, and a win check that only looks at what the last move touched.

• Stretch it. Connect Four is this exact class with n = 4 lines on a taller board plus gravity; Gomoku is "first to 5 on a 15×15". The counters survive both — work out what (if anything) breaks.
• Next machine in the queue: the Vending Machine, where — unlike here — a real pattern finally earns its keep.
• The recipe itself, if you skipped it: A Rookie's Guide to LLD.

The warm-up question was never about the game. It's about whether you can hear "easy" and still play like every line is being watched — which, in that room, it is.