11 — Problem: Connect Four

Understanding the Problem

Connect Four is a two-player board game on a 7-column by 6-row grid. Players alternate dropping discs of their color into a column; the disc falls to the lowest empty row in that column thanks to gravity. The first player to align four of their discs — horizontally, vertically, or diagonally — wins. Full board with no alignment is a draw.

On the surface it looks like Tic Tac Toe with a bigger board. It isn't. Two things change the design:

Gravity. A player names a column, not a cell. The cell is computed. That means move validation splits from move execution, and "this cell is legal" becomes "this column has room."
Directional, windowed win check. Tic Tac Toe has 8 winning lines — you scan all of them. Connect Four has roughly 70 possible 4-in-a-row windows. Scanning them all on every move is wasteful. The interesting algorithm is checking the four directions radiating from the piece we just dropped, which is O(1) — bounded by the win length, not the board size.

The interview meta — why this problem shows up

Connect Four is almost never asked in a vacuum. It appears as the second problem after Tic Tac Toe, and the interviewer is watching for one specific thing: do you rewrite the game from scratch, or do you reuse the chassis you just built?

An SDE2 who has just designed TTT with a Game loop, a Board interface, a WinStrategy, and a Player and then re-implements all four for Connect Four has failed a soft test. The signal the interviewer wants is: "the parts that change are the rule classes (how moves are placed, how wins are detected). The orchestration is already correct." That's the mental move this writeup is built around.

If the interviewer opens with Connect Four directly, the same reasoning still applies — you describe what the shared chassis would look like if TTT came first, and you justify why this problem's variant points plug in cleanly.

Clarifying Questions

You: Standard 7 columns by 6 rows, or should I make dimensions configurable?

Interviewer: Default to 7×6 but the code should accept any rows × cols at construction time.

You: Win length fixed at 4, or configurable? I ask because the same engine could power Gomoku (5-in-a-row) or TTT (3-in-a-row).

Interviewer: Configurable. Default 4. Assume winLength <= min(rows, cols).

You: When a player drops into a full column, do we reject the move, throw, or let the turn pass?

Interviewer: Reject — throw an InvalidMoveException (or return a result flag). Same player tries again. Turn doesn't advance.

You: Can a player drop multiple discs per turn, or always exactly one?

Interviewer: Exactly one. No power-ups, no multi-drops.

You: Exactly two players, or should I support N?

Interviewer: Two for now. But keep the door open for more — there are 4-player variants on bigger boards.

You: Is animation or UI in scope? Rendering the board, showing the disc falling?

Interviewer: Out of scope. A render() method that returns a text grid is enough — enough for tests and console demos.

You: Network play? Online multiplayer?

Interviewer: Out of scope. Single-process, turn-based, local. But mention briefly how the design accommodates it.

You: Undo a move?

Interviewer: Not required for core. Call it out as a follow-up.

You: AI opponent?

Interviewer: Out of scope. Assume both players are human.

What I'm taking away

Dimensions and win length are parameters, not constants.
drop(col, player) is the core operation. Validation and placement are separate responsibilities.
The win check runs after a successful drop and needs to know which cell was just filled.
No UI, no network, no AI, no undo — but the design should not forbid them.

Functional Requirements

Create a game with configurable rows, cols, winLength, and an ordered list of players.
drop(column) places the current player's disc at the lowest empty row of that column. Advances turn on success.
If the column is full or index is out of range, reject the move without advancing the turn.
After each successful drop, detect: win (four-in-a-row for the player who just moved), draw (board full, no win), or continue.
Expose the current player, the current game state (IN_PROGRESS | WON | DRAW), the winner if any, and a way to render the board.
The game refuses further moves once it is in a terminal state (WON or DRAW).

Non-Functional Requirements

Move placement + win check: O(winLength) per turn. Not O(rows × cols). The win check must be bounded by the win length, not the board size.
Correctness first, extensibility second. The board, win rule, and move rule are each swappable without touching the Game loop.
No global state. Multiple games must be able to run in the same process independently.
Deterministic. Given the same sequence of moves, the game produces the same outcome. No random elements.
Thread-safety: not required for the core, but a turn lock should be easy to add.

Core Entities and Relationships

