10 — Problem: Tic Tac Toe

Understanding the Problem

Tic Tac Toe is the LLD equivalent of FizzBuzz — getting it working takes five minutes, and that's exactly why it's dangerous. The interviewer isn't asking whether you can represent a 3×3 grid and detect three in a row. They're asking whether you can design the same system with the assumption that tomorrow's requirement is Connect Four, and the day after is Gomoku on a 19×19 board with five-in-a-row wins, and the week after is Wild Tic-Tac-Toe where either player can place either symbol.

The difference between an SDE2 answer and an SDE3 answer here is almost entirely about where you put the seams. A junior writes if board[0][0] === board[0][1] && board[0][1] === board[0][2] eight times. A senior writes a WinStrategy that doesn't know the board size, doesn't know how many symbols it takes to win, and doesn't know whether diagonals count — and then hands three-in-a-row to it as a configuration.

Senior framing: design for the next requirement, not the current one

The most common failure mode on "warm-up" problems is treating them as warm-ups. You implement the literal requirement, ship a working solution, and get downleveled because you demonstrated that you reach for hardcoded constants and nested conditionals when the problem is small. The cost of designing for extensibility upfront is one interface and one strategy class. The benefit is that you've shown the interviewer how you'd write production code when nobody's watching.

Treat Tic Tac Toe like you'd treat a Game module in a real codebase: the grid is a Board, the rule "three-in-a-row horizontally, vertically, or diagonally" is a WinStrategy, players are polymorphic so a bot can replace a human behind the same interface, and every move goes through a history log so replay and undo are free. None of that costs more than the naive version to write. It costs more to think about — which is the whole test.

---

Clarifying Questions

You: What board sizes do I need to support — just 3×3, or should the design generalize?

Interviewer: Start with 3×3. But assume the next ticket is Connect Four on 7×6, and after that Gomoku on 15×15. Design accordingly.

You: Exactly two players, or can there be more?

Interviewer: Two for Tic Tac Toe. But don't hardcode two — the design should accept N.

You: Do I need to support a bot / AI opponent?

Interviewer: Yes, at least a random-move bot. Stub the interface so minimax could slot in later.

You: How are symbols chosen — always X and O, or configurable?

Interviewer: Each player picks a symbol at construction. The board just stores whatever token the player owns.

You: Draw detection — do we declare a draw only when the board is full, or can we detect an "unwinnable" state earlier?

Interviewer: Full board = draw. Don't over-engineer early termination unless it falls out naturally.

You: Undo? Rematch? Move history?

Interviewer: Move history yes — you should be able to replay or serialize a game. Undo is a stretch goal; design so it's easy to add. Rematch means resetting state on the same Game instance, not creating a new one.

You: Is this in-memory only, or do I need to persist games?

Interviewer: In-memory. But mention the serialization story.

You: UI, networking, multiplayer over sockets?

Interviewer: Out of scope. This is a core-game-logic design. Assume a driver calls makeMove synchronously.

You: Should makeMove return a result, throw on invalid moves, or both?

Interviewer: Your call — justify it.

---

Functional Requirements

1. Support a configurable N×M board; default to 3×3.
2. Support 2+ players, each with a unique symbol.
3. Players alternate turns in a fixed order; the game rejects out-of-turn moves.
4. A move places a symbol in an empty cell identified by (row, col).
5. The game detects a win (three-in-a-row horizontally, vertically, or diagonally) immediately after the winning move.
6. The game detects a draw when the board is full and no player has won.
7. Once the game is over (won or drawn), no further moves are accepted.
8. Support human and bot players behind a single Player interface.
9. Maintain a full move history, in order, that can be replayed or serialized.
10. Support rematch: reset the board and history while retaining the same player lineup.

Non-Functional Requirements

1. Latency: a move — including win/draw check — must complete in O(win-length) on the last move, not O(N²). Full-scan win detection is a red flag at senior level.
2. Extensibility: adding Connect Four (gravity-based placement, 4-in-a-row) or Gomoku (larger board, 5-in-a-row) must not require modifying Game, Board, or Player — only adding a new strategy or subclass.
3. Testability: every component must be constructible without the others. WinStrategy should be unit-testable with a plain 2D array. BotPlayer should be unit-testable with a mock board. No hidden singletons.
4. Not in scope: networking, persistence, UI rendering, concurrent multiplayer sessions, authentication, matchmaking, ELO ratings.

---

Core Entities and Relationships

