Design Tic-Tac-Toe

1Clarify the requirements#

Pin down what you are building before you touch a class name. Tic-Tac-Toe sounds obvious, but the interviewer almost always has a variant in mind, and catching it is the whole point of this round.

Questions I ask out loud:

• Standard 3x3, or an N x N board? If N x N, does a win mean a full row, column, or diagonal, or K in a row?
• Two players only, or more marks (say X, O, and a third symbol)?
• Single process with two humans taking turns, or is there a network layer or an AI opponent?
• Do we need replay, undo, or persisted state? Or is one in-memory game enough?
• What happens on an illegal move: throw, return a status, or ignore it?

For this guide I lock the scope here.

Functional:

• A board of configurable size N, default 3.
• Two players, each with a distinct symbol.
• Players alternate turns. The engine rejects a move on an occupied cell or out of bounds.
• After each move, the engine reports one of three things: game in progress, a winner, or a draw.
• A win is any full row, any full column, or one of the two main diagonals.

Non-functional:

• The move check must be O(1) amortized, not a full O(N squared) board scan every turn. On a 3x3 the scan is free, so this does not matter for correctness. But the interviewer is really asking "can you make win detection cheap," so I show that I can.
• The design should extend to N x N and to new rules without rewriting the core.
• One game runs in one thread in the base version. Concurrency comes in section 6.

2Identify the core entities#

List the nouns, then throw out the ones that do not earn a class. On an Easy problem, every class has to justify its own existence.

• Board. Owns the grid and knows how to place a mark and report its dimensions. It must NOT know the rules of winning. That is the single most important boundary in this design, and I say so out loud. Keeping rules out of the board is what makes it reusable across variants.
• Cell / Symbol. A cell holds a symbol or is empty. I model the symbol as an enum: X, O, EMPTY. I do not make a separate Cell object on a problem this size. A 2D array of symbols is cleaner with zero wasted objects.
• Player. A name plus the symbol they play. Thin, but real. It gives me a place to hang a human or an AI later without touching the game loop.
• Move. Row, column, and who made it. Modeling the move as an immutable value object pays off the moment someone asks for undo or replay, and it costs almost nothing now.
• WinningStrategy. The rule that decides if the last move ended the game. Pulling this out of the board is the single best decision here. It swaps 3-in-a-row for "four in a row" without touching the board or the loop.
• Game. The orchestrator. Holds the board, the players, whose turn it is, and the status. It drives the loop and asks the strategy whether anyone won.
• GameStatus. An enum: IN_PROGRESS, WIN, DRAW.

Notice what I did NOT make:

• A Grid class separate from Board.
• A RuleEngine manager.
• A GameFactory interface with three implementations.

On an Easy problem, over-abstraction reads as worse, not better. I add abstraction only where I can name a second concrete thing that would use it today.

3Class design#

The shape is simple. Game is the brain. It composes a Board, a list of Player, and a WinningStrategy. The board is dumb storage with bounds checking. The strategy is the only place rules live.

A few design notes before the diagram:

• Board owns its cells by composition. If the game dies, the board dies with it. No board exists on its own, so this is a filled diamond.
• Game holds players by aggregation. A Player could outlive one game and join another, so this is a hollow diamond.
• WinningStrategy is an interface with one method. RowColDiagonalStrategy implements the classic rules. Swapping the implementation is how we handle every variant.
• Move is a plain immutable value object passed into Game.play.

Here is the runtime flow for a single turn, the part interviewers probe hardest. They want to see Game orchestrate and delegate, not do everything itself.

4Key implementation#

I show the parts that carry the design: the enums, the board, the strategy with the cheap win check, and the game loop. I skip getters and constructors where they add nothing on a whiteboard.

public enum Symbol { X, O, EMPTY }

public enum GameStatus { IN_PROGRESS, WIN, DRAW }

public class Move {
    final int row, col;
    final Symbol symbol;
    Move(int row, int col, Symbol symbol) {
        this.row = row; this.col = col; this.symbol = symbol;
    }
}

The board is deliberately thin:

• Stores marks in a 2D array.
• Checks bounds and rejects occupied cells.
• Counts fills so a draw is an O(1) check, not a full-grid scan.