Entity	Responsibility	Shared with TTT?
`Game`	Orchestrates turns, enforces terminal state, delegates placement + win detection.	Shared (chassis).
`Player`	Name + `Symbol` (color / glyph).	Shared.
`Symbol`	A small value type — `RED`, `YELLOW`, `X`, `O`, etc.	Shared.
`IBoard`	Grid abstraction: dimensions, read a cell, render.	Shared (interface).
`IMoveRule`	Validates a move and computes the target cell from a player's input (column for C4, cell for TTT).	New — TTT puts a disc exactly where asked; C4 needs gravity resolution.
`IWinStrategy`	Given the board and the last-filled cell, decide whether the last mover won.	Shared (interface), different implementation.
`ConnectFourBoard`	Column-major grid with a `nextRow[col]` heights array.	New (concrete board).
`GravityMoveRule`	"Column must exist; column must have room." Computes `(nextRow[col], col)`.	New.
`DirectionalWinStrategy`	Scans four directions from the last move, counting same-symbol runs.	New (concrete strategy).
`Move`	Value type: `{ player, row, col }`. Returned from the move rule; fed into the win check.	Shared.
`GameState`	Enum: `IN_PROGRESS`, `WON`, `DRAW`.	Shared.

The split pays off like this: the Game class is one of the shared entities, not one of the new ones. It is written once when TTT is designed and consumed unchanged for Connect Four. The only things the Connect Four problem actually adds are a concrete board, a concrete move rule, and a concrete win strategy.

Interfaces

typescript

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

type Symbol = string; // "R", "Y", "X", "O" — kept simple

interface Player {
  readonly id: string;
  readonly name: string;
  readonly symbol: Symbol;
}

interface Move {
  readonly player: Player;
  readonly row: number;
  readonly col: number;
}

interface IBoard {
  readonly rows: number;
  readonly cols: number;
  get(row: number, col: number): Symbol | null;
  set(row: number, col: number, symbol: Symbol): void;
  isFull(): boolean;
  render(): string;
}

/**
 * Resolves a player's input (column for C4, cell for TTT) into a concrete target cell,
 * throws InvalidMoveException on rejection. Also performs the placement.
 */
interface IMoveRule {
  place(board: IBoard, player: Player, input: MoveInput): Move;
}

/** Polymorphic input — a column index for Connect Four, a (row, col) pair for TTT. */
type MoveInput =
  | { kind: "column"; col: number }
  | { kind: "cell"; row: number; col: number };

/**
 * Checks whether the last move completed a win. Takes the *last move* so concrete
 * strategies can do incremental work rather than full-board scans.
 */
interface IWinStrategy {
  isWin(board: IBoard, last: Move, winLength: number): boolean;
}

interface IGame {
  drop(input: MoveInput): Move;      // C4 callers pass { kind: "column", col }
  currentPlayer(): Player;
  state(): GameState;
  winner(): Player | null;
  render(): string;
}

IMoveRule is the new interface and the reason the chassis extends cleanly. TTT's CellMoveRule reads { kind: "cell", row, col } and writes there directly. Connect Four's GravityMoveRule reads { kind: "column", col }, computes the row from a heights array, and writes at (row, col). The Game class doesn't know or care which kind was used.

Class Diagram

                              +-----------------+
                              |     Game        |  <-- shared chassis
                              |-----------------|
                              | - board         |
                              | - players[]     |
                              | - turnIdx       |
                              | - moveRule      |----> IMoveRule (strategy)
                              | - winStrategy   |----> IWinStrategy (strategy)
                              | - state         |
                              | - winner        |
                              | - winLength     |
                              |-----------------|
                              | + drop(input)   |
                              | + currentPlayer |
                              | + state()       |
                              | + render()      |
                              +--------+--------+
                                       |
                +----------------------+----------------------+
                |                      |                      |
                v                      v                      v
       +------------------+   +------------------+   +-------------------+
       |    IBoard        |   |    IMoveRule     |   |   IWinStrategy    |
       +------------------+   +------------------+   +-------------------+
       | get/set/render   |   | place(...)       |   | isWin(b,last,k)   |
       +--------+---------+   +----+-------------+   +---+---------------+
                ^                  ^                     ^
                |                  |                     |
                |                  |                     |
   +------------+------+    +------+-----------+   +-----+---------------+
   | ConnectFourBoard  |    | GravityMoveRule  |   | DirectionalWin      |
   |-------------------|    |------------------|   | Strategy            |
   | - grid[rows][cols]|    | - (stateless)    |   |---------------------|
   | - nextRow[cols]   |    | validates +      |   | scans 4 directions  |
   | O(1) hasRoom()    |    | uses board's     |   | from `last.row/col` |
   +-------------------+    | hasRoom/set      |   | O(winLength) each   |
                            +------------------+   +---------------------+

   (TTT would plug in:
      TTTBoard (row-major, no heights),
      CellMoveRule (direct write after emptiness check),
      LineScanWinStrategy (checks the 8 lines through the placed cell))

The box on the right is the one I re-use if asked "now do Gomoku." DirectionalWinStrategy doesn't hardcode 4 — it takes winLength as a parameter. Gomoku is just new Game(..., winLength=5).

