Games & SimulationsProblem 7 of 11

Games & SimulationsIntermediate

Minesweeper

Grid, mines, flood fill. The elegance is that every cell knows its neighbor-mine count at generation time — gameplay becomes pure state transitions.

Key Abstractions

Cell

One grid square. Holds mine-flag, adjacent-mine count, and reveal state.

Board

Grid of cells, mine layout, and reveal logic (flood fill for zero-adjacency)

MinePlacer

Strategy that places mines — random, fixed-seed, or first-click-safe

Game

Owns the board, status, and timer. Routes reveal/flag/chord actions. Declares win/lose.

Class Diagram

The Key Insight

Minesweeper's reveal logic looks like magic when someone clicks a zero-cell and half the board pops open. It's just BFS. Every cell with zero adjacent mines reveals its neighbors; if those are also zero, they cascade. A visited set (or the cell's own state transition) stops infinite loops. Eight lines of code.

Pre-computing adjacent-mine counts at generation time is the real win. The alternative — recounting neighbors on every reveal — means walking 8 cells per reveal, and on a 30x30 board with a cascade that can be 100+ cell reveals. Once-at-generation turns it into a single board walk, then O(1) per reveal.

First-click-safe is the detail that separates a good design from a working one. Placing mines after the first click, skipping the 3x3 window around the click, means the first move always opens up a useful area. Any commercial Minesweeper does this; most interview candidates miss it.

Requirements

Functional

Configurable rows, columns, and mine count
Reveal a cell; cascade through zero-adjacency neighbors
Flag/unflag a hidden cell
Track game status: playing, won, lost
First click is always safe (never a mine)

Non-Functional

O(1) per cell reveal after generation
O(cells) memory for the board
Reveal must be deterministic given a seed (testability)
Board and Game should be separately testable

Design Decisions

Why precompute adjacent counts?

Adjacent-mine count is needed on every reveal. Recomputing means scanning 8 neighbors per click. Precompute at generation means scanning everything once, then O(1) per click thereafter. For cascading reveals (which can touch hundreds of cells), this is essentially the difference between a smooth UI and a janky one.

Why MinePlacer as a Strategy?

Tests want deterministic layouts. The first-click-safe rule wants a placer that knows the safe cell. A "chess-style" variant might want specific patterns. Strategy abstracts all of it — RandomMinePlacer for games, FixedMinePlacer for tests, SymmetricMinePlacer for puzzle modes.

Why lazy mine placement?

If mines are placed at board construction, the first click can hit a mine — game over at step one. Real Minesweeper delays placement until the first reveal and places mines away from the clicked cell. The lazy approach handles this naturally: no mines until the player clicks.

Why `CellState.FLAGGED` as a tristate?

Flags aren't involved in the win condition — they're a UI hint for the player. But a flagged cell shouldn't be revealable by click (prevents accidents). Making state an enum with three values captures all three behaviors (hidden-clickable, revealed, flagged-protected) in one field.

Why BFS instead of DFS for flood fill?

Either works. BFS is slightly safer for large cascades because it avoids deep recursion — Python's default recursion limit is 1000; a 40x40 board with one big zero-cluster could blow it. Iterative BFS with a deque has no such limit.

Interview Follow-ups

"How would you save/load games?" Serialize the board (cell states, mine positions, adjacent counts) to JSON. Restore reconstructs Board with the same state. Skip minesPlaced=false — use the loaded mines directly.
"What about chord clicks (click a revealed number to auto-reveal neighbors if flag count matches)?" New method chord(r, c): if the revealed cell's number equals its flagged neighbors, reveal all non-flagged neighbors.
"How do you generate no-guessing boards?" Constraint solver — after placement, verify a logic-only solver can solve the board. If not, reroll. Expensive for large boards; typically done offline for puzzle packs.
"How do you support a hint system?" The board internals already know mine positions. The hint service reveals one safe cell the player hasn't revealed yet — picks from cells where !hasMine && state == HIDDEN.

45-Minute LLD Playbook

45 min total

Each phase is what the interviewer expects you to do and say. Concrete steps, not topic hints. Diagrams are what you would sketch on the board.

1
Clarify the rules and lock the data model
5 min
GoalPin down the win condition, the first-click-safe rule, what flags actually do, and what chord-click means. End with the diagram-vs-code question.
Do & Say
1. ASK·1Open with: Win condition is every non-mine cell revealed, regardless of flags. Flags are a UI hint, they do not count toward winning. Loss is revealing any mine cell. Lock the win condition explicitly because the all-flags-on-mines variant is a common trap.
2. SAY·2Pin first-click-safe: I will place mines lazily, on the first reveal, and skip the 3x3 window around the clicked cell. Real Minesweeper does this so the first click always opens a useful area. Park no-guessing board generation as v2.
3. SAY·3Confirm adjacent-mine count is pre-computed: After mine placement, I walk every non-mine cell once and count mine neighbours, storing the number on the cell. Reveal becomes O(1) per cell after that. Recomputing on every reveal would be wasteful, especially during flood fill.
4. SAY·4Pin the flood fill: On revealing a cell with adjacent_mines == 0, BFS cascades through zero neighbours. Border cells (non-zero) reveal but do not extend. Iterative BFS with a deque, not recursive DFS, so a 40x40 board with one big zero region does not blow the stack.
5. SAY·5Confirm chord: On a clicked revealed number cell, if flagged neighbours exactly equals the number, auto-reveal the remaining non-flag neighbours. Wrong flags mean revealing a mine, which loses the game. Same code path as a normal reveal, just looped over neighbours.
6. ASK·6Ask the process question: Diagram first, or jump into code with Cell, Board, MinePlacer, Game? Either way I want to budget the 40 minutes deliberately.
Interviewer is grading: You name the win-condition trap (all-flags-on-mines) before the interviewer brings it up. You commit to lazy mine placement and the 3x3 safe window unprompted. You pick BFS over recursive DFS with the stack-overflow rationale named.
2
Sketch the grid model and the reveal cascade
5-10 min
GoalDraw a small grid showing the BFS cascade, name where Cell, Board, MinePlacer, and Game live, and write the method signatures.
Do & Say
1. DRAW·1Draw a 4x4 grid. Mark one mine in a corner. Trace BFS from a far-corner click: Click sees zero, enqueues neighbours. Each zero-neighbour enqueues its own. Border numbers reveal but stop. Say: BFS through zeros only, border numbers are the cascade stop sign.
2. SAY·2Name the abstractions: Cell (row, col, has_mine, adjacent_mines, state). CellState enum (HIDDEN, REVEALED, FLAGGED). MinePlacer interface with RandomMinePlacer concrete. Board (rows, cols, grid, mines_placed flag, reveal/flag/neighbors methods). Game (board, status, started_at, finished_at, reveal/flag/chord methods). GameStatus enum (PLAYING, WON, LOST).
3. WRITE·3Write Board signatures: reveal(r, c) returns the list of newly revealed cells. flag(r, c) toggles HIDDEN and FLAGGED. neighbors(r, c) returns the 8-direction neighbours. all_safe_revealed() returns the win check. Say: Board does not own status or timer; Game wraps Board with those concerns.
4. WRITE·4Write Game signatures: reveal(r, c) returns GameStatus. flag(r, c). chord(r, c) returns GameStatus. elapsed_seconds(). Say: Game is what turns Board's mechanical reveal into a game session with a clock and a terminal status.
5. SAY·5Pin the lazy placement: Board.reveal checks a mines_placed flag. If False, call placer.place(self, r, c, mine_count), set the flag. That is the only place mines get put down.
Interviewer is grading: You draw the BFS cascade with border numbers acting as the stop. You separate Board (mechanics) from Game (session, clock, status). You commit to the mines_placed flag as the single source of truth for lazy placement.
3
Code in this sequence (bottom-up)
25 min
GoalType CellState and GameStatus, then Cell, then MinePlacer and RandomMinePlacer, then Board, then Game. Match the existing pythonCode order exactly.
Do & Say
1. SAY·1Start with CellState (HIDDEN, REVEALED, FLAGGED) and GameStatus (PLAYING, WON, LOST) as Enum classes. (~1 min)
2. SAY·2Code Cell as a dataclass with fields: row, col. has_mine (False). adjacent_mines (0). state (HIDDEN). Add __str__ returning a flag, dot, asterisk, number, or space based on state. Say: Cell is data plus a rendering hint, no game logic. (~3 min)
3. SAY·3Code MinePlacer abstract with place(board, safe_row, safe_col, count). Then RandomMinePlacer constructor takes an optional rng for deterministic tests. (~1 min)
4. SAY·4Code place in three steps: Build candidates as every (r, c) OUTSIDE the 3x3 safe window. Validate count <= len(candidates). rng.sample picks count positions, set has_mine = True on each. (~2 min)
5. SAY·5Walk every non-mine cell and count mine neighbours via board.neighbors, store on adjacent_mines. Say: Pre-computing adjacent_mines lets reveal stay O(1) per cell during the cascade. Without it, every cell visit costs 8 neighbour lookups. (~2 min)
6. SAY·6Code Board with constants for the 8 deltas: Constructor validates positive dimensions, validates mine_count < rows * cols, creates the grid as a list of lists of Cell. Holds the placer and mines_placed flag. neighbors(r, c) iterates the 8 deltas, bounds-checks, returns the in-bounds cells. (~3 min)
7. SAY·7Code Board.reveal: Bounds-check first. If not mines_placed, call placer.place(self, r, c, mine_count) and set the flag. That is the lazy-placement hook. (~2 min)
8. SAY·8Continue Board.reveal: Fetch the cell, return empty list if not HIDDEN. If has_mine, mark REVEALED, return [cell]. (~1 min)
9. SAY·9Otherwise BFS: queue with [cell], mark cell REVEALED. Loop popping, skip if adjacent_mines != 0. Else enqueue HIDDEN non-mine neighbours after marking them REVEALED. Return the revealed list. (~2 min)
10. SAY·10Say: The skip-if-nonzero inside the loop stops the cascade at border numbers. Neighbours of a non-zero cell are reachable only via a different path through a zero. (~1 min)
11. SAY·11Code Board.flag: Bounds-check, fetch cell. If REVEALED, return (can't flag a revealed cell). Otherwise toggle HIDDEN and FLAGGED. (~1 min)
12. SAY·12Code Board.all_safe_revealed: Every cell where not has_mine must be in REVEALED state. Single double-loop. Say: This is the win check, not all-flags-on-mines. Flags do not appear here at all. (~1 min)
13. SAY·13Code Game constructor: Builds a Board with the optional MinePlacer. Holds status (PLAYING) and started_at / finished_at as None. (~1 min)
14. SAY·14Code Game.reveal(r, c): If not PLAYING, return current status. If started_at is None, record now (timer starts on first reveal, not at construction). (~2 min)
15. SAY·15Continue Game.reveal: Call board.reveal, iterate the returned cells. If any has_mine then status = LOST and finished_at = now. Else if board.all_safe_revealed, status = WON. Return status. (~1 min)
16. SAY·16Say: Timer starts on first reveal, not at construction. The player gets to study the board without the clock ticking. (~1 min)
17. SAY·17Code Game.flag as a passthrough to board.flag when PLAYING. (~1 min)
18. SAY·18Code Game.chord: Check the cell is REVEALED with non-zero adjacent_mines. Count FLAGGED neighbours, no-op if count != adjacent_mines. Otherwise iterate HIDDEN neighbours and call self.reveal on each, returning LOST early if any reveal returns LOST. (~2 min)
19. SAY·19Say: Chord reuses reveal, so wrong flags lose the game through the same code path as a direct mine click. Intentional behaviour, not a bug. (~1 min)
20. SAY·20Code elapsed_seconds(): 0 if started_at is None, else (finished_at or now) - started_at total seconds. (~1 min)
21. SAY·21Walk-through part one: 5x5 board, 5 mines, seed=7. Game.reveal(0, 0). mines_placed is False, RandomMinePlacer.place skips the 3x3 around (0,0). Drops 5 mines in the remaining 16 cells, pre-computes adjacent_mines for every safe cell.
22. SAY·22Walk-through part two: Cell (0,0) is HIDDEN, no mine, adjacent_mines 0. BFS: enqueue, mark REVEALED, pop, enqueue (0,1), (1,0), (1,1) if hidden and non-mine. Cascade until every neighbour is a border number. Revealed list has 8 cells. all_safe_revealed False. Return PLAYING. (~1 min)
Interviewer is grading: Code compiles as you type. You name pre-computed adjacent_mines as the optimisation enabling fast cascades. You volunteer that timer starts on first reveal, not at construction. You walk through a single reveal-with-cascade as a self-check before declaring done.
4
Trade-offs and extensions
5 min
GoalDefend lazy mine placement, defend BFS over DFS, defend the FLAGGED tristate over a separate flag-only data structure, volunteer save/load and hint system.
Do & Say
1. SAY·1Trade-off one, lazy placement over construction-time: Construction-time placement means the first click can hit a mine. Game ends at step one. Commercial Minesweeper delays placement until the first reveal, with a 3x3 skip around the click so the opening is interesting, not just safe.
2. SAY·2Trade-off two, BFS over recursive DFS: Either correctly computes the cascade. BFS with a deque has no recursion depth limit. Python defaults to 1000 frames. A 40x40 board with one big zero cluster can blow that. Iterative BFS keeps the per-game memory bounded by the cascade size, no stack risk.
3. SAY·3Trade-off three, FLAGGED inside CellState over a separate flags set: Separate set means every reveal consults grid and flags map. The tristate enum keeps it on the cell. Cost: needs a transition guard (revealed cells cannot become flagged), encoded in Board.flag.
4. SAY·4Extension to volunteer, save/load: Serialise the grid (cell states, mine positions, adjacent counts) to JSON. Restore rebuilds Board with mines_placed=True so the placer never runs again. Game-level state (status, started_at) serialises alongside.
5. SAY·5Extension to volunteer, hint system: Add Board.hint() returning any cell where not has_mine and state == HIDDEN. Useful in tutorial mode. No-guessing boards are harder: post-placement, run a logic-only solver and reroll if it fails. Expensive, usually baked offline for puzzle packs.
6. SAY·6Close with one sentence: CellState and GameStatus as enums. Pre-computed adjacent_mines on every cell. Lazy first-click-safe mine placement. BFS flood fill from zero cells. Board for mechanics and Game for the session. Three classes plus two enums, O(1) reveal after generation.
Interviewer is grading: You name the cascade-stack risk as the reason for BFS over recursive DFS. You volunteer save/load and hint system unprompted. You can summarise the three classes, two enums, and the O(1) reveal in one breath.

Code Implementation

from __future__ import annotations
from abc import ABC, abstractmethod
from collections import deque
from dataclasses import dataclass
from datetime import datetime
from enum import Enum
import random


class CellState(Enum):
    HIDDEN = "hidden"
    REVEALED = "revealed"
    FLAGGED = "flagged"


class GameStatus(Enum):
    PLAYING = "playing"
    WON = "won"
    LOST = "lost"


@dataclass
class Cell:
    row: int
    col: int
    has_mine: bool = False
    adjacent_mines: int = 0
    state: CellState = CellState.HIDDEN

    def __str__(self) -> str:
        if self.state == CellState.FLAGGED: return "⚑"
        if self.state == CellState.HIDDEN: return "·"
        if self.has_mine: return "*"
        return str(self.adjacent_mines) if self.adjacent_mines else " "


class MinePlacer(ABC):
    @abstractmethod
    def place(self, board: "Board", safe_row: int, safe_col: int, count: int) -> None: ...


class RandomMinePlacer(MinePlacer):
    """First-click-safe: avoid a 3x3 window around the first click."""

    def __init__(self, rng: random.Random | None = None):
        self._rng = rng or random.Random()

    def place(self, board: "Board", safe_row: int, safe_col: int, count: int) -> None:
        candidates = [
            (r, c) for r in range(board.rows) for c in range(board.cols)
            if not (abs(r - safe_row) <= 1 and abs(c - safe_col) <= 1)
        ]
        if count > len(candidates):
            raise ValueError("Too many mines for board size")
        picks = self._rng.sample(candidates, count)
        for r, c in picks:
            board.grid[r][c].has_mine = True
        # Precompute adjacent counts once. O(rows*cols*8) — fast.
        for r in range(board.rows):
            for c in range(board.cols):
                if board.grid[r][c].has_mine:
                    continue
                board.grid[r][c].adjacent_mines = sum(
                    1 for n in board.neighbors(r, c) if n.has_mine
                )


class Board:
    DELTAS = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]

    def __init__(self, rows: int, cols: int, mine_count: int,
                 placer: MinePlacer | None = None):
        if rows <= 0 or cols <= 0:
            raise ValueError("rows and cols must be positive")
        if mine_count >= rows * cols:
            raise ValueError("Too many mines")
        self.rows = rows
        self.cols = cols
        self.mine_count = mine_count
        self.grid = [[Cell(r, c) for c in range(cols)] for r in range(rows)]
        self._placer = placer or RandomMinePlacer()
        self._mines_placed = False

    def neighbors(self, r: int, c: int) -> list[Cell]:
        out = []
        for dr, dc in self.DELTAS:
            nr, nc = r + dr, c + dc
            if 0 <= nr < self.rows and 0 <= nc < self.cols:
                out.append(self.grid[nr][nc])
        return out

    def reveal(self, r: int, c: int) -> list[Cell]:
        """Reveal (r, c) and cascade through zero-adjacency cells. Returns cells newly revealed."""
        if not self._in_bounds(r, c):
            raise IndexError("out of bounds")

        # Lazy mine placement — first click is always safe.
        if not self._mines_placed:
            self._placer.place(self, r, c, self.mine_count)
            self._mines_placed = True

        cell = self.grid[r][c]
        if cell.state != CellState.HIDDEN:
            return []   # already revealed or flagged; no-op

        revealed: list[Cell] = []
        if cell.has_mine:
            cell.state = CellState.REVEALED
            revealed.append(cell)
            return revealed

        # BFS flood-fill through zero-adjacency cells.
        queue = deque([cell])
        cell.state = CellState.REVEALED
        revealed.append(cell)
        while queue:
            curr = queue.popleft()
            if curr.adjacent_mines != 0:
                continue
            for n in self.neighbors(curr.row, curr.col):
                if n.state == CellState.HIDDEN and not n.has_mine:
                    n.state = CellState.REVEALED
                    revealed.append(n)
                    queue.append(n)
        return revealed

    def flag(self, r: int, c: int) -> None:
        if not self._in_bounds(r, c):
            raise IndexError("out of bounds")
        cell = self.grid[r][c]
        if cell.state == CellState.REVEALED:
            return   # can't flag a revealed cell
        cell.state = CellState.FLAGGED if cell.state == CellState.HIDDEN else CellState.HIDDEN

    def all_safe_revealed(self) -> bool:
        """Win condition: every non-mine cell is revealed."""
        for row in self.grid:
            for cell in row:
                if not cell.has_mine and cell.state != CellState.REVEALED:
                    return False
        return True

    def _in_bounds(self, r: int, c: int) -> bool:
        return 0 <= r < self.rows and 0 <= c < self.cols

    def render(self, reveal_mines: bool = False) -> str:
        lines = []
        for row in self.grid:
            parts = []
            for cell in row:
                if reveal_mines and cell.has_mine:
                    parts.append("*")
                else:
                    parts.append(str(cell))
            lines.append(" ".join(parts))
        return "\n".join(lines)


class Game:
    def __init__(self, rows: int, cols: int, mines: int, placer: MinePlacer | None = None):
        self._board = Board(rows, cols, mines, placer)
        self._status = GameStatus.PLAYING
        self._started_at: datetime | None = None
        self._finished_at: datetime | None = None

    @property
    def status(self) -> GameStatus: return self._status

    @property
    def board(self) -> Board: return self._board

    def reveal(self, r: int, c: int) -> GameStatus:
        if self._status != GameStatus.PLAYING:
            return self._status
        if self._started_at is None:
            self._started_at = datetime.utcnow()
        revealed = self._board.reveal(r, c)
        for cell in revealed:
            if cell.has_mine:
                self._status = GameStatus.LOST
                self._finished_at = datetime.utcnow()
                return self._status
        if self._board.all_safe_revealed():
            self._status = GameStatus.WON
            self._finished_at = datetime.utcnow()
        return self._status

    def flag(self, r: int, c: int) -> None:
        if self._status != GameStatus.PLAYING:
            return
        self._board.flag(r, c)

    def chord(self, r: int, c: int) -> GameStatus:
        """Click-a-number to auto-reveal neighbors when the flag count matches.
        Mis-flagging and then chording is a classic way to lose — by design."""
        if self._status != GameStatus.PLAYING:
            return self._status
        if not self._board._in_bounds(r, c):
            raise IndexError("out of bounds")
        cell = self._board.grid[r][c]
        if cell.state != CellState.REVEALED or cell.adjacent_mines == 0:
            return self._status
        flagged = sum(1 for n in self._board.neighbors(r, c) if n.state == CellState.FLAGGED)
        if flagged != cell.adjacent_mines:
            return self._status  # no-op — not enough (or too many) flags
        for n in self._board.neighbors(r, c):
            if n.state == CellState.HIDDEN:
                result = self.reveal(n.row, n.col)
                if result == GameStatus.LOST:
                    return result
        return self._status

    def elapsed_seconds(self) -> float:
        if self._started_at is None:
            return 0.0
        end = self._finished_at or datetime.utcnow()
        return (end - self._started_at).total_seconds()


if __name__ == "__main__":
    # Deterministic placement for the demo.
    game = Game(5, 5, 5, placer=RandomMinePlacer(random.Random(7)))
    print("Initial board (hidden):")
    print(game.board.render())

    game.reveal(0, 0)
    print(f"\nAfter first reveal at (0,0) — status: {game.status.value}")
    print(game.board.render())

    # Flag a cell.
    game.flag(2, 2)
    print("\nAfter flagging (2,2):")
    print(game.board.render())

    # Reveal every non-mine cell to win.
    for r in range(game.board.rows):
        for c in range(game.board.cols):
            cell = game.board.grid[r][c]
            if not cell.has_mine:
                game.reveal(r, c)
    print(f"\nFinal status: {game.status.value}")
    print(game.board.render(reveal_mines=True))
    print(f"Elapsed: {game.elapsed_seconds():.3f}s")

    # Chord: correctly flag neighbors then chord-click reveals the rest.
    chord_game = Game(3, 3, 1, placer=RandomMinePlacer(random.Random(2)))
    chord_game.reveal(0, 0)  # lazy-places mines away from (0,0)
    # Find a revealed number cell with exactly one mine neighbor.
    target = None
    for r in range(3):
        for c in range(3):
            cell = chord_game.board.grid[r][c]
            if cell.state == CellState.REVEALED and cell.adjacent_mines == 1:
                target = (r, c); break
        if target: break
    if target:
        r, c = target
        # Flag the one mine neighbor correctly.
        for n in chord_game.board.neighbors(r, c):
            if n.has_mine:
                chord_game.flag(n.row, n.col)
                break
        before = sum(1 for row in chord_game.board.grid for cell in row
                     if cell.state == CellState.REVEALED)
        chord_game.chord(r, c)
        after = sum(1 for row in chord_game.board.grid for cell in row
                    if cell.state == CellState.REVEALED)
        print(f"Chord revealed {after - before} new cell(s); status: {chord_game.status.value}")

import java.util.*;

enum CellState { HIDDEN, REVEALED, FLAGGED }
enum GameStatus { PLAYING, WON, LOST }

class Cell {
    final int row, col;
    boolean hasMine = false;
    int adjacentMines = 0;
    CellState state = CellState.HIDDEN;

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

interface MinePlacer {
    void place(Board board, int safeRow, int safeCol, int count);
}

class RandomMinePlacer implements MinePlacer {
    private final Random rng;
    RandomMinePlacer(Random rng) { this.rng = rng; }

    public void place(Board board, int safeRow, int safeCol, int count) {
        List<int[]> candidates = new ArrayList<>();
        for (int r = 0; r < board.rows; r++)
            for (int c = 0; c < board.cols; c++)
                if (Math.abs(r - safeRow) > 1 || Math.abs(c - safeCol) > 1)
                    candidates.add(new int[]{r, c});

        if (count > candidates.size()) throw new IllegalArgumentException("too many mines");
        Collections.shuffle(candidates, rng);
        for (int i = 0; i < count; i++) {
            int[] pos = candidates.get(i);
            board.grid[pos[0]][pos[1]].hasMine = true;
        }
        for (int r = 0; r < board.rows; r++) {
            for (int c = 0; c < board.cols; c++) {
                if (board.grid[r][c].hasMine) continue;
                int count2 = 0;
                for (Cell n : board.neighbors(r, c)) if (n.hasMine) count2++;
                board.grid[r][c].adjacentMines = count2;
            }
        }
    }
}

class Board {
    private static final int[][] DELTAS = {
        {-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}
    };
    final int rows, cols, mineCount;
    final Cell[][] grid;
    private final MinePlacer placer;
    private boolean minesPlaced = false;

    Board(int rows, int cols, int mineCount, MinePlacer placer) {
        if (rows <= 0 || cols <= 0) throw new IllegalArgumentException("positive dims");
        if (mineCount >= rows * cols) throw new IllegalArgumentException("too many mines");
        this.rows = rows; this.cols = cols; this.mineCount = mineCount; this.placer = placer;
        this.grid = new Cell[rows][cols];
        for (int r = 0; r < rows; r++)
            for (int c = 0; c < cols; c++)
                grid[r][c] = new Cell(r, c);
    }

    List<Cell> neighbors(int r, int c) {
        List<Cell> out = new ArrayList<>(8);
        for (int[] d : DELTAS) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) out.add(grid[nr][nc]);
        }
        return out;
    }

    List<Cell> reveal(int r, int c) {
        if (!minesPlaced) { placer.place(this, r, c, mineCount); minesPlaced = true; }
        Cell cell = grid[r][c];
        if (cell.state != CellState.HIDDEN) return List.of();

        List<Cell> out = new ArrayList<>();
        if (cell.hasMine) { cell.state = CellState.REVEALED; out.add(cell); return out; }

        Deque<Cell> q = new ArrayDeque<>();
        cell.state = CellState.REVEALED; out.add(cell); q.offer(cell);
        while (!q.isEmpty()) {
            Cell curr = q.poll();
            if (curr.adjacentMines != 0) continue;
            for (Cell n : neighbors(curr.row, curr.col)) {
                if (n.state == CellState.HIDDEN && !n.hasMine) {
                    n.state = CellState.REVEALED;
                    out.add(n); q.offer(n);
                }
            }
        }
        return out;
    }

    void flag(int r, int c) {
        Cell cell = grid[r][c];
        if (cell.state == CellState.REVEALED) return;
        cell.state = cell.state == CellState.HIDDEN ? CellState.FLAGGED : CellState.HIDDEN;
    }

    boolean allSafeRevealed() {
        for (Cell[] row : grid)
            for (Cell cell : row)
                if (!cell.hasMine && cell.state != CellState.REVEALED) return false;
        return true;
    }
}

