androidinterview.com

Low Level Design (LLD) Interview Questions

Design Tic Tac Toe

Tier: EssentialDifficulty: EasyAsked of: Junior, MidAsked at: Flipkart

Design Tic Tac Toe for two players taking turns placing X and O on a board. A full row, column or diagonal of one player's marks wins.

The problem

On a three by three board, X plays the top row while O plays elsewhere. When X fills the last empty square in that row, X wins and further moves are rejected.

Start with two human players and a square board of size three or more. A win requires a whole line. Bots, undo and shorter winning runs on large boards are follow-ups.

How to explain the design

“I keep the board, current player, move count and game status. A move checks the player's turn and that the square is empty. After placing the mark, I check the affected row and column plus the two diagonals. If there is no winner and the board is full, it is a draw. Otherwise I switch players.”

TicTacToe owns the board and rules. Status says playing, X won, O won or draw. Scanning a line is easy to write and fast enough for a small board.

Walk through one move

  1. Reject a move after the game ends or from the wrong player.
  2. Reject an off-board or occupied square.
  3. Place the mark and increment the move count.
  4. Check for a win first, then a draw.
  5. Switch players only if the game is still running.

Interview implementation

The win check takes O(N) time for an N by N board. Start here before considering counters or strategy classes.

Java

TicTacToe.java

package interview.tictactoe;

public class TicTacToe {
    public enum Status { PLAYING, X_WON, O_WON, DRAW }
    private final char[][] board;
    private final int size;
    private int moves;
    private char turn = 'X';
    private Status status = Status.PLAYING;

    public TicTacToe(int size) {
        if (size < 3) throw new IllegalArgumentException("Board is too small");
        this.size = size;
        board = new char[size][size];
    }

    public char turn() { return turn; }
    public Status status() { return status; }

    public Status play(char player, int row, int col) {
        if (status != Status.PLAYING || player != turn) throw new IllegalStateException("Not this player's turn");
        if (row < 0 || row >= size || col < 0 || col >= size || board[row][col] != 0) {
            throw new IllegalArgumentException("Invalid square");
        }
        board[row][col] = player;
        moves++;
        boolean rowWin = true, colWin = true, diagonalWin = true, otherDiagonalWin = true;
        for (int i = 0; i < size; i++) {
            rowWin &= board[row][i] == player;
            colWin &= board[i][col] == player;
            diagonalWin &= board[i][i] == player;
            otherDiagonalWin &= board[i][size - 1 - i] == player;
        }
        if (rowWin || colWin || diagonalWin || otherDiagonalWin) status = player == 'X' ? Status.X_WON : Status.O_WON;
        else if (moves == size * size) status = Status.DRAW;
        else turn = turn == 'X' ? 'O' : 'X';
        return status;
    }
}

package interview.tictactoe;

public class TicTacToe {
    public enum Status { PLAYING, X_WON, O_WON, DRAW }
    private final char[][] board;
    private final int size;
    private int moves;
    private char turn = 'X';
    private Status status = Status.PLAYING;

    public TicTacToe(int size) {
        if (size < 3) throw new IllegalArgumentException("Board is too small");
        this.size = size;
        board = new char[size][size];
    }

    public char turn() { return turn; }
    public Status status() { return status; }

    public Status play(char player, int row, int col) {
        if (status != Status.PLAYING || player != turn) throw new IllegalStateException("Not this player's turn");
        if (row < 0 || row >= size || col < 0 || col >= size || board[row][col] != 0) {
            throw new IllegalArgumentException("Invalid square");
        }
        board[row][col] = player;
        moves++;
        boolean rowWin = true, colWin = true, diagonalWin = true, otherDiagonalWin = true;
        for (int i = 0; i < size; i++) {
            rowWin &= board[row][i] == player;
            colWin &= board[i][col] == player;
            diagonalWin &= board[i][i] == player;
            otherDiagonalWin &= board[i][size - 1 - i] == player;
        }
        if (rowWin || colWin || diagonalWin || otherDiagonalWin) status = player == 'X' ? Status.X_WON : Status.O_WON;
        else if (moves == size * size) status = Status.DRAW;
        else turn = turn == 'X' ? 'O' : 'X';
        return status;
    }
}

