Design Tic Tac Toe | androidinterview.com

Design it for an N by N board with N players from the first line you write. Three by three and two players is then just the case where N is three, and you never have to go back and change anything. Interviewers ask this one because the small version is trivial and the general version is not, and Flipkart has asked for it in those words, a tic tac toe scalable to multiple users and an N by N grid.

The other half of the answer is where the win rule lives. The board holds squares. Something else decides what a win is. Keep those apart and every follow up is easy, put them together and every follow up is a rewrite.

What this really tests

Whether you can spot the general problem hiding inside a toy one, and whether you keep state and rules in separate classes. A weak answer is one class with a two dimensional array and a checkWinner method wired for three in a row. Everything the interviewer asks next breaks it.

What to clarify first

Ask these before you draw a single box. Most of them change the design.

Is the board fixed at three by three, or N by N. Assume N by N unless you are told otherwise. It costs nothing up front and it is expensive to retrofit.
How many players. Two is the default, but N players on an N by N board falls out of the same code if you plan for it.
Are there bots. If yes you need a seam where a move gets chosen, and difficulty becomes a strategy rather than a flag.
Is undo in scope. If yes, your win detection has to be reversible, and that changes which algorithm you pick.
Is the win condition always a full line. It might be K in a row on a big board, or four corners, or something the interviewer invents halfway through.
What happens on an invalid move. An exception, or a return value the caller checks. Either is fine, say which one you chose.

Why N by N and N players from the start

Hardcoding three by three does not just mean a literal three in one place. It leaks. The win check becomes eight explicit line comparisons. The draw check becomes a count against nine. The turn logic becomes a boolean called isPlayerOne, or a field that flips between X and O.

Now the interviewer says make it four by four. You are not changing a constant, you are rewriting the win check, the draw check and the turn order, and you are doing it under time pressure in front of someone.

The general version costs almost nothing if you decide it early. The board takes a size. Turn order is an index into a list of players, advanced modulo the list length, which handles two players and seven players with the same line. The win check takes the last move rather than scanning for shapes it already knows. None of that is harder to write than the hardcoded version, it is just a decision you have to make before you start.

The classes

Each class owns one thing, and the reason it owns that thing is the interesting part.

Symbol wraps the mark a player plays. It exists so the code is not full of chars. The moment there are five players, X and O run out, and a value type absorbs that without touching anything else.
Position is a row and a column together. Two loose ints are two chances to pass them in the wrong order.
Board owns the grid and the count of free squares, and that is all. It can place a symbol, clear a square and list the empty ones. It has no checkWinner method, and that absence is the design. Storage and rules are different jobs. Note there is no Cell class either. A square is a symbol or it is null, and a wrapper object around one nullable field would be a layer that carries nothing.
Player is anything that can be asked for a move. HumanPlayer wraps an input source, BotPlayer wraps a strategy. Two classes rather than one, because a single Player carrying a difficulty field and a strategy field forces every human to hold two nulls it never reads.
PlayingStrategy decides which square a bot plays. Random is one implementation, a heuristic is another, minimax is a third, and the game never knows which one it is talking to.
WinningStrategy answers one question, did the move that was just made win the game. This is where the rules live. Swapping a full line rule for a K in a row rule is a different implementation and no change anywhere else.
Move records the player index, the symbol and the position. It is what the history stack holds, and it is exactly the information undo needs.
GameStatus is one enum, in progress, won or draw. Not two booleans. Two booleans let you write down a game that is not over but has a winner, which is nonsense, and then every reader has to remember that combination cannot happen. In Java the enum still costs a nullable winner field beside it, and the Kotlin version removes even that by putting the winner inside the won case.
Game is the orchestrator. It owns turn order, validation and status. It asks the board to store things and asks the strategy whether the game is won, and it does neither itself. It also enforces the one construction rule that matters, at least two players and no two of them sharing a symbol.

Every one of these decisions makes the code shorter, not longer. That is the tell. Pulling the win rule out of the board removes eight hardcoded line comparisons. Making turn order an index removes the boolean that flips between two players. If your general design is longer than the hardcoded one, you have probably added layers rather than removed assumptions.

The relationships are short to say out loud. A game owns its board and its history, holds its players in turn order, and hands every finished move to a rule object it never names.

