LOW LEVEL DESIGN · MACHINE CODING · EASY · 26 OF 42

Design Tic-Tac-Toe: Machine Coding Interview in Java

A classic warm-up machine coding round, done properly: an N x N board, a win check in O(1) per move using row, column and diagonal counters, players as Strategies (a scripted human and a win-or-block bot), a read-only board view, game status, undo with a move stack, an Observer for moves, strict turns for online play and the follow-ups, with a full Java 17 solution.

Patterns usedStrategyObserver

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
  15. 15
  16. 16
  17. 17
  18. 18
  19. 19
  20. 20
  21. 21
  22. 22
  23. 23
  24. 24
  25. 25
  26. 26
  27. 27
  28. 28
  29. 29
  30. 30
  31. 31
  32. 32
  33. 33
  34. 34
  35. 35
  36. 36
  37. 37
  38. 38
  39. 39
  40. 40
  41. 41
  42. 42
1 / 21

Press play to hear the narration, or step through at your own pace. The full Java code is below.

Full Java solution

One file, Java 17, 312 lines, with a small main() demo. Save it as TicTacToe.java, then run javac TicTacToe.java && java TicTacToe.

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
import java.util.Optional;
import java.util.Random;

/** N x N tic-tac-toe: O(1) win check with counters, pluggable players, undo and strict turns. */
public class TicTacToe {

    // ---------- the model ----------
    enum Status { IN_PROGRESS, WON, DRAW }

    record Cell(int row, int col) {
        @Override
        public String toString() { return "(" + row + "," + col + ")"; }
    }

    record Move(Player player, Cell cell) {}

    /** Read-only view the players see: they can look at the board but never change it. */
    interface BoardView {
        int size();

        char at(int row, int col);

        List<Cell> emptyCells();
    }

    /** The grid plus the counters. Win check is O(1) per move; undo is O(1) too. */
    static final class Board implements BoardView {
        private final int n;
        private final char[][] grid;
        private final int[][] rows, cols; // [player index][row or column] = marks placed
        private final int[] diag, anti;   // [player index]
        private int filled;

        Board(int n, int players) {
            if (n < 3) throw new IllegalArgumentException("board must be at least 3 x 3");
            this.n = n;
            this.grid = new char[n][n];
            this.rows = new int[players][n];
            this.cols = new int[players][n];
            this.diag = new int[players];
            this.anti = new int[players];
        }

        @Override
        public int size() { return n; }

        @Override
        public char at(int r, int c) { return grid[r][c] == 0 ? '.' : grid[r][c]; }

        @Override
        public List<Cell> emptyCells() {
            List<Cell> out = new ArrayList<>();
            for (int r = 0; r < n; r++)
                for (int c = 0; c < n; c++)
                    if (grid[r][c] == 0) out.add(new Cell(r, c));
            return out;
        }

        boolean isEmpty(Cell c) {
            return c.row() >= 0 && c.row() < n && c.col() >= 0 && c.col() < n && grid[c.row()][c.col()] == 0;
        }

        /** Place a mark and return true if this move completes a line. */
        boolean place(Cell c, int p, char mark) {
            grid[c.row()][c.col()] = mark;
            filled++;
            return bump(c, p, +1);
        }

        void remove(Cell c, int p) {
            grid[c.row()][c.col()] = 0;
            filled--;
            bump(c, p, -1);
        }

        private boolean bump(Cell c, int p, int d) {
            int r = c.row(), col = c.col();
            rows[p][r] += d;
            cols[p][col] += d;
            if (r == col) diag[p] += d;
            if (r + col == n - 1) anti[p] += d;
            return rows[p][r] == n || cols[p][col] == n
                    || (r == col && diag[p] == n) || (r + col == n - 1 && anti[p] == n);
        }

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

        /** Slow O(n squared) scan, used only by the demo to double-check the counters. */
        boolean bruteWin(char m) {
            boolean d1 = true, d2 = true;
            for (int i = 0; i < n; i++) {
                boolean row = true, col = true;
                for (int j = 0; j < n; j++) {
                    row &= grid[i][j] == m;
                    col &= grid[j][i] == m;
                }
                if (row || col) return true;
                d1 &= grid[i][i] == m;
                d2 &= grid[i][n - 1 - i] == m;
            }
            return d1 || d2;
        }

