Design tic-tac-toe

“Design tic-tac-toe.” Sometimes it’s “for two players on one screen”, and sometimes it’s “that people can play online”. Which one you get changes the last part of the answer.

Tic-tac-toe looks like a warm-up question, but it has a trap in it. The game is so small that most people write one class with a 3x3 grid and a loop that checks the whole board for a winner. They finish in ten minutes. That answer works, but it shows the interviewer nothing.

The interesting part is everything around the grid. Where do the rules live? How do we track whose turn it is, so it can never be wrong? How do we spot a win without checking the whole board again? And when the game is online, what happens if the same move arrives twice?

The framework

1. 01Answer
2. 02Scope
3. 03Build
4. 04Full design
5. 05Stress
6. 06Wrap up

The answer in one minute

If you only have a minute, this is the design. The rest of the page explains how we get here.

1. The board and the game are separate classes. The Board only holds marks. The Game holds the rules: whose turn it is, which moves are allowed, and who won.
2. Whose turn it is comes from the move count. We never store it in its own field. After an even number of moves it’s X’s turn, after an odd number it’s O’s. So it can never get out of step, even after an undo.
3. A win is found by reading four numbers, not by scanning the board. We keep one counter for each row, each column and each diagonal. X adds 1 and O subtracts 1. A counter that reaches the board size means a full line.
4. Undo and bots don’t change the game’s rules. Undo reverses the last move from a history list. A bot is just another caller that looks at the board and plays a move like a person.
5. Online, each move can only happen once. One lock per game stops two requests from overlapping. Each request also says which move number it is, so a repeated request is refused.

We’ll build this in four stages, then put the game online.

Scope it

The game’s rules are fixed, but the system around it isn’t. A few questions change the design a lot. Anything else, we assume and move on.

Interviewerminute 0

Design tic-tac-toe.

What they are testing

Whether you find the two or three questions that change the design (board size, local or online, undo) in under three minutes. Asking about colors or sounds looks like stalling. Asking nothing looks like a memorized 3x3 answer.

Here are the questions that matter:

• Is the board always 3x3? We’ll support any size, n by n, where n in a row wins. With a 3x3 board only, checking the whole board for a winner is fine. On a big board it isn’t. So we write the size as a setting from the start. It costs nothing.
• Is it played on one screen, or online? Online, with two devices and one game on a server. If it were only on one screen, the last part of this page (two requests at once) would go away.
• Do we need undo? Yes, any number of times, even after a winning move.
• Can a computer play? Yes. A bot can play either side, and we want to be able to swap in a smarter bot later.

These answers give us one promise that matters more than the others: each turn results in exactly one move, even when two requests for it arrive at once. Three smaller promises come with it. A win is found in the same short time on any board size. Whose turn it is can never be wrong, even after an undo. And a new win rule, or a new kind of bot, doesn’t mean editing Game.

We leave out matchmaking, accounts and ratings, saving games, and the screen itself. The screen only reads the board and sends moves.

Go deeperFour more questions, and what each changes1 min

Question	We assume	If the answer were different
Is the win rule always n in a row?	For now; Gomoku (5 in a row on 15x15) later	A fixed rule could live inside Game; we put it behind an interface
Who moves first?	The first player passed in, usually X	A coin toss is a choice made when the game is created, not in play
More than two players?	No	Turn becomes moves % players.length; the counters need one per mark
Time limits per move?	No	A clock and a timeout that forfeits; the same injected clock as any game

Build it

We’ll build the design in four stages. Each stage adds only the classes that a new requirement needs. In each diagram, the new parts are outlined, and the colors show what each class does (the key is under every diagram).

Stage 1: A board that knows who won

Interviewerminute 5

Let’s start with two people on one screen. What are your classes?

What they are testing

Whether you get a working game in two or three minutes and keep the grid apart from the game. A single TicTacToe class with a char[3][3] and everything else inside it is the answer they’ve seen a hundred times.

Start with the smallest thing that works. We need three things: the marks (X and O), the board that holds them, and the game that owns the board and knows whose turn it is.

The board only knows about cells and lines. It doesn’t know whose turn it is. That keeps it simple, and a different game could reuse the same grid.

Stage 1: the smallest model that plays a game

Scroll or pinch to zoom, drag to pan

• Color key
• Facade
• Entity
• Value object
• Enum
• Interface
• Implementation
• New in this step

JBoard.javaPyboard.pyC#Board.csGoboard.goTSboard.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

// The two marks a cell can hold. A closed set of names, so an enum.
enum Mark { X, O }

// Board owns the grid and nothing else. It doesn't know whose turn it is,
// so a different game on the same grid (Gomoku, Connect Four) can reuse it.
class Board {
    final int size;
    private final Mark[][] cells;  // null means the cell is empty

    Board(int size) {
        this.size = size;
        this.cells = new Mark[size][size];
    }

    Mark at(int row, int col) { return cells[row][col]; }

    void place(int row, int col, Mark m) { cells[row][col] = m; }

    // flaw 2: rescans every row, column and diagonal after every move. Fine for 3x3,
    // O(n^2) per move on an n x n board. Stage 3 replaces it with O(1) counters.
    boolean hasLine(Mark m) {
        boolean diag = true, anti = true;
        for (int i = 0; i < size; i++) {
            boolean row = true, col = true;
            for (int j = 0; j < size; j++) {
                row &= cells[i][j] == m;
                col &= cells[j][i] == m;
            }
            if (row || col) return true;
            diag &= cells[i][i] == m;
            anti &= cells[i][size - 1 - i] == m;
        }
        return diag || anti;
    }
}

// Game is the one class callers talk to. It owns the board and the turn.
class Game {
    private final Board board = new Board(3);
    private Mark turn = Mark.X;  // X always opens
    private Mark winner;         // null while nobody has won

    void play(int row, int col) {
        // flaw 1: no checks. A taken cell, a cell off the board, a move after
        // the game is over: all accepted. Stage 2 adds the rules.
        board.place(row, col, turn);
        if (board.hasLine(turn)) winner = turn;
        turn = (turn == Mark.X) ? Mark.O : Mark.X;
    }

    Mark winner() { return winner; }
}