The board is storage and nothing else, so a change of rule is a second strategy beside the counters rather than an edit to the class that holds the squares.

O(1) win detection, and why it also gives you undo

The obvious win check looks at the row, the column and both diagonals of the square just played. That is O(N) per move. It works, and on a three by three board nobody cares.

The better version keeps counters. For every symbol, hold a count per row, a count per column, one count for the main diagonal and one for the anti diagonal. When a player plays at row r and column c, increment the count for row r, the count for column c, the diagonal count if r equals c, and the anti diagonal count if r plus c is N minus one. If any of those counters reaches N, that player has just completed a line. No square is ever read.

That is O(1) per move, and the part that matters is what it does for undo. Taking a move back is the same four increments run backwards, plus clearing one square. No recomputation, no rescanning, O(1) as well. If you had written the scanning version, undo would mean rescanning the whole board to work out whether the game is still won, and you would probably get it wrong.

One trap worth knowing. Bump all four counters before you test any of them. If you return as soon as the row counter hits N, the column counter never got incremented, and the next undo decrements a counter that was never raised. The state quietly goes wrong several moves later, which is the worst kind of bug to find at a whiteboard.

Counters only work when a win means a full line. For K in a row on a large board a run can start anywhere, so you walk outward from the last move along four axes, up to K minus one squares each way. That is O(K), still far better than scanning the board, and it is a second implementation of the same interface rather than a change to any existing class.

One honest note on cost. The bot asking the board for its free squares is the only linear step left, and it belongs to the bot rather than to the rule, so the win check stays O(1) no matter how the bot gets slower.

One turn, walked through

A player is about to complete a diagonal on a four by four board. Here is what actually happens between objects.

The game asks the current player for a move. If that player is a human, the input source returns whatever the person typed. If it is a bot, the strategy picks a square. The game cannot tell the two apart and does not try.
The game validates. Is the game still in progress, is the position on the board, is that square empty. All three checks live here, in one place, not scattered through the board and the player.
The game builds a Move holding the current player index, that player's symbol and the position, tells the board to place the symbol, and pushes the move onto the history stack.
The game hands the move to the winning strategy. The counter strategy increments the row counter, the column counter and, because the row equals the column, the diagonal counter. The diagonal counter reaches four.
The strategy says yes. The game sets the status to won and records the winner. It does not advance the turn, because there is no next turn.
If the strategy had said no, the game would check whether the board reports zero free squares. Zero free squares and no winner is a draw. That is a field lookup, not a board scan, because the board maintained the count as squares were filled.
Otherwise the game advances the player index by one, wrapping at the number of players, and waits for the next call.

Undo runs that backwards. Pop the move, clear the square, tell the strategy to decrement, set the status back to in progress and set the turn index back to the player recorded on the move. Turn order comes back for free, which is the second reason to put the player index on the move rather than reconstructing it.

Patterns actually used

Two patterns carry this design, and a third is worth a sentence.

Strategy for the win rule. This is the load bearing one. It is the direct answer to what if the rules change, and the answer is a new class and no edits. Without it, every rule variant is another branch inside a method that already handles three by three.
Strategy for bot play. Same shape, different axis. Difficulty becomes a class instead of an if chain, and the game stays out of it.
Command, in a small way. The move history stack is a command log and it is what makes undo possible. Only include it if undo is in scope, otherwise it is a stack nobody pops.

Three patterns to leave out, and say so out loud, because knowing what not to use reads as more senior than knowing one more pattern.

A builder. Most write ups reach for a GameBuilder here. There are three construction parameters and one real invariant, so a constructor that checks it is the same safety in a quarter of the lines. A builder pays for itself when there are eight optional parameters, not three.
The full State pattern, with an InProgressState class and a WonState class, is bolted on here. Three states with no per state behaviour is an enum. State earns its keep in a vending machine, where each state genuinely accepts different inputs.
Observer for a scoreboard is decoration in a console game. Mention it only as what you would add if this were networked and other people were watching.

There is also a defensible argument for having no winning strategy interface at all. If the rule is fixed, one method parameterised by direction vectors is simpler than four classes. The senior move is to name that tradeoff rather than reaching for an interface by reflex. Say you would keep the interface because the interviewer is about to change the rules, which is the whole reason this question gets asked.