Class Design

`Game` — the shared chassis

The Game class is an orchestrator. It holds the board, the players, whose turn it is, the injected move rule, the injected win strategy, and the current state. Its drop() method is effectively a template:

Reject if terminal.
Ask the move rule to validate + place. Get a Move back.
Ask the win strategy if that Move completed a win.
If win, transition to WON. If board is full, transition to DRAW. Else advance the turn.

None of those steps mention "Connect Four" or "gravity." The same class drives Tic Tac Toe with different injected strategies.

`ConnectFourBoard`

Two pieces of state:

grid[rows][cols]: (Symbol | null)[][] — row-major for rendering convenience. Row 0 is the bottom row (discs fall to row 0 first). This matches the physics and makes "how high is column c" trivial.
nextRow[cols]: number[] — nextRow[c] is the next empty row in column c. Starts at 0, increments on each drop. Column is full when nextRow[c] === rows.

The heights array is why column-full is O(1) and why placement is O(1). Without it, drop becomes "scan up from the bottom until you find an empty cell" — O(rows) per move. That's fine for a 6-row board, but the array expresses intent and costs nothing.

`GravityMoveRule`

Stateless. One method:

place(board, player, { kind: "column", col }):
  reject if col < 0 or col >= board.cols
  reject if column is full
  row = board.nextRow(col)
  board.set(row, col, player.symbol)
  board.bumpNextRow(col)          // or board encapsulates this via a single drop() call
  return { player, row, col }

Dropping on a full column throws InvalidMoveException. The Game catches or propagates per the interviewer's choice — mine propagates; the caller (UI / test) retries without the turn advancing.

`DirectionalWinStrategy`

The crown jewel. Given last = { row, col, player }, it scans four direction pairs radiating from (row, col):

Horizontal: (0, -1) and (0, +1)
Vertical: (-1, 0) and (+1, 0)
Diagonal ↗: (-1, -1) and (+1, +1)
Anti-diagonal ↘: (-1, +1) and (+1, -1)

For each pair, count contiguous cells of the same symbol in both directions (plus the center, which is 1). If any pair's total is >= winLength, it's a win.

Cost: 4 pairs × 2 directions × up to winLength - 1 steps = at most 8 × (winLength - 1) cell reads. For winLength = 4 that's 24 reads, independent of board size. O(winLength), not O(rows × cols).

`Player`

Just data. id, name, symbol. I don't put behavior on it — the player is acted upon by the game, not the other way around. (In an AI-opponent extension, Player would grow a chooseMove(board) method, but that's out of scope here.)

Key Methods

typescript

class ConnectFourBoard implements IBoard {
  public readonly rows: number;
  public readonly cols: number;
  private readonly grid: (Symbol | null)[][];
  private readonly heights: number[];  // heights[c] = number of discs in column c
  private filled = 0;

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

  get(row: number, col: number): Symbol | null {
    if (row < 0 || row >= this.rows || col < 0 || col >= this.cols) return null;
    return this.grid[row][col];
  }

  set(row: number, col: number, symbol: Symbol): void {
    if (this.grid[row][col] !== null) {
      throw new Error(`cell (${row}, ${col}) is not empty`);
    }
    this.grid[row][col] = symbol;
    this.filled++;
  }

  /** C4-specific: next empty row in this column, or rows if full. */
  nextRowFor(col: number): number {
    return this.heights[col];
  }

  hasRoom(col: number): boolean {
    return this.heights[col] < this.rows;
  }

  /** Atomic: place at (heights[col], col), bump height. Returns the row used. */
  dropInto(col: number, symbol: Symbol): number {
    if (!this.hasRoom(col)) throw new InvalidMoveException(`column ${col} full`);
    const row = this.heights[col];
    this.set(row, col, symbol);
    this.heights[col]++;
    return row;
  }

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

  render(): string {
    const out: string[] = [];
    for (let r = this.rows - 1; r >= 0; r--) {    // print top row first
      const line = this.grid[r].map(c => c ?? ".").join(" ");
      out.push(line);
    }
    out.push(Array.from({ length: this.cols }, (_, i) => String(i)).join(" "));
    return out.join("\n");
  }
}

class InvalidMoveException extends Error {}

class GravityMoveRule implements IMoveRule {
  place(board: IBoard, player: Player, input: MoveInput): Move {
    if (input.kind !== "column") {
      throw new InvalidMoveException(`gravity rule expects a column input`);
    }
    const { col } = input;
    if (col < 0 || col >= board.cols) {
      throw new InvalidMoveException(`column ${col} out of range`);
    }
    // Downcast is acceptable here: this rule is bound to a board that supports dropInto.
    // In a stricter design, add hasRoom/dropInto to IBoard (only C4 needs them; TTT stubs them).
    const cfBoard = board as ConnectFourBoard;
    if (!cfBoard.hasRoom(col)) {
      throw new InvalidMoveException(`column ${col} is full`);
    }
    const row = cfBoard.dropInto(col, player.symbol);
    return { player, row, col };
  }
}

