Tic-Tac-Toe

“Design tic-tac-toe.” A hard-coded 3×3 loop can pass a demo, but the interview payoff is whether turns, illegal moves, and win rules still have clear owners when the board becomes N×N and the target becomes K in a row. We will design that extension deliberately without turning a small game into a framework.

Requirements

The familiar game gives us a small surface and several strict invariants. Write them down before choosing classes.

An AI opponent, networking, a GUI, persistent match history, replay, undo, rankings, and matchmaking are out of scope. “Connect-style” means configurable K-in-a-row here; gravity and column-only placement are not silently included.

Clarifying questions to ask

These questions look small, but each closes an ambiguity that would otherwise become a late conditional.

• Is the board fixed at 3×3? No. The engine accepts an N×N board and a target K, with 3 <= K <= N. We will run the usual 3×3 game as one configuration.
• Does K-in-a-row mean contiguous marks? Yes. A gap breaks the line. A run longer than K still wins because it contains a contiguous run of K.
• Which directions count? Horizontal, vertical, the descending diagonal, and the rising diagonal. Only lines through the most recent move can have become winners.
• Does “Connect-style” include gravity? Not in this version. Players choose a row and column directly. If gravity is requested later, a move-placement policy can translate a column choice into the lowest free row before Board.place().
• Are both players human? Yes. The core receives player IDs and coordinates; it does not prompt a person or choose a move. A computer move selector can be added at the boundary later.
• Who goes first and how are marks assigned? The first Player passed to Game starts. The two players must have distinct non-empty symbols, so setup cannot create X versus X.
• What happens after an illegal move? The method throws a domain error and the turn does not advance. An HTTP or UI adapter may translate that error into a user-facing result without weakening the core invariant.
• How should the winner be reported? Game.move() returns a structured MoveResult with status, the player who placed the mark, an optional winner, and the optional next player. The core does not print messages.
• When do we test for a draw? After testing for a win. The last empty cell may both fill the board and complete a winning line; a win must not be mislabeled as a draw.
• Do we need replay or multiple rounds? No. Construct a new Game for a new round. If replay arrives, record immutable moves; do not expose the mutable cell matrix.
• Can two clients submit moves concurrently? The in-memory skeleton assumes serialized calls. A networked version would use a game version or transaction so two requests cannot both play the same turn.
• Are coordinates zero-based? Yes inside the model. A UI may display 1–3 or chess-like labels and translate them at the boundary.

Entity extraction

On the noun pass, mark the domain vocabulary before deciding what survives as a class:

1. A game has two players, a current turn, a status, and an optional winner.
2. A board contains N×N cells addressed by a row and column.
3. Each player owns a distinct symbol; each cell contains X, O, or empty.
4. A move proposes a position for the current player's symbol.
5. A win rule checks whether the latest move completes K contiguous symbols.

Sort the nouns by identity, behavior, and lifecycle:

Move does not earn a class yet. The game needs only the latest { row, column }, and replay is excluded. If moves later gain timestamps, audit identity, undo, or persistence, that relationship starts carrying enough data for a real Move entity.

Now assign verbs to the object that owns the required data and invariant:

The split matters during failure. Game verifies the lifecycle and current player, then calls Board.place(). Only after that call succeeds does it check the win and advance the turn. An occupied cell therefore cannot consume a turn.

Core class diagram

The core needs seven types. GameStatus and the { row, column } position stay as fields and values, keeping the diagram focused on collaboration.

WinStrategy uses the Strategy pattern: Game receives an interchangeable rule object. That seam is justified because the prompt explicitly asks for K-in-a-row extensibility. If the only product requirement were fixed 3×3 tic-tac-toe forever, a private Game.hasWon() method would be a smaller honest design.

Cell may look tiny, but it owns a useful invariant: a mark cannot be overwritten. The board keeps the two-dimensional structure and boundary check; the cell keeps its one-way state transition.

Critical-flow sequence diagram

The critical flow is “make a move and check for a win.” Follow a legal winning move from the player to the result.

The sequence shows the winning branch. If Cell.place() rejects an occupied square, the placement return and every win-check message disappear, while Game.current remains unchanged. If the checker returns false, Game asks Board.isFull() before either declaring a draw or switching players.

TypeScript skeleton

The code uses a directional win check. Starting at the latest mark, it counts matching symbols in both directions on each of four axes. That makes the work proportional to K rather than to all N² cells. The small BoardView contract exposes only queries to the win policy, so the policy cannot call place().

export {};
 
enum Symbol {
  Empty = ".",
  X = "X",
  O = "O",
}
 
enum GameStatus {
  InProgress = "in-progress",
  Won = "won",
  Draw = "draw",
}
 
interface Position {
  readonly row: number;
  readonly col: number;
}
 
interface MoveResult {
  readonly status: GameStatus;
  readonly placedBy: string;
  readonly winner: string | null;
  readonly nextPlayer: string | null;
}
 