This version has two problems, and we leave them in on purpose. First, play accepts anything: a cell that’s already taken, a cell off the board, or a move after someone has won. Second, hasLine checks every row, column and diagonal after every move. On an n by n board, that’s about n² cells each time. Stage 2 fixes the first problem, and stage 3 fixes the second.

Stage 2: Turns, rules and results

Interviewerminute 9

What stops a player moving twice in a row, or playing on a taken cell?

What they are testing

Whether every rule is checked in one place, in a fixed order, and whether an illegal move is a normal outcome rather than a crash. A turn field updated separately from the move count is the bug they’re waiting to ask about when you get to undo.

Now we add the rules. All the checks go at the top of play, always in the same order. So the same bad move always gets the same answer.

A few small types come with this. A player is a name and a mark. The game gets a status: in progress, won, or a draw. And each kind of refused move gets a name, like “not your turn” or “cell taken”.

The most important change is how we track the turn. We don’t keep a turn field anymore. Instead, the turn comes from how many moves have been played: moves % 2. Zero, two, four moves means it’s X’s turn. One, three, five means it’s O’s. There’s only one number to keep right, so the turn can’t drift.

Stage 2: players, status and move results

Scroll or pinch to zoom, drag to pan

• Color key
• Facade
• Entity
• Value object
• Enum
• Interface
• Implementation
• New in this step

JGame.javaPygame.pyC#Game.csGogame.goTSgame.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

// A player is a value: a name and the mark they play. Two equal records are the same
// player, which is exactly what the turn check compares.
record Player(String name, Mark mark) {}

// Where the game stands. Callers read it after a move instead of working it out.
enum GameStatus { IN_PROGRESS, WON, DRAW }

// Every way a move can be refused, plus OK. In a game people play, a bad move is
// expected input, so it is a result the UI must show, not an exception.
enum MoveResult { OK, GAME_OVER, NOT_YOUR_TURN, OUT_OF_BOUNDS, CELL_TAKEN }

class Game {
    private final Board board;
    private final Player[] players;  // index 0 moves first
    private int moves;               // moves so far; also the only record of whose turn it is
    private GameStatus status = GameStatus.IN_PROGRESS;
    private Player winner;           // set only when status is WON

    Game(int size, Player first, Player second) {
        // Reject a broken setup here, so play() never has to think about it.
        if (first.mark() == second.mark()) throw new IllegalArgumentException("players need different marks");
        this.board = new Board(size);
        this.players = new Player[] { first, second };
    }

    // The turn is derived from the move count, so there is no second field to drift out of step.
    Player current() { return players[moves % 2]; }

    GameStatus status() { return status; }

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

    MoveResult play(Player p, int row, int col) {
        // Checks run in a fixed order, so the same bad move always gets the same answer.
        if (status != GameStatus.IN_PROGRESS) return MoveResult.GAME_OVER;
        if (!p.equals(current())) return MoveResult.NOT_YOUR_TURN;
        if (row < 0 || col < 0 || row >= board.size || col >= board.size) return MoveResult.OUT_OF_BOUNDS;
        if (board.at(row, col) != null) return MoveResult.CELL_TAKEN;

        board.place(row, col, p.mark());
        moves++;
        // Win before draw: the last free cell can complete a line.
        if (board.hasLine(p.mark())) {
            status = GameStatus.WON;
            winner = p;
        } else if (moves == board.size * board.size) {
            status = GameStatus.DRAW;
        }
        return MoveResult.OK;
    }
}

Notice that we check for a win before we check for a draw. The last free cell can also complete a line. If we checked the draw first, a game won on the ninth move would be reported as a draw.

Why return a result like “cell taken” instead of throwing an exception? In a game, a bad move is normal: a mis-tap, or a screen that’s a second out of date. Real bugs, like a game with two X players, still throw an exception when the game is created.

Stage 3: A win check that doesn’t scan

Interviewerminute 13

Your win check scans the whole board. Make it work for a 1,000 by 1,000 board.

What they are testing

Whether you see that a move can only complete the lines through its own cell, and get from there to counters. Checking only that move’s row, column and diagonals is a good answer. Counters that give the answer in one step are the strong one.

Checking the whole board after every move is wasteful. Think about what one move can change. A mark at a given cell can only complete four lines: its row, its column, and the two diagonals (if the cell is on them). No other line changed.

So we keep a counter for each row, each column and each of the two diagonals. When X plays, we add 1 to the counters of the lines through that cell. When O plays, we subtract 1. A row’s counter can only reach +n if all n cells in that row are X. It can only reach −n if all of them are O. So to check for a win, we read four numbers. The board size doesn’t matter.

There’s one condition for this to be correct: each cell must add to each counter only once. Stage 2 already guarantees that, because a taken cell can never be played again.

We also move this logic out of Game and behind an interface, WinRule. That way, a different rule (like Gomoku’s five in a row) can be swapped in later without touching Game. This is the Strategy pattern.

Stage 3: the win rule behind an interface

Scroll or pinch to zoom, drag to pan

• Color key
• Facade
• Entity
• Value object
• Enum
• Interface
• Implementation
• New in this step

JGame.javaPygame.pyC#Game.csGogame.goTSgame.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

// The rule that decides a win. An interface, because "n in a row on an n x n board" is one
// rule among several (five in a row on 15 x 15 is Gomoku), and Game shouldn't care which.
interface WinRule {
    /** Records an accepted move and says whether it completed a win. */
    boolean record(int row, int col, Mark m);
}

// n in a row on an n x n board, in O(1) per move. One counter per row, per column and per
// diagonal: X adds 1, O subtracts 1. A counter reaches +n or -n only when all n cells of its
// line hold the same mark. That relies on the game never letting a taken cell be played again.
class LineCounterRule implements WinRule {
    private final int n;
    private final int[] rows, cols;
    private int diag, anti;

    LineCounterRule(int n) {
        this.n = n;
        this.rows = new int[n];
        this.cols = new int[n];
    }

    public boolean record(int row, int col, Mark m) {
        int d = (m == Mark.X) ? 1 : -1;
        rows[row] += d;
        cols[col] += d;
        if (row == col) diag += d;          // on the main diagonal
        if (row + col == n - 1) anti += d;  // on the anti-diagonal (the centre is on both)
        // Only lines through this cell changed. The diagonals can't already be at +-n,
        // or the game would have ended, so checking them unconditionally is safe.
        return Math.abs(rows[row]) == n || Math.abs(cols[col]) == n
            || Math.abs(diag) == n || Math.abs(anti) == n;
    }
}