        String render() {
            StringBuilder sb = new StringBuilder();
            for (int r = 0; r < n; r++) {
                sb.append("  ");
                for (int c = 0; c < n; c++) sb.append(at(r, c)).append(c + 1 < n ? " " : "\n");
            }
            return sb.toString();
        }
    }

    // ---------- players: Strategy ----------
    interface MoveStrategy { Cell choose(BoardView board, char me, char opponent); }

    /** A human: in a real app the UI or console fills this queue; here the demo scripts it. */
    static final class HumanInput implements MoveStrategy {
        private final Deque<Cell> clicks = new ArrayDeque<>();

        HumanInput click(int r, int c) {
            clicks.add(new Cell(r, c));
            return this;
        }

        @Override
        public Cell choose(BoardView board, char me, char opponent) { return clicks.remove(); }
    }

    /** Simple bot: win if it can, block if it must, else centre, then a corner, then anything. */
    static final class SimpleBot implements MoveStrategy {
        private final Random rnd;

        SimpleBot(Random rnd) { this.rnd = rnd; }

        @Override
        public Cell choose(BoardView b, char me, char opponent) {
            List<Cell> empty = b.emptyCells();
            for (Cell c : empty) if (completesLine(b, c, me)) return c;
            for (Cell c : empty) if (completesLine(b, c, opponent)) return c;
            int mid = b.size() / 2;
            Cell centre = new Cell(mid, mid);
            if (b.size() % 2 == 1 && empty.contains(centre)) return centre;
            int last = b.size() - 1;
            List<Cell> corners = new ArrayList<>();
            for (Cell c : List.of(new Cell(0, 0), new Cell(0, last), new Cell(last, 0), new Cell(last, last)))
                if (empty.contains(c)) corners.add(c);
            if (!corners.isEmpty()) return corners.get(rnd.nextInt(corners.size()));
            return empty.get(rnd.nextInt(empty.size()));
        }

        /** Would putting mark m on c finish a row, column or diagonal? Reads only the view. */
        private static boolean completesLine(BoardView b, Cell c, char m) {
            int n = b.size(), r = c.row(), col = c.col();
            int row = 0, column = 0, d1 = 0, d2 = 0;
            for (int i = 0; i < n; i++) {
                if (b.at(r, i) == m) row++;
                if (b.at(i, col) == m) column++;
                if (b.at(i, i) == m) d1++;
                if (b.at(i, n - 1 - i) == m) d2++;
            }
            return row == n - 1 || column == n - 1
                    || (r == col && d1 == n - 1) || (r + col == n - 1 && d2 == n - 1);
        }
    }

    record Player(String name, char mark, MoveStrategy strategy) {}

    interface GameListener { void onMove(Move m, Status status); }

    // ---------- the game ----------
    private final Board board;
    private final List<Player> players;
    private final Deque<Move> history = new ArrayDeque<>();
    private final List<GameListener> listeners = new ArrayList<>();
    private int turn;
    private Status status = Status.IN_PROGRESS;
    private Player winner;

    TicTacToe(int n, List<Player> players) {
        if (players.size() < 2) throw new IllegalArgumentException("need at least two players");
        this.players = List.copyOf(players);
        this.board = new Board(n, players.size());
    }

    void subscribe(GameListener l) { listeners.add(l); }

    /** Ask the current player's strategy for a cell, then play it. */
    synchronized Move playTurn() {
        Player p = current();
        char next = players.get((turn + 1) % players.size()).mark();
        return play(p, p.strategy().choose(board, p.mark(), next));
    }

    /** One move. The whose-turn check and the empty-cell check both happen under the lock. */
    synchronized Move play(Player who, Cell cell) {
        if (status != Status.IN_PROGRESS) throw new IllegalStateException("game is over: " + status);
        if (!who.equals(current())) throw new IllegalStateException("not " + who.name() + "'s turn");
        if (!board.isEmpty(cell)) throw new IllegalArgumentException("cell " + cell + " is taken or outside");
        boolean won = board.place(cell, turn, who.mark());
        Move m = new Move(who, cell);
        history.push(m);
        if (won) {
            status = Status.WON;
            winner = who;
        } else if (board.full()) {
            status = Status.DRAW;
        } else {
            turn = (turn + 1) % players.size();
        }
        for (GameListener l : listeners) l.onMove(m, status);
        return m;
    }