class Player {
  public constructor(
    public readonly id: string,
    public readonly name: string,
    public readonly symbol: Symbol,
  ) {
    if (id.trim().length === 0 || name.trim().length === 0) {
      throw new Error("player id and name are required");
    }
 
    if (symbol === Symbol.Empty) {
      throw new Error("a player needs a non-empty symbol");
    }
  }
}
 
class Cell {
  private symbol = Symbol.Empty;
 
  public get value(): Symbol {
    return this.symbol;
  }
 
  public place(symbol: Symbol): void {
    if (symbol === Symbol.Empty) {
      throw new Error("cannot place the empty symbol");
    }
 
    if (this.symbol !== Symbol.Empty) {
      throw new Error("cell is already occupied");
    }
 
    this.symbol = symbol;
  }
}
 
interface BoardView {
  readonly size: number;
  isInside(row: number, col: number): boolean;
  symbolAt(row: number, col: number): Symbol;
}
 
class Board implements BoardView {
  public readonly size: number;
  private readonly cells: readonly (readonly Cell[])[];
 
  public constructor(size: number) {
    if (!Number.isInteger(size) || size < 3) {
      throw new Error("board size must be an integer of at least 3");
    }
 
    this.size = size;
    this.cells = Array.from(
      { length: size },
      () => Array.from({ length: size }, () => new Cell()),
    );
  }
 
  public isInside(row: number, col: number): boolean {
    return (
      Number.isInteger(row) &&
      Number.isInteger(col) &&
      row >= 0 &&
      row < this.size &&
      col >= 0 &&
      col < this.size
    );
  }
 
  public place(row: number, col: number, symbol: Symbol): void {
    this.cellAt(row, col).place(symbol);
  }
 
  public symbolAt(row: number, col: number): Symbol {
    return this.cellAt(row, col).value;
  }
 
  public isFull(): boolean {
    return this.cells.every((row) =>
      row.every((cell) => cell.value !== Symbol.Empty),
    );
  }
 
  public snapshot(): readonly (readonly Symbol[])[] {
    return this.cells.map((row) =>
      row.map((cell) => cell.value),
    );
  }
 
  private cellAt(row: number, col: number): Cell {
    if (!this.isInside(row, col)) {
      throw new Error(`position (${row}, ${col}) is outside the board`);
    }
 
    return this.cells[row][col];
  }
}
 
interface WinStrategy {
  hasWon(
    board: BoardView,
    lastMove: Position,
    symbol: Symbol,
    target: number,
  ): boolean;
}
 
class ConnectKWinStrategy implements WinStrategy {
  private static readonly directions: readonly (
    readonly [number, number]
  )[] = [
    [0, 1],
    [1, 0],
    [1, 1],
    [1, -1],
  ];
 
  public hasWon(
    board: BoardView,
    lastMove: Position,
    symbol: Symbol,
    target: number,
  ): boolean {
    for (const [rowStep, colStep] of
      ConnectKWinStrategy.directions) {
      const connected =
        1 +
        this.countDirection(
          board,
          lastMove,
          symbol,
          rowStep,
          colStep,
          target,
        ) +
        this.countDirection(
          board,
          lastMove,
          symbol,
          -rowStep,
          -colStep,
          target,
        );
 
      if (connected >= target) {
        return true;
      }
    }
 
    return false;
  }
 
  private countDirection(
    board: BoardView,
    origin: Position,
    symbol: Symbol,
    rowStep: number,
    colStep: number,
    target: number,
  ): number {
    let count = 0;
 
    for (let distance = 1; distance < target; distance += 1) {
      const row = origin.row + rowStep * distance;
      const col = origin.col + colStep * distance;
 
      if (
        !board.isInside(row, col) ||
        board.symbolAt(row, col) !== symbol
      ) {
        break;
      }
 
      count += 1;
    }
 
    return count;
  }
}
 
class Game {
  private readonly board: Board;
  private readonly players: readonly [Player, Player];
  private readonly target: number;
  private readonly winStrategy: WinStrategy;
  private currentIndex = 0;
  private status = GameStatus.InProgress;
  private winner: Player | null = null;
 
  public constructor(
    boardSize: number,
    players: readonly [Player, Player],
    target: number,
    winStrategy: WinStrategy,
  ) {
    const board = new Board(boardSize);
 
    if (!Number.isInteger(target) || target < 3 || target > board.size) {
      throw new Error("target must be an integer from 3 through board size");
    }
 
    if (players[0].id === players[1].id) {
      throw new Error("players need distinct ids");
    }
 
    if (players[0].symbol === players[1].symbol) {
      throw new Error("players need distinct symbols");
    }
 
    this.board = board;
    this.players = [players[0], players[1]];
    this.target = target;
    this.winStrategy = winStrategy;
  }
 
  public get currentPlayer(): Player {
    return this.players[this.currentIndex];
  }
 
  public boardSnapshot(): readonly (readonly Symbol[])[] {
    return this.board.snapshot();
  }
 
