More interview problems · Chapter 27

Tic-tac-toe

Design tic-tac-toe for a machine-coding round: board, players, turn rules, O(1) win detection with line counters, N×N boards, game state and undo.

BeginnerInterview priority: High50 min
On this page
  1. The problem: a game that checks every line after every move
  2. 1. Clarify the requirements
  3. 2. Entities and the class design
  4. 3. O(1) win detection with counters
  5. 4. The code
  6. 5. Undo
  7. 6. Concurrency: two requests, one turn
  8. 7. Extensions the interviewer will ask for
  9. When not to over-design
  10. In the interview
  11. Quiz

The problem: a game that checks every line after every move

Tic-tac-toe looks too small for an interview, which is exactly why it is asked: with the game itself trivial, the interviewer sees how you split responsibilities, handle invalid input and make the win check efficient. A first attempt usually puts everything in one class:

class TicTacToe {
    char[][] b = new char[3][3];
    char turn = 'X';

    boolean move(int r, int c) {
        b[r][c] = turn;                          // no check: overwrites O's mark, or throws off the board
        turn = turn == 'X' ? 'O' : 'X';
        return checkWin();                       // rescans all 8 lines every move
    }
    boolean checkWin() {
        for (int i = 0; i < 3; i++)
            if (b[i][0] == b[i][1] && b[i][1] == b[i][2] && b[i][0] != 0) return true;
        // … columns and both diagonals, all hard-coded for 3
        return false;
    }
}

The problems an interviewer will raise:

  • No validation. A move on a taken cell overwrites it; a move after the game ended is accepted; anyone can move for either player.
  • Hard-coded to 3×3. "Make it 4×4" means rewriting checkWin.
  • The win check rescans the board. For N×N that is O(N²) per move. Fine for 3×3, but the interviewer will ask for better.
  • No game state. Who won? Is it a draw? The caller cannot tell "no win yet" from "draw".

1. Clarify the requirements

Your turn: scope it

The interviewer says "Design tic-tac-toe." Write 4–5 questions and the requirements you would agree on.

Compare with our answer

Questions worth asking: Always 3×3, or any N×N? Is a win always a full line, or K in a row? Two humans, or a computer player too? Do we need undo? Is it played over a network (several requests at once)? Is there a user interface, or just the model and a demo?

A strong answer mentions: board size N · win rule (full row, column or diagonal) · two players taking turns, X first · rejecting invalid moves with a reason · a game state (in progress, X won, O won, draw) · undo or network play as possible extensions.

The agreed list:

RequirementDetail
BoardN×N, N ≥ 3, chosen when the game starts
PlayersTwo, marks X and O; X moves first; turns alternate
WinN of one mark in a row, a column or either diagonal
DrawThe board is full and nobody has won
Invalid movesOff the board, cell taken, wrong player's turn, game already over: rejected with a reason, state unchanged
UndoTake back the last move, repeatedly
PlayersA human, a scripted test player or a simple bot, all behind one interface

Out of scope: a graphical interface, networking, accounts and rankings. K-in-a-row on a large board (Gomoku) comes as an extension.

2. Entities and the class design

Nouns from the requirements: board, cell, mark, player, move, game, turn, state, win. Cell is just a position in the board's array, not a class. Turn and state are fields of the game. Win is not an object; it is the result of a check, which deserves its own small class because it is the clever part.

Game owns the board, the win tracker and the history

Class / typeKindResponsibility
MarkenumX or O; carries a sign (+1 / −1) used by the counters and knows other()
GameStateenumIN_PROGRESS, X_WON, O_WON, DRAW
Movevalue object (record)Row, column, mark; stored in the history for undo
BoardclassThe N×N grid and a count of filled cells. No rules
WinTrackerclassCounters per row, column and diagonal; says whether a move completed a line
PlayerinterfacechooseMove(board); implemented by a human input reader, ScriptedPlayer, FirstFreeBot
GameclassThe rules: whose turn, validation, state changes, history and undo