class Game {
    private final Board board;
    private final WinRule rule;      // injected, so Gomoku is a different rule, not a different Game
    private final Player[] players;
    private int moves;
    private GameStatus status = GameStatus.IN_PROGRESS;
    private Player winner;

    Game(int size, Player first, Player second) {
        this(size, new LineCounterRule(size), first, second);
    }

    Game(int size, WinRule rule, Player first, Player second) {
        if (first.mark() == second.mark()) throw new IllegalArgumentException("players need different marks");
        this.board = new Board(size);
        this.rule = rule;
        this.players = new Player[] { first, second };
    }

    Player current() { return players[moves % 2]; }

    GameStatus status() { return status; }

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

    MoveResult play(Player p, int row, int col) {
        if (status != GameStatus.IN_PROGRESS) return MoveResult.GAME_OVER;
        if (!p.equals(current())) return MoveResult.NOT_YOUR_TURN;
        if (row < 0 || col < 0 || row >= board.size || col >= board.size) return MoveResult.OUT_OF_BOUNDS;
        if (board.at(row, col) != null) return MoveResult.CELL_TAKEN;

        board.place(row, col, p.mark());
        moves++;
        if (rule.record(row, col, p.mark())) {  // O(1) instead of rescanning the board
            status = GameStatus.WON;
            winner = p;
        } else if (moves == board.size * board.size) {
            status = GameStatus.DRAW;
        }
        return MoveResult.OK;
    }
}

The memory cost is small: 2n + 2 numbers. A 1,000 by 1,000 board needs about 2,000 counters, next to the million cells it already stores. The board goes back to just holding cells.

There is one risk. The counters are a second copy of what’s on the board. If anything changes a cell without telling the counters, they’ll be wrong. Undo, in the next stage, is exactly that kind of change, so we’ll have to be careful.

Common mistake

Counting marks instead of adding and subtracting

Some answers keep one count per row and check whether it equals n. That’s wrong: two X and one O in a row also add up to three. Others keep separate counts for X and O, which works but doubles the memory. Adding for X and subtracting for O is both smaller and correct.

Stage 4: Undo and bots

Interviewerminute 18

Players want undo. And we want a computer opponent. Where do those go?

What they are testing

Whether undo reverses every piece of state a move changed (the cell, the counters, the status, the turn), and whether the bot lives outside the game. A Player.makeMove() with a Scanner inside, or a game loop that asks bots for moves, ties the model to one screen.

Undo needs a record of what happened. So every accepted move goes onto a history list. To undo, we take the last move off the list and reverse everything play changed: we clear the cell, take the move back out of the counters, and reset the status.

What about the turn? It now comes from the history: history.size() % 2. So removing a move from the list hands the turn back automatically. This is the payoff of not storing the turn in stage 2.

The WinRule interface gets an undo method too. With counters, undo is easy: subtract what record added.

JGame.javaPygame.pyC#Game.csGogame.goTSgame.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

// One accepted move. Kept in a history so it can be undone, replayed, or sent to the other player.
record Move(Player player, int row, int col) {}

// Decides when a move wins. Whoever records a move must be able to take it back.
interface WinRule {
    boolean record(int row, int col, Mark m);
    void undo(int row, int col, Mark m);
}

// Wins n in a row on an n x n board, in O(1) per move: one counter per row, column and
// diagonal, where X adds 1 and O subtracts 1. The counters also make undo trivial: subtract
// what record added. A rule that rescanned the board would get undo for free; one that cached
// "lines nearly won" would have to rebuild them.
class LineCounterRule implements WinRule {
    private final int n;
    private final int[] rows, cols;
    private int diag, anti;

    LineCounterRule(int n) {
        this.n = n;
        this.rows = new int[n];
        this.cols = new int[n];
    }

    // Adds this move to its row, column and diagonals, and says whether any of them is now full
    // of one mark.
    public boolean record(int row, int col, Mark m) {
        add(row, col, (m == Mark.X) ? 1 : -1);
        return Math.abs(rows[row]) == n || Math.abs(cols[col]) == n
            || Math.abs(diag) == n || Math.abs(anti) == n;
    }

    // Subtracts exactly what record added.
    public void undo(int row, int col, Mark m) { add(row, col, (m == Mark.X) ? -1 : 1); }

    // One place that knows which counters a cell touches, shared by record and undo.
    private void add(int row, int col, int d) {
        rows[row] += d;
        cols[col] += d;
        if (row == col) diag += d;
        if (row + col == n - 1) anti += d;
    }
}

class Game {
    private final Board board;
    private final WinRule rule;
    private final Player[] players;
    private final Deque<Move> history = new ArrayDeque<>();  // newest last; its size replaces the move count
    private GameStatus status = GameStatus.IN_PROGRESS;
    private Player winner;

    Game(int size, WinRule rule, Player first, Player second) {
        if (first.mark() == second.mark()) throw new IllegalArgumentException("players need different marks");
        this.board = new Board(size);
        this.rule = rule;
        this.players = new Player[] { first, second };
    }

    Player current() { return players[history.size() % 2]; }

    GameStatus status() { return status; }

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

    // Read-only, so a bot or a UI can look at the board but only play() can change it.
    BoardView board() { return board; }

    MoveResult play(Player p, int row, int col) {
        int n = board.size();
        if (status != GameStatus.IN_PROGRESS) return MoveResult.GAME_OVER;
        if (!p.equals(current())) return MoveResult.NOT_YOUR_TURN;
        if (row < 0 || col < 0 || row >= n || col >= n) return MoveResult.OUT_OF_BOUNDS;
        if (board.at(row, col) != null) return MoveResult.CELL_TAKEN;

        board.place(row, col, p.mark());
        history.addLast(new Move(p, row, col));
        if (rule.record(row, col, p.mark())) {
            status = GameStatus.WON;
            winner = p;
        } else if (history.size() == n * n) {
            status = GameStatus.DRAW;
        }
        return MoveResult.OK;
    }