    /** Undo the last move: clear the cell, roll the counters back, give the turn back. */
    synchronized Optional<Move> undo() {
        if (history.isEmpty()) return Optional.empty();
        Move m = history.pop();
        int p = players.indexOf(m.player());
        board.remove(m.cell(), p);
        turn = p;
        status = Status.IN_PROGRESS;
        winner = null;
        return Optional.of(m);
    }

    synchronized Player current() { return players.get(turn); }

    synchronized Status status() { return status; }

    synchronized Optional<Player> winner() { return Optional.ofNullable(winner); }

    synchronized String render() { return board.render(); }

    // ---------- demo ----------
    static void check(boolean ok, String what) {
        if (!ok) throw new AssertionError(what);
    }

    public static void main(String[] args) {
        // 1. Two humans on 3 x 3: X takes the main diagonal.
        HumanInput xs = new HumanInput().click(0, 0).click(1, 1).click(2, 2);
        HumanInput os = new HumanInput().click(0, 1).click(0, 2);
        Player home = new Player("Home", 'X', xs), away = new Player("Away", 'O', os);
        TicTacToe g = new TicTacToe(3, List.of(home, away));
        g.subscribe((m, s) -> System.out.println(m.player().name() + " plays " + m.cell() + " -> " + s));
        while (g.status() == Status.IN_PROGRESS) g.playTurn();
        System.out.print(g.render());
        System.out.println("Winner: " + g.winner().map(Player::name).orElse("none"));
        check(g.winner().orElseThrow().equals(home), "X should win on the diagonal");

        // 2. Undo the winning move: the game is live again and it is X's turn.
        Move undone = g.undo().orElseThrow();
        System.out.println("Undo " + undone.cell() + ": status " + g.status()
                + ", turn " + g.current().name());
        check(g.status() == Status.IN_PROGRESS && g.current().equals(home), "undo should reopen the game");

        // 3. Rules are enforced.
        try {
            g.play(away, new Cell(2, 0));
            throw new AssertionError("O moved out of turn");
        } catch (IllegalStateException e) {
            System.out.println("Rejected: " + e.getMessage());
        }
        try {
            g.play(home, new Cell(1, 1));
            throw new AssertionError("X played on a taken cell");
        } catch (IllegalArgumentException e) {
            System.out.println("Rejected: " + e.getMessage());
        }

        // 4. Bot against bot over many seeds: win-or-block play draws every game.
        int xWins = 0, oWins = 0, draws = 0;
        for (int seed = 0; seed < 300; seed++) {
            Random rnd = new Random(seed);
            TicTacToe b = new TicTacToe(3, List.of(new Player("BotX", 'X', new SimpleBot(rnd)),
                    new Player("BotO", 'O', new SimpleBot(rnd))));
            while (b.status() == Status.IN_PROGRESS) b.playTurn();
            if (b.status() == Status.DRAW) draws++;
            else if (b.winner().orElseThrow().mark() == 'X') xWins++;
            else oWins++;
        }
        System.out.println("300 bot games: X " + xWins + ", O " + oWins + ", draws " + draws);
        check(draws == 300, "two win-or-block bots should always draw");

        // 5. Counters agree with a full scan on random 5 x 5 games with three players.
        int checkedMoves = 0;
        for (int seed = 0; seed < 500; seed++) {
            Random rnd = new Random(seed);
            List<Player> three = List.of(new Player("A", 'A', (v, me, op) -> pick(v, rnd)),
                    new Player("B", 'B', (v, me, op) -> pick(v, rnd)),
                    new Player("C", 'C', (v, me, op) -> pick(v, rnd)));
            TicTacToe t = new TicTacToe(5, three);
            while (t.status() == Status.IN_PROGRESS) {
                Move m = t.playTurn();
                checkedMoves++;
                boolean scan = t.board.bruteWin(m.player().mark());
                check(scan == (t.status() == Status.WON), "counters disagree with the scan");
            }
        }
        System.out.println("O(1) win check matched a full scan on " + checkedMoves + " moves");
    }