Why split it this way:

  • Board knows cells, Game knows rules. A different game on the same grid (Connect Four, Gomoku) reuses Board and changes Game or the tracker.
  • WinTracker is separate so the win rule can be swapped (full line vs K in a row) without touching turn logic. In pattern terms it is a small strategy.
  • Player is an interface, also a strategy: the game loop asks "your move" without knowing whether a person or a bot answers. Tests use a scripted player, so they need no keyboard.
  • Mark is an enum, not a char: there is no way to place a 'Z', and the sign lives with the mark.

3. O(1) win detection with counters

The key idea of this problem. A move at (r, c) can only complete four lines: row r, column c, and the two diagonals if the cell is on them. So keep one integer per line, add +1 for an X and −1 for an O, and after each move check only the counters that changed. A line is won when its counter reaches +N (all X) or −N (all O). A line holding both marks can never reach ±N, because an O cancels an X.

Counters per line: only four change per move

The two diagonal tests are worth saying out loud:

  • The main diagonal (top-left to bottom-right) is the cells where r == c.
  • The anti-diagonal (top-right to bottom-left) is where r + c == n - 1. The centre of an odd board is on both.
CheckTime per moveMemory
Rescan every lineO(N²)none extra
Scan only the lines through the last moveO(N)none extra
Counters (used here)O(1)2N + 2 integers

For 3×3 all three are instant, so say so; the interviewer is testing whether you can see the better structure, not saving microseconds. The counters also make undo trivial: subtract what you added.

4. The code

The complete model: validation with clear reasons, O(1) win detection, draws, undo, an N×N board and swappable players. The demo plays a 3×3 game with one illegal move, undoes two moves, plays a 4×4 game against a bot, and ends with a draw.

import java.util.*;

enum Mark {
    X(1), O(-1);
    final int sign;                               // X adds +1 to counters, O adds -1
    Mark(int sign) { this.sign = sign; }
    Mark other() { return this == X ? O : X; }
}

enum GameState { IN_PROGRESS, X_WON, O_WON, DRAW }

record Move(int row, int col, Mark mark) {}

class InvalidMoveException extends RuntimeException {
    InvalidMoveException(String msg) { super(msg); }
}

/** The grid only: knows cells, nothing about turns or winning. */
final class Board {
    final int n;
    private final Mark[][] cells;
    private int filled;
    Board(int n) {
        if (n < 3) throw new IllegalArgumentException("n must be at least 3");
        this.n = n; this.cells = new Mark[n][n];
    }
    boolean inside(int r, int c) { return r >= 0 && r < n && c >= 0 && c < n; }
    Mark at(int r, int c) { return cells[r][c]; }
    void place(int r, int c, Mark m) { cells[r][c] = m; filled++; }
    void clear(int r, int c) { cells[r][c] = null; filled--; }
    boolean full() { return filled == n * n; }
    String render() {
        StringBuilder sb = new StringBuilder();
        for (Mark[] row : cells) {
            for (Mark m : row) sb.append(m == null ? '.' : m.name().charAt(0)).append(' ');
            sb.append('\n');
        }
        return sb.toString();
    }
}

/** Remembers sums per line so a win is detected in O(1) after each move. */
final class WinTracker {
    private final int n;
    private final int[] rows, cols;
    private int diag, anti;
    WinTracker(int n) { this.n = n; rows = new int[n]; cols = new int[n]; }

    /** Applies delta (+1 or -1 times the mark's sign) and reports whether that line is now complete. */
    boolean apply(int r, int c, int delta) {
        rows[r] += delta; cols[c] += delta;
        if (r == c) diag += delta;
        if (r + c == n - 1) anti += delta;
        return Math.abs(rows[r]) == n || Math.abs(cols[c]) == n
            || (r == c && Math.abs(diag) == n) || (r + c == n - 1 && Math.abs(anti) == n);
    }
}

interface Player {
    String name();
    int[] chooseMove(Board board);                // a human reads input; a bot computes
}