class DirectionalWinStrategy implements IWinStrategy {
  private static readonly DIRECTIONS: ReadonlyArray<readonly [number, number]> = [
    [0, 1],    // horizontal
    [1, 0],    // vertical
    [1, 1],    // diagonal ↗
    [1, -1],   // anti-diagonal ↘
  ];

  isWin(board: IBoard, last: Move, winLength: number): boolean {
    const { row, col, player } = last;
    const target = player.symbol;

    for (const [dr, dc] of DirectionalWinStrategy.DIRECTIONS) {
      // 1 for the cell we just placed, plus runs in both opposite directions.
      const total =
        1 +
        this.runLength(board, row, col, dr, dc, target, winLength - 1) +
        this.runLength(board, row, col, -dr, -dc, target, winLength - 1);

      if (total >= winLength) return true;
    }
    return false;
  }

  /**
   * Starting one cell away from (row, col) in direction (dr, dc), count how many
   * consecutive cells hold `target`. Bounded by `max` steps so the cost is O(winLength).
   */
  private runLength(
    board: IBoard,
    row: number,
    col: number,
    dr: number,
    dc: number,
    target: Symbol,
    max: number,
  ): number {
    let count = 0;
    let r = row + dr;
    let c = col + dc;
    while (count < max && board.get(r, c) === target) {
      count++;
      r += dr;
      c += dc;
    }
    return count;
  }
}

class Game implements IGame {
  private turnIdx = 0;
  private _state: GameState = GameState.IN_PROGRESS;
  private _winner: Player | null = null;

  constructor(
    private readonly board: IBoard,
    private readonly players: ReadonlyArray<Player>,
    private readonly moveRule: IMoveRule,
    private readonly winStrategy: IWinStrategy,
    private readonly winLength: number,
  ) {
    if (players.length < 2) throw new Error("need at least two players");
  }

  currentPlayer(): Player {
    return this.players[this.turnIdx];
  }

  state(): GameState { return this._state; }
  winner(): Player | null { return this._winner; }
  render(): string { return this.board.render(); }

  drop(input: MoveInput): Move {
    if (this._state !== GameState.IN_PROGRESS) {
      throw new InvalidMoveException(`game is ${this._state}`);
    }
    const player = this.currentPlayer();
    const move = this.moveRule.place(this.board, player, input);

    if (this.winStrategy.isWin(this.board, move, this.winLength)) {
      this._state = GameState.WON;
      this._winner = player;
      return move;
    }
    if (this.board.isFull()) {
      this._state = GameState.DRAW;
      return move;
    }
    this.turnIdx = (this.turnIdx + 1) % this.players.length;
    return move;
  }
}

// --- Usage ---
const red:    Player = { id: "p1", name: "Alice", symbol: "R" };
const yellow: Player = { id: "p2", name: "Bob",   symbol: "Y" };

const game = new Game(
  new ConnectFourBoard(6, 7),
  [red, yellow],
  new GravityMoveRule(),
  new DirectionalWinStrategy(),
  4,
);

game.drop({ kind: "column", col: 3 });  // Alice drops in middle
game.drop({ kind: "column", col: 3 });  // Bob stacks on top
// ...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190

Why isWin receives last instead of scanning the whole board. A full-board scan is O(rows × cols × directions). For 7×6 that's 168 cell reads per move, every move. The directional-from-last-move scan is bounded by winLength regardless of board size. On a 30×30 Gomoku board with winLength=5 the full-board scan is 3600 reads; the directional scan is at most 32. The gap grows with board size and is the reason this design holds up for Gomoku without a rewrite.

Why the runLength helper is bounded by max. Without the cap, a long existing chain of the same symbol (unlikely but possible for winLength > 4) would let the scan run the full diameter of the board. Capping at winLength - 1 keeps the cost flat. It's also the right semantic answer: we only care whether the chain is at least winLength, not how long it actually is.

Design Decisions & Tradeoffs

1. Column-major state (heights array) vs row-major only

I keep the grid row-major (grid[row][col]) because render() and the win-check are easier to read that way. But I add a heights[col] array to make gravity O(1). Without heights, drop has to scan up from row 0 until it finds an empty cell — O(rows) per move.