The implementation

Both trees are the same design. The board stores, the strategy decides, the game orchestrates. Everything here is short enough to write by hand in the room, which is the real test.

The Kotlin is written as Kotlin rather than translated. Symbol is a value class, the status is a sealed interface so the won state carries its winner and an impossible combination cannot be written down, the bot strategy is a function type instead of an interface, and construction uses default arguments with one require.

Java

com.androidinterview.tictactoe.game.Game.java

package com.androidinterview.tictactoe.game;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.List;

import com.androidinterview.tictactoe.model.Board;
import com.androidinterview.tictactoe.model.GameStatus;
import com.androidinterview.tictactoe.model.Move;
import com.androidinterview.tictactoe.model.Position;
import com.androidinterview.tictactoe.player.Player;
import com.androidinterview.tictactoe.win.CounterWinningStrategy;
import com.androidinterview.tictactoe.win.WinningStrategy;

// The orchestrator. It owns turn order, validation and status, delegates
// storage to the board and rules to the strategy, and nothing in here knows
// that a line is three long or that there are two players.
public final class Game {

    private final Board board;
    private final List<Player> players;
    private final WinningStrategy rules;
    private final Deque<Move> history = new ArrayDeque<>();

    private GameStatus status = GameStatus.IN_PROGRESS;
    private Player winner;
    private int nextPlayerIndex;

    public Game(List<Player> players, int size, WinningStrategy rules) {
        // The one invariant worth guarding. Two players sharing a symbol makes
        // the board unreadable and every win check wrong.
        if (players.size() < 2 || players.stream().map(Player::symbol).distinct().count() != players.size()) {
            throw new IllegalArgumentException("Need at least two players, each with a different symbol");
        }
        this.board = new Board(size);
        this.players = List.copyOf(players);
        this.rules = rules;
    }

    public Game(List<Player> players, int size) {
        this(players, size, new CounterWinningStrategy(size));
    }

    // Read only. The live board is handed out so a console can print it, and a
    // caller that sets a square directly desynchronises the free count and the
    // win counters.
    public Board board() {
        return board;
    }

    public GameStatus status() {
        return status;
    }

    public Player winner() {
        return winner;
    }

    public Player currentPlayer() {
        return players.get(nextPlayerIndex);
    }

    // The whole loop for a console game, called until the status leaves
    // IN_PROGRESS. A human blocks on input and a bot returns at once, and this
    // method cannot tell which it just spoke to.
    public Move playTurn() {
        return makeMove(currentPlayer().decideMove(board));
    }

    public Move makeMove(Position at) {
        if (status != GameStatus.IN_PROGRESS) {
            throw new IllegalStateException("The game already ended as " + status);
        }
        if (!board.contains(at) || board.at(at) != null) {
            throw new IllegalArgumentException(at + " is off the board or already taken");
        }

        Player player = currentPlayer();
        Move move = new Move(nextPlayerIndex, player.symbol(), at);
        board.set(at, player.symbol());
        history.push(move);

        if (rules.isWinningMove(board, move)) {
            status = GameStatus.WON;
            winner = player;
        } else if (board.isFull()) {
            // A draw is the free count reaching zero with no winner. There is
            // never a reason to rescan the board to find that out.
            status = GameStatus.DRAW;
        } else {
            nextPlayerIndex = (nextPlayerIndex + 1) % players.size();
        }
        return move;
    }

    // O(1). One square is cleared, the strategy decrements the counters it
    // incremented, and turn order comes back for free because the move recorded
    // whose turn it was.
    public Move undo() {
        Move move = history.poll();
        if (move == null) {
            throw new IllegalStateException("There is nothing to undo");
        }
        board.set(move.at(), null);
        rules.undo(move);
        status = GameStatus.IN_PROGRESS;
        winner = null;
        nextPlayerIndex = move.playerIndex();
        return move;
    }
}

com.androidinterview.tictactoe.model.Board.java

package com.androidinterview.tictactoe.model;

import java.util.ArrayList;
import java.util.List;

// The board owns the grid and the number of free squares, and that is all.
// Notice what is missing, there is no checkWinner here. Hanging the win rule
// off the board is what forces a rewrite when the interviewer says four by
// four, or five players, or four in a row.
public final class Board {