public class Minesweeper {
    private final Board board;
    private GameStatus status = GameStatus.PLAYING;
    private java.time.Instant startedAt;
    private java.time.Instant finishedAt;

    public Minesweeper(int rows, int cols, int mines, MinePlacer placer) {
        this.board = new Board(rows, cols, mines, placer);
    }

    public Board board() { return board; }

    public GameStatus reveal(int r, int c) {
        if (status != GameStatus.PLAYING) return status;
        if (startedAt == null) startedAt = java.time.Instant.now();
        List<Cell> revealed = board.reveal(r, c);
        for (Cell cell : revealed) {
            if (cell.hasMine) {
                status = GameStatus.LOST;
                finishedAt = java.time.Instant.now();
                return status;
            }
        }
        if (board.allSafeRevealed()) {
            status = GameStatus.WON;
            finishedAt = java.time.Instant.now();
        }
        return status;
    }

    public void flag(int r, int c) { if (status == GameStatus.PLAYING) board.flag(r, c); }

    public GameStatus chord(int r, int c) {
        if (status != GameStatus.PLAYING) return status;
        Cell cell = board.grid[r][c];
        if (cell.state != CellState.REVEALED || cell.adjacentMines == 0) return status;
        int flagged = 0;
        for (Cell n : board.neighbors(r, c)) if (n.state == CellState.FLAGGED) flagged++;
        if (flagged != cell.adjacentMines) return status;
        for (Cell n : board.neighbors(r, c)) {
            if (n.state == CellState.HIDDEN) {
                GameStatus result = reveal(n.row, n.col);
                if (result == GameStatus.LOST) return result;
            }
        }
        return status;
    }