Entity	Responsibility
Game	Orchestrates turn flow. Owns Board, player list, WinStrategy, MoveHistory, and GameState. Accepts moves, validates turn order, triggers win/draw detection, announces the result.
Board	Owns the 2D grid of `Cell
Cell	Value object tying a symbol to its owning player. Immutable.
Position	Value object { row, col }. Immutable.
Player	Abstract — identity (id, name, symbol) plus getNextMove(board): Position.
HumanPlayer	getNextMove reads from an injected input provider. The UI/driver is responsible for producing the position.
BotPlayer	getNextMove runs a MoveStrategy against the board. Random strategy first; minimax later.
WinStrategy	Given a board and the last move, returns `WinResult
LineOfKWinStrategy	Concrete — scans the four lines through the last move and reports a win if any contain K identical symbols.
MoveHistory	Append-only log of Move records. Supports replay and (optionally) undo.
Move	Value object: { player, position, timestamp }.
GameState	Enum: IN_PROGRESS, WON, DRAWN. Transitions are controlled by Game.
MoveResult	Discriminated union returned by Game.makeMove: Placed, Won, Drawn, Rejected(reason).

Relationships: Game has-a Board, has-many Player, has-a WinStrategy, has-a MoveHistory. Player is an interface; HumanPlayer and BotPlayer implement it. BotPlayer has-a MoveStrategy. WinStrategy is an interface; concrete strategies plug in.

---

Interfaces

type Symbol = string; // single character typically, but no need to constrain here

interface Position {
  readonly row: number;
  readonly col: number;
}

interface Cell {
  readonly symbol: Symbol;
  readonly playerId: string;
}

interface Move {
  readonly player: IPlayer;
  readonly position: Position;
  readonly timestamp: number;
}

interface IPlayer {
  readonly id: string;
  readonly name: string;
  readonly symbol: Symbol;
  getNextMove(board: IBoard): Promise<Position> | Position;
}

interface IBoard {
  readonly rows: number;
  readonly cols: number;
  place(pos: Position, cell: Cell): void;
  getAt(pos: Position): Cell | null;
  isInBounds(pos: Position): boolean;
  isEmpty(pos: Position): boolean;
  isFull(): boolean;
  reset(): void;
}

interface WinResult {
  readonly winner: IPlayer;
  readonly winningLine: Position[];
}

interface IWinStrategy {
  check(board: IBoard, lastMove: Move): WinResult | null;
}

interface IMoveStrategy {
  chooseMove(board: IBoard, self: IPlayer): Position;
}

type MoveResult =
  | { kind: "placed"; move: Move }
  | { kind: "won"; move: Move; result: WinResult }
  | { kind: "drawn"; move: Move }
  | { kind: "rejected"; reason: RejectionReason };

type RejectionReason =
  | "out_of_bounds"
  | "cell_occupied"
  | "not_your_turn"
  | "game_over";

interface IGame {
  makeMove(player: IPlayer, pos: Position): MoveResult;
  playTurn(): MoveResult; // convenience: pulls next move from current player
  getState(): GameState;
  getBoard(): IBoard;
  getHistory(): readonly Move[];
  reset(): void;
}

Every external boundary is an interface. Game depends on IPlayer, IBoard, and IWinStrategy — never on concrete HumanPlayer, Board, or LineOfKWinStrategy. That's the seam that lets Connect Four reuse 90% of this code.

---

Class Diagram

                         ┌─────────────────┐
                         │      Game       │
                         ├─────────────────┤
                         │ - board         │
                         │ - players[]     │◆───────────────┐
                         │ - winStrategy   │◆──────┐        │
                         │ - history       │◆──┐   │        │
                         │ - state         │   │   │        │
                         │ - currentIdx    │   │   │        │
                         ├─────────────────┤   │   │        │
                         │ makeMove()      │   │   │        │
                         │ playTurn()      │   │   │        │
                         │ reset()         │   │   │        │
                         └────────┬────────┘   │   │        │
                                  │            │   │        │
                                  │ owns       │   │        │
                                  ▼            │   │        │
                         ┌─────────────────┐   │   │        │
                         │     Board       │   │   │        │
                         ├─────────────────┤   │   │        │
                         │ - grid[][]      │   │   │        │
                         │ - filled count  │   │   │        │
                         └─────────────────┘   │   │        │
                                               │   │        │
                         ┌─────────────────┐   │   │        │
                         │  MoveHistory    │◀──┘   │        │
                         ├─────────────────┤       │        │
                         │ - moves[]       │       │        │
                         │ append/undo/it  │       │        │
                         └─────────────────┘       │        │
                                                   │        │
                  «interface»                      │        │
                  IWinStrategy ◀────────────────────        │
                  ▲                                         │
                  │                                         │
          ┌───────┴────────┐                                │
          │                │                                │
 LineOfKWinStrategy  ConnectFourWin                         │
                                                            │
                  «interface»                               │
                  IPlayer ◀───────────────────────────────────
                  ▲
                  │
          ┌───────┴─────────┐
          │                 │
    HumanPlayer        BotPlayer ◆──── IMoveStrategy
                                         ▲
                                         │
                              ┌──────────┴──────────┐
                              │                     │
                       RandomMoveStrategy   MinimaxStrategy