    private final int size;
    private final Symbol[][] grid;
    private int emptyCount;

    public Board(int size) {
        this.size = size;
        this.grid = new Symbol[size][size];
        this.emptyCount = size * size;
    }

    public int size() {
        return size;
    }

    public boolean isFull() {
        return emptyCount == 0;
    }

    public boolean contains(Position at) {
        return at.row() >= 0 && at.row() < size && at.col() >= 0 && at.col() < size;
    }

    public Symbol at(Position position) {
        return grid[position.row()][position.col()];
    }

    // Passing null clears the square, which is what undo does. The free count
    // is maintained here so nobody ever has to walk the grid to find a draw.
    public void set(Position position, Symbol symbol) {
        Symbol previous = at(position);
        if (previous == null && symbol != null) {
            emptyCount--;
        }
        if (previous != null && symbol == null) {
            emptyCount++;
        }
        grid[position.row()][position.col()] = symbol;
    }

    // The one linear scan in the whole design, and it belongs to the bot rather
    // than to the rule. Win detection never walks the grid.
    public List<Position> emptyPositions() {
        List<Position> free = new ArrayList<>();
        for (int row = 0; row < size; row++) {
            for (int col = 0; col < size; col++) {
                if (grid[row][col] == null) {
                    free.add(new Position(row, col));
                }
            }
        }
        return free;
    }
}

com.androidinterview.tictactoe.model.GameStatus.java

package com.androidinterview.tictactoe.model;

// One enum, not a pair of booleans. Two flags can express isOver false and
// hasWinner true, which is nonsense, and every reader of the code then has to
// remember that combination cannot happen. An enum makes it unrepresentable.
public enum GameStatus {
    IN_PROGRESS,
    WON,
    DRAW
}

com.androidinterview.tictactoe.model.Move.java

package com.androidinterview.tictactoe.model;

// Everything undo needs, which player, which mark, which square. Holding the
// index rather than the player keeps this package independent of the players.
public record Move(int playerIndex, Symbol symbol, Position at) {
}

com.androidinterview.tictactoe.model.Position.java

package com.androidinterview.tictactoe.model;

// Row and column travel together everywhere, so they are one value. Two loose
// ints are two chances to swap them at a call site.
public record Position(int row, int col) {

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

com.androidinterview.tictactoe.model.Symbol.java

package com.androidinterview.tictactoe.model;

// A symbol is a value, not a char. X and O are only the default pair, and five
// players need five marks, so the type has to widen without anything else
// changing. A record costs one line.
public record Symbol(String mark) {

    public static final Symbol X = new Symbol("X");
    public static final Symbol O = new Symbol("O");

    @Override
    public String toString() {
        return mark;
    }
}

com.androidinterview.tictactoe.player.BotPlayer.java

package com.androidinterview.tictactoe.player;

import com.androidinterview.tictactoe.model.Board;
import com.androidinterview.tictactoe.model.Position;
import com.androidinterview.tictactoe.model.Symbol;

// A bot is a player plus a strategy. Human and bot are separate classes so a
// human never carries a strategy field it does not use.
public record BotPlayer(String name, Symbol symbol, PlayingStrategy strategy) implements Player {

    @Override
    public Position decideMove(Board board) {
        return strategy.choose(board, symbol);
    }
}

com.androidinterview.tictactoe.player.HumanPlayer.java

package com.androidinterview.tictactoe.player;

import java.util.function.Function;

import com.androidinterview.tictactoe.model.Board;
import com.androidinterview.tictactoe.model.Position;
import com.androidinterview.tictactoe.model.Symbol;

// A record, so name and symbol come free. The input source is injected rather
// than wired to the console, so the same class works behind a socket or a test.
public record HumanPlayer(String name, Symbol symbol, Function<Board, Position> input)
        implements Player {

    @Override
    public Position decideMove(Board board) {
        return input.apply(board);
    }
}

com.androidinterview.tictactoe.player.Player.java

package com.androidinterview.tictactoe.player;

import com.androidinterview.tictactoe.model.Board;
import com.androidinterview.tictactoe.model.Position;
import com.androidinterview.tictactoe.model.Symbol;

// A player is anything that can be asked for a move. The game calls this and
// never learns whether a person or a bot answered.
public interface Player {