    public double elapsedSeconds() {
        if (startedAt == null) return 0.0;
        java.time.Instant end = finishedAt != null ? finishedAt : java.time.Instant.now();
        return java.time.Duration.between(startedAt, end).toMillis() / 1000.0;
    }

    public GameStatus getStatus() { return status; }

    public static void main(String[] args) {
        Minesweeper game = new Minesweeper(5, 5, 5, new RandomMinePlacer(new Random(7)));
        game.reveal(0, 0);
        System.out.println("Status after first reveal: " + game.getStatus());
        for (int r = 0; r < 5; r++)
            for (int c = 0; c < 5; c++) game.reveal(r, c);
        System.out.println("Final: " + game.getStatus() + " elapsed: " +
            String.format("%.3fs", game.elapsedSeconds()));

        // Chord: correct flags unlock the rest.
        Minesweeper chordGame = new Minesweeper(3, 3, 1, new RandomMinePlacer(new Random(2)));
        chordGame.reveal(0, 0);
        int[] target = null;
        for (int r = 0; r < 3 && target == null; r++)
            for (int c = 0; c < 3 && target == null; c++) {
                Cell cell = chordGame.board().grid[r][c];
                if (cell.state == CellState.REVEALED && cell.adjacentMines == 1)
                    target = new int[]{r, c};
            }
        if (target != null) {
            for (Cell n : chordGame.board().neighbors(target[0], target[1])) {
                if (n.hasMine) { chordGame.flag(n.row, n.col); break; }
            }
            GameStatus after = chordGame.chord(target[0], target[1]);
            System.out.println("Chord result: " + after);
        }
    }
}

