Design Tic Tac Toe (LLD)

The standard machine-coding warm-up. Everyone can make it work, so nobody is graded on that — you are graded on the win check and on whether the design survives "now make it N×N with K players".

Clarify first

Always ask these; the answers change the design:

• Board size — fixed 3×3, or N×N with a win length of K?
• Number of players — always 2, or more with different symbols?
• Human vs human, or is there a computer opponent?
• Undo, replay, persistence?

Design for N×N with pluggable players. It costs nothing and it is what the follow-up will ask for.

Entities

Game          orchestrates: turns, move validation, win/draw detection
Board         the grid, placing pieces, the win check
Player        name + symbol; a strategy decides the move
Move          row, column, player
Symbol        X / O / … (enum, or a character)
GameStatus    IN_PROGRESS | WON | DRAW

Keep the responsibilities clean: **Board knows the grid, Game knows the rules of play.** Mixing them is the most common structural criticism.

The win check

The naive check scans the whole board after every move — O(N²). The expected answer scans only the four lines through the move — O(N):

public boolean isWinningMove(int row, int col, Symbol s) {
    return count(row, col,  0, 1, s) >= winLength   // horizontal
        || count(row, col,  1, 0, s) >= winLength   // vertical
        || count(row, col,  1, 1, s) >= winLength   // ↘ diagonal
        || count(row, col,  1, -1, s) >= winLength; // ↙ diagonal
}

/** Length of the run through (row, col) along ±(dr, dc). */
private int count(int row, int col, int dr, int dc, Symbol s) {
    int total = 1;
    total += walk(row + dr, col + dc,  dr,  dc, s);
    total += walk(row - dr, col - dc, -dr, -dc, s);
    return total;
}

The better answer for a fixed 3×3-style board is O(1) with running counters:

class Board {
    private final int[] rowCount, colCount;   // signed: +1 per X, -1 per O
    private int diagCount, antiDiagCount;
    private int filled;

    boolean place(int row, int col, Symbol s) {
        int delta = (s == Symbol.X) ? 1 : -1;
        grid[row][col] = s;
        filled++;

        rowCount[row] += delta;
        colCount[col] += delta;
        if (row == col)          diagCount     += delta;
        if (row + col == n - 1)  antiDiagCount += delta;

        return Math.abs(rowCount[row]) == n
            || Math.abs(colCount[col]) == n
            || Math.abs(diagCount)     == n
            || Math.abs(antiDiagCount) == n;
    }

    boolean isFull() { return filled == n * n; }
}

One signed counter per line: it reaches +n only if X filled the line, −n only if O did. Constant time per move, constant extra space. Volunteer this — it is the same trick as LeetCode's Design Tic-Tac-Toe, and it is what the interviewer is waiting to hear.

(It generalises cleanly to two players; with more than two, use a count-per-symbol per line instead of a single signed integer.)

The game loop

class Game {
    private final Board board;
    private final Deque<Player> players;     // rotate for turn order
    private GameStatus status = IN_PROGRESS;
    private Player winner;

    void play() {
        while (status == IN_PROGRESS) {
            Player current = players.pollFirst();
            Move move = current.decideMove(board);

            if (!board.isValid(move)) {
                players.addFirst(current);   // invalid: same player retries
                continue;
            }

            if (board.place(move.row(), move.col(), current.symbol())) {
                status = WON;
                winner = current;
            } else if (board.isFull()) {
                status = DRAW;
            }
            players.addLast(current);
        }
    }
}

A deque for turn order generalises to any number of players for free — a boolean isPlayerOne does not, and that difference is exactly the kind of thing these rounds test.

Patterns worth naming

• Strategy for the player's move decision: HumanPlayer reads input, RandomBot picks

any free cell, MinimaxBot searches. Game calls decideMove and does not care which.

• State if you want GameStatus to own transition rules rather than if chains.
• Observer for notifying a UI, a scoreboard or a logger on each move, without Game

knowing about them.

• Factory for constructing a game from a configuration.

Do not apply all four. Name Strategy, apply it, and mention the others as extensions — over- patterning a small problem reads as poor judgement.

Edge cases to handle

• A move outside the board, or onto an occupied cell.
• A draw on the final move that is also a win — check the win first.
• A win length greater than the board size.
• Playing after the game has ended.

Extensions to be ready for

• N×N with win length K — the counter trick no longer suffices; use the directional

scan above.

• A computer opponent — minimax with alpha-beta pruning, a new Strategy.
• Undo — keep a move stack and reverse the counter updates; this is why place should

have a matching undo.

• Persistence — serialise the move list, not the board; it replays and gives history.
• Multiplayer over a network — Game becomes a server-side session, and the same

design holds.

Track this problem on the System Design sheet.