    private static Cell pick(BoardView v, Random rnd) {
        List<Cell> empty = v.emptyCells();
        return empty.get(rnd.nextInt(empty.size()));
    }
}

Notes

Requirements

Fix the scope first. The board is N by N, three by default. Two players, X and O, take turns marking one empty cell. You win with a full row, a full column or a full diagonal of your mark. If the board fills up with no winner, it is a draw. A player can be a human or a computer, and we can undo the last move. Graphics, rankings and chat are out of scope.

Ask the questions that change the code. Does a win need the whole line, or K in a row on a big board? The whole line for now; K in a row is a follow-up. More than two players? Allow it, each with their own mark. How far back can undo go? All the way. An invalid move is rejected and the same player tries again. And the bot is simple: win if it can, block if it must, otherwise take the centre.

Requirements
  • board of N x N, default 3
  • two players, X and O, in turns
  • a move marks one empty cell
  • win: a full row, column or
  • diagonal of your mark
  • draw: board full, no winner
  • players: human or computer
  • undo the last move
  • out of scope: graphics,
  • rankings, chat
Clarify first
  • win needs the full line?
  • yes; K in a row is a follow-up
  • more than two players?
  • allowed, each with a mark
  • undo how far back?
  • any number of moves
  • invalid move?
  • reject, same player again
  • how smart is the bot?
  • win, else block, else centre

Entities

Underline the nouns: game, board, cell, player, move. The game owns the board, the list of players, whose turn it is and the status. One idea makes the design flexible: a player is just a name and a mark, and how that player decides where to move is a separate object, a move strategy. Moves are pushed on a stack so we can undo them.

Class diagram

In code the small things are records: a cell is a row and a column, a move is a player and a cell, a player is a name, a mark and a strategy. The status is an enum with three values: in progress, won and draw. The game class holds the board, the players, the index of whose turn it is, the status and a deque of past moves.

Value types
enum Status { IN_PROGRESS, WON, DRAW }
record Cell(int row, int col)
record Move(Player player, Cell cell)
record Player(String name, char mark,
              MoveStrategy strategy)

class TicTacToe {
  Board board; List<Player> players;
  int turn; Status status;
  Deque<Move> history; }

The naive win check

The first idea most people write is to scan the whole board after each move: every row, every column and both diagonals. On three by three that is fine. On a hundred by a hundred it is ten thousand reads for every move. The key observation is that one move can only change four lines: its own row, its own column, and at most the two diagonals. So we only need to look at those.

Naive: scan after each move
for each row: all cells == mark?
for each column: all cells == mark?
main diagonal, anti diagonal

3 x 3: 9 reads, nobody cares
100 x 100: 10,000 reads per move

but only 4 lines can change:
  this row, this column,
  and maybe the 2 diagonals

O(1) win check

Keep counters instead. For each player, count how many of their marks are in each row and each column, plus one counter for the main diagonal and one for the anti diagonal. Placing a mark adds one to its row and column, and to a diagonal if the cell is on it. If any of those counts reaches N, that player has just won. Four additions and four comparisons: constant time per move, whatever the board size.

Walk one example. X already has the corner and the centre, and now plays the bottom right corner, row two and column two counting from zero. Its row count and column count go from zero to one. Row equals column, so the cell is on the main diagonal, and that count goes from two to three. Row plus column is four, not two, so the anti diagonal is untouched. Three equals N, so X wins. The memory cost is just two N plus two numbers per player.

Board.place()
int[][] rows, cols;  // [player][i]
int[] diag, anti;    // [player]

rows[p][r]++; cols[p][c]++;
if (r == c) diag[p]++;
if (r + c == n - 1) anti[p]++;

return rows[p][r] == n
    || cols[p][c] == n
    || diag[p] == n || anti[p] == n;
X plays (2,2) on 3 x 3
  • before: X at (0,0) and (1,1)
  • rows[X][2]: 0 to 1
  • cols[X][2]: 0 to 1
  • row equals col: diag[X] 2 to 3
  • row + col = 4, not 2: no anti
  • diag[X] equals 3: X wins
  • memory: 2N + 2 ints per player

Strategy: players