---

Class Design

Game

State

• board: IBoard
• players: IPlayer[] — order defines turn rotation
• winStrategy: IWinStrategy
• history: MoveHistory
• state: GameState
• currentIdx: number — index into players

Methods

• makeMove(player, pos) — primary entry point. Validates, places, checks for win/draw, updates state, returns MoveResult.
• playTurn() — asks players[currentIdx] for a move, then calls makeMove. Useful for auto-playing bots against bots.
• getState(), getBoard(), getHistory() — read-only views.
• reset() — clears board, history, state; turn pointer returns to player 0.

Design rationale. Game is a facade. It does no rule logic itself — rules live in WinStrategy, placement lives in Board, move generation lives in Player. This is what lets Connect Four reuse the same Game class.

Why does Game hold currentIdx instead of Player? Because index lets us cycle with modular arithmetic (currentIdx = (currentIdx + 1) % players.length) and keeps the turn order implicit in the list. Named turn ownership (currentPlayer: Player) requires a separate ordering structure. Less code, no loss of information.

Board

State

• grid: (Cell | null)[][] — eagerly allocated N×M array.
• filled: number — running count of non-null cells. Avoids O(N²) isFull scans.

Methods

• place(pos, cell) — assumes caller has validated bounds/emptiness. Throws in dev; the public guard lives in Game.
• getAt(pos): Cell | null — null means empty.
• isInBounds(pos), isEmpty(pos), isFull() — constant-time predicates.
• reset() — wipe grid, zero filled.

Design rationale. Two choices to defend:

1. 2D array over bitmask. Bitmasks are faster for 3×3 but don't generalize cleanly to N×M or to multi-symbol games. The 2D array is cache-friendly enough for any realistic board size and reads clearly. A senior candidate picks readable and generalizable unless the interviewer asks for raw speed.
2. Cell | null over sentinel. A null cell is a distinct type from a placed cell. Sentinel values ("" or " ") leak into win-check logic and cause subtle bugs where a "match" compares empty cells. Type safety > micro-optimization.

Player, HumanPlayer, BotPlayer

Player is an interface, not a base class. There's nothing meaningful to share via inheritance — HumanPlayer and BotPlayer produce moves in entirely different ways. Inheritance would add a protected field nobody uses.

HumanPlayer

• State: id, name, symbol, inputProvider: InputProvider (an injected callback or readable stream abstraction).
• getNextMove(board) delegates entirely to the input provider. It does no validation — that's the Game's job.

BotPlayer

• State: id, name, symbol, strategy: IMoveStrategy.
• getNextMove(board) returns strategy.chooseMove(board, this).

Why two strategy interfaces (IWinStrategy + IMoveStrategy)? They answer different questions.

• IWinStrategy.check(board, lastMove) → "did this move end the game?"
• IMoveStrategy.chooseMove(board, self) → "what move should I make?"

Collapsing them into one strategy object fails the single-responsibility test: a bot that picks moves doesn't need to know how to detect wins, and the game's win detector doesn't need to know how to pick moves.

WinStrategy

IWinStrategy.check(board, lastMove) → WinResult | null

Crucial API shape: it takes lastMove, not just the board. That's what enables the O(K) incremental check instead of an O(N²) full scan. A junior writes checkBoard(board); a senior writes checkLastMove(board, move).

LineOfKWinStrategy

• Configuration: k (run length required to win).
• For Tic Tac Toe, k = 3 on a 3×3 board. For Gomoku, k = 5 on 15×15. For Connect Four, k = 4 on 7×6 — but Connect Four also needs a separate ConnectFourWinStrategy or, more elegantly, a gravity-aware board that enforces bottom-up placement and reuses LineOfKWinStrategy for the win check.