Kotlin

TicTacToe.kt

package interview.tictactoe

enum class Status { PLAYING, X_WON, O_WON, DRAW }

class TicTacToe(private val size: Int = 3) {
    private val board: Array<CharArray>
    private var moves = 0
    var turn = 'X'
        private set
    var status = Status.PLAYING
        private set

    init {
        require(size >= 3)
        board = Array(size) { CharArray(size) { '.' } }
    }

    fun play(player: Char, row: Int, col: Int): Status {
        check(status == Status.PLAYING && player == turn) { "Not this player's turn" }
        require(row in 0 until size && col in 0 until size && board[row][col] == '.')
        board[row][col] = player
        moves++
        val won = (0 until size).all { board[row][it] == player } ||
            (0 until size).all { board[it][col] == player } ||
            (0 until size).all { board[it][it] == player } ||
            (0 until size).all { board[it][size - 1 - it] == player }
        status = when {
            won -> if (player == 'X') Status.X_WON else Status.O_WON
            moves == size * size -> Status.DRAW
            else -> Status.PLAYING
        }
        if (status == Status.PLAYING) turn = if (turn == 'X') 'O' else 'X'
        return status
    }
}

package interview.tictactoe

enum class Status { PLAYING, X_WON, O_WON, DRAW }

class TicTacToe(private val size: Int = 3) {
    private val board: Array<CharArray>
    private var moves = 0
    var turn = 'X'
        private set
    var status = Status.PLAYING
        private set

    init {
        require(size >= 3)
        board = Array(size) { CharArray(size) { '.' } }
    }

    fun play(player: Char, row: Int, col: Int): Status {
        check(status == Status.PLAYING && player == turn) { "Not this player's turn" }
        require(row in 0 until size && col in 0 until size && board[row][col] == '.')
        board[row][col] = player
        moves++
        val won = (0 until size).all { board[row][it] == player } ||
            (0 until size).all { board[it][col] == player } ||
            (0 until size).all { board[it][it] == player } ||
            (0 until size).all { board[it][size - 1 - it] == player }
        status = when {
            won -> if (player == 'X') Status.X_WON else Status.O_WON
            moves == size * size -> Status.DRAW
            else -> Status.PLAYING
        }
        if (status == Status.PLAYING) turn = if (turn == 'X') 'O' else 'X'
        return status
    }
}

Follow-up questions

Constant time win checks?

“I would keep counters for each row, column and diagonal.” Add 1 for X and subtract 1 for O. A line whose count reaches the board size or its negative belongs entirely to one player. Keep the board as well, because counters cannot tell whether a square is occupied.

Add two zero-filled arrays of length size, rows and columns, and two integers starting at zero, diagonal and antiDiagonal, to the class. After a valid move is placed, replace the scanning win check with this fragment. Use won to decide the winning status. A draw still depends on the move count.

Kotlin

val delta = if (player == 'X') 1 else -1
rows[row] += delta
columns[col] += delta
if (row == col) diagonal += delta
if (row + col == size - 1) antiDiagonal += delta
val target = delta * size
val won = rows[row] == target || columns[col] == target ||
    diagonal == target || antiDiagonal == target

Java

int delta = player == 'X' ? 1 : -1;
rows[row] += delta;
columns[col] += delta;
if (row == col) diagonal += delta;
if (row + col == size - 1) antiDiagonal += delta;
int target = delta * size;
boolean won = rows[row] == target || columns[col] == target ||
    diagonal == target || antiDiagonal == target;

Undo?

“I would push each accepted move onto a history stack.” Undo pops the last move, clears its square, decreases the move count and restores the player whose move was removed. The previous status is playing because moves after a finished game are rejected. If using counters, reverse their updates too. With an empty history, undo does nothing or reports that there is no move to undo.