How a player picks a cell is the Strategy pattern. The interface has one method, choose, which gets a view of the board and the two marks and returns a cell. A human strategy returns the next click from the user interface. A bot strategy computes a move. Later you can add a perfect minimax bot or a remote player over the network, and the game class does not change at all.

MoveStrategy
interface MoveStrategy {
  Cell choose(BoardView b,
              char me, char opponent);
}

HumanInput: next click from the UI
SimpleBot: win, block, centre,
  corner, anything
MinimaxBot, RemotePlayer:
  new classes, game unchanged

Strategy: the bot

The simple bot follows four rules in order. If one move completes a line for me, take it. If one move would complete a line for the opponent, block it. Otherwise take the centre, then a random free corner, then any empty cell. The random generator is passed in, so a test can seed it and get the same game every time. Two of these bots playing each other draw every game in the demo.

SimpleBot.choose()
for (Cell c : empty)
  if (completesLine(b, c, me)) return c;
for (Cell c : empty)
  if (completesLine(b, c, opp)) return c;
if centre is free: return centre
free corner: pick one at random
else: any empty cell

Random is injected: seeded in tests

Read-only view

What does a strategy receive? Not the real board, because then a buggy or cheating bot could place marks itself. It receives a board view: an interface with only read methods, size, the mark at a cell and the list of empty cells. The board implements it, but placing and removing marks are not part of the view. This is interface segregation used as a safety rail.

BoardView
interface BoardView {
  int size();
  char at(int row, int col);
  List<Cell> emptyCells();
}
class Board implements BoardView
  place() and remove() are not in
  the interface: a bot cannot cheat

Flow: one move

Walk one move. The user interface calls play turn. The game asks the current player's strategy for a cell. It rejects the move if the game is over, if it is not this player's turn, or if the cell is taken or off the board. Then the board places the mark and reports a win in constant time. The move goes on the history stack, the status is updated, the turn passes on, and listeners hear about it.

play(player, cell)
if status != IN_PROGRESS: throw
if player != current(): throw
if cell not empty or outside: throw
won = board.place(cell, turn, mark)
history.push(new Move(player, cell))
if won: WON, winner = player
else if board full: DRAW
else turn = (turn + 1) % players
notify listeners, return the Move

Game state

The game has three states. In progress allows moves. Won is set the moment the counters report a full line. Draw is set when the board is full and the last move did not win; the board keeps a simple filled counter, so this check is constant time too. Once the game is won or drawn, play throws, so a late click cannot add a mark. Undo is the only way back to in progress.

State rules
  • IN_PROGRESS: moves allowed
  • WON: set by the counters
  • DRAW: filled == N x N
  • and no win on the last move
  • WON or DRAW: play() throws
  • undo: back to IN_PROGRESS
  • a filled counter makes the
  • draw check O(1) too

Undo

Undo is easy because every move carries enough information to reverse itself. Pop the last move from the stack, clear its cell, and run the same counter update with minus one instead of plus one. Give the turn back to that player and set the status to in progress, because the move we removed might have been the winning one. No board snapshots, so undo is constant time and memory stays small.

undo()
Move m = history.pop();
int p = players.indexOf(m.player());
board.remove(m.cell(), p);
  // same counters, minus one
turn = p;
status = IN_PROGRESS; winner = null;

each Move is enough to reverse
  itself: no board snapshots

Observer

The game itself should never print or draw. It publishes each move and the new status to listeners: the Observer pattern. A console view, a graphical board, a replay recorder and a statistics counter all subscribe the same way. In tests you subscribe a list and assert the exact sequence of moves, which is much cleaner than reading printed output.

Concurrency

On one device there is no concurrency, so say that. Online, two requests can reach the same game at once, or one player double clicks. Make play and undo synchronized on the game, and do the whose-turn check and the empty-cell check inside the same lock, so the second request sees the updated state and is rejected. Different games have different locks and never wait on each other.

Online, many games
  • play() and undo() synchronized
  • on the game object
  • turn check + empty-cell check
  • inside the same lock
  • double click: second is rejected
  • games never block each other
  • or: one actor per game,
  • moves in a queue

Extensibility