    String name();

    Symbol symbol();

    Position decideMove(Board board);
}

com.androidinterview.tictactoe.player.PlayingStrategy.java

package com.androidinterview.tictactoe.player;

import java.util.List;
import java.util.Random;

import com.androidinterview.tictactoe.model.Board;
import com.androidinterview.tictactoe.model.Position;
import com.androidinterview.tictactoe.model.Symbol;

// How a bot picks. Difficulty is a strategy rather than an if chain inside the
// bot, so a minimax bot later is one new lambda and no edits.
@FunctionalInterface
public interface PlayingStrategy {

    Position choose(Board board, Symbol symbol);

    static PlayingStrategy random(Random random) {
        return (board, symbol) -> {
            List<Position> free = board.emptyPositions();
            return free.get(random.nextInt(free.size()));
        };
    }
}

com.androidinterview.tictactoe.win.CounterWinningStrategy.java

package com.androidinterview.tictactoe.win;

import java.util.HashMap;
import java.util.Map;

import com.androidinterview.tictactoe.model.Board;
import com.androidinterview.tictactoe.model.Move;
import com.androidinterview.tictactoe.model.Symbol;

// A whole line of one symbol, the standard rule, and the version worth
// remembering. The naive check rescans a row, a column and two diagonals after
// every move, which is O(N). Counting is O(1), and because the counters are
// only numbers, taking a move back is O(1) too.
public final class CounterWinningStrategy implements WinningStrategy {

    private final int size;
    private final Map<Symbol, int[]> rows = new HashMap<>();
    private final Map<Symbol, int[]> cols = new HashMap<>();
    // Two slots, the main diagonal and the anti diagonal.
    private final Map<Symbol, int[]> diagonals = new HashMap<>();

    public CounterWinningStrategy(int size) {
        this.size = size;
    }

    // Greater than or equal rather than equal. No counter can pass the board
    // size today, and a rule change that broke that should fail loudly rather
    // than silently stop detecting wins.
    @Override
    public boolean isWinningMove(Board board, Move move) {
        return bumpCounters(move, 1) >= size;
    }

    @Override
    public void undo(Move move) {
        bumpCounters(move, -1);
    }

    // One method for both directions. Every counter the move touches is bumped
    // before any is compared, because returning early would leave a counter
    // unbumped and the next undo would then push it below zero.
    private int bumpCounters(Move move, int delta) {
        int row = move.at().row();
        int col = move.at().col();
        int[] rowCounts = counters(rows, move.symbol(), size);
        int[] colCounts = counters(cols, move.symbol(), size);
        int[] diagonalCounts = counters(diagonals, move.symbol(), 2);

        int best = rowCounts[row] += delta;
        best = Math.max(best, colCounts[col] += delta);
        if (row == col) {
            best = Math.max(best, diagonalCounts[0] += delta);
        }
        if (row + col == size - 1) {
            best = Math.max(best, diagonalCounts[1] += delta);
        }
        return best;
    }

    private int[] counters(Map<Symbol, int[]> of, Symbol symbol, int length) {
        return of.computeIfAbsent(symbol, ignored -> new int[length]);
    }
}

com.androidinterview.tictactoe.win.KInARowWinningStrategy.java

package com.androidinterview.tictactoe.win;

import com.androidinterview.tictactoe.model.Board;
import com.androidinterview.tictactoe.model.Move;
import com.androidinterview.tictactoe.model.Position;

// Five in a row on a large board, the Gomoku rule. Counters do not work when a
// run can start anywhere, so this walks outward from the move along four axes.
// Right, down, down right and down left cover all eight directions once the
// sign is flipped, so there is no class per direction.
public final class KInARowWinningStrategy implements WinningStrategy {

    private static final int[][] AXES = {{0, 1}, {1, 0}, {1, 1}, {1, -1}};

    private final int k;

    public KInARowWinningStrategy(int k) {
        this.k = k;
    }

    @Override
    public boolean isWinningMove(Board board, Move move) {
        for (int[] axis : AXES) {
            int run = 1 + count(board, move, axis[0], axis[1]) + count(board, move, -axis[0], -axis[1]);
            if (run >= k) {
                return true;
            }
        }
        return false;
    }