public class Board {
    private final Symbol[][] cells;
    private final int size;
    private int filled = 0;

    public Board(int size) {
        this.size = size;
        this.cells = new Symbol[size][size];
        for (Symbol[] row : cells) java.util.Arrays.fill(row, Symbol.EMPTY);
    }

    public boolean place(int row, int col, Symbol sym) {
        if (row < 0 || row >= size || col < 0 || col >= size) return false;
        if (cells[row][col] != Symbol.EMPTY) return false;
        cells[row][col] = sym;
        filled++;
        return true;
    }

    public boolean isFull() { return filled == size * size; }
    public Symbol get(int row, int col) { return cells[row][col]; }
    public int getSize() { return size; }
}

Now the part that earns points. I only check the lines the last move actually touched:

• Its row and its column, always.
• The main diagonal, only if row == col.
• The anti-diagonal, only if row + col == n - 1.

That is O(N) per move. Here is the clean version, which reads well on a whiteboard and is the right default to write first.

public class RowColDiagonalStrategy implements WinningStrategy {

    @Override
    public boolean checkWin(Board board, Move move) {
        int n = board.getSize();
        Symbol s = move.symbol;

        boolean rowWin = true, colWin = true;
        for (int i = 0; i < n; i++) {
            if (board.get(move.row, i) != s) rowWin = false;
            if (board.get(i, move.col) != s) colWin = false;
        }
        if (rowWin || colWin) return true;

        if (move.row == move.col) {
            boolean diag = true;
            for (int i = 0; i < n; i++)
                if (board.get(i, i) != s) { diag = false; break; }
            if (diag) return true;
        }

        if (move.row + move.col == n - 1) {
            boolean anti = true;
            for (int i = 0; i < n; i++)
                if (board.get(i, n - 1 - i) != s) { anti = false; break; }
            if (anti) return true;
        }
        return false;
    }
}

If the interviewer wants true O(1), here is the trade:

• Swap the scans for running counters: one per row, one per column, one for each diagonal.
• On each move, increment the counter for the current player on the lines it touches.
• Any counter hitting N means a win.
• Cost: O(N) counters of memory. Payoff: constant-time checks per move.
• I only write it out if they ask, because the O(N) version is clearer and 3x3 does not care. Saying "I know the faster version and here is exactly how" is usually worth more than five minutes of coding it.

Finally the orchestrator. It owns turn order, placement, and status, and nothing else.

public class Game {
    private final Board board;
    private final List<Player> players;
    private final WinningStrategy strategy;
    private int current = 0;
    private GameStatus status = GameStatus.IN_PROGRESS;

    public Game(int size, List<Player> players, WinningStrategy strategy) {
        this.board = new Board(size);
        this.players = players;
        this.strategy = strategy;
    }

    public GameStatus play(int row, int col) {
        if (status != GameStatus.IN_PROGRESS)
            throw new IllegalStateException("Game is over");

        Player p = players.get(current);
        if (!board.place(row, col, p.getSymbol()))
            throw new IllegalArgumentException("Illegal move at " + row + "," + col);

        Move move = new Move(row, col, p.getSymbol());
        if (strategy.checkWin(board, move)) {
            status = GameStatus.WIN;
        } else if (board.isFull()) {
            status = GameStatus.DRAW;
        } else {
            current = (current + 1) % players.size();
        }
        return status;
    }

    public GameStatus getStatus() { return status; }
}

The key move in that loop:

• On a win or a draw, I do NOT advance the turn, and I freeze the status.
• The caller gets the result straight back.
• A UI or a network layer just reacts to the return value instead of poking at internal state.

5Design decisions and patterns used#

One pattern carries this problem. The rest are options you name and hold in reserve.