    // Takes back the last move, a winning one included. Everything play() changed is
    // reversed here, so the game is exactly as it was one move earlier.
    boolean undo() {
        Move last = history.pollLast();
        if (last == null) return false;  // nothing to undo
        rule.undo(last.row(), last.col(), last.player().mark());
        board.clear(last.row(), last.col());
        status = GameStatus.IN_PROGRESS;  // a game one move earlier was still open
        winner = null;
        return true;
    }
}

Bots live outside the game. A bot is anything that looks at the board, picks a cell, and calls game.play, just like a person’s app would. To make sure a bot can only look, it gets a read-only view of the board, called BoardView. The game never knows which players are bots. So a random bot, a “win or block” bot, and an unbeatable bot are each just one class behind the BotStrategy interface.

Stage 4: history, undo, and bots as callers

Scroll or pinch to zoom, drag to pan

• Color key
• Facade
• Entity
• Value object
• Enum
• Interface
• Implementation
• New in this step

JBoard.javaPyboard.pyC#Board.csGorandom_bot.goTSboard.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

// Read-only view of the board. Bots and UIs get this, so nothing outside Game can place a mark.
interface BoardView {
    int size();
    Mark at(int row, int col);
}

// The grid. Only the game changes it: place on a move, clear on undo. Bots and UIs see it
// through the read-only BoardView.
class Board implements BoardView {
    final int size;
    private final Mark[][] cells;

    Board(int size) {
        this.size = size;
        this.cells = new Mark[size][size];
    }

    public int size() { return size; }

    public Mark at(int row, int col) { return cells[row][col]; }

    void place(int row, int col, Mark m) { cells[row][col] = m; }

    void clear(int row, int col) { cells[row][col] = null; }  // only undo calls this
}

// A cell a bot wants to play. Game still validates it like any other move.
record Cell(int row, int col) {}

// How a bot picks a move. A strategy, because random, win-or-block and minimax are
// interchangeable, and Game doesn't need to know that any of them exist.
interface BotStrategy {
    Cell choose(BoardView board, Mark me);
}

// Plays any empty cell. The Random is injected, so a test can fix the seed and
// get the same game every run.
class RandomBot implements BotStrategy {
    private final Random random;

    RandomBot(Random random) { this.random = random; }

    public Cell choose(BoardView board, Mark me) {
        List<Cell> empty = new ArrayList<>();
        for (int r = 0; r < board.size(); r++)
            for (int c = 0; c < board.size(); c++)
                if (board.at(r, c) == null) empty.add(new Cell(r, c));
        return empty.get(random.nextInt(empty.size()));
    }
}

A bot’s turn is two lines in whatever runs the game: ask the bot for a cell, then call game.play with it. The game checks the bot’s move like anyone else’s, so a buggy bot can’t break the game.

Go deeperA bot's turn, step by step1 min

Sequence: a bot takes its turn

Scroll or pinch to zoom, drag to pan

• Color key
• Interface
• Facade

There is one small cost. Something outside the game has to decide when the bot moves (after the person’s move comes back OK). In a game on one screen, that’s a small loop. It just isn’t the game’s job anymore.

Common mistake

An undo that forgets the counters

Clearing the cell and lowering the move count is not enough. If the counters still say X has three in the top row, the next X move anywhere looks like a win. Undo must reverse everything play changed, in one method, and a test should prove it.

Go deeperIsn't undo the Command pattern?1 min

Interviewer asksIsn't undo the Command pattern? Why no Command classes?

It’s the same idea: each move is a small object that knows enough to be reversed. A full Command pattern (a PlaceMarkCommand class with execute and undo) pays off when there are many kinds of action. Here there’s only one, placing a mark. So a Move value plus one undo method says the same thing with less code. If the game grew other actions, like resigning, I’d add the interface then.

This is enough for a mid-level answer. Moves are checked in one place, the win check only looks at the lines through the last move, and undo works from a history list. The rest of the page is what makes it a senior answer.

The full design

Here is everything together. Each class is here because a requirement needed it.

Tic-tac-toe: full class diagram

Scroll or pinch to zoom, drag to pan

• Color key
• Facade
• Entity
• Value object
• Enum
• Interface
• Implementation

</>tic-tac-toe· read only

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

Explorer

• JAllInOne.java
• src
• JBoard.java
• JBoardView.java
• JGame.java
• JGameStatus.java
• JLineCounterRule.java
• JMark.java
• JMove.java
• JMoveResult.java
• JPlayer.java
• JWinRule.java

JAllInOne.java

AllInOne.javasrc/Board.javasrc/BoardView.javasrc/Game.javasrc/GameStatus.javasrc/LineCounterRule.javasrc/Mark.javasrc/Move.javasrc/MoveResult.javasrc/Player.javasrc/WinRule.java

AllInOne.java

// The complete design, built from every stage on this page.

import java.util.*;

// The two marks a cell can hold. A closed set of names, so an enum.
enum Mark { X, O }

// The grid. Only the game changes it: place on a move, clear on undo. Bots and UIs see it
// through the read-only BoardView.
class Board implements BoardView {
    final int size;
    private final Mark[][] cells;

    Board(int size) {
        this.size = size;
        this.cells = new Mark[size][size];
    }

    public int size() { return size; }

    public Mark at(int row, int col) { return cells[row][col]; }

    void place(int row, int col, Mark m) { cells[row][col] = m; }

    void clear(int row, int col) { cells[row][col] = null; }  // only undo calls this
}

// One game, shared by both players' connections. One lock guards all of it, so a move is
// checked and placed as one step, and games never wait on each other.
class Game {
    private final Object lock = new Object();  // one lock per game; games share nothing
    private final Board board;
    private final WinRule rule;
    private final Player[] players;
    private final Deque<Move> history = new ArrayDeque<>();
    private GameStatus status = GameStatus.IN_PROGRESS;
    private Player winner;

    Game(int size, WinRule rule, Player first, Player second) {
        if (first.mark() == second.mark()) throw new IllegalArgumentException("players need different marks");
        this.board = new Board(size);
        this.rule = rule;
        this.players = new Player[] { first, second };
    }