An alternative I considered: store the board column-first (cols[c]: Symbol[] where each column is a stack). Drop becomes cols[c].push(symbol) — beautifully natural. The cost is that get(row, col) has to convert indices, and diagonal scans in the win check become cols[c+dc][row+dr]-style lookups. I chose the hybrid — row-major grid + heights array — because it keeps the win check clean. Same Big-O either way.

2. Incremental win check from `last` vs full-board scan

Covered above. The short version: full-board scan is simpler to write (just enumerate all 70 windows on a 7×6 board and check each). It's also O(windows × winLength) = O(rows × cols × winLength) per move. The incremental scan from the last move is O(directions × winLength) = O(winLength). For Connect Four the difference barely matters; for Gomoku on a 19×19 board it's the difference between a fluid UI and a laggy one.

A senior candidate explicitly walks through both and picks the incremental one, explaining why. Even if the win length is constant, passing last to the strategy is a design signal: "I know the board could grow; I won't bake board size into the algorithm."

3. Injecting `IMoveRule` vs hardcoding gravity into the board

I could put gravity inside ConnectFourBoard.drop(col, symbol) and skip the IMoveRule abstraction entirely. It would even be one fewer interface. But then Game has to know it's a "gravity game" vs a "cell game" — it either calls board.drop(col) or board.place(row, col), which means Game branches on game type. That defeats the chassis.

With IMoveRule, Game always does the same thing: moveRule.place(board, player, input). The input type is polymorphic; the rule interprets it. Adding a "pick a row OR a column" variant (like Pop Out Connect Four) becomes a new IMoveRule, not a change in Game.

4. `IBoard` genericity — does it know about heights?

Tension: IBoard is shared with TTT, which has no heights. If I put hasRoom(col) / dropInto(col, symbol) on IBoard, every TTT board has to stub them.

My answer: keep IBoard small (get, set, isFull, render, dimensions) and let GravityMoveRule downcast to ConnectFourBoard when it needs gravity semantics. The downcast is isolated to one class — the move rule is "bound" to the board type by construction. An alternative is to split into IBoard (read-only) and two sibling interfaces (ICellBoard, IColumnBoard), and let each move rule target the right one. Cleaner types, more ceremony. For interview scope, the downcast is fine and I'd flag that I know it's a seam I could tighten.

5. Exceptions vs result types for invalid moves

I threw InvalidMoveException. The alternative is a Result<Move, InvalidMove> discriminated union. Exceptions read better for rare, exceptional paths ("you tried to drop on a full column — that shouldn't happen in a correct UI"). Results are better when invalid moves are routine (e.g., a dumb AI randomly guessing). I'd keep exceptions for the base; easy to swap to results if the caller needs them.

Patterns Used

Strategy — IMoveRule and IWinStrategy are both strategies. The game doesn't know or care how a move is placed or how a win is detected; it delegates.
Template Method (informally) — Game.drop() is a fixed-shape template: validate terminal → place via rule → check win → check draw → advance. Subclassing would make this a literal template method; I prefer the strategy injection because subclasses of Game are a code smell for this kind of problem.
State — GameState enum plus a single state field. The transitions are linear (IN_PROGRESS → WON or IN_PROGRESS → DRAW); a full State pattern with classes per state is overkill. If I added pausing, forfeiting, rematch, I'd promote the enum to state classes.
Command — not in the core design, but the natural extension point for undo. Each Move becomes a DropCommand with execute (drop + bump heights) and undo (clear cell + decrement heights). We'll see this in the follow-up questions.
Value Object — Move, Player, Symbol. Immutable, equatable by value, no identity.

Patterns I deliberately did not use:

Observer — tempting for "notify UI when a move is made," but the spec is console-only. Adding it now is speculative.
Factory — only one concrete board, one move rule, one win strategy. Direct construction is fine. If variants multiply, a GameFactory.connectFour() / .tictactoe() / .gomoku() becomes worth it.

Concurrency Considerations

Single-player, turn-based, single-threaded. The core design needs no locks.

For online play you'd add two things:

Turn lock. Exactly one drop() at a time, and the caller must be the current player. A single mutex around Game.drop() is enough because contention is low (one move per few seconds per game).
Session identity. The game doesn't know who the caller is — it trusts that whoever invoked drop() is currentPlayer(). Online, you wrap the game in a GameSession that maps authenticated user IDs to player slots and rejects mismatches before reaching drop().

Neither belongs in the core. The reason the core is ready for them is that Game is state-encapsulated and the only mutating method is drop(). A lock has one place to live.

Scaling to many concurrent games is a different axis: each Game instance is independent, so a server hosts N games as N objects. No shared state means horizontal scaling across worker processes is just sticky-by-game-id routing.

Scale & Extensibility

The point of the whole design is that variants are new classes, not rewrites.