A computer player?

“I would keep move selection outside the game rules.” A simple bot picks any empty square and submits it through play, just like a human. A stronger 3 by 3 bot can use minimax, which tries possible moves and replies, assuming both players choose their best result. The existing game still validates every move.

What should I test?

“Rows, columns and both diagonals should recognize a win for either player.” A full board with no winning line should be a draw. If the final empty square completes a line, the result should be a win, so check for a win before a draw. Occupied squares, wrong turns and moves after the game ends should be rejected without changing the board.

Extended implementation and optional features

This reference explores a larger scope. Use it after you can explain and write the interview version. Its extra types and features are not required for the scope above.

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;
    }
}

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;

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) {
        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));
    }

    public Board board() {
        return board;
    }

    public GameStatus status() {
        return status;
    }

    public Player winner() {
        return winner;
    }

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

    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()) {
            status = GameStatus.DRAW;
        } else {
            nextPlayerIndex = (nextPlayerIndex + 1) % players.size();
        }
        return move;
    }

    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;
    }
}

package com.androidinterview.tictactoe.model;

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

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()];
    }

    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;
    }

    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
}

package com.androidinterview.tictactoe.model;

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) {
}

package com.androidinterview.tictactoe.model;

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;
    }
}

package com.androidinterview.tictactoe.model;

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;
    }
}

package com.androidinterview.tictactoe.model;

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);
    }
}

package com.androidinterview.tictactoe.player;

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

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);
    }
}

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;

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);
}

package com.androidinterview.tictactoe.player;

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

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()));
        };
    }
}

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;

@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]);
    }
}

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;

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<>();
    private final Map<Symbol, int[]> diagonals = new HashMap<>();

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

    @Override
    public boolean isWinningMove(Board board, Move move) {
        return bumpCounters(move, 1) >= size;
    }

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

    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;
    }
}

package com.androidinterview.tictactoe.win;

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

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) {
    }
}

package com.androidinterview.tictactoe.win;

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

public interface WinningStrategy {

    boolean isWinningMove(Board board, Move move);

    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
    }
}

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

class Game(
    private val players: List<Player>,
    size: Int = 3,
    private val rules: WinningStrategy = CounterWinningStrategy(size),
) {

    init {
        require(players.size >= 2 && players.distinctBy { it.symbol }.size == players.size) {
            "Need at least two players, each with a different symbol"
        }
    }

    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]

    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)
            board.isFull -> GameStatus.Draw
            else -> {
                nextPlayerIndex = (nextPlayerIndex + 1) % players.size
                GameStatus.InProgress
            }
        }
        return move
    }

    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
}

package com.androidinterview.tictactoe.game

import com.androidinterview.tictactoe.player.Player

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 ?: "." } }
}

package com.androidinterview.tictactoe.model

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]

    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
    }

    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)

package com.androidinterview.tictactoe.model

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"
}

package com.androidinterview.tictactoe.model

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")
    }
}

package com.androidinterview.tictactoe.model

@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)
}

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

typealias PlayingStrategy = (board: Board, symbol: Symbol) -> Position

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

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
    }
}

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

interface WinningStrategy {
    fun isWinningMove(board: Board, move: Move): Boolean

    fun undo(move: Move) = Unit
}

class CounterWinningStrategy(private val size: Int) : WinningStrategy {

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

    private val diagonals = mutableMapOf<Symbol, IntArray>()

    override fun isWinningMove(board: Board, move: Move) = bumpCounters(move, 1) >= size

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

    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]
    }
}

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
    }
}

Watch

Design Tic Tac Toe: Low Level Design Coding Interview Question (opens in a new tab)Gaurav Sen
✅ Complete Tic-Tac-Toe System Design & Low Level Design | Full Explanation + Code (opens in a new tab)codeWithAryan
TicTacToe | Google Gigachad SWE Teaches Low Level Design Episode 1 (opens in a new tab)Jordan has no life