Interview Grading by Level

What an interviewer at each level expects to see in your answer. Use this to calibrate, not to perform.

Junior Engineer (L3)

Builds a grid, places mines, and implements a basic reveal, but misses lazy placement, the flood fill or the win condition.

Signals

Models Cell with has_mine and a revealed flag.
Builds a Board with rows, cols, and a 2D grid of cells.
Implements a basic reveal that marks cells revealed and returns whether a mine was hit.
Adds a flag toggle for the UI.
Recognises that adjacent-mine counts need to be computed somewhere.

Common gaps at this level

Places mines at board construction, so the first click can immediately hit a mine.
Uses recursive DFS for flood fill, risking stack overflow on large zero clusters.
Defines the win condition as all flags on mines, which forces the user to flag perfectly.
Recomputes adjacent-mine counts during reveal instead of once at generation, making cascades slow.
Forgets to mark cells visited during flood fill, causing infinite loops on the first zero click.

Mid-Level Engineer (L4)

Drives the design with lazy first-click-safe placement, pre-computed adjacent counts, iterative BFS flood fill, and the all-safe-cells-revealed win check.

Signals

MinePlacer is an interface with RandomMinePlacer as a concrete, taking an optional rng for deterministic tests.
Lazy placement triggered inside Board.reveal on the first call, skipping the 3x3 around the safe cell.
Adjacent_mines pre-computed once for every non-mine cell after placement.
Iterative BFS with a deque for the flood fill, with the skip-if-nonzero check stopping the cascade at border numbers.
Win condition is all_safe_revealed (every non-mine cell in REVEALED state); flags are excluded.
Game wraps Board with status, started_at, finished_at, where the timer starts on first reveal.

Common gaps at this level

Does not implement chord-click unless prompted.
Does not volunteer save/load or hint system as extensions.
Treats no-guessing board generation as the same problem as random placement, missing the constraint-solver framing.

Senior Engineer (L5+)

Volunteers chord-click, save/load, and no-guessing generation, names BFS over DFS for the stack-depth reason, and frames the pre-computed adjacent_mines as the cascade-time optimisation.

Signals

Implements chord-click that reuses Game.reveal so wrong flags lose through the same code path as a direct mine click.
Volunteers serialisation of the grid plus mines_placed=True flag for save/load so the placer never reruns on restore.
Volunteers a hint system that picks any non-mine HIDDEN cell as a tutorial-mode helper.
Frames no-guessing board generation as a constraint-solver problem run post-placement, with the reroll-if-not-solvable loop and the offline-puzzle-pack caveat.
Names the Python recursion limit (1000) and explains the cascade-size risk as the reason for iterative BFS.
Names the timer-starts-on-first-reveal rule explicitly, distinguishing game construction from session start.
Closes with a one-sentence summary that names the three classes, two enums, lazy placement, and O(1) reveal in under 20 seconds.

Common Mistakes

✗Checking 'all flags on mines' for the win condition. That forces the user to flag perfectly — not how the game works.
✗Placing mines at board creation. If the first click lands on a mine, the game ends before it starts — bad UX.
✗Revealing recursively without a visited set. Infinite loop on the first zero-cell click.
✗Storing only mine positions and recomputing counts per reveal. Slow and error-prone.

Key Points

✓Pre-compute adjacent-mine count once at board generation. Reveal becomes O(1) per cell.
✓Flood fill on reveal when adjacent count is 0 — BFS from the clicked cell through zero-cells.
✓First-click-safe: place mines *after* the first reveal and away from the clicked cell.
✓Win condition: all non-mine cells revealed, regardless of flags. Flags are just a UI hint.
✓Chord click: on a revealed number cell with matching flagged neighbors, auto-reveal the rest. Wrong flags → loss.
✓Timer starts on first reveal and stops on terminal status — clock doesn't tick before the player commits.