Interviewers will change the rules. K in a row on a large board, like five in a row on fifteen by fifteen, breaks the full-line counters, so instead walk the four directions out from the last move and count matching marks, which is order K per move. A perfect player is a minimax strategy. Three players already work, since counters are kept per player. A redo button is a second stack that undo pushes onto.

Extension points
  • K in a row on a big board:
  • walk 4 directions from the
  • last move, O(K) per move
  • perfect bot: MinimaxBot
  • three players: already works
  • move timer: a clock per player
  • replay: listener records moves
  • redo: a second stack

Testing

The full code is below the player. Two scripted humans play until X wins on the diagonal, then undo reopens the game. Out-of-turn and taken-cell moves are rejected. Three hundred seeded games between two simple bots all end in a draw. Finally, five hundred random games with three players on a five by five board compare the counters against a slow full scan after every single move, and they always agree.

Run it
Home plays (0,0) -> IN_PROGRESS
Home plays (2,2) -> WON
Winner: Home
Undo (2,2): status IN_PROGRESS
Rejected: not Away's turn
Rejected: cell (1,1) is taken
300 bot games: X 0, O 0, draws 300
O(1) win check matched a full scan
  on 12421 moves

Follow-ups

Expect follow-ups. Why counters? Constant time per move instead of N squared. A neat two-player trick uses one counter per line, where X adds one and O subtracts one, and a value of plus or minus N is a win. K in a row means counting outward from the last move. Perfect play is minimax with memoised board states. And a saved game is simply its list of moves, replayed onto an empty board.

Follow-ups to expect
  • why counters, not a scan?
  • two players only: one counter
  • per line, X adds 1, O adds -1
  • K in a row? check from the move
  • perfect play? minimax, memo
  • on the board state
  • save a game? the move list
  • million games online?
  • state in a store by game id

Say it like this

Here is the short version to say out loud. The board keeps per-player counts for every row, every column and both diagonals, so checking a win is constant time. Each player holds a move strategy and only sees a read-only board view. Moves go on a stack, so undo just runs the counters backwards. Moves are published to observers, and play checks the turn under a per-game lock.

In the interview
  • "A Board keeps per-player counts
  • for each row, column and both
  • diagonals, so a win is O(1).
  • Players hold a MoveStrategy and
  • see a read-only BoardView. Moves
  • go on a stack for undo, go to
  • observers, and play() checks the
  • turn under a per-game lock."

Interview questions

How do you check for a winner in O(1) per move?

Keep, per player, a count of marks in each row and column plus one count for each diagonal. A move updates at most four counts; if any reaches N, that player has a full line. No scan of the board is needed.

How does the two-player counter trick work?

Use one int per row, column and diagonal. X adds 1 and O adds -1. A line is full for one player exactly when its value is N or -N, which halves the memory compared with per-player counters.

How do you detect a draw cheaply?

Keep a filled counter on the board. If the last move did not win and filled equals N x N, the game is a draw. Some versions declare a draw earlier when every line already holds two different marks, which is also trackable with counters.

Why make the player behaviour a Strategy?

A human, a simple bot, a minimax bot and a remote player differ only in how they choose a cell. With a MoveStrategy interface the game calls choose() and never checks the player type, so new player kinds are new classes and the game is closed for modification.

Why give strategies a BoardView instead of the Board?

BoardView exposes only read methods, so a strategy cannot place or remove marks itself. This protects the game rules from buggy or cheating bots and is a small, practical use of interface segregation.

How do you implement undo?

Push each Move onto a stack. Undo pops it, clears the cell and applies the same counter update with minus one, then gives the turn back and sets the status to in progress. Each move reverses itself, so no board snapshots are needed.

How would you support K in a row on a large board?

Full-line counters no longer apply. After each move, walk out from the new mark in the four directions (horizontal, vertical and two diagonals), counting matching marks on both sides; a total of at least K is a win. This is O(K) per move.

How do you make the game safe for online play?

Synchronize play() and undo() on the game object and do the whose-turn and empty-cell checks inside the lock, so a duplicate request sees the new state and is rejected. Each game has its own lock, so games never block one another.

How would you build an unbeatable bot?

Use minimax: try every empty cell, recursively assume the opponent plays its best reply, and score wins, losses and draws. On 3 x 3 the tree is small, and caching scores by board state makes it instant. It plugs in as another MoveStrategy.