Algorithm. For the last move at (r, c), walk in all four directions (horizontal, vertical, two diagonals). For each direction, extend forward and backward counting same-symbol cells. If any direction's run length ≥ k, report a win with the run as the winning line.

Complexity: O(4 · K) = O(K). For Tic Tac Toe that's 12 cell reads per move — faster than the 24 reads a naive full-board scan does on a 3×3 grid, and dramatically faster on 15×15 Gomoku (60 vs 225+ per move).

GameState

enum GameState {
  IN_PROGRESS = "IN_PROGRESS",
  WON = "WON",
  DRAWN = "DRAWN",
}

Transitions are total: IN_PROGRESS → WON, IN_PROGRESS → DRAWN, terminal otherwise. reset() returns any state to IN_PROGRESS.

Some designs add a formal state machine (with StateTransition objects and a transition table). For three states and two transitions it's overkill — but mention the state machine pattern in the interview as the generalization when asked about pause/resume, time-outs, or network disconnects.

MoveHistory

State: moves: Move[].

Methods:

• append(move) — O(1).
• last() — O(1).
• all() — readonly snapshot for serialization.
• pop() — only exposed if undo is enabled; otherwise omit to keep the API honest.
• replay(onMove: (move) => void) — iterate in order; consumer rebuilds state.
• clear() — for rematch.

Why append-only by default? Because history is an audit log, not a working set. Exposing pop() on every history object tempts callers to mutate the past. Make undo an opt-in capability.

---

Key Methods

class Game implements IGame {
  private state: GameState = GameState.IN_PROGRESS;
  private currentIdx = 0;

  constructor(
    private readonly board: IBoard,
    private readonly players: IPlayer[],
    private readonly winStrategy: IWinStrategy,
    private readonly history: MoveHistory = new MoveHistory(),
  ) {
    if (players.length < 2) {
      throw new Error("at least two players required");
    }
    const symbols = new Set(players.map(p => p.symbol));
    if (symbols.size !== players.length) {
      throw new Error("players must have unique symbols");
    }
  }

  makeMove(player: IPlayer, pos: Position): MoveResult {
    if (this.state !== GameState.IN_PROGRESS) {
      return { kind: "rejected", reason: "game_over" };
    }
    if (player.id !== this.currentPlayer().id) {
      return { kind: "rejected", reason: "not_your_turn" };
    }
    if (!this.board.isInBounds(pos)) {
      return { kind: "rejected", reason: "out_of_bounds" };
    }
    if (!this.board.isEmpty(pos)) {
      return { kind: "rejected", reason: "cell_occupied" };
    }

    const cell: Cell = { symbol: player.symbol, playerId: player.id };
    this.board.place(pos, cell);
    const move: Move = { player, position: pos, timestamp: Date.now() };
    this.history.append(move);

    // Incremental win check on the last move — O(K), not O(N·M).
    const winResult = this.winStrategy.check(this.board, move);
    if (winResult) {
      this.state = GameState.WON;
      return { kind: "won", move, result: winResult };
    }

    if (this.board.isFull()) {
      this.state = GameState.DRAWN;
      return { kind: "drawn", move };
    }

    this.advanceTurn();
    return { kind: "placed", move };
  }

  playTurn(): MoveResult {
    if (this.state !== GameState.IN_PROGRESS) {
      return { kind: "rejected", reason: "game_over" };
    }
    const player = this.currentPlayer();
    const pos = player.getNextMove(this.board) as Position;
    return this.makeMove(player, pos);
  }

  getState(): GameState { return this.state; }
  getBoard(): IBoard { return this.board; }
  getHistory(): readonly Move[] { return this.history.all(); }

  reset(): void {
    this.board.reset();
    this.history.clear();
    this.state = GameState.IN_PROGRESS;
    this.currentIdx = 0;
  }

  private currentPlayer(): IPlayer {
    return this.players[this.currentIdx];
  }

  private advanceTurn(): void {
    this.currentIdx = (this.currentIdx + 1) % this.players.length;
  }
}

class LineOfKWinStrategy implements IWinStrategy {
  constructor(private readonly k: number) {}

