Designing Tic-Tac-Toe

Difficulty: Beginner Patterns: Strategy, State, Factory Asked at: Amazon, PhonePe, Flipkart, Adobe, Walmart

Tic-Tac-Toe is a warm-up problem, but interviewers use it to check two things: can you generalise 3×3 to N×N without special-casing, and can you detect a win in O(1) per move instead of re-scanning the board every time? Get those right and the rest — turns, validation, draw detection — is straightforward. The trap is hardcoding “3”, eight win-lines, and an O(N²) scan after each move.

Functional Requirements

Board is N×N (3×3 by default, but the code must not assume 3).
Two players, each with a distinct symbol (X / O), taking turns.
A move places a symbol in an empty cell; occupied or out-of-bounds moves are rejected.
Detect a win: a full row, column, or either diagonal of one symbol.
Detect a draw: board full with no winner.
Win detection should be O(1) per move (no full-board rescans).

Non-Functional Requirements

Extensibility — support more players, bigger boards, or new win rules with minimal change.
Clean separation — the board doesn’t know about turn order; the game doesn’t know how cells are stored.
Robust validation — no move ever corrupts game state.

Core Entities

Entity	Description
`Symbol`	A player’s mark (X, O, …) — value object over a char
`Player`	Name + symbol
`Cell`	One board square; empty or holding a symbol
`Board`	N×N grid; applies moves, exposes cell state
`WinningStrategy`	Decides whether the last move won
`RowColDiagonalStrategy`	O(1) win check via running tallies
`GameState`	Enum: IN_PROGRESS, WIN, DRAW
`Game`	Orchestrates players, turns, the board, and the strategy

The O(1) win-check insight

The naive check rescans the placed cell’s row, column, and diagonals after every move — O(N) per move, and you re-derive the eight lines each time. The clean trick: keep running counts. For each row, column, and the two diagonals, track a signed tally per symbol. When a symbol is placed, increment the relevant tallies; if any reaches N, that line is complete — a win. Each move touches at most 4 counters, so it’s O(1).

💡 This is the same “maintain an aggregate incrementally instead of recomputing it” idea behind running sums and streaming statistics — the interviewer wants to see you avoid the rescan.

classDiagram
    class Symbol {
        -char mark
    }

    class Player {
        -String name
        -Symbol symbol
    }

    class Cell {
        -int row
        -int col
        -Symbol symbol
        +isEmpty() boolean
    }

    class Board {
        -int size
        -Cell[][] grid
        -int filledCells
        +place(int r, int c, Symbol) boolean
        +isFull() boolean
        +isValid(int r, int c) boolean
    }

    class WinningStrategy {
        <<interface>>
        +checkWin(Board, int r, int c, Symbol) boolean
    }

    class RowColDiagonalStrategy {
        -Map counts
        +checkWin(Board, int, int, Symbol) boolean
    }

    class Game {
        -Board board
        -Deque~Player~ players
        -WinningStrategy strategy
        -GameState state
        +move(int r, int c) GameState
    }

    WinningStrategy <|.. RowColDiagonalStrategy
    Game --> Board
    Game --> Player
    Game --> WinningStrategy
    Board --> Cell
    Player --> Symbol
    Cell --> Symbol

Design Patterns

Pattern	Where	Why
Strategy	`WinningStrategy`	Swap win rules — standard lines, or “3-in-a-row on a 5×5” (Gomoku-style) — without touching the game loop.
State	`GameState` enum drives the loop	The game stops accepting moves once it’s WIN or DRAW.
Factory (extension)	Board / player creation	Configure 3×3 two-player or N×N multi-player from one place.
Command (extension)	Moves as objects	Enables undo/redo and replay.

Data Structures

Component	Structure	Why
Grid	`Cell[][]`	Direct O(1) access by (row, col)
Win tallies	`int[] rows`, `int[] cols`, `int diag`, `int antiDiag` per symbol	O(1) win check; increment on place
Turn order	`ArrayDeque<Player>` (rotate)	Poll front, offer back — trivially extends past 2 players
Fill count	single `int filledCells`	O(1) draw detection, no board scan

Using a Deque for players is the small touch that makes “add a third player” a non-event: you rotate the queue instead of flipping a boolean.

Complete Code

Symbol.java

A value object wrapping the player’s mark. Wrapping it (rather than passing raw char) leaves room to attach colour, avatar, or scoring later without changing signatures everywhere.

package tictactoe.model;

public class Symbol {
    private final char mark;

    public Symbol(char mark) { this.mark = mark; }

    public char getMark() { return mark; }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Symbol)) return false;
        return mark == ((Symbol) o).mark;
    }

    @Override public int hashCode() { return Character.hashCode(mark); }
    @Override public String toString() { return String.valueOf(mark); }
}