• Strategy pattern. WinningStrategy is the heart of it. The board stores marks, the game runs the loop, the win rule lives in one swappable object. When the interviewer says "now it is four in a row" or "add Connect Four scoring," I hand them a new strategy and change nothing else. This is the one pattern they are checking you know to apply here.
• Value object. Move and the enums are immutable little carriers. Immutability means I can log them, queue them, or replay them without worrying who mutated what behind my back.
• Composition over inheritance. Game is built from a board, players, and a strategy rather than extending some AbstractGame. A Tic-Tac-Toe game is not a kind of board; it has one. Keeping that honest avoids the deep hierarchies that turn brittle the moment requirements shift.
• Factory, held in reserve. If the interviewer asks for several game types, I introduce a small factory that picks the board size and strategy from a config. I do not add it up front. On an Easy problem, an unused factory is clutter, and clutter costs points.
• Observer, mentioned not built. If a UI or scoreboard needs to react to each move, I would add a listener interface that Game notifies after play. I name it so the interviewer knows I see the seam, then build it only if they want it.

Pick the one pattern the problem actually needs, which is Strategy, and treat the rest as options you reach for on demand.

6Handling edge cases and concurrency#

The cases I make sure my code survives:

• Move on an occupied cell. Board.place returns false, Game.play throws a clear exception. I prefer throwing over silently ignoring, because a swallowed illegal move hides bugs in the caller and desyncs the UI from the real state.
• Out-of-bounds coordinates. Same path: place returns false, the game rejects with an IllegalArgumentException.
• Playing after the game ended. play guards on status and throws IllegalStateException. Nobody marks a cell after a win or a draw.
• The draw-vs-win order. I check the win first, then the full board. A single move can fill the last cell AND complete a line at once. Check "full" first and you wrongly call a draw and rob the player of a legitimate win. This exact ordering bug is a thing I watch for, and plenty of people get it backwards.
• The winning move also being the last cell. Covered by checking win before draw, as above.

On concurrency, the base version assumes one thread drives one game, the normal setup for a turn-based game. But the interviewer may ask "what if two clients send moves at once?"

• The race is NOT two players moving simultaneously, since turns alternate by rule.
• The real race is a double submit: two requests for the same turn landing together.
• I protect play with a lock on the game instance (or make the method synchronized), so the second request sees the already-updated turn and the already-filled cell, and gets rejected.
• The board state and the current pointer are the shared mutable things. Guard them together, or you get a torn update where two marks land on the same turn and the counter advances twice.
• For a server hosting many games, I lock per game, not globally. One hot game should never stall a thousand cold ones.

7Extensions and follow-ups#

Where this design goes when I get pushed:

• N x N or K-in-a-row. Board size is already a constructor argument. For "K in a row on an N board," I write a new strategy that scans a window around the last move. Board untouched, game untouched.
• AI opponent. Player becomes an interface with getMove(board). A HumanPlayer reads input, a BotPlayer runs minimax. The loop does not change; it just asks the current player for a move.
• Undo and replay. Every turn produces an immutable Move, so I push them onto a stack. Undo pops the last move, clears that cell, decrements filled, and rewinds the turn pointer. Replay reapplies the list in order.
• Networked multiplayer. The game already returns a status per move, so a thin server wraps play, broadcasts the new state, and the Observer seam pushes updates to both clients.
• Scoring across rounds. A Match object holds several Game instances and a score map. The single-game design stays pure and untouched.

Every one of these lands cleanly because the board does not know the rules and the game returns a plain status. That separation is the whole point, and it is why I spend the first two minutes defending the board-knows-nothing-about-winning boundary.

8What the interviewer is really checking#

I am not grading whether you can detect three X's in a row. A kid can do that. Here is the rubric I actually score on:

• Did you scope it before coding? Asking about N x N and win conditions tells me you design for change instead of hardcoding 3.
• Is the win rule separated from storage? If win detection is buried in the board, your design is stuck the moment rules change. If it is a strategy, you are thinking in seams. This is the line between a hire and a no-hire for me on this problem.
• Right amount of abstraction. Too little and it is a pile of arrays. Too much and I cannot find the logic. The sweet spot on an Easy problem is five or six honest classes, exactly what we built.
• The ordering and edge cases. Win before draw, reject moves after game over, clean handling of illegal input. These show care, and care is the cheapest signal to send.
• Can you grow it on demand? When I say "now add an AI," a good design barely flinches. That calm is the signal I am buying.

Next, try Design a Parking Lot or Design an Elevator System to see the Strategy and State patterns stretch across bigger boards.