  check(board: IBoard, lastMove: Move): WinResult | null {
    const { row, col } = lastMove.position;
    const symbol = lastMove.player.symbol;
    const directions: Array<[number, number]> = [
      [0, 1],   // horizontal
      [1, 0],   // vertical
      [1, 1],   // diagonal ↘
      [1, -1],  // anti-diagonal ↙
    ];

    for (const [dr, dc] of directions) {
      const line: Position[] = [{ row, col }];

      // extend forward
      let r = row + dr, c = col + dc;
      while (this.matches(board, r, c, symbol)) {
        line.push({ row: r, col: c });
        r += dr; c += dc;
      }
      // extend backward
      r = row - dr; c = col - dc;
      while (this.matches(board, r, c, symbol)) {
        line.unshift({ row: r, col: c });
        r -= dr; c -= dc;
      }

      if (line.length >= this.k) {
        return { winner: lastMove.player, winningLine: line.slice(0, this.k) };
      }
    }
    return null;
  }

  private matches(board: IBoard, r: number, c: number, symbol: Symbol): boolean {
    const pos = { row: r, col: c };
    if (!board.isInBounds(pos)) return false;
    const cell = board.getAt(pos);
    return cell !== null && cell.symbol === symbol;
  }
}

class Board implements IBoard {
  private grid: (Cell | null)[][];
  private filled = 0;

  constructor(public readonly rows: number, public readonly cols: number) {
    this.grid = Array.from({ length: rows }, () => Array(cols).fill(null));
  }

  place(pos: Position, cell: Cell): void {
    if (!this.isInBounds(pos)) throw new Error("place: out of bounds");
    if (this.grid[pos.row][pos.col] !== null) throw new Error("place: cell occupied");
    this.grid[pos.row][pos.col] = cell;
    this.filled++;
  }

  getAt(pos: Position): Cell | null {
    if (!this.isInBounds(pos)) return null;
    return this.grid[pos.row][pos.col];
  }

  isInBounds(pos: Position): boolean {
    return pos.row >= 0 && pos.row < this.rows && pos.col >= 0 && pos.col < this.cols;
  }

  isEmpty(pos: Position): boolean {
    return this.isInBounds(pos) && this.grid[pos.row][pos.col] === null;
  }

  isFull(): boolean {
    return this.filled === this.rows * this.cols;
  }

  reset(): void {
    for (let r = 0; r < this.rows; r++) {
      for (let c = 0; c < this.cols; c++) this.grid[r][c] = null;
    }
    this.filled = 0;
  }
}

Read the makeMove flow carefully. Every rejection is a typed reason, not a thrown exception. Exceptions for "cell already taken" are hostile to callers — makeMove is called by bots in a loop, and forcing bots into try/catch to handle a normal gameplay branch is poor API design. Invalid programmer states (negative board size, duplicate symbols at construction) still throw, because those represent bugs.

---

Design Decisions & Tradeoffs

Board representation

Representation	Pros	Cons
2D array Cell[][]	Readable; generalizes to any N×M; easy to iterate	Slightly more memory than bitmask
Flat array Cell[] with row-major indexing	Same asymptotics; better cache behavior; one allocation	Index math everywhere; harder to read
Bitmask per player (two numbers for 3×3)	Fastest; win check is one bitwise AND against masks	Doesn't scale beyond ~64 cells per player; hardcodes symbol count
Sparse map Map<"r,c", Cell>	Memory-efficient for huge mostly-empty boards (e.g., Go)	Hashing overhead; isFull is bookkeeping not geometry

Choice: 2D array. The bitmask version is faster only for 3×3. At Gomoku size it's strictly worse. For a design that's explicitly meant to generalize, the 2D array is the obviously correct choice.

Win detection

Approach	Complexity per move	Notes
Full-board scan each move	O(N · M · K) or O(N²) for square boards	Dead simple; fine for 3×3 only
Scan all N+M+2 lines	O((N + M) · K)	Better but still wasteful — most lines don't touch the last move
Incremental check from last move	O(K)	Only four directions, each up to K cells
Precomputed line index per cell	O(L · K) where L = lines through the cell (≤4)	Same as incremental in practice; worth the complexity only if you also need "could-this-player-still-win" queries

Choice: incremental check from last move. O(K) per move is optimal because a winning run must pass through the last move — no other cell's state changed. Expressing this correctly is a senior signal.

Player polymorphism

Design	Pros	Cons
Player as abstract class; HumanPlayer/BotPlayer extend	Can share common fields	Nothing real to share; inheritance hierarchy for three shared strings is overkill
IPlayer interface; concrete implementations	Testable, composable, no inheritance	Slight duplication of id/name/symbol fields
Single Player class with `type: "human"	"bot"` and a callback	Terse