    private int count(Board board, Move move, int rowStep, int colStep) {
        int found = 0;
        Position at = new Position(move.at().row() + rowStep, move.at().col() + colStep);
        while (found < k - 1 && board.contains(at) && move.symbol().equals(board.at(at))) {
            found++;
            at = new Position(at.row() + rowStep, at.col() + colStep);
        }
        return found;
    }
}

com.androidinterview.tictactoe.win.WinningStrategy.java

package com.androidinterview.tictactoe.win;

import com.androidinterview.tictactoe.model.Board;
import com.androidinterview.tictactoe.model.Move;

// The rules live here and nowhere else, so a rule change is a new class and no
// edits. The move that was just played is passed in rather than asking for a
// board scan, and that is what allows an O(1) implementation.
public interface WinningStrategy {

    boolean isWinningMove(Board board, Move move);

    // A stateless rule ignores this. A counting rule rolls its counters back.
    default void undo(Move move) {
    }
}

Kotlin

com.androidinterview.tictactoe.game.Game.kt

package com.androidinterview.tictactoe.game

import com.androidinterview.tictactoe.model.Board
import com.androidinterview.tictactoe.model.Move
import com.androidinterview.tictactoe.model.Position
import com.androidinterview.tictactoe.player.Player
import com.androidinterview.tictactoe.win.CounterWinningStrategy
import com.androidinterview.tictactoe.win.WinningStrategy

// The orchestrator. It owns turn order, validation and status. Storage belongs
// to the board and rules belong to the strategy, and nothing here knows that a
// line is three long or that there are two players.
class Game(
    private val players: List<Player>,
    size: Int = 3,
    private val rules: WinningStrategy = CounterWinningStrategy(size),
) {

    // Kotlin needs no builder here. Default arguments cover the optional
    // parameters and require covers the one invariant that matters, which is
    // that two players sharing a symbol makes every win check wrong.
    init {
        require(players.size >= 2 && players.distinctBy { it.symbol }.size == players.size) {
            "Need at least two players, each with a different symbol"
        }
    }

    // Read only. The live board is exposed so a console can print it, and a
    // caller that sets a square directly desynchronises the free count and the
    // win counters.
    val board = Board(size)
    private val history = ArrayDeque<Move>()
    private var nextPlayerIndex = 0

    var status: GameStatus = GameStatus.InProgress
        private set

    val currentPlayer: Player get() = players[nextPlayerIndex]

    // The whole loop for a console game, called until the status is no longer
    // InProgress. A human blocks on input and a bot returns at once, and this
    // function cannot tell which it just spoke to.
    fun playTurn(): Move = makeMove(currentPlayer.decideMove(board))

    fun makeMove(at: Position): Move {
        check(status is GameStatus.InProgress) { "The game already ended as $status" }
        require(at in board && board[at] == null) { "$at is off the board or already taken" }

        val player = currentPlayer
        val move = Move(nextPlayerIndex, player.symbol, at)
        board[at] = player.symbol
        history.addLast(move)

        status = when {
            rules.isWinningMove(board, move) -> GameStatus.Won(player)
            // A draw is the free count reaching zero with no winner. There is
            // never a reason to rescan the board to work that out.
            board.isFull -> GameStatus.Draw
            else -> {
                nextPlayerIndex = (nextPlayerIndex + 1) % players.size
                GameStatus.InProgress
            }
        }
        return move
    }

    // O(1). One square is cleared, the strategy decrements the counters it
    // incremented, and turn order comes back for free because the move recorded
    // whose turn it was.
    fun undo(): Move {
        val move = checkNotNull(history.removeLastOrNull()) { "There is nothing to undo" }
        board[move.at] = null
        rules.undo(move)
        status = GameStatus.InProgress
        nextPlayerIndex = move.playerIndex
        return move
    }
}

com.androidinterview.tictactoe.game.GameStatus.kt

package com.androidinterview.tictactoe.game

import com.androidinterview.tictactoe.player.Player

// A sealed hierarchy instead of an enum plus a nullable winner field. Won
// carries its winner, so a won game with no winner cannot be written down, and
// a when over the status is exhaustive.
sealed interface GameStatus {
    data object InProgress : GameStatus
    data class Won(val player: Player) : GameStatus
    data object Draw : GameStatus
}

com.androidinterview.tictactoe.model.Board.kt

package com.androidinterview.tictactoe.model

// The board owns the grid and the number of free squares. Notice what is not
// here, there is no win check. Hanging the rule off the board is what forces a
// rewrite when the interviewer says four by four, or five players.
class Board(val size: Int) {