Gomoku (5-in-a-row on a 19×19 board)

typescript

new Game(
  new ConnectFourBoard(19, 19),   // works, but no gravity needed
  players,
  new CellMoveRule(),             // reuse from TTT
  new DirectionalWinStrategy(),   // reuse — takes winLength as parameter
  5,
);

Wait — Gomoku doesn't have gravity. So we swap the move rule to CellMoveRule (plays at any empty cell), keep the directional win strategy unchanged, and pass winLength = 5. The board works as-is; the heights array is simply unused when the move rule doesn't call dropInto. In a stricter design I'd split the board into GravityBoard and CellBoard — but the core point stands: the win strategy is reused verbatim.

Non-gravity Connect Four variants (e.g., "pop out")

Pop Out Connect Four lets players remove their own disc from the bottom of a column, collapsing the stack down by one. New IMoveRule: PopOutMoveRule with input { kind: "popout", col }. Win strategy is unchanged, but now we need to re-check all pieces in that column since the collapse could have broken or made lines. This is the one case where incremental win-check doesn't save us — pop-out is a "global state" move. Fall back to full-board scan for that variant, flag the cost.

Bigger boards

new ConnectFourBoard(20, 30) just works. The heights array grows; everything else is unchanged. Win check stays O(winLength).

More than two players

new Game(board, [red, yellow, green, blue], ...) works today. turnIdx = (turnIdx + 1) % players.length. The only subtle point: in 4-player Connect Four, four colors can share a column, so "was it my symbol" matters (it already does — DirectionalWinStrategy compares to last.player.symbol).

3D Connect Four (qubic, or 4×4×4)

This is a rewrite — kind of. IBoard becomes 3D. GravityMoveRule now drops along the Z axis given (x, y). DirectionalWinStrategy now scans 13 direction pairs (the 3D equivalent of the 4 in 2D). But the chassis — Game, Player, Move, GameState, the dispatch in drop() — is unchanged. The parts that change are exactly the parts that should change: the board's geometry, the move rule's placement logic, the win scan's direction set.

AI opponent

Add an IPlayerAgent with chooseMove(game): MoveInput. A minimax agent implements it with alpha-beta pruning; the game doesn't know. The drop() loop stays the same — the driver asks the current player's agent for input, passes it to drop().

Edge Cases

Column full on drop. GravityMoveRule.place throws InvalidMoveException. Game.drop propagates. The turn does not advance — turnIdx updates only after a successful placement.
Column index out of range (negative or >= cols). Same — InvalidMoveException, turn unchanged.
Wrong input kind (cell input passed to gravity rule). Throws. Defensive check catches misconfigured games (e.g., someone wired a CellMoveRule game and called drop({ kind: "column" })).
Board full with no winner. Game.drop sets state to DRAW after the no-win branch. A move that fills the last cell AND completes a win is correctly reported as WON, not DRAW — the win check runs first.
First move. winLength=4, last.row=0, run-length scans stop immediately at out-of-bounds. isWin returns false. No special-casing needed.
Last move that also wins. Covered in #4 — win check precedes draw check. State is WON, winner is set.
Move after game is over. Game.drop checks _state first and throws. Prevents phantom moves after a win.
Single-player game passed to constructor. Rejected in constructor (players.length < 2).
Win length > min(rows, cols). Not rejected by default — the game will simply never reach a win. I'd add a sanity check in production; in an interview I'd flag it verbally.
Diagonal win that wraps around the last move from both sides (e.g., last dropped piece is the middle of a 4-in-a-row, with two pieces on each side). The two-direction sum in isWin handles this — runLength counts both sides of last independently, and we add them plus 1 for the center.

Follow-up Questions

Expose Game, IBoard, IMoveRule, IWinStrategy, Player, Move, GameState in a shared core/ module. TTT adds TTTBoard, CellMoveRule, LineScanWinStrategy. C4 adds ConnectFourBoard, GravityMoveRule, DirectionalWinStrategy. Both games are composed via new Game(board, players, moveRule, winStrategy, winLength) — a factory call, not a new class.

2. How would you detect a win in O(1)?

"O(1)" is loose here — I mean O(winLength) with winLength treated as a constant. The directional scan from last is already that. If truly constant-time is needed, you can maintain a side table: for each cell, the length of the run-of-same-symbol ending at that cell in each of the four directions. On drop, update the cell's four entries in O(1) each from its neighbors' values. Win if any of the four new values is >= winLength. Memory: 4 ints per cell.

3. How would you add Gomoku?

Discussed above. Three lines change: new ConnectFourBoard(19, 19) (or a non-gravity variant), new CellMoveRule() instead of gravity, winLength = 5. The win strategy is identical.

4. How would you add an AI?