Player.java

package tictactoe.model;

public class Player {
    private final String name;
    private final Symbol symbol;

    public Player(String name, Symbol symbol) {
        this.name = name;
        this.symbol = symbol;
    }

    public String getName() { return name; }
    public Symbol getSymbol() { return symbol; }

    @Override public String toString() { return name + " (" + symbol + ")"; }
}

Cell.java

package tictactoe.model;

public class Cell {
    private final int row, col;
    private Symbol symbol; // null = empty

    public Cell(int row, int col) { this.row = row; this.col = col; }

    public boolean isEmpty() { return symbol == null; }
    public Symbol getSymbol() { return symbol; }
    public void setSymbol(Symbol s) { this.symbol = s; }
    public int getRow() { return row; }
    public int getCol() { return col; }
}

Board.java

Owns the grid and the only mutation path (place). It validates bounds and emptiness, tracks a filledCells counter for O(1) draw detection, and prints itself — but it knows nothing about turns or winning. Single responsibility: hold and mutate the grid.

package tictactoe.model;

public class Board {
    private final int size;
    private final Cell[][] grid;
    private int filledCells = 0;

    public Board(int size) {
        this.size = size;
        this.grid = new Cell[size][size];
        for (int r = 0; r < size; r++)
            for (int c = 0; c < size; c++)
                grid[r][c] = new Cell(r, c);
    }

    public boolean isValid(int r, int c) {
        return r >= 0 && r < size && c >= 0 && c < size && grid[r][c].isEmpty();
    }

    /** Place a symbol. Returns false if the move is illegal (caller decides what to do). */
    public boolean place(int r, int c, Symbol symbol) {
        if (!isValid(r, c)) return false;
        grid[r][c].setSymbol(symbol);
        filledCells++;
        return true;
    }

    public boolean isFull() { return filledCells == size * size; }
    public int getSize() { return size; }
    public Cell getCell(int r, int c) { return grid[r][c]; }

    public void print() {
        for (int r = 0; r < size; r++) {
            StringBuilder sb = new StringBuilder();
            for (int c = 0; c < size; c++) {
                sb.append(grid[r][c].isEmpty() ? "." : grid[r][c].getSymbol());
                if (c < size - 1) sb.append(" | ");
            }
            System.out.println("  " + sb);
        }
        System.out.println();
    }
}

WinningStrategy.java (Strategy interface)

package tictactoe.strategy;

import tictactoe.model.Board;
import tictactoe.model.Symbol;

public interface WinningStrategy {
    /** Called right after (r,c) was set to `symbol`. Return true if that move wins. */
    boolean checkWin(Board board, int r, int c, Symbol symbol);
}

RowColDiagonalStrategy.java

The O(1) heart of the design. It keeps per-symbol tallies for every row, every column, and the two diagonals. Placing a symbol bumps at most four counters; if any hits N, that line is full and the move wins — no board rescan.

package tictactoe.strategy;

import tictactoe.model.Board;
import tictactoe.model.Symbol;

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

public class RowColDiagonalStrategy implements WinningStrategy {
    private final int size;

    // Per-symbol running tallies.
    private final Map<Symbol, int[]> rowCounts = new HashMap<>();
    private final Map<Symbol, int[]> colCounts = new HashMap<>();
    private final Map<Symbol, Integer> diagCounts = new HashMap<>();
    private final Map<Symbol, Integer> antiDiagCounts = new HashMap<>();

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

    @Override
    public boolean checkWin(Board board, int r, int c, Symbol symbol) {
        rowCounts.putIfAbsent(symbol, new int[size]);
        colCounts.putIfAbsent(symbol, new int[size]);

        int[] rows = rowCounts.get(symbol);
        int[] cols = colCounts.get(symbol);

        if (++rows[r] == size) return true;
        if (++cols[c] == size) return true;

        if (r == c) { // main diagonal
            int d = diagCounts.merge(symbol, 1, Integer::sum);
            if (d == size) return true;
        }
        if (r + c == size - 1) { // anti-diagonal
            int a = antiDiagCounts.merge(symbol, 1, Integer::sum);
            if (a == size) return true;
        }
        return false;
    }
}

GameState.java

package tictactoe.model;

public enum GameState {
    IN_PROGRESS, WIN, DRAW
}

Game.java (Orchestrator)

Ties it together: rotates players via a Deque, applies each move through the board, asks the strategy whether it won, and flips to WIN/DRAW when appropriate. Once the game is over it refuses further moves — the GameState acts as the guard.

package tictactoe;