    // moveNumber is the move the client thinks it is making: 0 for the first, 1 for the
    // second. A double tap or a network retry sends the same number twice, and the second
    // copy is turned away as STALE instead of being played as the opponent's move.
    MoveResult play(Player p, int moveNumber, int row, int col) {
        // The lock makes "check, then place" one step. Without it two requests can both
        // pass the checks before either one places its mark.
        synchronized (lock) {
            int n = board.size();
            if (moveNumber != history.size()) return MoveResult.STALE;
            if (status != GameStatus.IN_PROGRESS) return MoveResult.GAME_OVER;
            if (!p.equals(players[history.size() % 2])) return MoveResult.NOT_YOUR_TURN;
            if (row < 0 || col < 0 || row >= n || col >= n) return MoveResult.OUT_OF_BOUNDS;
            if (board.at(row, col) != null) return MoveResult.CELL_TAKEN;

            board.place(row, col, p.mark());
            history.addLast(new Move(p, row, col));
            if (rule.record(row, col, p.mark())) {
                status = GameStatus.WON;
                winner = p;
            } else if (history.size() == n * n) {
                status = GameStatus.DRAW;
            }
            return MoveResult.OK;
        }
    }

    // Undo takes the same lock, so it can never interleave with a half-finished move.
    boolean undo() {
        synchronized (lock) {
            Move last = history.pollLast();
            if (last == null) return false;
            rule.undo(last.row(), last.col(), last.player().mark());
            board.clear(last.row(), last.col());
            status = GameStatus.IN_PROGRESS;
            winner = null;
            return true;
        }
    }

    // Turns alternate, so whose turn it is follows from how many moves were made.
    Player current() { synchronized (lock) { return players[history.size() % 2]; } }

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

    // Readers take the lock too: it is what guarantees they see a move's writes all together.
    GameStatus status() { synchronized (lock) { return status; } }

    // The number the next move must carry. A client reads it to know where the game is.
    int moveNumber() { synchronized (lock) { return history.size(); } }
}

// A player is a value: a name and the mark they play. Two equal records are the same
// player, which is exactly what the turn check compares.
record Player(String name, Mark mark) {}

// Where the game stands. Callers read it after a move instead of working it out.
enum GameStatus { IN_PROGRESS, WON, DRAW }

// What a move gets back. STALE means the move was sent for a turn that has already been played.
enum MoveResult { OK, GAME_OVER, NOT_YOUR_TURN, OUT_OF_BOUNDS, CELL_TAKEN, STALE }

// Decides when a move wins. Whoever records a move must be able to take it back.
interface WinRule {
    boolean record(int row, int col, Mark m);
    void undo(int row, int col, Mark m);
}

// Wins n in a row on an n x n board, in O(1) per move: one counter per row, column and
// diagonal, where X adds 1 and O subtracts 1. The counters also make undo trivial: subtract
// what record added. A rule that rescanned the board would get undo for free; one that cached
// "lines nearly won" would have to rebuild them.
class LineCounterRule implements WinRule {
    private final int n;
    private final int[] rows, cols;
    private int diag, anti;

    LineCounterRule(int n) {
        this.n = n;
        this.rows = new int[n];
        this.cols = new int[n];
    }

    // Adds this move to its row, column and diagonals, and says whether any of them is now full
    // of one mark.
    public boolean record(int row, int col, Mark m) {
        add(row, col, (m == Mark.X) ? 1 : -1);
        return Math.abs(rows[row]) == n || Math.abs(cols[col]) == n
            || Math.abs(diag) == n || Math.abs(anti) == n;
    }

    // Subtracts exactly what record added.
    public void undo(int row, int col, Mark m) { add(row, col, (m == Mark.X) ? -1 : 1); }

    // One place that knows which counters a cell touches, shared by record and undo.
    private void add(int row, int col, int d) {
        rows[row] += d;
        cols[col] += d;
        if (row == col) diag += d;
        if (row + col == n - 1) anti += d;
    }
}

// Read-only view of the board. Bots and UIs get this, so nothing outside Game can place a mark.
interface BoardView {
    int size();
    Mark at(int row, int col);
}

// One accepted move. Kept in a history so it can be undone, replayed, or sent to the other player.
record Move(Player player, int row, int col) {}

Read onlyJava 21Every file builds in CI11 files155 lines

Explorer

• Pyall_in_one.py
• tic_tac_toe
• Pyboard.py
• Pyboard_view.py
• Pygame.py
• Pygame_status.py
• Pyline_counter_rule.py
• Pymark.py
• Pymove.py
• Pymove_result.py
• Pyplayer.py
• Pywin_rule.py

Pyall_in_one.py

all_in_one.pytic_tac_toe/board.pytic_tac_toe/board_view.pytic_tac_toe/game.pytic_tac_toe/game_status.pytic_tac_toe/line_counter_rule.pytic_tac_toe/mark.pytic_tac_toe/move.pytic_tac_toe/move_result.pytic_tac_toe/player.pytic_tac_toe/win_rule.py

all_in_one.py

Read onlyPython 3.12Every file builds in CI11 files172 lines

Explorer

• C#AllInOne.cs
• src
• C#Board.cs
• C#Game.cs
• C#GameStatus.cs
• C#IBoardView.cs
• C#IWinRule.cs
• C#LineCounterRule.cs
• C#Mark.cs
• C#Move.cs
• C#MoveResult.cs
• C#Player.cs

C#AllInOne.cs

AllInOne.cssrc/Board.cssrc/Game.cssrc/GameStatus.cssrc/IBoardView.cssrc/IWinRule.cssrc/LineCounterRule.cssrc/Mark.cssrc/Move.cssrc/MoveResult.cssrc/Player.cs

AllInOne.cs

Read onlyC# · .NET 10Every file builds in CI11 files144 lines

Explorer

• Goall_in_one.go
• Goboard.go
• Gogame.go
• Gogame_status.go
• Goline_counter_rule.go
• Gomark.go
• Gomove.go
• Goplayer.go
• Gowin_rule.go

Goall_in_one.go

all_in_one.goboard.gogame.gogame_status.goline_counter_rule.gomark.gomove.goplayer.gowin_rule.go

all_in_one.go

Read onlyGo 1.24Every file builds in CI9 files224 lines

Explorer

• TSall-in-one.ts
• src
• TSboard-view.ts
• TSboard.ts
• TSgame-status.ts
• TSgame.ts
• TSline-counter-rule.ts
• TSmark.ts
• TSmove-result.ts
• TSmove.ts
• TSplayer.ts
• TSwin-rule.ts