    private val cells = Array(size) { arrayOfNulls<Symbol>(size) }

    var emptyCount = size * size
        private set

    val isFull get() = emptyCount == 0

    operator fun contains(at: Position) = at.row in 0 until size && at.col in 0 until size

    operator fun get(at: Position): Symbol? = cells[at.row][at.col]

    // Setting null clears the square, which is what undo does. The free count
    // is kept here so nobody ever walks the grid to find a draw.
    operator fun set(at: Position, symbol: Symbol?) {
        val previous = cells[at.row][at.col]
        if (previous == null && symbol != null) emptyCount--
        if (previous != null && symbol == null) emptyCount++
        cells[at.row][at.col] = symbol
    }

    // The one linear scan in the whole design, and it belongs to the bot rather
    // than to the rule. Win detection never walks the grid.
    fun emptyPositions(): List<Position> =
        (0 until size).flatMap { row ->
            (0 until size).mapNotNull { col -> Position(row, col).takeIf { cells[row][col] == null } }
        }

    override fun toString() =
        cells.joinToString("\n") { row -> row.joinToString(" ") { it?.mark ?: "." } }
}

com.androidinterview.tictactoe.model.Move.kt

package com.androidinterview.tictactoe.model

// Everything undo needs, which player, which mark, which square.
data class Move(val playerIndex: Int, val symbol: Symbol, val at: Position)

com.androidinterview.tictactoe.model.Position.kt

package com.androidinterview.tictactoe.model

// Row and column travel together, so they are one value.
data class Position(val row: Int, val col: Int) {
    override fun toString() = "$row,$col"
}

com.androidinterview.tictactoe.model.Symbol.kt

package com.androidinterview.tictactoe.model

// A symbol is a value, not a Char, so five players is five marks and not a
// rewrite. A value class means it costs nothing at runtime.
@JvmInline
value class Symbol(val mark: String) {
    override fun toString() = mark

    companion object {
        val X = Symbol("X")
        val O = Symbol("O")
    }
}

com.androidinterview.tictactoe.player.Player.kt

package com.androidinterview.tictactoe.player

import com.androidinterview.tictactoe.model.Board
import com.androidinterview.tictactoe.model.Position
import com.androidinterview.tictactoe.model.Symbol
import kotlin.random.Random

// A one method strategy is a function type in Kotlin, so a new bot difficulty
// is a lambda and never a class.
typealias PlayingStrategy = (board: Board, symbol: Symbol) -> Position

fun randomPlay(random: Random = Random.Default): PlayingStrategy =
    { board, _ -> board.emptyPositions().random(random) }

// A player is anything that can be asked for a move, so this is a plain
// interface and not a sealed one. Nothing in the game ever branches on which
// kind it has, and sealing would only stop a caller writing a network player.
// A human carries an input source, a bot carries a strategy, and neither holds
// a field it never reads.
interface Player {
    val name: String
    val symbol: Symbol
    fun decideMove(board: Board): Position
}

class HumanPlayer(
    override val name: String,
    override val symbol: Symbol,
    private val input: (Board) -> Position,
) : Player {
    override fun decideMove(board: Board) = input(board)
}

class BotPlayer(
    override val name: String,
    override val symbol: Symbol,
    private val strategy: PlayingStrategy = randomPlay(),
) : Player {
    override fun decideMove(board: Board) = strategy(board, symbol)
}

com.androidinterview.tictactoe.win.WinningStrategy.kt

package com.androidinterview.tictactoe.win

import com.androidinterview.tictactoe.model.Board
import com.androidinterview.tictactoe.model.Move
import com.androidinterview.tictactoe.model.Position
import com.androidinterview.tictactoe.model.Symbol

// The rules live here and nowhere else, so a rule change is a new class and no
// edits. The move just played is passed in rather than asking for a board scan,
// which is what allows an O(1) implementation.
interface WinningStrategy {
    fun isWinningMove(board: Board, move: Move): Boolean