/** Plays a fixed list of moves: handy for demos and tests. */
final class ScriptedPlayer implements Player {
    private final String name; private final Deque<int[]> moves;
    ScriptedPlayer(String name, int[]... moves) { this.name = name; this.moves = new ArrayDeque<>(List.of(moves)); }
    public String name() { return name; }
    public int[] chooseMove(Board b) { return moves.poll(); }
}

/** Takes the first empty cell. A smarter bot is just another Player. */
final class FirstFreeBot implements Player {
    public String name() { return "bot"; }
    public int[] chooseMove(Board b) {
        for (int r = 0; r < b.n; r++) for (int c = 0; c < b.n; c++) if (b.at(r, c) == null) return new int[]{r, c};
        throw new IllegalStateException("board is full");
    }
}

final class Game {
    final Board board;
    private final WinTracker tracker;
    private final Map<Mark, Player> players = new EnumMap<>(Mark.class);
    private final Deque<Move> history = new ArrayDeque<>();
    private Mark turn = Mark.X;
    private GameState state = GameState.IN_PROGRESS;

    Game(int n, Player x, Player o) {
        board = new Board(n); tracker = new WinTracker(n);
        players.put(Mark.X, x); players.put(Mark.O, o);
    }

    synchronized GameState play(int r, int c, Mark who) {
        if (state != GameState.IN_PROGRESS) throw new InvalidMoveException("game is over: " + state);
        if (who != turn) throw new InvalidMoveException("not " + who + "'s turn");
        if (!board.inside(r, c)) throw new InvalidMoveException("off the board: " + r + "," + c);
        if (board.at(r, c) != null) throw new InvalidMoveException("cell taken: " + r + "," + c);
        board.place(r, c, who);
        history.push(new Move(r, c, who));
        if (tracker.apply(r, c, who.sign)) state = who == Mark.X ? GameState.X_WON : GameState.O_WON;
        else if (board.full()) state = GameState.DRAW;
        turn = who.other();
        return state;
    }

    /** Undo the last move: reverse every change play() made. */
    synchronized void undo() {
        Move m = history.poll();
        if (m == null) throw new InvalidMoveException("nothing to undo");
        board.clear(m.row(), m.col());
        tracker.apply(m.row(), m.col(), -m.mark().sign);
        turn = m.mark();
        state = GameState.IN_PROGRESS;            // the position before any finishing move was in progress
    }

    /** Asks each player in turn until the game ends. */
    GameState run() {
        while (state == GameState.IN_PROGRESS) {
            int[] mv = players.get(turn).chooseMove(board);
            try { play(mv[0], mv[1], turn); }
            catch (InvalidMoveException e) { System.out.println("  rejected: " + e.getMessage()); }
        }
        return state;
    }

    synchronized GameState state() { return state; }
    synchronized Mark turn() { return turn; }
}

public class TicTacToeDemo {
    public static void main(String[] args) {
        // X takes the anti-diagonal; O makes one illegal move (a taken cell) along the way
        Game g = new Game(3,
            new ScriptedPlayer("alice", new int[]{0, 2}, new int[]{1, 1}, new int[]{2, 0}),
            new ScriptedPlayer("bob", new int[]{0, 2}, new int[]{0, 0}, new int[]{2, 2}));
        System.out.println("result: " + g.run());
        System.out.print(g.board.render());

        g.undo(); g.undo();                         // take back X's win and O's last move
        System.out.println("after undo: " + g.state() + ", turn " + g.turn());
        System.out.println("O blocks: " + g.play(2, 0, Mark.O));

        try { g.play(1, 1, Mark.X); } catch (InvalidMoveException e) { System.out.println("rejected: " + e.getMessage()); }

        // 4x4 against the first-free bot: the same code, a bigger n
        Game big = new Game(4, new ScriptedPlayer("alice",
            new int[]{1, 0}, new int[]{1, 1}, new int[]{1, 2}, new int[]{1, 3}), new FirstFreeBot());
        System.out.println("4x4 result: " + big.run());
        System.out.print(big.board.render());

        // A draw on 3x3
        Game d = new Game(3, new FirstFreeBot(), new FirstFreeBot());
        int[][] seq = {{0,0},{0,1},{0,2},{1,1},{1,0},{1,2},{2,1},{2,0},{2,2}};
        GameState s = null; Mark m = Mark.X;
        for (int[] mv : seq) { s = d.play(mv[0], mv[1], m); m = m.other(); }
        System.out.println("full board: " + s);
    }
}