TSall-in-one.ts

all-in-one.tssrc/board-view.tssrc/board.tssrc/game-status.tssrc/game.tssrc/line-counter-rule.tssrc/mark.tssrc/move-result.tssrc/move.tssrc/player.tssrc/win-rule.ts

all-in-one.ts

Read onlyTypeScript, strictEvery file builds in CI11 files162 lines

Three ideas hold it together:

• One source of truth for progress. The history list decides whose turn it is and how many moves were played. Nothing else stores either one, so undo can’t leave them out of step.
• Only Game changes the board. The methods that place and clear marks can’t be called from outside the package. Everyone else gets the read-only BoardView. That’s why a buggy bot or screen can’t do any harm. To its callers, Game is a simple front door (a facade) with play, undo and a view of the board.
• The two rules that vary sit behind interfaces (the amber boxes): how a win is decided, and how a bot picks a move. Gomoku is a new WinRule. A smarter bot is a new BotStrategy. That’s the Strategy pattern twice.

Stress it

The design works for two people on one screen. Now we put it online, where two requests can arrive at the same moment.

One turn, two requests

Interviewerminute 25

It’s online now. Player X double-taps a cell, and both requests reach the server. What happens?

What they are testing

Whether you see that this is two problems: a race between threads, and a repeated request that isn’t a race at all. A lock fixes the first but not the second. Saying “add synchronized” and stopping there is the mid-level answer they’re trying to get past.

There are two different ways the same turn can be played twice.

The first is a race. Two requests run at the same time, on two server threads. Both check “is it X’s turn?” before either one places a mark. Both checks pass, and both moves land.

The second is a late copy. A request arrives after its turn is already over. For example, the phone retried after a lost response, or a tap was still on its way when the move was undone. Our normal checks catch some late copies by luck, but with a confusing answer (“cell taken” for your own move). And they miss one case completely. After an undo, it’s X’s turn again and the cell is free. So a late copy of the undone move passes every check and quietly plays it again.

First, fix the race. Put one lock around each game. play and undo both hold it while they run. Now a move’s checks and its changes happen as one step, and no other request can get in between. Readers take the lock too, so they always see a whole move or none of it.

A lock doesn’t fix the late copy, though. The late copy doesn’t overlap with anything. It simply arrives later. So we add a move number. The app sends the number of the move it’s making: “this is move 4”. If the game has already played move 4, the request is refused as stale. Now each turn can only be played once, in whatever order the copies arrive.

Option	How	Fixes the race	Fixes the late copy
1. A lock per game	play and undo hold the game’s lock	Yes	No
2. One thread per game	All requests for a game go through its own queue	Yes	No
3. Expected move number	The client sends which move it is making; a mismatch is stale	No, alone	Yes
4. Lock plus move number (our choice)	Both	Yes	Yes

Sequence: a double tap, with the lock and the move number

Scroll or pinch to zoom, drag to pan

• Color key
• Facade

JGame.javaPygame.pyC#Game.csGogame.goTSgame.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

// What a move gets back. STALE means the move was sent for a turn that has already been played.
enum MoveResult { OK, GAME_OVER, NOT_YOUR_TURN, OUT_OF_BOUNDS, CELL_TAKEN, STALE }

// One game, shared by both players' connections. One lock guards all of it, so a move is
// checked and placed as one step, and games never wait on each other.
class Game {
    private final Object lock = new Object();  // one lock per game; games share nothing
    private final Board board;
    private final WinRule rule;
    private final Player[] players;
    private final Deque<Move> history = new ArrayDeque<>();
    private GameStatus status = GameStatus.IN_PROGRESS;
    private Player winner;

    Game(int size, WinRule rule, Player first, Player second) {
        if (first.mark() == second.mark()) throw new IllegalArgumentException("players need different marks");
        this.board = new Board(size);
        this.rule = rule;
        this.players = new Player[] { first, second };
    }

    // moveNumber is the move the client thinks it is making: 0 for the first, 1 for the
    // second. A double tap or a network retry sends the same number twice, and the second
    // copy is turned away as STALE instead of being played as the opponent's move.
    MoveResult play(Player p, int moveNumber, int row, int col) {
        // The lock makes "check, then place" one step. Without it two requests can both
        // pass the checks before either one places its mark.
        synchronized (lock) {
            int n = board.size();
            if (moveNumber != history.size()) return MoveResult.STALE;
            if (status != GameStatus.IN_PROGRESS) return MoveResult.GAME_OVER;
            if (!p.equals(players[history.size() % 2])) return MoveResult.NOT_YOUR_TURN;
            if (row < 0 || col < 0 || row >= n || col >= n) return MoveResult.OUT_OF_BOUNDS;
            if (board.at(row, col) != null) return MoveResult.CELL_TAKEN;

            board.place(row, col, p.mark());
            history.addLast(new Move(p, row, col));
            if (rule.record(row, col, p.mark())) {
                status = GameStatus.WON;
                winner = p;
            } else if (history.size() == n * n) {
                status = GameStatus.DRAW;
            }
            return MoveResult.OK;
        }
    }

    // Undo takes the same lock, so it can never interleave with a half-finished move.
    boolean undo() {
        synchronized (lock) {
            Move last = history.pollLast();
            if (last == null) return false;
            rule.undo(last.row(), last.col(), last.player().mark());
            board.clear(last.row(), last.col());
            status = GameStatus.IN_PROGRESS;
            winner = null;
            return true;
        }
    }

    // Turns alternate, so whose turn it is follows from how many moves were made.
    Player current() { synchronized (lock) { return players[history.size() % 2]; } }

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

    // Readers take the lock too: it is what guarantees they see a move's writes all together.
    GameStatus status() { synchronized (lock) { return status; } }

    // The number the next move must carry. A client reads it to know where the game is.
    int moveNumber() { synchronized (lock) { return history.size(); } }
}

Why is this correct? Every read and write of a game’s state happens under its lock, so a move’s checks and its changes can’t be split by another request. And each request names the turn it belongs to. Once that turn is played, every later copy of it is refused.