Related Designs

Games & SimulationsProblem 7 of 11

Games & SimulationsIntermediate

Minesweeper

Grid, mines, flood fill. The elegance is that every cell knows its neighbor-mine count at generation time — gameplay becomes pure state transitions.

Key Abstractions

Cell

One grid square. Holds mine-flag, adjacent-mine count, and reveal state.

Board

Grid of cells, mine layout, and reveal logic (flood fill for zero-adjacency)

MinePlacer

Strategy that places mines — random, fixed-seed, or first-click-safe

Game

Owns the board, status, and timer. Routes reveal/flag/chord actions. Declares win/lose.

Class Diagram

The Key Insight

Requirements

Functional

Configurable rows, columns, and mine count
Reveal a cell; cascade through zero-adjacency neighbors
Flag/unflag a hidden cell
Track game status: playing, won, lost
First click is always safe (never a mine)

Non-Functional

O(1) per cell reveal after generation
O(cells) memory for the board
Reveal must be deterministic given a seed (testability)
Board and Game should be separately testable

Design Decisions

Why precompute adjacent counts?

Why MinePlacer as a Strategy?

Why lazy mine placement?

Why `CellState.FLAGGED` as a tristate?

Why BFS instead of DFS for flood fill?

Interview Follow-ups

"How would you save/load games?" Serialize the board (cell states, mine positions, adjacent counts) to JSON. Restore reconstructs Board with the same state. Skip minesPlaced=false — use the loaded mines directly.
"What about chord clicks (click a revealed number to auto-reveal neighbors if flag count matches)?" New method chord(r, c): if the revealed cell's number equals its flagged neighbors, reveal all non-flagged neighbors.
"How do you generate no-guessing boards?" Constraint solver — after placement, verify a logic-only solver can solve the board. If not, reroll. Expensive for large boards; typically done offline for puzzle packs.
"How do you support a hint system?" The board internals already know mine positions. The hint service reveals one safe cell the player hasn't revealed yet — picks from cells where !hasMine && state == HIDDEN.

45-Minute LLD Playbook

45 min total

Each phase is what the interviewer expects you to do and say. Concrete steps, not topic hints. Diagrams are what you would sketch on the board.