    // A stateless rule ignores this. A counting rule rolls its counters back.
    fun undo(move: Move) = Unit
}

// A whole line of one symbol, the standard rule, and the version worth
// remembering. The naive check rescans a row, a column and two diagonals every
// move, which is O(N). Counting is O(1), and since the counters are only
// numbers, taking a move back is O(1) as well.
class CounterWinningStrategy(private val size: Int) : WinningStrategy {

    private val rows = mutableMapOf<Symbol, IntArray>()
    private val cols = mutableMapOf<Symbol, IntArray>()

    // Two slots, the main diagonal and the anti diagonal.
    private val diagonals = mutableMapOf<Symbol, IntArray>()

    // Greater than or equal rather than equal. No counter can pass the board
    // size today, and a rule change that broke that should fail loudly rather
    // than silently stop detecting wins.
    override fun isWinningMove(board: Board, move: Move) = bumpCounters(move, 1) >= size

    override fun undo(move: Move) {
        bumpCounters(move, -1)
    }

    // One function for both directions. Every counter the move touches is
    // bumped before any is compared, because returning early would leave one
    // unbumped and the next undo would push it below zero.
    private fun bumpCounters(move: Move, delta: Int): Int {
        val (_, symbol, at) = move
        var best = rows.counters(symbol, size).bump(at.row, delta)
        best = maxOf(best, cols.counters(symbol, size).bump(at.col, delta))
        if (at.row == at.col) {
            best = maxOf(best, diagonals.counters(symbol, 2).bump(0, delta))
        }
        if (at.row + at.col == size - 1) {
            best = maxOf(best, diagonals.counters(symbol, 2).bump(1, delta))
        }
        return best
    }

    private fun MutableMap<Symbol, IntArray>.counters(symbol: Symbol, length: Int) =
        getOrPut(symbol) { IntArray(length) }

    private fun IntArray.bump(index: Int, delta: Int): Int {
        this[index] += delta
        return this[index]
    }
}

// Five in a row on a large board, the Gomoku rule. Counters do not work when a
// run can start anywhere, so this walks outward from the move along four axes.
// Right, down, down right and down left cover all eight directions once the
// sign is flipped, so there is no class per direction.
class KInARowWinningStrategy(private val k: Int) : WinningStrategy {

    private val axes = listOf(0 to 1, 1 to 0, 1 to 1, 1 to -1)

    override fun isWinningMove(board: Board, move: Move) = axes.any { (rowStep, colStep) ->
        1 + board.runFrom(move, rowStep, colStep) + board.runFrom(move, -rowStep, -colStep) >= k
    }

    private fun Board.runFrom(move: Move, rowStep: Int, colStep: Int): Int {
        var found = 0
        var at = Position(move.at.row + rowStep, move.at.col + colStep)
        while (found < k - 1 && at in this && this[at] == move.symbol) {
            found++
            at = Position(at.row + rowStep, at.col + colStep)
        }
        return found
    }
}

Concurrency and edge cases

Do not invent a concurrency story. Tic tac toe is turn based and single threaded, and a candidate who starts adding locks to a board is answering a question nobody asked. If you are pushed on it, the honest answer is short. The bot strategies are stateless and shareable. The counting win strategy is not, it holds this game's counters, so every game gets its own. A server hosting many games locks per game, never per board. The lock protects the turn, so only the player whose turn it is can move.

The edge cases that actually come up.

A move off the board. Rejected by the game before the board is touched.
A move on a taken square. Same place, same check.
A move after the game ended. The status enum blocks it. This is the case the two boolean design gets wrong.
A draw. Zero free squares and no winner. Read the count, do not rescan.
Undo at the start of the game. Empty history, so it fails loudly rather than corrupting the turn index.
Undo after a win. Legal, and it is why the counters are all bumped before any is tested.
Two players with the same symbol. Caught at construction, because a board with two X players cannot be read by anyone.
Fewer than two players. Also caught at construction.
A bot with no free squares. Cannot happen, because a full board is already a draw and the game never asks for another move.