What does it cost? Very little. At most two players touch a game, and a move takes microseconds, so nobody waits long. Games never share a lock, so a million games work like one. The one limit is that a lock only works inside one program. If two servers held copies of the same game, the move number check would have to move into the database.

Common mistake

Making each cell atomic

Atomic cells stop two marks landing in one cell. But they don’t stop two moves in one turn: X could still claim two different empty cells. The rule that matters, “one move per turn”, covers the turn check, the cell, the counters and the history together. So it needs one lock around all of them.

Interviewer asksHow does the app know which move number to send?

Every response includes the game’s current move number, and so does the board the app draws. The app sends the number it last saw. If it’s behind, the server answers “stale” and the app reloads the board, which is what the player needed to see anyway.

Go deeperHow each language does the lock, and the database version2 min

Java uses a private lock object instead of synchronized methods, so no outside code can lock on the game and stall it. C# 13 has a dedicated Lock type. Go uses a sync.Mutex with defer, so the lock is released on every return path. Python uses a threading.Lock in a with block. TypeScript in one Node process needs no lock at all, because nothing interrupts a play call while it runs. It still needs the move number, because retries can happen anywhere.

If the game is stored in a database, the move number becomes an update with a condition:

UPDATE games SET board = ?, move_count = move_count + 1
WHERE id = ? AND move_count = ?;
-- 1 row changed: the move was played. 0 rows changed: the request was stale.

The database checks the condition and makes the change as one step, so two servers can’t both play the same move.

Go deeperWhy not a read-write lock?1 min

Screens read the board far more often than players move, so a read-write lock sounds like a good fit. But reading a board takes nanoseconds, and there are only two players. A read-write lock costs more per call than a plain lock, and it only helps when many readers compete, which a two-player game never has. If spectators were watching, we’d publish a frozen copy of the board after each move and let them read that without any lock.

How you’d prove it works

Name each test after the promise it protects. Then a failing test tells you which promise broke. These matter most:

• A win is found on every kind of line (row, column, both diagonals), on a board bigger than 3x3, so nothing is hard-coded.
• A full board with no line is a draw, and a line on the last cell is a win.
• Every illegal move gets its own result and changes nothing.
• Undoing a winning move reopens the game and reverses the counters.
• Undo hands the turn back to the player whose move was undone.
• Two requests for the same turn result in exactly one move.

The undo test is the one that catches real bugs. It plays a win, undoes it, then plays a move that would only count as a win if the counters were left behind. The race test sends nine requests for move 0 at the same moment, each for a different cell, and checks that exactly one landed. Remove the lock and it fails most runs. A race test can pass by luck, so pair it with the reasoning above.

Go deeperThe tests in five languages2 min

JMain.javaPyexample.pyC#Program.csGomain.goTSexample.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

static final Player X = new Player("Ana", Mark.X), O = new Player("Bo", Mark.O);

// Plays (row, col) pairs alternately for X and O, numbering moves as a client would.
static Game play(int size, int... cells) {
    Game g = new Game(size, new LineCounterRule(size), X, O);
    for (int i = 0; i < cells.length; i += 2) {
        assertEquals(MoveResult.OK, g.play(i % 4 == 0 ? X : O, i / 2, cells[i], cells[i + 1]));
    }
    return g;
}

@Test
void antiDiagonalWinsOnAFourByFourBoard() {
    // X takes (0,3) (1,2) (2,1) (3,0); O plays elsewhere. The counters work for any n.
    Game g = play(4, 0, 3, 0, 0, 1, 2, 1, 0, 2, 1, 2, 0, 3, 0);
    assertEquals(GameStatus.WON, g.status());
}

@Test
void fullBoardWithNoLineIsADraw() {
    // X O X / X O O / O X X: nine moves, no line.
    Game g = play(3, 0, 0, 0, 1, 0, 2, 1, 1, 1, 0, 1, 2, 2, 1, 2, 0, 2, 2);
    assertEquals(GameStatus.DRAW, g.status());
}

@Test
void undoingAWinReopensTheGameAndTheCounters() {
    Game g = play(3, 0, 0, 1, 0, 0, 1, 1, 1, 0, 2);  // X wins the top row
    assertTrue(g.undo());
    assertEquals(GameStatus.IN_PROGRESS, g.status());
    // If undo forgot the counters, X's row would still read +3 and this move would "win".
    assertEquals(MoveResult.OK, g.play(X, 4, 2, 2));
    assertEquals(GameStatus.IN_PROGRESS, g.status());
}

@Test
void racingRequestsForOneTurnPlayExactlyOnce() throws Exception {
    // Nine requests all claim to be move 0, each for a different cell. One may win.
    Game g = new Game(3, new LineCounterRule(3), X, O);
    ExecutorService pool = Executors.newFixedThreadPool(9);
    CountDownLatch start = new CountDownLatch(1);  // the starting gun
    List<Future<MoveResult>> results = new ArrayList<>();
    for (int cell = 0; cell < 9; cell++) {
        int r = cell / 3, c = cell % 3;
        results.add(pool.submit(() -> { start.await(); return g.play(X, 0, r, c); }));
    }
    start.countDown();  // release every thread at once
    int ok = 0;
    for (var f : results) if (f.get() == MoveResult.OK) ok++;
    assertEquals(1, ok);                // exactly one move landed; the rest were STALE
    assertEquals(1, g.moveNumber());
}

Go deeperEvery edge case, and where it is handled2 min

Case	What happens	Where
Move off the board	OUT_OF_BOUNDS, nothing changes	Game.play checks
Move on a taken cell	CELL_TAKEN; this is also what keeps the counters honest	Game.play checks
Move after a win or draw	GAME_OVER	status check, first in line
Last cell completes a line	WON, not DRAW: the win is checked first	Game.play
Undo with no moves	Returns false	Game.undo
Undo a winning move	Status back to in progress, winner cleared, counters reversed	Game.undo, WinRule.undo
Double tap or network retry	The second copy is STALE	move number check
Two players send at once	One waits for the lock; the other gets NOT_YOUR_TURN or STALE	the game’s lock
Game created with two X players	Throws when the game is created: a bug, not input	Game constructor
Bot returns a taken cell	Refused like any move; whatever runs the bot asks again	Game.play
Screen reads while a move runs	Reads take the lock and see the move whole or not at all	readers lock too

Wrap up