1
Clarify the rules and lock the data model
5 min
GoalPin down the win condition, the first-click-safe rule, what flags actually do, and what chord-click means. End with the diagram-vs-code question.
Do & Say
1. ASK·1Open with: Win condition is every non-mine cell revealed, regardless of flags. Flags are a UI hint, they do not count toward winning. Loss is revealing any mine cell. Lock the win condition explicitly because the all-flags-on-mines variant is a common trap.
2. SAY·2Pin first-click-safe: I will place mines lazily, on the first reveal, and skip the 3x3 window around the clicked cell. Real Minesweeper does this so the first click always opens a useful area. Park no-guessing board generation as v2.
3. SAY·3Confirm adjacent-mine count is pre-computed: After mine placement, I walk every non-mine cell once and count mine neighbours, storing the number on the cell. Reveal becomes O(1) per cell after that. Recomputing on every reveal would be wasteful, especially during flood fill.
4. SAY·4Pin the flood fill: On revealing a cell with adjacent_mines == 0, BFS cascades through zero neighbours. Border cells (non-zero) reveal but do not extend. Iterative BFS with a deque, not recursive DFS, so a 40x40 board with one big zero region does not blow the stack.
5. SAY·5Confirm chord: On a clicked revealed number cell, if flagged neighbours exactly equals the number, auto-reveal the remaining non-flag neighbours. Wrong flags mean revealing a mine, which loses the game. Same code path as a normal reveal, just looped over neighbours.
6. ASK·6Ask the process question: Diagram first, or jump into code with Cell, Board, MinePlacer, Game? Either way I want to budget the 40 minutes deliberately.
Interviewer is grading: You name the win-condition trap (all-flags-on-mines) before the interviewer brings it up. You commit to lazy mine placement and the 3x3 safe window unprompted. You pick BFS over recursive DFS with the stack-overflow rationale named.
2
Sketch the grid model and the reveal cascade
5-10 min
GoalDraw a small grid showing the BFS cascade, name where Cell, Board, MinePlacer, and Game live, and write the method signatures.
Do & Say
1. DRAW·1Draw a 4x4 grid. Mark one mine in a corner. Trace BFS from a far-corner click: Click sees zero, enqueues neighbours. Each zero-neighbour enqueues its own. Border numbers reveal but stop. Say: BFS through zeros only, border numbers are the cascade stop sign.
2. SAY·2Name the abstractions: Cell (row, col, has_mine, adjacent_mines, state). CellState enum (HIDDEN, REVEALED, FLAGGED). MinePlacer interface with RandomMinePlacer concrete. Board (rows, cols, grid, mines_placed flag, reveal/flag/neighbors methods). Game (board, status, started_at, finished_at, reveal/flag/chord methods). GameStatus enum (PLAYING, WON, LOST).
3. WRITE·3Write Board signatures: reveal(r, c) returns the list of newly revealed cells. flag(r, c) toggles HIDDEN and FLAGGED. neighbors(r, c) returns the 8-direction neighbours. all_safe_revealed() returns the win check. Say: Board does not own status or timer; Game wraps Board with those concerns.
4. WRITE·4Write Game signatures: reveal(r, c) returns GameStatus. flag(r, c). chord(r, c) returns GameStatus. elapsed_seconds(). Say: Game is what turns Board's mechanical reveal into a game session with a clock and a terminal status.
5. SAY·5Pin the lazy placement: Board.reveal checks a mines_placed flag. If False, call placer.place(self, r, c, mine_count), set the flag. That is the only place mines get put down.
Interviewer is grading: You draw the BFS cascade with border numbers acting as the stop. You separate Board (mechanics) from Game (session, clock, status). You commit to the mines_placed flag as the single source of truth for lazy placement.
3
Code in this sequence (bottom-up)
25 min
GoalType CellState and GameStatus, then Cell, then MinePlacer and RandomMinePlacer, then Board, then Game. Match the existing pythonCode order exactly.
Do & Say
1. SAY·1Start with CellState (HIDDEN, REVEALED, FLAGGED) and GameStatus (PLAYING, WON, LOST) as Enum classes. (~1 min)
2. SAY·2Code Cell as a dataclass with fields: row, col. has_mine (False). adjacent_mines (0). state (HIDDEN). Add __str__ returning a flag, dot, asterisk, number, or space based on state. Say: Cell is data plus a rendering hint, no game logic. (~3 min)
3. SAY·3Code MinePlacer abstract with place(board, safe_row, safe_col, count). Then RandomMinePlacer constructor takes an optional rng for deterministic tests. (~1 min)
4. SAY·4Code place in three steps: Build candidates as every (r, c) OUTSIDE the 3x3 safe window. Validate count <= len(candidates). rng.sample picks count positions, set has_mine = True on each. (~2 min)
5. SAY·5Walk every non-mine cell and count mine neighbours via board.neighbors, store on adjacent_mines. Say: Pre-computing adjacent_mines lets reveal stay O(1) per cell during the cascade. Without it, every cell visit costs 8 neighbour lookups. (~2 min)
6. SAY·6Code Board with constants for the 8 deltas: Constructor validates positive dimensions, validates mine_count < rows * cols, creates the grid as a list of lists of Cell. Holds the placer and mines_placed flag. neighbors(r, c) iterates the 8 deltas, bounds-checks, returns the in-bounds cells. (~3 min)
7. SAY·7Code Board.reveal: Bounds-check first. If not mines_placed, call placer.place(self, r, c, mine_count) and set the flag. That is the lazy-placement hook. (~2 min)
8. SAY·8Continue Board.reveal: Fetch the cell, return empty list if not HIDDEN. If has_mine, mark REVEALED, return [cell]. (~1 min)
9. SAY·9Otherwise BFS: queue with [cell], mark cell REVEALED. Loop popping, skip if adjacent_mines != 0. Else enqueue HIDDEN non-mine neighbours after marking them REVEALED. Return the revealed list. (~2 min)
10. SAY·10Say: The skip-if-nonzero inside the loop stops the cascade at border numbers. Neighbours of a non-zero cell are reachable only via a different path through a zero. (~1 min)
11. SAY·11Code Board.flag: Bounds-check, fetch cell. If REVEALED, return (can't flag a revealed cell). Otherwise toggle HIDDEN and FLAGGED. (~1 min)
12. SAY·12Code Board.all_safe_revealed: Every cell where not has_mine must be in REVEALED state. Single double-loop. Say: This is the win check, not all-flags-on-mines. Flags do not appear here at all. (~1 min)
13. SAY·13Code Game constructor: Builds a Board with the optional MinePlacer. Holds status (PLAYING) and started_at / finished_at as None. (~1 min)
14. SAY·14Code Game.reveal(r, c): If not PLAYING, return current status. If started_at is None, record now (timer starts on first reveal, not at construction). (~2 min)
15. SAY·15Continue Game.reveal: Call board.reveal, iterate the returned cells. If any has_mine then status = LOST and finished_at = now. Else if board.all_safe_revealed, status = WON. Return status. (~1 min)
16. SAY·16Say: Timer starts on first reveal, not at construction. The player gets to study the board without the clock ticking. (~1 min)
17. SAY·17Code Game.flag as a passthrough to board.flag when PLAYING. (~1 min)
18. SAY·18Code Game.chord: Check the cell is REVEALED with non-zero adjacent_mines. Count FLAGGED neighbours, no-op if count != adjacent_mines. Otherwise iterate HIDDEN neighbours and call self.reveal on each, returning LOST early if any reveal returns LOST. (~2 min)
19. SAY·19Say: Chord reuses reveal, so wrong flags lose the game through the same code path as a direct mine click. Intentional behaviour, not a bug. (~1 min)
20. SAY·20Code elapsed_seconds(): 0 if started_at is None, else (finished_at or now) - started_at total seconds. (~1 min)
21. SAY·21Walk-through part one: 5x5 board, 5 mines, seed=7. Game.reveal(0, 0). mines_placed is False, RandomMinePlacer.place skips the 3x3 around (0,0). Drops 5 mines in the remaining 16 cells, pre-computes adjacent_mines for every safe cell.
22. SAY·22Walk-through part two: Cell (0,0) is HIDDEN, no mine, adjacent_mines 0. BFS: enqueue, mark REVEALED, pop, enqueue (0,1), (1,0), (1,1) if hidden and non-mine. Cascade until every neighbour is a border number. Revealed list has 8 cells. all_safe_revealed False. Return PLAYING. (~1 min)
Interviewer is grading: Code compiles as you type. You name pre-computed adjacent_mines as the optimisation enabling fast cascades. You volunteer that timer starts on first reveal, not at construction. You walk through a single reveal-with-cascade as a self-check before declaring done.
4
Trade-offs and extensions
5 min
GoalDefend lazy mine placement, defend BFS over DFS, defend the FLAGGED tristate over a separate flag-only data structure, volunteer save/load and hint system.
Do & Say
1. SAY·1Trade-off one, lazy placement over construction-time: Construction-time placement means the first click can hit a mine. Game ends at step one. Commercial Minesweeper delays placement until the first reveal, with a 3x3 skip around the click so the opening is interesting, not just safe.
2. SAY·2Trade-off two, BFS over recursive DFS: Either correctly computes the cascade. BFS with a deque has no recursion depth limit. Python defaults to 1000 frames. A 40x40 board with one big zero cluster can blow that. Iterative BFS keeps the per-game memory bounded by the cascade size, no stack risk.
3. SAY·3Trade-off three, FLAGGED inside CellState over a separate flags set: Separate set means every reveal consults grid and flags map. The tristate enum keeps it on the cell. Cost: needs a transition guard (revealed cells cannot become flagged), encoded in Board.flag.
4. SAY·4Extension to volunteer, save/load: Serialise the grid (cell states, mine positions, adjacent counts) to JSON. Restore rebuilds Board with mines_placed=True so the placer never runs again. Game-level state (status, started_at) serialises alongside.
5. SAY·5Extension to volunteer, hint system: Add Board.hint() returning any cell where not has_mine and state == HIDDEN. Useful in tutorial mode. No-guessing boards are harder: post-placement, run a logic-only solver and reroll if it fails. Expensive, usually baked offline for puzzle packs.
6. SAY·6Close with one sentence: CellState and GameStatus as enums. Pre-computed adjacent_mines on every cell. Lazy first-click-safe mine placement. BFS flood fill from zero cells. Board for mechanics and Game for the session. Three classes plus two enums, O(1) reveal after generation.
Interviewer is grading: You name the cascade-stack risk as the reason for BFS over recursive DFS. You volunteer save/load and hint system unprompted. You can summarise the three classes, two enums, and the O(1) reveal in one breath.

Code Implementation

from __future__ import annotations
from abc import ABC, abstractmethod
from collections import deque
from dataclasses import dataclass
from datetime import datetime
from enum import Enum
import random


class CellState(Enum):
    HIDDEN = "hidden"
    REVEALED = "revealed"
    FLAGGED = "flagged"


class GameStatus(Enum):
    PLAYING = "playing"
    WON = "won"
    LOST = "lost"


@dataclass
class Cell:
    row: int
    col: int
    has_mine: bool = False
    adjacent_mines: int = 0
    state: CellState = CellState.HIDDEN

    def __str__(self) -> str:
        if self.state == CellState.FLAGGED: return "⚑"
        if self.state == CellState.HIDDEN: return "·"
        if self.has_mine: return "*"
        return str(self.adjacent_mines) if self.adjacent_mines else " "


class MinePlacer(ABC):
    @abstractmethod
    def place(self, board: "Board", safe_row: int, safe_col: int, count: int) -> None: ...


class RandomMinePlacer(MinePlacer):
    """First-click-safe: avoid a 3x3 window around the first click."""

    def __init__(self, rng: random.Random | None = None):
        self._rng = rng or random.Random()

    def place(self, board: "Board", safe_row: int, safe_col: int, count: int) -> None:
        candidates = [
            (r, c) for r in range(board.rows) for c in range(board.cols)
            if not (abs(r - safe_row) <= 1 and abs(c - safe_col) <= 1)
        ]
        if count > len(candidates):
            raise ValueError("Too many mines for board size")
        picks = self._rng.sample(candidates, count)
        for r, c in picks:
            board.grid[r][c].has_mine = True
        # Precompute adjacent counts once. O(rows*cols*8) — fast.
        for r in range(board.rows):
            for c in range(board.cols):
                if board.grid[r][c].has_mine:
                    continue
                board.grid[r][c].adjacent_mines = sum(
                    1 for n in board.neighbors(r, c) if n.has_mine
                )


class Board:
    DELTAS = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]

    def __init__(self, rows: int, cols: int, mine_count: int,
                 placer: MinePlacer | None = None):
        if rows <= 0 or cols <= 0:
            raise ValueError("rows and cols must be positive")
        if mine_count >= rows * cols:
            raise ValueError("Too many mines")
        self.rows = rows
        self.cols = cols
        self.mine_count = mine_count
        self.grid = [[Cell(r, c) for c in range(cols)] for r in range(rows)]
        self._placer = placer or RandomMinePlacer()
        self._mines_placed = False

    def neighbors(self, r: int, c: int) -> list[Cell]:
        out = []
        for dr, dc in self.DELTAS:
            nr, nc = r + dr, c + dc
            if 0 <= nr < self.rows and 0 <= nc < self.cols:
                out.append(self.grid[nr][nc])
        return out

    def reveal(self, r: int, c: int) -> list[Cell]:
        """Reveal (r, c) and cascade through zero-adjacency cells. Returns cells newly revealed."""
        if not self._in_bounds(r, c):
            raise IndexError("out of bounds")

        # Lazy mine placement — first click is always safe.
        if not self._mines_placed:
            self._placer.place(self, r, c, self.mine_count)
            self._mines_placed = True

        cell = self.grid[r][c]
        if cell.state != CellState.HIDDEN:
            return []   # already revealed or flagged; no-op

        revealed: list[Cell] = []
        if cell.has_mine:
            cell.state = CellState.REVEALED
            revealed.append(cell)
            return revealed

        # BFS flood-fill through zero-adjacency cells.
        queue = deque([cell])
        cell.state = CellState.REVEALED
        revealed.append(cell)
        while queue:
            curr = queue.popleft()
            if curr.adjacent_mines != 0:
                continue
            for n in self.neighbors(curr.row, curr.col):
                if n.state == CellState.HIDDEN and not n.has_mine:
                    n.state = CellState.REVEALED
                    revealed.append(n)
                    queue.append(n)
        return revealed

    def flag(self, r: int, c: int) -> None:
        if not self._in_bounds(r, c):
            raise IndexError("out of bounds")
        cell = self.grid[r][c]
        if cell.state == CellState.REVEALED:
            return   # can't flag a revealed cell
        cell.state = CellState.FLAGGED if cell.state == CellState.HIDDEN else CellState.HIDDEN

    def all_safe_revealed(self) -> bool:
        """Win condition: every non-mine cell is revealed."""
        for row in self.grid:
            for cell in row:
                if not cell.has_mine and cell.state != CellState.REVEALED:
                    return False
        return True

    def _in_bounds(self, r: int, c: int) -> bool:
        return 0 <= r < self.rows and 0 <= c < self.cols

    def render(self, reveal_mines: bool = False) -> str:
        lines = []
        for row in self.grid:
            parts = []
            for cell in row:
                if reveal_mines and cell.has_mine:
                    parts.append("*")
                else:
                    parts.append(str(cell))
            lines.append(" ".join(parts))
        return "\n".join(lines)