Running either version prints (Java adds a trailing space after each board row):

  rejected: cell taken: 0,2
result: X_WON
O . X
. X .
X . O
after undo: IN_PROGRESS, turn O
O blocks: IN_PROGRESS
rejected: cell taken: 1,1
4x4 result: X_WON
O O O .
X X X X
. . . .
. . . .
full board: DRAW

Notice the order of checks in play: the win test comes before the draw test. A move that fills the last cell and completes a line is a win, not a draw.

5. Undo

undo() must reverse every change play() made, in one place: clear the cell, subtract the mark's sign from the same counters, hand the turn back to the player who made that move, and set the state to IN_PROGRESS (the position before any move that ended the game was, by definition, still in progress). The history is a stack because undo always takes the newest move first.

Undo pops the last move and reverses each change

This is the Command pattern in a light form: each Move records enough to reverse itself. If moves later have side effects (a timer, a score), give Move its own apply and revert methods. Redo is a second stack: undo pushes onto it, and any new move clears it.

6. Concurrency: two requests, one turn

A local game has one thread. The interviewer's follow-up is usually "now it's played online": each move arrives as an HTTP request, and two can arrive at the same moment (a double click, or both players clicking quickly).

RaceWhat goes wrongFix
Double clickBoth requests pass "is it X's turn?" before either flips the turn; X moves twiceplay validates and applies under one lock per game (synchronized / with self._lock)
Both players click the same cellBoth see it empty; the second overwrites the firstSame lock: check-then-act becomes one atomic step
Undo during a moveUndo pops a move while play is half-applied; counters and board disagreeundo takes the same lock
Stale screenA player moves based on an old board after the opponent undidSend the move number with each request and reject it if it is not the current one

The lock is per game, not global: a million games are a million independent locks that never contend with each other. Holding it is cheap because a move is a few array writes.

7. Extensions the interviewer will ask for

  • N×N: already done; the counters and diagonal tests use n.
  • K in a row on a big board (Gomoku: 5 in a row on 15×15): counters per full line no longer work. Check outward from the last move in four directions (horizontal, vertical, two diagonals), counting same-mark cells until a different one: O(K) per move. (Try box below.)
  • More than two players: replace the sign trick with one counter array per player (or per-line counts per player), and a turn order list.
  • A smarter bot: another Player. Minimax (search every possible future position and assume both sides play perfectly) solves 3×3 instantly; there are under 6,000 reachable positions. On large boards it needs depth limits and pruning.
  • Time limit per move: the game loop asks the player with a deadline; on timeout it forfeits or plays a default.
  • Replay and spectators: the move history is already a log; spectators subscribe to move events (the Observer pattern).

When not to over-design

  • Exactly 3×3, forever: a rescan of 8 lines is clear and fast. Mention counters, but simple code is fine.
  • One process, one user: no lock needed. Add it the moment moves arrive from more than one thread.
  • No undo requirement: you can drop the history, though keeping it costs little and helps debugging.

In the interview

Your turn: spot the bug

A candidate's win check gives false wins and misses others. Find the bugs and fix them.

boolean apply(int r, int c) {
    rows[r]++; cols[c]++;
    if (r == c) diag++;
    if (r == n - c) anti++;
    return rows[r] == n || cols[c] == n || diag == n || anti == n;
}
Compare with our answer