The decisions, and what each one costs

Decision	We chose	We gave up
Board and game	Board holds cells; Game holds rules and turn	Nothing
Illegal moves	Named results (errors in Go), not exceptions	The caller can ignore a result
Whose turn	Worked out from the history’s length	Nothing; one fewer field to keep in step
Win check	Signed counters per line, one step per move	A second copy of state that undo must reverse
Win rule	Strategy (WinRule)	A little indirection
Undo	History list of Move values	Memory for the history (tiny)
Bots	Callers of play behind BotStrategy	Something outside must decide when bots move
Online play	Lock per game plus an expected move number	One program only, unless the database checks too

Go deeperGenuinely different designs, and when to pick them2 min

Bitboards. Each player’s marks are bits in one number (9 bits for 3x3), and the eight winning lines are eight masks. A win is (bits & mask) == mask. This is very fast, and it’s how game engines store positions, because an unbeatable bot checks millions of them. But it doesn’t work for big boards and it hides the model. So it’s a speed trick for a bot, not the interview design.

A game state that never changes. play returns a new GameState instead of changing the old one. Undo means keeping the previous state. Online play only needs one compare-and-set on “the current state”. Replays come for free. The cost is copying the board on every move: nothing at 3x3, a lot at 1,000 by 1,000.

Storing only the moves. Keep just the list of moves, and rebuild the board, counters and status from it whenever needed. This is the history list taken all the way, and it’s called event sourcing. It’s the natural design once games are saved and replayed.

How to spend 45 minutes

• 0 to 3. Board size, local or online, undo, bots.
• 3 to 5. The promises. Name “one move per turn, even online” as the hard one.
• 5 to 23. Stages 1 to 4. Code play, the counter rule and undo. Describe the bot in words.
• 23 to 25. Walk through the full diagram and name each pattern by the rule it protects.
• 25 to 33. Online play: the race and the late copy, then the lock and the move number.
• 33 to 45. One extension, usually Gomoku or a smarter bot, then your own questions.

If time is short, describe the bot in a sentence instead of coding it. Never skip the counters. They are what the question is really about.

Follow-up questions

Interviewerminute 35

Make it Gomoku: 15 by 15, five in a row wins.

What they are testing

Whether the change lands in one new class. If Game.play needs editing beyond what you pass in when creating the game, the win rule wasn’t really separated.

Most extensions fit into one place:

Extension	What changes	Touches Game?
Gomoku (k in a row, k < n)	A KInARowRule that walks four directions from the last move; its undo does nothing	No
Smarter bot	A MinimaxBot or WinOrBlockBot implementing BotStrategy	No
Replays	Go through the history and play each move into a fresh Game	No
Spectators	Publish a frozen copy of the board after each move to a list of listeners	One hook in play
Three players	Turn is moves % players.length; the rule keeps a set of counters per mark	Constructor
Saving games	Store the move list; loading a game means replaying it	No

For Gomoku, the counters stop working, because a row of 15 can hold five in a row anywhere along it. The new rule walks outward from the cell just played, in each of the four directions, and counts matching marks in a row. That’s about k steps per move, whatever the board size.

Go deeperBuilding an unbeatable bot, step by step4 min

The interviewer asks: “How would you build a bot that never loses?” The answer is a search called minimax, and our design makes it short to write.

Start with the idea. The bot wants the best result it can be sure of, even if the opponent plays perfectly. So for every move it could make, it asks: “If I play here, and then my opponent plays their best reply, and then I play my best reply, and so on to the end, how does the game end?” Then it picks the move whose ending is best for it.

To compare endings, give each finished game a score from the bot’s point of view: +1 for a win, 0 for a draw, and −1 for a loss. Now the search is a simple rule, applied over and over:

• On the bot’s turn, try every free cell and take the move with the highest score.
• On the opponent’s turn, try every free cell and assume they take the move with the lowest score, because that’s best for them.
• When the game is over, return the score.

That’s where the name comes from: the bot picks the maximum, and assumes the opponent picks the minimum.

How does it “try” a move? With the parts we already built. It calls play, searches further, then calls undo. The counters make each win check one step, and undo puts everything back exactly as it was. So the bot doesn’t build a new board for every position it looks at. It plays and undoes on one board. This is a good moment to point out that undo wasn’t only for players. It’s what makes the bot cheap.

How big is the search? On a 3x3 board, all possible games add up to fewer than 600,000 positions. A computer checks that in well under a second. A trick called alpha-beta pruning makes it much faster. While searching, the bot keeps track of the best score it’s already sure of. If a branch can’t possibly beat that, it stops searching that branch. On 3x3 this skips most of the positions.

On bigger boards, the search can’t reach the end of the game. A 15x15 Gomoku board has far too many possible games. So the bot searches only a few moves ahead, then scores the position with a rule of thumb, for example “how many open lines of four do I have, minus how many my opponent has”. This is how real game engines work. The engine is just another BotStrategy. Game doesn’t change at all.

Two details matter in an interview. First, prefer quicker wins: score a win as +10 minus the number of moves it took, so the bot doesn’t play slowly when it could win now. Second, the bot does all this playing and undoing on its own copy of the game, made once before it starts searching. Never search on the live game players are using. Otherwise a person’s request could arrive in the middle of the bot’s play and undo.

Go deeperTwo more follow-up questions1 min

Interviewer asksA player disconnects mid-game. What happens?

The game itself doesn’t care. It just waits for the next valid move. A timer outside the game decides what to do: after 60 seconds, the server calls a forfeit(player) method that gives the win to the other side. It runs under the same lock as play, so a late move can’t sneak in after the forfeit.

Interviewer asksHow would you run a million games at once?

Each game is small and independent, so the design already scales: one lock per game and nothing shared. A million 3x3 games take a few hundred megabytes. Across many servers, send every request for a game to the server that holds it (by hashing the game ID), or keep games in a database and use the move number in the update.

Further reading

• Strategy pattern, Command pattern
• Object modeling, Thread safety basics
• Design chess, the same structure with richer move rules
• Wikipedia: Minimax, the algorithm behind an unbeatable bot
• Wikipedia: m,n,k-game, the family tic-tac-toe and Gomoku belong to
• Martin Fowler: Event Sourcing, the history stack taken to its end