Add IPlayerAgent.chooseMove(game): MoveInput. A driver loop asks game.currentPlayer(), looks up the agent, asks for a move, passes it to game.drop(). For the AI itself: minimax with alpha-beta pruning, depth 6-8 for Connect Four, with a heuristic that counts 2-in-a-rows and 3-in-a-rows as partial credit. game.clone() support is needed for search — implement with a deep copy of the board and heights array.

5. How would you undo a move — including gravity implications?

Wrap each drop in a DropCommand:

typescript

class DropCommand {
  constructor(private board: ConnectFourBoard, private col: number, private player: Player) {}
  private row = -1;
  execute(): Move {
    this.row = this.board.dropInto(this.col, this.player.symbol);
    return { player: this.player, row: this.row, col: this.col };
  }
  undo(): void {
    // Clear the top cell of this column and decrement the height.
    this.board.clearTop(this.col);
  }
}

ConnectFourBoard.clearTop(col) sets grid[heights[col]-1][col] = null, decrements heights[col], decrements filled. Importantly, you can only undo the most recent drop in a column, because gravity means the top of the column is the only unambiguously-yours disc. Undoing an arbitrary past move requires either reverting forward from a snapshot or pushing the drops into a stack — the latter is cheaper (one Command per move, constant memory per undo step).

Game state restoration is also needed: an undo from WON returns to IN_PROGRESS, clears _winner, and rewinds turnIdx. That's why Game keeps its own Command stack rather than delegating undo to the board.

6. How would you serialize a game?

Two options. Full snapshot: serialize the grid, heights, current turn, state, winner. Simple, larger on disk, easy to diff. Replay log: serialize (winLength, rows, cols, players, [moveInputs]). Tiny, but reconstruction requires running the game forward from scratch. I'd use replay log for game history / cloud save and snapshot for in-memory clones (AI search).

7. How does this extend to 3D Connect Four (Qubic, 4×4×4)?

Covered above. IBoard3D with a third dimension; GravityMoveRule3D drops along Z given (x, y); DirectionalWinStrategy3D scans 13 direction pairs instead of 4. Chassis unchanged. The ratio of "new code" to "reused code" is still favorable: the Game, Player, Move, GameState, and dispatch logic carry over verbatim.

8. What if two players can win on the same move?

In standard Connect Four, only one player moves at a time, so only the mover can win on their own move. The scenario "two players win simultaneously" can't happen. In variants with simultaneous moves or team play, the win strategy would need to return Player | null instead of boolean — and if it returns multiple, the game rules define tie-break (typically a draw).

9. How do you test this?

Board unit tests: ConnectFourBoard dimensions, dropInto correctness, hasRoom, isFull.
Win strategy unit tests: parameterize over every direction (horizontal, vertical, both diagonals), every offset of the winning cell within the 4-run (leftmost, middle, rightmost), cases where runs sit on the border (run truncated by wall), cases where the opponent's symbol is adjacent (must not count).
Move rule unit tests: full column throws, out-of-range throws, valid drop returns correct (row, col).
Game integration tests: full game scripts — "Alice wins with a horizontal in row 0," "Bob wins with an anti-diagonal," "board fills to a draw," "drop after win throws."

The win-check matrix is the most testable part. I'd generate cases as a table: (direction, winningCellPositionInRun, borderTruncation) → expected boolean. 24 cases is enough to trust it.

10. What's the memory cost for a server hosting 10k concurrent games?

Each board: rows × cols symbols + cols ints for heights. For 7×6, that's 42 cells (pointer-sized in JS, or one byte in a tight representation) + 7 ints ≈ 50-350 bytes depending on encoding. Plus Game object overhead and player refs. Call it ~1 KB per game conservatively. 10k games = 10 MB. Negligible. The bottleneck for a real server will be connections and session state, not the game objects themselves.

SDE2 vs SDE3 — How the Bar Rises