Choice: interface with concrete implementations. Adding RemotePlayer (reads moves from a websocket) or ReplayPlayer (reads from a recorded history) becomes a pure addition — no edits to Game, Board, or existing players. Textbook open-closed.

Turn enforcement

Design	Notes
Game validates player.id === currentPlayer.id on every move	Defensive; catches bugs in driver code
Game pulls the move itself via currentPlayer.getNextMove()	Cleaner for auto-play; makeMove(player, pos) can become private

Choice: expose both. makeMove(player, pos) is the externally-driven API (used by UIs that accept events); playTurn() is the auto-driven API (used by bot tournaments, tests, replays). Both route through the same validation core.

Error shape

Choice	Tradeoff
Throw on invalid moves	Simple call sites for success path; forces try/catch in bot loops
Return discriminated union MoveResult	Explicit at call sites; verbose for callers that don't care; ideal for bot/tournament code
Return boolean, separate lastError	Worst of both worlds

Choice: discriminated union. Invalid moves are expected in normal gameplay (a bot might probe cells). Exceptions should be for invariant violations, not control flow.

---

Patterns Used

Strategy — IWinStrategy. The whole extensibility story hinges on this. Game asks a WinStrategy whether the last move was a winner, and doesn't care whether that's "3 in a row anywhere" (Tic Tac Toe), "4 in a row with gravity" (Connect Four), "5 in a row unbroken" (Gomoku), or "two-thirds majority of flipped disks" (Othello). The strategy lets us swap game rules without touching the orchestrator.

Strategy — IMoveStrategy. BotPlayer composes a move strategy rather than subclassing. A random bot and a minimax bot are the same class with different strategies injected. This is how you avoid the RandomBot/MinimaxBot/MctsBot class explosion.

State — GameState + Game. Even at three states, the state machine is load-bearing: every entry to makeMove gates on state === IN_PROGRESS, and the state transition is the only place state is written. If you later add PAUSED, TIMEOUT, FORFEITED, the central gate is where you extend. Junior candidates often scatter if (gameOver) return checks; senior candidates centralize.

Command / Memento — MoveHistory. Each Move is a command record: who did what, where, when. Replay is "re-execute in order." Undo (if we add it) is "pop the last move, clear the cell, flip state back to IN_PROGRESS, decrement filled, rewind currentIdx." The command log also gives us free serialization: persisting a game is persisting its move list.

Factory (implied) — GameBuilder. Not shown in the key methods but worth naming: construction of Game takes four collaborators, and in real code you'd front it with a builder: GameBuilder.ticTacToe().withPlayers(a, b).build(). Keeps wiring centralized and enforces constraints (K must be ≤ min(rows, cols), symbols must be unique).

Facade — Game. Game is a facade over Board + WinStrategy + MoveHistory + turn management. External callers never touch those collaborators directly through the Game API.

---

Concurrency Considerations

For single-user local play the game is strictly turn-based and single-threaded — no locks needed.

Online multiplayer changes the picture, but only modestly:

• Turn locking. makeMove must reject moves from the wrong player. We already do this (not_your_turn). In a distributed setting the authoritative Game instance lives on one server; players send intents over the wire and the server applies them serially. That's a queue, not a lock.
• Concurrent rematch + final move. If two clients hit "rematch" while a third final move is in flight, you want reset and makeMove to be serialized. A single mutex around Game mutating methods suffices — makeMove, playTurn, reset all acquire it.
• What you never need. Lock-free data structures, CAS operations, optimistic concurrency on the board. Tic Tac Toe's move volume is so low that any serialization scheme works.

Don't volunteer a lecture on AtomicReference here. Mention it if asked about online play, and be specific: the lock is at the Game boundary, not per-cell.

---

Scale & Extensibility

The whole design exists to make these follow-ups cheap. The interviewer will ask.

Connect Four. Add a GravityBoard extends Board whose place(pos, cell) ignores the row in pos and drops the piece to the lowest empty row in pos.col. Reuse LineOfKWinStrategy with k = 4. That's it — Game, Player, MoveHistory are unchanged. The column-only input is a UI concern; from the engine's perspective the UI sends a column and the board figures out the row.