class Game:
    def __init__(self, rows: int, cols: int, mines: int, placer: MinePlacer | None = None):
        self._board = Board(rows, cols, mines, placer)
        self._status = GameStatus.PLAYING
        self._started_at: datetime | None = None
        self._finished_at: datetime | None = None

    @property
    def status(self) -> GameStatus: return self._status

    @property
    def board(self) -> Board: return self._board

    def reveal(self, r: int, c: int) -> GameStatus:
        if self._status != GameStatus.PLAYING:
            return self._status
        if self._started_at is None:
            self._started_at = datetime.utcnow()
        revealed = self._board.reveal(r, c)
        for cell in revealed:
            if cell.has_mine:
                self._status = GameStatus.LOST
                self._finished_at = datetime.utcnow()
                return self._status
        if self._board.all_safe_revealed():
            self._status = GameStatus.WON
            self._finished_at = datetime.utcnow()
        return self._status

    def flag(self, r: int, c: int) -> None:
        if self._status != GameStatus.PLAYING:
            return
        self._board.flag(r, c)

    def chord(self, r: int, c: int) -> GameStatus:
        """Click-a-number to auto-reveal neighbors when the flag count matches.
        Mis-flagging and then chording is a classic way to lose — by design."""
        if self._status != GameStatus.PLAYING:
            return self._status
        if not self._board._in_bounds(r, c):
            raise IndexError("out of bounds")
        cell = self._board.grid[r][c]
        if cell.state != CellState.REVEALED or cell.adjacent_mines == 0:
            return self._status
        flagged = sum(1 for n in self._board.neighbors(r, c) if n.state == CellState.FLAGGED)
        if flagged != cell.adjacent_mines:
            return self._status  # no-op — not enough (or too many) flags
        for n in self._board.neighbors(r, c):
            if n.state == CellState.HIDDEN:
                result = self.reveal(n.row, n.col)
                if result == GameStatus.LOST:
                    return result
        return self._status

    def elapsed_seconds(self) -> float:
        if self._started_at is None:
            return 0.0
        end = self._finished_at or datetime.utcnow()
        return (end - self._started_at).total_seconds()


if __name__ == "__main__":
    # Deterministic placement for the demo.
    game = Game(5, 5, 5, placer=RandomMinePlacer(random.Random(7)))
    print("Initial board (hidden):")
    print(game.board.render())

    game.reveal(0, 0)
    print(f"\nAfter first reveal at (0,0) — status: {game.status.value}")
    print(game.board.render())

    # Flag a cell.
    game.flag(2, 2)
    print("\nAfter flagging (2,2):")
    print(game.board.render())

    # Reveal every non-mine cell to win.
    for r in range(game.board.rows):
        for c in range(game.board.cols):
            cell = game.board.grid[r][c]
            if not cell.has_mine:
                game.reveal(r, c)
    print(f"\nFinal status: {game.status.value}")
    print(game.board.render(reveal_mines=True))
    print(f"Elapsed: {game.elapsed_seconds():.3f}s")

    # Chord: correctly flag neighbors then chord-click reveals the rest.
    chord_game = Game(3, 3, 1, placer=RandomMinePlacer(random.Random(2)))
    chord_game.reveal(0, 0)  # lazy-places mines away from (0,0)
    # Find a revealed number cell with exactly one mine neighbor.
    target = None
    for r in range(3):
        for c in range(3):
            cell = chord_game.board.grid[r][c]
            if cell.state == CellState.REVEALED and cell.adjacent_mines == 1:
                target = (r, c); break
        if target: break
    if target:
        r, c = target
        # Flag the one mine neighbor correctly.
        for n in chord_game.board.neighbors(r, c):
            if n.has_mine:
                chord_game.flag(n.row, n.col)
                break
        before = sum(1 for row in chord_game.board.grid for cell in row
                     if cell.state == CellState.REVEALED)
        chord_game.chord(r, c)
        after = sum(1 for row in chord_game.board.grid for cell in row
                    if cell.state == CellState.REVEALED)
        print(f"Chord revealed {after - before} new cell(s); status: {chord_game.status.value}")

import java.util.*;

enum CellState { HIDDEN, REVEALED, FLAGGED }
enum GameStatus { PLAYING, WON, LOST }

class Cell {
    final int row, col;
    boolean hasMine = false;
    int adjacentMines = 0;
    CellState state = CellState.HIDDEN;

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

interface MinePlacer {
    void place(Board board, int safeRow, int safeCol, int count);
}

class RandomMinePlacer implements MinePlacer {
    private final Random rng;
    RandomMinePlacer(Random rng) { this.rng = rng; }

    public void place(Board board, int safeRow, int safeCol, int count) {
        List<int[]> candidates = new ArrayList<>();
        for (int r = 0; r < board.rows; r++)
            for (int c = 0; c < board.cols; c++)
                if (Math.abs(r - safeRow) > 1 || Math.abs(c - safeCol) > 1)
                    candidates.add(new int[]{r, c});

        if (count > candidates.size()) throw new IllegalArgumentException("too many mines");
        Collections.shuffle(candidates, rng);
        for (int i = 0; i < count; i++) {
            int[] pos = candidates.get(i);
            board.grid[pos[0]][pos[1]].hasMine = true;
        }
        for (int r = 0; r < board.rows; r++) {
            for (int c = 0; c < board.cols; c++) {
                if (board.grid[r][c].hasMine) continue;
                int count2 = 0;
                for (Cell n : board.neighbors(r, c)) if (n.hasMine) count2++;
                board.grid[r][c].adjacentMines = count2;
            }
        }
    }
}

class Board {
    private static final int[][] DELTAS = {
        {-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}
    };
    final int rows, cols, mineCount;
    final Cell[][] grid;
    private final MinePlacer placer;
    private boolean minesPlaced = false;

    Board(int rows, int cols, int mineCount, MinePlacer placer) {
        if (rows <= 0 || cols <= 0) throw new IllegalArgumentException("positive dims");
        if (mineCount >= rows * cols) throw new IllegalArgumentException("too many mines");
        this.rows = rows; this.cols = cols; this.mineCount = mineCount; this.placer = placer;
        this.grid = new Cell[rows][cols];
        for (int r = 0; r < rows; r++)
            for (int c = 0; c < cols; c++)
                grid[r][c] = new Cell(r, c);
    }

    List<Cell> neighbors(int r, int c) {
        List<Cell> out = new ArrayList<>(8);
        for (int[] d : DELTAS) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) out.add(grid[nr][nc]);
        }
        return out;
    }

    List<Cell> reveal(int r, int c) {
        if (!minesPlaced) { placer.place(this, r, c, mineCount); minesPlaced = true; }
        Cell cell = grid[r][c];
        if (cell.state != CellState.HIDDEN) return List.of();

        List<Cell> out = new ArrayList<>();
        if (cell.hasMine) { cell.state = CellState.REVEALED; out.add(cell); return out; }

        Deque<Cell> q = new ArrayDeque<>();
        cell.state = CellState.REVEALED; out.add(cell); q.offer(cell);
        while (!q.isEmpty()) {
            Cell curr = q.poll();
            if (curr.adjacentMines != 0) continue;
            for (Cell n : neighbors(curr.row, curr.col)) {
                if (n.state == CellState.HIDDEN && !n.hasMine) {
                    n.state = CellState.REVEALED;
                    out.add(n); q.offer(n);
                }
            }
        }
        return out;
    }

    void flag(int r, int c) {
        Cell cell = grid[r][c];
        if (cell.state == CellState.REVEALED) return;
        cell.state = cell.state == CellState.HIDDEN ? CellState.FLAGGED : CellState.HIDDEN;
    }

    boolean allSafeRevealed() {
        for (Cell[] row : grid)
            for (Cell cell : row)
                if (!cell.hasMine && cell.state != CellState.REVEALED) return false;
        return true;
    }
}