Aspect	SDE2 bar	SDE3 bar
Primary outcome	A working Connect Four with correct win detection and a clean OOP structure.	The chassis shared with Tic Tac Toe, justified as a deliberate reuse decision.
Chassis reuse	May design TTT and C4 independently, possibly noticing the overlap late.	Opens with "I'd lift `Game`, `IBoard`, `IWinStrategy` into a shared layer. The deltas are the move rule and the win strategy. Here's why."
Win check	Full-board or all-windows scan. Correct, but O(rows × cols × winLength) per move.	Directional scan from `last`. O(winLength). Explicitly justifies the complexity difference and why it matters for Gomoku.
Move rule	May hardcode gravity inside `Board.drop(col)`. Correct and simple.	Extracts `IMoveRule` because they can already name the next variant that breaks the assumption (pop-out, Gomoku, 3D).
Complexity analysis	Names the algorithms but may not reason about their complexity formally.	Gives per-operation Big-O. Calls out amortized vs worst-case where relevant (e.g., incremental win check is worst-case O(winLength), not amortized).
Testability	Tests exist; may miss directional cases or boundary cases.	Presents the win-check test matrix as a design artifact — `(direction) × (position in run) × (border truncation)` — and can enumerate the 24 cases without prompting.
Concurrency	"It's single-threaded, no locks needed."	"Single-threaded for now. Adding a turn lock is a one-line change because all mutation flows through `Game.drop()`. For online, session auth wraps the game — it doesn't modify it."
Extension stories	Can answer "how would you add Gomoku?" with a plausible sketch.	Answers it with a three-line code diff and can already enumerate which interfaces don't change — demonstrating that they designed for this case, not just rationalizing after the fact.
Tradeoffs	Picks one design and defends it.	Presents two or three, picks one, says what would flip the choice (e.g., "I'd drop `IMoveRule` if we were certain no variants existed").
Failure modes	Handles full-column and out-of-range.	Also handles: move after terminal state, win check precedes draw check, directional win with last-move in the middle of the run, and the single-column pop-out case where incremental win-check breaks down.

The single strongest differentiator: an SDE3 talks about the TTT chassis without being asked. They treat "can this scale to Gomoku / 3D / pop-out?" as a core part of the design, not a follow-up the interviewer pulled out of them. The interviewer asked Connect Four after TTT for exactly this reason — the signal is proactive.

11 — Problem: Connect Four ​

Understanding the Problem ​

Clarifying Questions ​

What I'm taking away ​

Functional Requirements ​

Non-Functional Requirements ​

Core Entities and Relationships ​

Interfaces ​

Class Diagram ​

Class Design ​

Game — the shared chassis ​

ConnectFourBoard ​

GravityMoveRule ​

DirectionalWinStrategy ​

Player ​

Key Methods ​

Design Decisions & Tradeoffs ​

1. Column-major state (heights array) vs row-major only ​

2. Incremental win check from last vs full-board scan ​

3. Injecting IMoveRule vs hardcoding gravity into the board ​

4. IBoard genericity — does it know about heights? ​

5. Exceptions vs result types for invalid moves ​

Patterns Used ​

Concurrency Considerations ​

Scale & Extensibility ​

Gomoku (5-in-a-row on a 19×19 board) ​

Non-gravity Connect Four variants (e.g., "pop out") ​

Bigger boards ​

More than two players ​

3D Connect Four (qubic, or 4×4×4) ​

AI opponent ​

Edge Cases ​

Follow-up Questions ​

1. How would you share code with Tic Tac Toe? ​

2. How would you detect a win in O(1)? ​

3. How would you add Gomoku? ​

4. How would you add an AI? ​

5. How would you undo a move — including gravity implications? ​

6. How would you serialize a game? ​

7. How does this extend to 3D Connect Four (Qubic, 4×4×4)? ​

8. What if two players can win on the same move? ​

9. How do you test this? ​

10. What's the memory cost for a server hosting 10k concurrent games? ​

SDE2 vs SDE3 — How the Bar Rises ​

11 — Problem: Connect Four

Understanding the Problem

Clarifying Questions

What I'm taking away

Functional Requirements

Non-Functional Requirements

Core Entities and Relationships

Interfaces

Class Diagram

Class Design

`Game` — the shared chassis

`ConnectFourBoard`

`GravityMoveRule`

`DirectionalWinStrategy`

`Player`

Key Methods

Design Decisions & Tradeoffs

1. Column-major state (heights array) vs row-major only

2. Incremental win check from `last` vs full-board scan

3. Injecting `IMoveRule` vs hardcoding gravity into the board

4. `IBoard` genericity — does it know about heights?

5. Exceptions vs result types for invalid moves

Patterns Used

Concurrency Considerations

Scale & Extensibility

Gomoku (5-in-a-row on a 19×19 board)

Non-gravity Connect Four variants (e.g., "pop out")

Bigger boards

More than two players

3D Connect Four (qubic, or 4×4×4)

AI opponent

Edge Cases

Follow-up Questions

1. How would you share code with Tic Tac Toe?

2. How would you detect a win in O(1)?

3. How would you add Gomoku?

4. How would you add an AI?

5. How would you undo a move — including gravity implications?

6. How would you serialize a game?

7. How does this extend to 3D Connect Four (Qubic, 4×4×4)?

8. What if two players can win on the same move?

9. How do you test this?

10. What's the memory cost for a server hosting 10k concurrent games?

SDE2 vs SDE3 — How the Bar Rises