Gomoku. Same Board, same LineOfKWinStrategy with k = 5, change the constructor to new Board(15, 15). If the variant forbids overlines (runs > 5 don't count as wins), add a StrictLineOfKWinStrategy that enforces exact length.

n×n board with variable K. Already supported — Board(n, n) and LineOfKWinStrategy(k). No code changes.

> 2 players. Already supported — players is a list, not a pair. The win check logic is per-symbol, so more symbols just means more distinct wins possible.

Online multiplayer. Wrap Game behind a server. Each player is a RemotePlayer whose getNextMove awaits a websocket message. Add a lock at the Game boundary. Add a serializer that emits the move history as JSON for reconnect/resume.

AI opponent. New IMoveStrategy implementations:

• RandomMoveStrategy — pick any empty cell uniformly. Baseline.
• MinimaxStrategy — recursion over empty cells, alternating min/max, scoring terminal states via winStrategy. For 3×3 the full tree is ~255k nodes — trivial. For larger boards, add alpha-beta pruning and depth limits.
• MCTSStrategy — Monte Carlo tree search for Gomoku-sized boards.

None of these require changes to Game, Board, or Player. They plug into BotPlayer.

Replay. MoveHistory.replay iterates moves in order. Deserialize a recorded game by constructing a fresh Game with the same player lineup and calling makeMove for each recorded position. Serialize by exporting history.all().

Undo/Redo. Expose Game.undo():

undo(): void {
  const last = this.history.pop();
  if (!last) return;
  this.board.clear(last.position);    // new Board method
  this.state = GameState.IN_PROGRESS;
  this.currentIdx = this.players.indexOf(last.player);
}

For redo, keep a parallel redo stack that makeMove clears on any new move (same pattern as the text editor's undo/redo).

Time controls. Wrap playTurn in a timeout. On expiry, either (a) forfeit the current player, transitioning state to WON for the opponent, or (b) auto-make a random move. Cleanly modeled as a new state TIMEOUT plus an extended state machine.

---

Edge Cases

1. First move. Empty board, state is IN_PROGRESS, currentIdx = 0. No special case in code — the general path handles it.
2. Last move fills the board and wins simultaneously. Win check runs before full check, so WON takes precedence over DRAWN. Correct: a winning move is a win even if it happens to be the 9th move.
3. Last move fills the board without a win. isFull() returns true after filled++; state transitions to DRAWN.
4. Out-of-bounds move. Returns { kind: "rejected", reason: "out_of_bounds" }. Turn pointer does not advance — the current player tries again.
5. Move on occupied cell. Returns { kind: "rejected", reason: "cell_occupied" }. Turn does not advance.
6. Move after game over. Returns { kind: "rejected", reason: "game_over" }. state is terminal; only reset() gets you out.
7. Out-of-turn move. Returns { kind: "rejected", reason: "not_your_turn" }. Common when a UI lets both players click: the game is the source of truth.
8. Simultaneous wins. Cannot occur in standard Tic Tac Toe — a move creates at most one new completed line for one symbol. Clarify this up front and move on; don't spend time designing against an impossibility. The LineOfKWinStrategy returns the first direction that meets the length threshold, and that direction is the one containing the last-placed symbol — so even if you were paranoid, it'd be correct.
9. Two symbols shared between players. Rejected at Game construction.
10. k > min(rows, cols). Winnable only along diagonals; if k > max(rows, cols) the game can never be won. Validate in the builder; warn the interviewer that the configuration is trivially drawable.
11. Bot loops on an invalid move. If BotPlayer.getNextMove returns an occupied cell, makeMove rejects. If the driver (playTurn) doesn't handle the rejection, you get an infinite loop. The driver must either re-prompt the bot or treat repeated rejections as a forfeit. Document this contract.
12. Rematch mid-game. reset() is always legal. State returns to IN_PROGRESS; history and board clear.

---

Follow-up Questions

Q: How would you add AI / minimax? A: BotPlayer already composes an IMoveStrategy. Implement MinimaxStrategy whose chooseMove recursively simulates moves on a cloned board (add Board.clone()), scoring terminal states as +∞/-∞/0 via the existing WinStrategy. For 3×3 the full tree is small; for larger boards add alpha-beta pruning and a depth limit with a heuristic evaluation function. No changes to Game, Board, or Player.

Q: How would you support Connect Four? A: Add GravityBoard (extends Board; place drops to lowest empty row in the target column). Reuse LineOfKWinStrategy with k = 4 and rows=7, cols=6. The UI sends column-only moves; Game is unchanged.

Q: How would you persist game state? A: Serialize three things: the player lineup (ids, names, symbols, types), the move history (history.all()), and the game configuration (board dims, k). On load, reconstruct a fresh Game and replay the moves. This is more robust than serializing the board directly because it validates the moves through the same rules engine — a corrupted save file fails visibly instead of silently loading an illegal state.

Q: How would you add an online multiplayer mode? A: Authoritative server owns the Game. Clients send { playerId, position } intents; server calls game.makeMove and broadcasts MoveResult to all clients. RemotePlayer implements IPlayer and receives moves over a websocket. Add a mutex at the Game boundary to serialize makeMove/reset. Handle reconnects by replaying history over the socket.

Q: How would you replay a game? A: MoveHistory.replay((move) => applyToView(move)) iterates in order. The engine itself can replay by constructing a fresh Game with the same lineup and calling makeMove for each move in order. For UI playback, emit each Move to a timeline component with a configurable delay.

Q: What changes for n×n? A: Nothing in Board or Game — rows and cols are constructor parameters. LineOfKWinStrategy is parameterized on k. The only changes are at the builder/configuration layer.

Q: How would you detect a draw efficiently? A: Keep a filled counter on Board, incremented on place and zeroed on reset. isFull() is then filled === rows * cols — O(1). Draw detection is "win check returned null AND isFull." No board scan needed.

Q: How would you handle undo/redo? A: Mirror the text editor's command stack model. Push each successful move onto an undo stack; on undo(), pop the last move, clear its cell, decrement filled, flip state back to IN_PROGRESS, rewind currentIdx, and push onto a redo stack. Any new makeMove clears the redo stack. Add a Board.clear(pos) method (currently absent) to support the reverse operation.

Q: How do you keep the API stable while rules evolve? A: The IGame interface exposes only makeMove, playTurn, getState, getBoard, getHistory, reset. Rule variants (Tic Tac Toe, Connect Four, Gomoku, Wild TTT) are configurations of collaborators — they don't change the interface. That's the contract.

Q: What if the interviewer asks you to avoid the Strategy pattern entirely? A: I'd push back once: the whole extensibility story hinges on it, and the alternative — subclassing Game per variant — duplicates turn management and invariants across variants. If they insist (e.g., "no runtime polymorphism"), I'd use template-method-style hooks on a generic AbstractGame<Rules> where Rules is a compile-time type parameter. Same structural idea, different binding time.

---

SDE2 vs SDE3 — How the Bar Rises

Dimension	SDE2-acceptable answer	SDE3-expected answer
Abstraction	Correctly separates Game, Board, Player.	Adds IWinStrategy, IMoveStrategy, MoveHistory as first-class interfaces, and can articulate which follow-up each seam supports.
Win-check complexity	Full-board scan or 8-line scan after every move; "it's only 3×3, doesn't matter."	Incremental O(K) check from the last move, with explanation tying it to why the last move is the only cell whose state changed.
Extensibility	"I could add Connect Four by subclassing Game."	"Connect Four is a GravityBoard and reusing LineOfKWinStrategy(k=4). Game doesn't change. Here's the two-class delta."
Concurrency awareness	"Single-threaded, no concurrency needed."	"Local play single-threaded. Online play serializes at the Game boundary — one mutex, not per-cell. Mentions the state transition races on rematch."
Error handling	Throws on invalid moves.	Discriminated union for in-domain rejections (occupied, out of bounds, out of turn, game over); throws only on constructor-time invariants and programmer bugs. Articulates why bots shouldn't try/catch normal gameplay.
Naming	checkWin(board), player1, player2, makeMove(row, col).	IWinStrategy.check(board, lastMove), players: IPlayer[], makeMove(player, Position). Names encode the contract.
Tradeoff articulation	States a choice.	States the choice, names the alternatives, quantifies where each wins, and picks based on the stated requirements — not gut feel.
State modeling	Boolean gameOver, boolean draw.	Explicit GameState enum with a documented transition table; extension path to PAUSED/TIMEOUT/FORFEITED pre-thought.
Testability	"I'd write tests."	Every collaborator constructs independently. LineOfKWinStrategy tested with a plain 2D array and a synthesized Move. BotPlayer tested with a mock IBoard. No hidden statics, no time dependency outside the injectable clock.
Scope discipline	Goes down a minimax rabbit hole unprompted.	Builds the core cleanly, names minimax/MCTS/CRDT as slot-in extensions, returns to the core until prompted.
The "it's just Tic Tac Toe" trap	Treats it as trivial; ships hardcoded 3×3 logic.	Recognizes that the interviewer is testing whether you'd design this way even when you don't have to — and gets downleveled if you don't.