public class Minesweeper {
    private final Board board;
    private GameStatus status = GameStatus.PLAYING;
    private java.time.Instant startedAt;
    private java.time.Instant finishedAt;

    public Minesweeper(int rows, int cols, int mines, MinePlacer placer) {
        this.board = new Board(rows, cols, mines, placer);
    }

    public Board board() { return board; }

    public GameStatus reveal(int r, int c) {
        if (status != GameStatus.PLAYING) return status;
        if (startedAt == null) startedAt = java.time.Instant.now();
        List<Cell> revealed = board.reveal(r, c);
        for (Cell cell : revealed) {
            if (cell.hasMine) {
                status = GameStatus.LOST;
                finishedAt = java.time.Instant.now();
                return status;
            }
        }
        if (board.allSafeRevealed()) {
            status = GameStatus.WON;
            finishedAt = java.time.Instant.now();
        }
        return status;
    }

    public void flag(int r, int c) { if (status == GameStatus.PLAYING) board.flag(r, c); }

    public GameStatus chord(int r, int c) {
        if (status != GameStatus.PLAYING) return status;
        Cell cell = board.grid[r][c];
        if (cell.state != CellState.REVEALED || cell.adjacentMines == 0) return status;
        int flagged = 0;
        for (Cell n : board.neighbors(r, c)) if (n.state == CellState.FLAGGED) flagged++;
        if (flagged != cell.adjacentMines) return status;
        for (Cell n : board.neighbors(r, c)) {
            if (n.state == CellState.HIDDEN) {
                GameStatus result = reveal(n.row, n.col);
                if (result == GameStatus.LOST) return result;
            }
        }
        return status;
    }

    public double elapsedSeconds() {
        if (startedAt == null) return 0.0;
        java.time.Instant end = finishedAt != null ? finishedAt : java.time.Instant.now();
        return java.time.Duration.between(startedAt, end).toMillis() / 1000.0;
    }

    public GameStatus getStatus() { return status; }

    public static void main(String[] args) {
        Minesweeper game = new Minesweeper(5, 5, 5, new RandomMinePlacer(new Random(7)));
        game.reveal(0, 0);
        System.out.println("Status after first reveal: " + game.getStatus());
        for (int r = 0; r < 5; r++)
            for (int c = 0; c < 5; c++) game.reveal(r, c);
        System.out.println("Final: " + game.getStatus() + " elapsed: " +
            String.format("%.3fs", game.elapsedSeconds()));

        // Chord: correct flags unlock the rest.
        Minesweeper chordGame = new Minesweeper(3, 3, 1, new RandomMinePlacer(new Random(2)));
        chordGame.reveal(0, 0);
        int[] target = null;
        for (int r = 0; r < 3 && target == null; r++)
            for (int c = 0; c < 3 && target == null; c++) {
                Cell cell = chordGame.board().grid[r][c];
                if (cell.state == CellState.REVEALED && cell.adjacentMines == 1)
                    target = new int[]{r, c};
            }
        if (target != null) {
            for (Cell n : chordGame.board().neighbors(target[0], target[1])) {
                if (n.hasMine) { chordGame.flag(n.row, n.col); break; }
            }
            GameStatus after = chordGame.chord(target[0], target[1]);
            System.out.println("Chord result: " + after);
        }
    }
}

Interview Grading by Level

What an interviewer at each level expects to see in your answer. Use this to calibrate, not to perform.

Junior Engineer (L3)

Builds a grid, places mines, and implements a basic reveal, but misses lazy placement, the flood fill or the win condition.

Signals

Models Cell with has_mine and a revealed flag.
Builds a Board with rows, cols, and a 2D grid of cells.
Implements a basic reveal that marks cells revealed and returns whether a mine was hit.
Adds a flag toggle for the UI.
Recognises that adjacent-mine counts need to be computed somewhere.

Common gaps at this level

Places mines at board construction, so the first click can immediately hit a mine.
Uses recursive DFS for flood fill, risking stack overflow on large zero clusters.
Defines the win condition as all flags on mines, which forces the user to flag perfectly.
Recomputes adjacent-mine counts during reveal instead of once at generation, making cascades slow.
Forgets to mark cells visited during flood fill, causing infinite loops on the first zero click.

Mid-Level Engineer (L4)

Drives the design with lazy first-click-safe placement, pre-computed adjacent counts, iterative BFS flood fill, and the all-safe-cells-revealed win check.

Signals

MinePlacer is an interface with RandomMinePlacer as a concrete, taking an optional rng for deterministic tests.
Lazy placement triggered inside Board.reveal on the first call, skipping the 3x3 around the safe cell.
Adjacent_mines pre-computed once for every non-mine cell after placement.
Iterative BFS with a deque for the flood fill, with the skip-if-nonzero check stopping the cascade at border numbers.
Win condition is all_safe_revealed (every non-mine cell in REVEALED state); flags are excluded.
Game wraps Board with status, started_at, finished_at, where the timer starts on first reveal.

Common gaps at this level

Does not implement chord-click unless prompted.
Does not volunteer save/load or hint system as extensions.
Treats no-guessing board generation as the same problem as random placement, missing the constraint-solver framing.

Senior Engineer (L5+)

Volunteers chord-click, save/load, and no-guessing generation, names BFS over DFS for the stack-depth reason, and frames the pre-computed adjacent_mines as the cascade-time optimisation.

Signals

Implements chord-click that reuses Game.reveal so wrong flags lose through the same code path as a direct mine click.
Volunteers serialisation of the grid plus mines_placed=True flag for save/load so the placer never reruns on restore.
Volunteers a hint system that picks any non-mine HIDDEN cell as a tutorial-mode helper.
Frames no-guessing board generation as a constraint-solver problem run post-placement, with the reroll-if-not-solvable loop and the offline-puzzle-pack caveat.
Names the Python recursion limit (1000) and explains the cascade-size risk as the reason for iterative BFS.
Names the timer-starts-on-first-reveal rule explicitly, distinguishing game construction from session start.
Closes with a one-sentence summary that names the three classes, two enums, lazy placement, and O(1) reveal in under 20 seconds.

Common Mistakes

✗Checking 'all flags on mines' for the win condition. That forces the user to flag perfectly — not how the game works.
✗Placing mines at board creation. If the first click lands on a mine, the game ends before it starts — bad UX.
✗Revealing recursively without a visited set. Infinite loop on the first zero-cell click.
✗Storing only mine positions and recomputing counts per reveal. Slow and error-prone.

Key Points

✓Pre-compute adjacent-mine count once at board generation. Reveal becomes O(1) per cell.
✓Flood fill on reveal when adjacent count is 0 — BFS from the clicked cell through zero-cells.
✓First-click-safe: place mines *after* the first reveal and away from the clicked cell.
✓Win condition: all non-mine cells revealed, regardless of flags. Flags are just a UI hint.
✓Chord click: on a revealed number cell with matching flagged neighbors, auto-reveal the rest. Wrong flags → loss.
✓Timer starts on first reveal and stops on terminal status — clock doesn't tick before the player commits.

Key Abstractions

Class Diagram

The Key Insight

Requirements

Functional

Non-Functional

Design Decisions

Why precompute adjacent counts?

Why MinePlacer as a Strategy?

Why lazy mine placement?

Why CellState.FLAGGED as a tristate?

Why BFS instead of DFS for flood fill?

Interview Follow-ups

45-Minute LLD Playbook

Clarify the rules and lock the data model

Sketch the grid model and the reveal cascade

Code in this sequence (bottom-up)

Trade-offs and extensions

Code Implementation

Interview Grading by Level

Junior Engineer (L3)

Mid-Level Engineer (L4)

Senior Engineer (L5+)

Common Mistakes

Key Points

Related Designs

Key Abstractions

Class Diagram

The Key Insight

Requirements

Functional

Non-Functional

Design Decisions

Why precompute adjacent counts?

Why MinePlacer as a Strategy?

Why lazy mine placement?

Why CellState.FLAGGED as a tristate?

Why BFS instead of DFS for flood fill?

Interview Follow-ups

45-Minute LLD Playbook

Clarify the rules and lock the data model

Sketch the grid model and the reveal cascade

Code in this sequence (bottom-up)

Trade-offs and extensions

Code Implementation

Interview Grading by Level

Junior Engineer (L3)

Mid-Level Engineer (L4)

Senior Engineer (L5+)

Common Mistakes

Key Points

Related Designs

Why `CellState.FLAGGED` as a tristate?

Why `CellState.FLAGGED` as a tristate?