import tictactoe.model.*;
import tictactoe.strategy.RowColDiagonalStrategy;
import tictactoe.strategy.WinningStrategy;

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

public class Game {
    private final Board board;
    private final Deque<Player> players = new ArrayDeque<>();
    private final WinningStrategy strategy;
    private GameState state = GameState.IN_PROGRESS;
    private Player winner;

    public Game(int size, List<Player> playerList) {
        this.board = new Board(size);
        this.players.addAll(playerList);
        this.strategy = new RowColDiagonalStrategy(size);
    }

    /** Play the current player's move at (r,c). Returns the new game state. */
    public GameState move(int r, int c) {
        if (state != GameState.IN_PROGRESS) {
            System.out.println("✗ Game is over.");
            return state;
        }

        Player current = players.peekFirst();
        if (!board.place(r, c, current.getSymbol())) {
            System.out.println("✗ Illegal move at (" + r + "," + c + ") by " + current.getName());
            return state; // same player retries; turn not consumed
        }

        System.out.println(current.getName() + " → (" + r + "," + c + ")");

        if (strategy.checkWin(board, r, c, current.getSymbol())) {
            state = GameState.WIN;
            winner = current;
        } else if (board.isFull()) {
            state = GameState.DRAW;
        } else {
            players.addLast(players.pollFirst()); // rotate turn
        }
        return state;
    }

    public GameState getState() { return state; }
    public Player getWinner() { return winner; }
    public void print() { board.print(); }
}

Demo.java (Runnable end-to-end)

Plays a full 3×3 game to a win, prints the board after each move, then re-uses the exact same classes for a 4×4 board — demonstrating that nothing was hardcoded to 3.

package tictactoe;

import tictactoe.model.*;

import java.util.Arrays;

public class Demo {
    public static void main(String[] args) {
        Player alice = new Player("Alice", new Symbol('X'));
        Player bob   = new Player("Bob",   new Symbol('O'));

        System.out.println("=== 3×3 game ===");
        Game game = new Game(3, Arrays.asList(alice, bob));

        // X wins on the top row.
        game.move(0, 0); // X
        game.move(1, 0); // O
        game.move(0, 1); // X
        game.move(1, 1); // O
        game.move(0, 2); // X → completes top row
        game.print();

        if (game.getState() == GameState.WIN)
            System.out.println("🏆 Winner: " + game.getWinner());
        else if (game.getState() == GameState.DRAW)
            System.out.println("🤝 Draw");

        System.out.println("\n=== Illegal move + same classes on a 4×4 board ===");
        Game big = new Game(4, Arrays.asList(alice, bob));
        big.move(0, 0);   // X
        big.move(0, 0);   // O tries an occupied cell → rejected, O retries
        big.move(1, 1);   // O
        big.print();
        System.out.println("State: " + big.getState());
    }
}

Sequence Diagram — A Move

sequenceDiagram
    participant P as Player
    participant G as Game
    participant B as Board
    participant W as WinningStrategy

    P->>G: move(r, c)
    G->>B: place(r, c, symbol)
    B-->>G: true (valid)
    G->>W: checkWin(board, r, c, symbol)
    W->>W: bump row/col/diag tallies
    W-->>G: win? (tally == N)
    alt win
        G->>G: state = WIN
    else board full
        G->>G: state = DRAW
    else
        G->>G: rotate players
    end
    G-->>P: GameState

How to Extend

Extension	Implementation
N players	Add more `Player`s to the list — the `Deque` rotation already handles it
Gomoku (K-in-a-row)	New `KInARowStrategy implements WinningStrategy`
Undo/redo	Wrap moves as Command objects on a stack; reverse the tally increments
AI opponent	A `Player` subtype whose move is chosen by minimax over the board
Custom symbols	`Symbol` already abstracts the mark — pass any char
Persistence / replay	Log each `move()`; replay by re-applying in order

What Interviewers Look For

✅ Generalised to N×N — no hardcoded 3 or hardcoded win-lines
✅ O(1) win check — running tallies, not an O(N) rescan every move
✅ Strategy for win rules — swappable, so Gomoku is a new class
✅ Clean responsibilities — Board mutates the grid, Game runs turns, Strategy judges wins
✅ Deque for turns — extends past two players for free
✅ Illegal moves rejected without corrupting state — turn isn’t consumed on a bad move
✅ Runnable demo — a full win, an illegal move, and a different board size

Snake & Ladder — turn-based board game loop
Vending Machine — State pattern for action handling
Parking Lot — Strategy pattern for swappable behaviour

Written by SystemCraft Interview Prep Platform

Free system design, LLD, and DSA resources built by engineers who went through the interview grind at Indian and international tech companies.