  public move(
    playerId: string,
    row: number,
    col: number,
  ): MoveResult {
    if (this.status !== GameStatus.InProgress) {
      throw new Error("game is already over");
    }
 
    const player = this.currentPlayer;
    if (player.id !== playerId) {
      throw new Error(`it is ${player.name}'s turn`);
    }
 
    this.board.place(row, col, player.symbol);
 
    const won = this.winStrategy.hasWon(
      this.board,
      { row, col },
      player.symbol,
      this.target,
    );
 
    if (won) {
      this.status = GameStatus.Won;
      this.winner = player;
      return this.resultFor(player);
    }
 
    if (this.board.isFull()) {
      this.status = GameStatus.Draw;
      return this.resultFor(player);
    }
 
    this.currentIndex = 1 - this.currentIndex;
    return this.resultFor(player);
  }
 
  private resultFor(placedBy: Player): MoveResult {
    return {
      status: this.status,
      placedBy: placedBy.name,
      winner: this.winner?.name ?? null,
      nextPlayer:
        this.status === GameStatus.InProgress
          ? this.currentPlayer.name
          : null,
    };
  }
}
 
const ada = new Player("p1", "Ada", Symbol.X);
const lin = new Player("p2", "Lin", Symbol.O);
const game = new Game(
  3,
  [ada, lin],
  3,
  new ConnectKWinStrategy(),
);
 
game.move("p1", 0, 0);
game.move("p2", 1, 0);
game.move("p1", 0, 1);
game.move("p2", 1, 1);
const result = game.move("p1", 0, 2);
 
const boardText = game
  .boardSnapshot()
  .map((row) => row.join(" "))
  .join("\n");
 
console.log(boardText);
console.log(`${result.status}: ${result.winner}`);

X X X O O . . . . won: Ada

The fifth move wins across row zero. Game checks that result before checking Board.isFull(), stores Ada as the winner, and returns no next player because the lifecycle is terminal.

Generalizing N and K was not speculative here; it was an explicit requirement. The design generalizes only the dimensions and winning rule. It does not invent tournaments, spectators, persistence, or a universal board-game engine.

Design-review checklist

Expect the interviewer to test the seams, not only the happy-path output.

• 3×3 to N×N and K-in-a-row: N and K are validated configuration, all loops use board size or target, and no winning line is hard-coded to three cells. This early generalization is justified by the prompt; without that requirement, fixed 3×3 code would be simpler.
• Meaning of a line: Confirm contiguity, four axes, whether runs longer than K win, and whether wraparound is forbidden. The skeleton answers yes, four, yes, and yes respectively, but a different interview assumption changes tests.
• Efficient win checks: A full scan costs O(N²) after each move. The directional check costs at most O(K) work on each of four axes because only a line through the latest mark can become new. For very large boards, cached segment counts trade faster reads for more update complexity.
• Illegal-move ownership: Game rejects wrong turns and terminal games; Board rejects coordinates; Cell rejects overwrites. Because the turn changes only after placement and rule checks, every rejected move leaves match state untouched.
• Errors versus result values: Exceptions make invalid commands loud in this skeleton. A UI-heavy application may return a MoveAccepted | MoveRejected result instead. Keep the invariant location the same even if the transport shape changes.
• Terminal-state edge cases: Check win before draw on the last empty cell. Reject every move after won or drawn status. Preserve the winner as lifecycle state rather than recomputing it for every result.
• Adding a computer player: Add a move-selection Strategy that receives a read-only board view and returns a position. Feed that choice through the same Game.move() method, so AI code cannot bypass turns, bounds, or occupancy. WinStrategy should not choose moves; it answers a different question.
• Adding gravity: A Connect Four-style rule changes legal placement, not only win detection. Introduce a placement or move policy that maps a column to a cell, then keep Board as the state owner. Do not hide gravity inside the win checker.
• Separating rules from I/O: Game returns data and domain errors. Prompts, buttons, JSON, coordinate labels, and victory text belong in adapters. This separation makes the entire move sequence testable without capturing console output.
• Concurrent clients: A network service should serialize commands per game or update only when a stored version matches the client's version. Otherwise, two requests can both pass “current player” against stale state.
• Replay and undo: If required, introduce an immutable Move log. Replay folds moves through a fresh game; undo may use the Command or Memento pattern, but only after rules define who may undo and whether a finished game can reopen.
• Testing the rule matrix: Cover both diagonals, horizontal and vertical wins, K smaller than N, a run longer than K, gaps, corners, out-of-range coordinates, occupied cells, wrong players, draw on the last move, win on the last move, and invalid N/K setup.
• With more time: Add typed domain-error codes, an injected game ID, persistence with optimistic locking, and generated-game tests that assert marks never disappear and turns alternate after every accepted move.

The final design is small because each rule has a precise owner: Game controls the match, Board and Cell protect placement, and WinStrategy answers one configurable question. That is the machine-coding habit to carry into larger case studies: generalize where the requirement applies pressure, and keep everything else concrete.