The bugs: (1) every move adds +1 whoever played, so a row with X, O, X "wins". (2) The anti-diagonal test is r == n - c, which is off by one: the anti-diagonal is r + c == n - 1. On 3×3 this counts (1,2) and (2,1) instead of (0,2), (1,1), (2,0). (3) Returning diag == n even when the move was not on the diagonal is harmless only by luck; checking only the lines this move touched is clearer.

boolean apply(int r, int c, int sign) {          // sign: +1 for X, -1 for O
    rows[r] += sign; cols[c] += sign;
    if (r == c) diag += sign;
    if (r + c == n - 1) anti += sign;
    return Math.abs(rows[r]) == n || Math.abs(cols[c]) == n
        || (r == c && Math.abs(diag) == n) || (r + c == n - 1 && Math.abs(anti) == n);
}

A strong answer mentions: a sign per mark so mixed lines cancel · abs(...) == n to catch both players · the anti-diagonal is r + c == n - 1 · only the four lines through the move are checked · a quick test with X, O, X in one row.

Your turn: the requirement changes

The product team wants Gomoku: a 15×15 board where 5 in a row wins. Why do the line counters stop working, and what replaces them? Write the new check.

Compare with our answer

A full-line counter reaching 5 on a 15-cell row does not mean the 5 are consecutive, and a line of 15 is never filled by one player. Instead, after each move, count same-mark cells outward from the move in each of four directions (and their opposites). Cost: O(K) per move, independent of the board size. WinTracker is replaced by a KInARowChecker behind the same role; Game does not change.

boolean wins(Mark[][] b, int r, int c, int k) {
    int[][] dirs = {{0, 1}, {1, 0}, {1, 1}, {1, -1}};
    Mark m = b[r][c];
    for (int[] d : dirs) {
        int count = 1;
        for (int s = -1; s <= 1; s += 2) {           // both ways along the line
            int rr = r + s * d[0], cc = c + s * d[1];
            while (rr >= 0 && rr < b.length && cc >= 0 && cc < b.length && b[rr][cc] == m) {
                count++; rr += s * d[0]; cc += s * d[1];
            }
        }
        if (count >= k) return true;
    }
    return false;
}

A strong answer mentions: counters measure whole lines, not runs of K · scanning four directions from the last move · counting both ways along each direction · O(K) per move · the checker swapped behind its role while Game stays the same · whether six in a row counts (standard Gomoku rules differ; ask).

Tic-tac-toe on one page
  • Classes: Mark and GameState enums, Move record, Board (cells only), WinTracker (the check), Player interface, Game (rules).
  • Validation order: game over → right turn → on board → cell free; reject with a reason and change nothing.
  • O(1) win: 2N + 2 counters; X = +1, O = −1; won at abs == n; diagonal r == c, anti-diagonal r + c == n - 1.
  • Win before draw; draw = board full and no win.
  • Undo: stack of moves; clear cell, subtract sign, return turn, state back to in progress. Redo = second stack.
  • Players are strategies: human, scripted (tests), bot (minimax for 3×3).
  • Online: one lock per game; move number against stale requests; across servers, optimistic UPDATE … WHERE move_number = ? or a unique (game_id, move_number).
  • Gomoku (K in a row): scan four directions from the last move, O(K).
Check what stuck

1. On a 4×4 board X plays (0,3). Which counters does the O(1) win tracker update?

2. A candidate's play() checks for a draw (board full) before checking for a win. What is the visible bug?

3. Your online game receives two move requests for the same game at the same instant: X double-clicked two different cells. What prevents X from moving twice?

4. Which extension breaks the line-counter approach and forces a different win check?

5. Why is Player an interface with chooseMove(board) rather than the game reading from the keyboard?

6. After undo() reverses X's winning move, what must the game state and turn be?

7. A 3×3 game uses a full rescan of all 8 lines after every move. The interviewer asks if that is a problem. What is the best answer?

Score 60% or more and the lesson is marked complete.

Passing the quiz also marks it complete. Progress is saved in this browser only.