Games & SimulationsProblem 10 of 11

Games & SimulationsAdvanced

Chess

Each piece owns its move generation via Strategy. Command pattern wraps every move so you can undo it during check validation. Board stays clean.

Key Abstractions

Game

Turn management, game state transitions, coordinates between board and move validation

Board

8x8 grid, executes and undoes moves, tracks piece positions by color

Piece

Abstract base with color, position, and delegated move generation

King / Queen / Rook / Bishop / Knight / Pawn

Concrete pieces, each implementing its own legal move generation

MoveValidator

Filters pseudo-legal moves by checking if they leave the king in check

Move

Value object with from/to squares, captured piece, and special flags (castling, promotion)

GameState

Enum: IN_PROGRESS, CHECK, CHECKMATE, STALEMATE

Class Diagram

Every Piece Knows How It Moves

Chess has six piece types and each one moves differently. You could put all the movement rules in a giant switch statement inside Board, but that turns the Board class into a knowledge dump for every piece's quirks. Instead, give each piece its own getPseudoLegalMoves method. King knows it moves one square in any direction. Knight knows it jumps in L-shapes. Sliding pieces (rook, bishop, queen) share a template method that walks along direction vectors until hitting the edge or another piece.

"Pseudo-legal" is an important distinction. A piece might generate a move that looks valid based on its own movement rules but actually leaves the king in check. That filtering happens one level up, in the MoveValidator. This two-phase approach keeps piece logic simple and testable in isolation.

The other critical pattern here is Command on moves. Every Move object carries enough information to undo itself: the piece that moved, where it came from, where it went, and what it captured. This undo capability isn't just nice for implementing a "take back" feature. It's essential for check validation. To determine whether a move is legal, you execute it, check if your king is in check, then undo it. Without undo, you'd need to clone the entire board for every candidate move. On a board with 30+ legal moves per position, that's a lot of garbage.

Requirements

Functional

Standard 8x8 board with all six piece types
Each piece generates its own legal moves based on chess rules
Move validation rejects moves that leave the king in check
Detect check, checkmate, and stalemate after every move
Support basic pawn movement (forward, two-square start, diagonal capture)

Non-Functional

Move generation per piece should be self-contained and independently testable
Check validation should reuse move/undo rather than cloning the board
Adding a new piece type should not require modifying existing piece classes

Design Decisions

Why does each piece own its move generation?

Single responsibility. A King, a Knight, and a Pawn have completely different movement rules. Centralizing them in Board creates a class that changes every time any piece's rules change. With move generation on the piece itself, adding a fairy chess piece (like an Amazon or Archbishop) means writing one new class. Nothing else changes.

Why Command pattern for moves instead of board cloning?

Check validation requires "what if" analysis: execute a candidate move, see if the king is attacked, then roll back. Cloning an 8x8 board with piece references for each of the ~30 candidate moves per turn is wasteful. A Move object that stores the before-state (from position, captured piece) gives you O(1) undo. Execute, check, undo. No allocations, no deep copies.

Why not use inheritance for piece color (WhiteKing, BlackKing)?

Color doesn't change behavior. A white rook and a black rook move the same way. Color is just a data field that determines which side a piece belongs to. Creating separate subclasses per color doubles the class count for zero behavioral difference. Composition handles this cleanly: the piece has a color field, and move generation uses it to determine which pieces are friendly vs. enemy.

Why separate MoveValidator from Board?

Board manages the grid: placing pieces, executing moves, undoing moves. MoveValidator answers the question "is this move legal?" and "is this color in check?" These are different responsibilities. You can test Board's execute/undo without involving check logic. You can test check detection with a carefully arranged board without going through the full game flow.

Interview Follow-ups

"How would you add castling?" Special-case in King's move generation. Check that the king and rook haven't moved (add a hasMoved flag), that squares between them are empty, and that the king doesn't pass through check. Represent it as a Move with a special flag that triggers both king and rook movement in execute/undo.
"How would you add en passant?" Track the last move. If it was a pawn double-step, the adjacent pawn can capture to the square behind it. Store a board-level enPassantTarget position that resets every turn.
"How would you implement an AI player?" Minimax with alpha-beta pruning. The Game class already produces legal moves. AI evaluates board positions using a heuristic (material count, piece-square tables) and picks the best move.
"How would you handle draw by repetition or the 50-move rule?" Maintain a move history list and a hash of each board position. Three identical position hashes triggers a draw. A counter that resets on captures and pawn moves tracks the 50-move rule.

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 scope and lock the process
5 min
GoalPin down which chess rules are in scope (movement plus check/checkmate, no castling or en passant), then ask the interviewer whether they want a class diagram or code-first.
Do & Say
1. ASK·1Open with: Are castling, en passant, and pawn promotion in scope? I will park them as extensions and cover the six piece types with basic movement plus check, checkmate, and stalemate detection.
2. SAY·2Pin the board model: 8x8 grid, pieces tracked by color for O(enemy_pieces) check detection. Color is data, not behavior, so no WhiteKing class.
3. SAY·3Lock the legality definition: Pseudo-legal moves come from the piece. A move is legal if applying it does not leave the moving side's king in check. That is the two-phase split.
4. SAY·4Park draws and AI: No 50-move rule, no threefold repetition, no minimax AI. Move history is not tracked for this design.
5. ASK·5Ask the process question: Do you want me to sketch a class diagram on the whiteboard first, or jump to code with the Piece-Board-Move relationships expressed in the code? Either way, I want to budget the remaining 40 minutes deliberately.
Interviewer is grading: You park castling, en passant, and promotion explicitly so they do not creep into v1. You name the pseudo-legal vs legal split unprompted before any code starts.
2
Sketch the API and (optionally) the class diagram
5-10 min
GoalLock the public signatures: Piece.get_pseudo_legal_moves, Board.execute_move/undo_move, MoveValidator.is_legal. Draw the diagram only if requested.
Do & Say
1. SAY·1Name the abstractions: Color enum, GameState enum, Position dataclass, Move dataclass, Piece abstract with six concrete subclasses, Board, MoveValidator, Game.
2. WRITE·2Write the Piece signature: abstract get_pseudo_legal_moves(board) -> list[Move] and abstract symbol() -> str. Sliders share a _slide_moves(board, directions) template method. Say: Pseudo-legal means without considering check. That filtering is one level up in MoveValidator.
3. WRITE·3Write the Move dataclass: piece, from_pos, to_pos, captured (Optional). Captured is what makes undo O(1). No deep copy of the board.
4. WRITE·4Write the Board API: execute_move applies a move in place, undo_move reverses it. find_king(color) returns the king's position. get_pieces_by_color(color) iterates by side. Say: execute plus undo is the Command pattern. We use it to test what-if moves during check validation.
5. WRITE·5Write the MoveValidator API: is_in_check(board, color), is_legal(board, move) executes-checks-undoes, has_legal_moves(board, color). Game uses has_legal_moves to detect checkmate and stalemate.
6. WRITE·6Write the Game API: make_move(from_pos, to_pos) -> bool. Returns false on illegal. Internally generates legal moves for the source piece, applies, then asks MoveValidator if opponent is in check and whether opponent has any legal moves. From those two booleans, the state flips to IN_PROGRESS, CHECK, CHECKMATE, or STALEMATE.
7. SAY·7If a diagram was requested, draw Piece at the top with six subclass arrows. Board, MoveValidator, Game in their own boxes. Move connects to Piece. GameState as an enum on the side.
Interviewer is grading: Method signatures are crisp before any code starts. You name execute/undo as the trick that avoids board cloning during check validation. You explain pseudo-legal vs legal as a deliberate two-phase split.
3
Code in this sequence (bottom-up)
25 min
GoalType the code in the order Color/GameState/Position/Move, Piece base with slide template, the six pieces, Board, MoveValidator, Game so each layer has its dependencies defined when referenced.
Do & Say
1. SAY·1Code Color and GameState enums plus the Position frozen dataclass with is_valid checking 0 <= row, col < 8. (~2 min)
2. SAY·2Code Move as a dataclass with piece, from_pos, to_pos, and captured defaulting to None. Say: captured is the only field that makes undo O(1). Without it we would have to snapshot the whole 64-square grid. (~1 min)
3. SAY·3Code the Piece abstract base. Constructor stores color and position. Abstract get_pseudo_legal_moves and abstract symbol. (~1 min)
4. SAY·4Code _slide_moves template. Walks each direction until it hits the edge, a friendly piece (break without adding), or an enemy piece (add capture move and break). Say: Rook, Bishop, Queen all reuse this. No duplication of the slide loop. (~3 min)
5. SAY·5Code King: 8 unit-offset moves, drop the (0,0) self-square, add capture or empty-target moves. Code Queen, Rook, Bishop as one-liners calling _slide_moves with their direction sets. (~3 min)
6. SAY·6Code Knight: 8 L-shape offsets with the same target-validation as King. (~1 min)
7. SAY·7Code Pawn. Direction sign based on color. Forward one, forward two from start_row, diagonal captures only when an enemy is on the diagonal. (~3 min)
8. SAY·8Say while coding Pawn: Pawn is the weird one because forward and capture move differently. That is why each piece owns its own method. (~1 min)
9. SAY·9Code Board layout and helpers. 8x8 grid plus a dict[Color, list[Piece]] for fast color iteration. place_piece writes the grid and appends to the pieces list. find_king scans the color list for an instance of King. (~2 min)
10. SAY·10Code execute_move and undo_move. Both mutate the grid plus the captured-piece list in opposite directions. Say: undo_move is the exact inverse. If execute and undo are not symmetric, check validation will leave a corrupted board. (~3 min)
11. SAY·11Code MoveValidator.is_in_check and has_legal_moves. is_in_check iterates enemy pieces, generates their pseudo-legal moves, returns True if any target is the king's square. has_legal_moves short-circuits at the first legal move. (~2 min)
12. SAY·12Code is_legal. Executes the candidate move on the board, calls is_in_check on the moving side, undoes the move, returns the negation. Say: execute-test-undo pattern. Zero allocations after the Move object itself. (~2 min)
13. SAY·13Code Game init and make_move part one. Constructor takes a Board, sets current_color = WHITE, state = IN_PROGRESS. make_move looks up the source piece, generates legal moves filtered to those ending at to_pos, executes the first match. (~2 min)
14. SAY·14Code make_move state update. Ask MoveValidator about the opponent: in_check and has_moves give IN_PROGRESS, CHECK, CHECKMATE, or STALEMATE. Flip current_color and return True. (~1 min)
15. SAY·15Mentally walk through one execute-undo to confirm symmetry before declaring done. White Pawn at (6,4) moves to (4,4). execute clears (6,4), writes Pawn to (4,4), sets pawn.position = (4,4). undo writes captured (None in this case) to (4,4), writes Pawn back to (6,4), restores pawn.position. Symmetric. (~2 min)
Interviewer is grading: You name _slide_moves as the template method savings for Rook/Bishop/Queen unprompted. You volunteer the execute/undo symmetry as the invariant that prevents corrupted board state. You confirm with a mental walk-through before declaring done.
4
Trade-offs, extensions, and wrap-up
5 min
GoalName two trade-offs, volunteer two extensions, close with one sentence.
Do & Say
1. SAY·1Trade-off one, piece-owned moves over a Board switch: A flat switch in Board on piece type means every new piece edits Board. Piece-owned moves mean a new piece is a new class with zero edits elsewhere.
2. SAY·2Defend the cost: Six subclasses plus the abstract base instead of one Board with six branches. Worth it for the closed-for-modification win.
3. SAY·3Trade-off two, execute/undo over board cloning: Each turn has roughly 30 candidate moves. Cloning an 8x8 grid 30 times per turn for check validation is real garbage pressure. Move plus undo is O(1) per candidate.
4. SAY·4Defend the cost: execute and undo must be exact inverses, including the captured-piece list. Asymmetry leaves a corrupted board.
5. SAY·5Extension to volunteer, castling: Add a has_moved boolean to King and Rook. King.get_pseudo_legal_moves adds the two-square castle move when has_moved is False on both pieces, intermediate squares are empty, and the king does not pass through check.
6. SAY·6Defend castle encoding: Encode it as a Move with a special flag so execute_move handles the rook movement in the same call. Pass-through-check is verified by simulating one-square moves.
7. SAY·7Extension to volunteer, AI player: Minimax with alpha-beta pruning. MoveValidator.has_legal_moves already enumerates all options. The evaluator scores material plus piece-square tables. The Move/undo plumbing we built is exactly what the search needs to walk and unwalk positions.
8. SAY·8Close with one sentence: Strategy on Piece for movement. Command on Move for O(1) undo. Template Method for sliders. And a two-phase pseudo-legal vs legal split that keeps each layer testable on its own.
Interviewer is grading: You name two concrete trade-offs and quantify the cost of the alternative. You volunteer castling and AI as the natural extensions before being asked. You can summarize the design in under 20 seconds.

Code Implementation

from abc import ABC, abstractmethod
from dataclasses import dataclass
from enum import Enum
from typing import Optional


class Color(Enum):
    WHITE = "white"
    BLACK = "black"

    def opposite(self) -> "Color":
        return Color.BLACK if self == Color.WHITE else Color.WHITE


class GameState(Enum):
    IN_PROGRESS = "in_progress"
    CHECK = "check"
    CHECKMATE = "checkmate"
    STALEMATE = "stalemate"


@dataclass(frozen=True)
class Position:
    row: int
    col: int

    def is_valid(self) -> bool:
        return 0 <= self.row < 8 and 0 <= self.col < 8


@dataclass
class Move:
    piece: "Piece"
    from_pos: Position
    to_pos: Position
    captured: Optional["Piece"] = None


class Piece(ABC):
    def __init__(self, color: Color, position: Position):
        self.color = color
        self.position = position

    @abstractmethod
    def get_pseudo_legal_moves(self, board: "Board") -> list[Move]:
        """Generate moves without considering check constraints."""
        ...

    @abstractmethod
    def symbol(self) -> str: ...

    def _slide_moves(self, board: "Board", directions: list[tuple[int, int]]) -> list[Move]:
        """Template method for sliding pieces (rook, bishop, queen)."""
        moves: list[Move] = []
        for dr, dc in directions:
            r, c = self.position.row + dr, self.position.col + dc
            while 0 <= r < 8 and 0 <= c < 8:
                target = Position(r, c)
                occupant = board.get_piece(r, c)
                if occupant is None:
                    moves.append(Move(self, self.position, target))
                elif occupant.color != self.color:
                    moves.append(Move(self, self.position, target, captured=occupant))
                    break
                else:
                    break
                r, c = r + dr, c + dc
        return moves

    def __repr__(self) -> str:
        return f"{self.symbol()}@({self.position.row},{self.position.col})"


class King(Piece):
    def symbol(self) -> str:
        return "K" if self.color == Color.WHITE else "k"

    def get_pseudo_legal_moves(self, board: "Board") -> list[Move]:
        moves: list[Move] = []
        for dr in (-1, 0, 1):
            for dc in (-1, 0, 1):
                if dr == 0 and dc == 0:
                    continue
                target = Position(self.position.row + dr, self.position.col + dc)
                if not target.is_valid():
                    continue
                occupant = board.get_piece(target.row, target.col)
                if occupant is None or occupant.color != self.color:
                    moves.append(Move(self, self.position, target, captured=occupant))
        return moves


class Queen(Piece):
    def symbol(self) -> str:
        return "Q" if self.color == Color.WHITE else "q"

    def get_pseudo_legal_moves(self, board: "Board") -> list[Move]:
        directions = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
        return self._slide_moves(board, directions)


class Rook(Piece):
    def symbol(self) -> str:
        return "R" if self.color == Color.WHITE else "r"

    def get_pseudo_legal_moves(self, board: "Board") -> list[Move]:
        return self._slide_moves(board, [(-1, 0), (1, 0), (0, -1), (0, 1)])


class Bishop(Piece):
    def symbol(self) -> str:
        return "B" if self.color == Color.WHITE else "b"

    def get_pseudo_legal_moves(self, board: "Board") -> list[Move]:
        return self._slide_moves(board, [(-1, -1), (-1, 1), (1, -1), (1, 1)])


class Knight(Piece):
    def symbol(self) -> str:
        return "N" if self.color == Color.WHITE else "n"

    def get_pseudo_legal_moves(self, board: "Board") -> list[Move]:
        moves: list[Move] = []
        offsets = [(-2, -1), (-2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2), (2, -1), (2, 1)]
        for dr, dc in offsets:
            target = Position(self.position.row + dr, self.position.col + dc)
            if not target.is_valid():
                continue
            occupant = board.get_piece(target.row, target.col)
            if occupant is None or occupant.color != self.color:
                moves.append(Move(self, self.position, target, captured=occupant))
        return moves


class Pawn(Piece):
    def symbol(self) -> str:
        return "P" if self.color == Color.WHITE else "p"

    def get_pseudo_legal_moves(self, board: "Board") -> list[Move]:
        moves: list[Move] = []
        direction = -1 if self.color == Color.WHITE else 1
        start_row = 6 if self.color == Color.WHITE else 1

        # Forward one
        one_ahead = Position(self.position.row + direction, self.position.col)
        if one_ahead.is_valid() and board.get_piece(one_ahead.row, one_ahead.col) is None:
            moves.append(Move(self, self.position, one_ahead))
            # Forward two from starting row
            two_ahead = Position(self.position.row + 2 * direction, self.position.col)
            if (self.position.row == start_row
                    and board.get_piece(two_ahead.row, two_ahead.col) is None):
                moves.append(Move(self, self.position, two_ahead))

        # Diagonal captures
        for dc in (-1, 1):
            diag = Position(self.position.row + direction, self.position.col + dc)
            if not diag.is_valid():
                continue
            occupant = board.get_piece(diag.row, diag.col)
            if occupant is not None and occupant.color != self.color:
                moves.append(Move(self, self.position, diag, captured=occupant))

        return moves


class Board:
    def __init__(self):
        self._grid: list[list[Optional[Piece]]] = [[None] * 8 for _ in range(8)]
        self._pieces: dict[Color, list[Piece]] = {Color.WHITE: [], Color.BLACK: []}

    def place_piece(self, piece: Piece) -> None:
        self._grid[piece.position.row][piece.position.col] = piece
        self._pieces[piece.color].append(piece)

    def get_piece(self, row: int, col: int) -> Optional[Piece]:
        return self._grid[row][col]

    def get_pieces_by_color(self, color: Color) -> list[Piece]:
        return list(self._pieces[color])

    def find_king(self, color: Color) -> Position:
        for piece in self._pieces[color]:
            if isinstance(piece, King):
                return piece.position
        raise RuntimeError(f"No {color.value} king on the board")

    def execute_move(self, move: Move) -> None:
        """Apply a move. Modifies board state in place."""
        if move.captured is not None:
            self._pieces[move.captured.color].remove(move.captured)

        self._grid[move.from_pos.row][move.from_pos.col] = None
        self._grid[move.to_pos.row][move.to_pos.col] = move.piece
        move.piece.position = move.to_pos

    def undo_move(self, move: Move) -> None:
        """Reverse a move. Used during check validation."""
        self._grid[move.to_pos.row][move.to_pos.col] = move.captured
        self._grid[move.from_pos.row][move.from_pos.col] = move.piece
        move.piece.position = move.from_pos

        if move.captured is not None:
            self._pieces[move.captured.color].append(move.captured)

    def display(self) -> str:
        rows = []
        for r in range(8):
            row_str = ""
            for c in range(8):
                piece = self._grid[r][c]
                row_str += piece.symbol() if piece else "."
                row_str += " "
            rows.append(f"{8 - r} {row_str}")
        rows.append("  a b c d e f g h")
        return "\n".join(rows)


class MoveValidator:
    def is_in_check(self, board: Board, color: Color) -> bool:
        king_pos = board.find_king(color)
        enemy_color = color.opposite()
        for piece in board.get_pieces_by_color(enemy_color):
            for move in piece.get_pseudo_legal_moves(board):
                if move.to_pos == king_pos:
                    return True
        return False

    def is_legal(self, board: Board, move: Move) -> bool:
        """A move is legal if it doesn't leave the moving player's king in check."""
        board.execute_move(move)
        in_check = self.is_in_check(board, move.piece.color)
        board.undo_move(move)
        return not in_check

    def get_legal_moves(self, board: Board, color: Color) -> list[Move]:
        legal: list[Move] = []
        for piece in board.get_pieces_by_color(color):
            for move in piece.get_pseudo_legal_moves(board):
                if self.is_legal(board, move):
                    legal.append(move)
        return legal

    def has_legal_moves(self, board: Board, color: Color) -> bool:
        for piece in board.get_pieces_by_color(color):
            for move in piece.get_pseudo_legal_moves(board):
                if self.is_legal(board, move):
                    return True
        return False


class Game:
    def __init__(self, board: Board):
        self._board = board
        self._validator = MoveValidator()
        self._current_color = Color.WHITE
        self._state = GameState.IN_PROGRESS

    @property
    def state(self) -> GameState:
        return self._state

    def make_move(self, from_pos: Position, to_pos: Position) -> bool:
        piece = self._board.get_piece(from_pos.row, from_pos.col)
        if piece is None or piece.color != self._current_color:
            print(f"No {self._current_color.value} piece at {from_pos}")
            return False

        legal_moves = [
            m for m in piece.get_pseudo_legal_moves(self._board)
            if m.to_pos == to_pos and self._validator.is_legal(self._board, m)
        ]

        if not legal_moves:
            print(f"Illegal move: {from_pos} -> {to_pos}")
            return False

        move = legal_moves[0]
        self._board.execute_move(move)

        opponent = self._current_color.opposite()
        in_check = self._validator.is_in_check(self._board, opponent)
        has_moves = self._validator.has_legal_moves(self._board, opponent)

        if in_check and not has_moves:
            self._state = GameState.CHECKMATE
        elif in_check:
            self._state = GameState.CHECK
        elif not has_moves:
            self._state = GameState.STALEMATE
        else:
            self._state = GameState.IN_PROGRESS

        self._current_color = opponent
        return True

    def display(self) -> None:
        print(self._board.display())
        print(f"Turn: {self._current_color.value} | State: {self._state.value}")
        print()


def setup_standard_board() -> Board:
    board = Board()
    # Black pieces (rows 0-1)
    piece_order = [Rook, Knight, Bishop, Queen, King, Bishop, Knight, Rook]
    for col, piece_cls in enumerate(piece_order):
        board.place_piece(piece_cls(Color.BLACK, Position(0, col)))
    for col in range(8):
        board.place_piece(Pawn(Color.BLACK, Position(1, col)))

    # White pieces (rows 6-7)
    for col, piece_cls in enumerate(piece_order):
        board.place_piece(piece_cls(Color.WHITE, Position(7, col)))
    for col in range(8):
        board.place_piece(Pawn(Color.WHITE, Position(6, col)))

    return board


if __name__ == "__main__":
    board = setup_standard_board()
    game = Game(board)

    print("=== Chess Game Demo ===\n")
    game.display()

    # Scholar's mate sequence (4-move checkmate)
    moves = [
        # White: King's pawn to e4
        (Position(6, 4), Position(4, 4)),
        # Black: King's pawn to e5
        (Position(1, 4), Position(3, 4)),
        # White: Bishop to c4
        (Position(7, 5), Position(4, 2)),
        # Black: Knight to c6
        (Position(0, 1), Position(2, 2)),
        # White: Queen to h5
        (Position(7, 3), Position(3, 7)),
        # Black: Knight to f6 (trying to block)
        (Position(0, 6), Position(2, 5)),
        # White: Queen takes f7 (checkmate)
        (Position(3, 7), Position(1, 5)),
    ]

    for i, (from_pos, to_pos) in enumerate(moves):
        color = "White" if i % 2 == 0 else "Black"
        piece = board.get_piece(from_pos.row, from_pos.col)
        piece_name = piece.__class__.__name__ if piece else "?"
        print(f"Move {i + 1}: {color} {piece_name} {from_pos} -> {to_pos}")
        success = game.make_move(from_pos, to_pos)
        if not success:
            print("Move failed!")
            break
        game.display()

        if game.state in (GameState.CHECKMATE, GameState.STALEMATE):
            print(f"Game over: {game.state.value}")
            break

import java.util.*;

enum Color {
    WHITE, BLACK;
    Color opposite() { return this == WHITE ? BLACK : WHITE; }
}

enum GameState { IN_PROGRESS, CHECK, CHECKMATE, STALEMATE }

class Position {
    final int row, col;
    Position(int row, int col) { this.row = row; this.col = col; }
    boolean isValid() { return row >= 0 && row < 8 && col >= 0 && col < 8; }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Position p)) return false;
        return row == p.row && col == p.col;
    }

    @Override
    public int hashCode() { return Objects.hash(row, col); }

    @Override
    public String toString() { return "(" + row + "," + col + ")"; }
}

class Move {
    final Piece piece;
    final Position from;
    final Position to;
    final Piece captured;

    Move(Piece piece, Position from, Position to, Piece captured) {
        this.piece = piece;
        this.from = from;
        this.to = to;
        this.captured = captured;
    }
}

abstract class Piece {
    Color color;
    Position position;

    Piece(Color color, Position position) {
        this.color = color;
        this.position = position;
    }

    abstract List<Move> getPseudoLegalMoves(Board board);
    abstract String symbol();

    List<Move> slideMoves(Board board, int[][] directions) {
        List<Move> moves = new ArrayList<>();
        for (int[] dir : directions) {
            int r = position.row + dir[0], c = position.col + dir[1];
            while (r >= 0 && r < 8 && c >= 0 && c < 8) {
                Position target = new Position(r, c);
                Piece occupant = board.getPiece(r, c);
                if (occupant == null) {
                    moves.add(new Move(this, position, target, null));
                } else {
                    if (occupant.color != this.color)
                        moves.add(new Move(this, position, target, occupant));
                    break;
                }
                r += dir[0];
                c += dir[1];
            }
        }
        return moves;
    }
}

class King extends Piece {
    King(Color c, Position p) { super(c, p); }
    String symbol() { return color == Color.WHITE ? "K" : "k"; }

    List<Move> getPseudoLegalMoves(Board board) {
        List<Move> moves = new ArrayList<>();
        for (int dr = -1; dr <= 1; dr++) {
            for (int dc = -1; dc <= 1; dc++) {
                if (dr == 0 && dc == 0) continue;
                Position t = new Position(position.row + dr, position.col + dc);
                if (!t.isValid()) continue;
                Piece occ = board.getPiece(t.row, t.col);
                if (occ == null || occ.color != color)
                    moves.add(new Move(this, position, t, occ));
            }
        }
        return moves;
    }
}

class Queen extends Piece {
    Queen(Color c, Position p) { super(c, p); }
    String symbol() { return color == Color.WHITE ? "Q" : "q"; }

    List<Move> getPseudoLegalMoves(Board board) {
        return slideMoves(board, new int[][]{{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}});
    }
}

class Rook extends Piece {
    Rook(Color c, Position p) { super(c, p); }
    String symbol() { return color == Color.WHITE ? "R" : "r"; }

    List<Move> getPseudoLegalMoves(Board board) {
        return slideMoves(board, new int[][]{{-1,0},{1,0},{0,-1},{0,1}});
    }
}

class Bishop extends Piece {
    Bishop(Color c, Position p) { super(c, p); }
    String symbol() { return color == Color.WHITE ? "B" : "b"; }

    List<Move> getPseudoLegalMoves(Board board) {
        return slideMoves(board, new int[][]{{-1,-1},{-1,1},{1,-1},{1,1}});
    }
}

class Knight extends Piece {
    Knight(Color c, Position p) { super(c, p); }
    String symbol() { return color == Color.WHITE ? "N" : "n"; }

    List<Move> getPseudoLegalMoves(Board board) {
        List<Move> moves = new ArrayList<>();
        int[][] offsets = {{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}};
        for (int[] o : offsets) {
            Position t = new Position(position.row + o[0], position.col + o[1]);
            if (!t.isValid()) continue;
            Piece occ = board.getPiece(t.row, t.col);
            if (occ == null || occ.color != color)
                moves.add(new Move(this, position, t, occ));
        }
        return moves;
    }
}

class Pawn extends Piece {
    Pawn(Color c, Position p) { super(c, p); }
    String symbol() { return color == Color.WHITE ? "P" : "p"; }

    List<Move> getPseudoLegalMoves(Board board) {
        List<Move> moves = new ArrayList<>();
        int dir = color == Color.WHITE ? -1 : 1;
        int startRow = color == Color.WHITE ? 6 : 1;

        Position oneAhead = new Position(position.row + dir, position.col);
        if (oneAhead.isValid() && board.getPiece(oneAhead.row, oneAhead.col) == null) {
            moves.add(new Move(this, position, oneAhead, null));
            Position twoAhead = new Position(position.row + 2 * dir, position.col);
            if (position.row == startRow && board.getPiece(twoAhead.row, twoAhead.col) == null)
                moves.add(new Move(this, position, twoAhead, null));
        }

        for (int dc : new int[]{-1, 1}) {
            Position diag = new Position(position.row + dir, position.col + dc);
            if (!diag.isValid()) continue;
            Piece occ = board.getPiece(diag.row, diag.col);
            if (occ != null && occ.color != color)
                moves.add(new Move(this, position, diag, occ));
        }
        return moves;
    }
}

class Board {
    private final Piece[][] grid = new Piece[8][8];
    private final Map<Color, List<Piece>> pieces = new HashMap<>();

    Board() {
        pieces.put(Color.WHITE, new ArrayList<>());
        pieces.put(Color.BLACK, new ArrayList<>());
    }

    void placePiece(Piece piece) {
        grid[piece.position.row][piece.position.col] = piece;
        pieces.get(piece.color).add(piece);
    }

    Piece getPiece(int row, int col) { return grid[row][col]; }

    List<Piece> getPiecesByColor(Color color) {
        return new ArrayList<>(pieces.get(color));
    }

    Position findKing(Color color) {
        for (Piece p : pieces.get(color))
            if (p instanceof King) return p.position;
        throw new RuntimeException("No " + color + " king found");
    }

    void executeMove(Move move) {
        if (move.captured != null)
            pieces.get(move.captured.color).remove(move.captured);
        grid[move.from.row][move.from.col] = null;
        grid[move.to.row][move.to.col] = move.piece;
        move.piece.position = move.to;
    }

    void undoMove(Move move) {
        grid[move.to.row][move.to.col] = move.captured;
        grid[move.from.row][move.from.col] = move.piece;
        move.piece.position = move.from;
        if (move.captured != null)
            pieces.get(move.captured.color).add(move.captured);
    }

    String display() {
        StringBuilder sb = new StringBuilder();
        for (int r = 0; r < 8; r++) {
            sb.append(8 - r).append(" ");
            for (int c = 0; c < 8; c++) {
                Piece p = grid[r][c];
                sb.append(p != null ? p.symbol() : ".").append(" ");
            }
            sb.append("\n");
        }
        sb.append("  a b c d e f g h");
        return sb.toString();
    }
}

class MoveValidator {
    boolean isInCheck(Board board, Color color) {
        Position kingPos = board.findKing(color);
        for (Piece p : board.getPiecesByColor(color.opposite()))
            for (Move m : p.getPseudoLegalMoves(board))
                if (m.to.equals(kingPos)) return true;
        return false;
    }

    boolean isLegal(Board board, Move move) {
        board.executeMove(move);
        boolean inCheck = isInCheck(board, move.piece.color);
        board.undoMove(move);
        return !inCheck;
    }

    List<Move> getLegalMoves(Board board, Color color) {
        List<Move> legal = new ArrayList<>();
        for (Piece p : board.getPiecesByColor(color))
            for (Move m : p.getPseudoLegalMoves(board))
                if (isLegal(board, m)) legal.add(m);
        return legal;
    }

    boolean hasLegalMoves(Board board, Color color) {
        for (Piece p : board.getPiecesByColor(color))
            for (Move m : p.getPseudoLegalMoves(board))
                if (isLegal(board, m)) return true;
        return false;
    }
}

public class Chess {
    private final Board board;
    private final MoveValidator validator = new MoveValidator();
    private Color currentColor = Color.WHITE;
    private GameState state = GameState.IN_PROGRESS;

    public Chess(Board board) { this.board = board; }

    public GameState getState() { return state; }

    public boolean makeMove(Position from, Position to) {
        Piece piece = board.getPiece(from.row, from.col);
        if (piece == null || piece.color != currentColor) {
            System.out.println("No " + currentColor + " piece at " + from);
            return false;
        }

        Move chosen = null;
        for (Move m : piece.getPseudoLegalMoves(board)) {
            if (m.to.equals(to) && validator.isLegal(board, m)) {
                chosen = m;
                break;
            }
        }

        if (chosen == null) {
            System.out.println("Illegal move: " + from + " -> " + to);
            return false;
        }

        board.executeMove(chosen);

        Color opponent = currentColor.opposite();
        boolean inCheck = validator.isInCheck(board, opponent);
        boolean hasMoves = validator.hasLegalMoves(board, opponent);

        if (inCheck && !hasMoves) state = GameState.CHECKMATE;
        else if (inCheck) state = GameState.CHECK;
        else if (!hasMoves) state = GameState.STALEMATE;
        else state = GameState.IN_PROGRESS;

        currentColor = opponent;
        return true;
    }

    public void display() {
        System.out.println(board.display());
        System.out.println("Turn: " + currentColor + " | State: " + state + "\n");
    }

    static Board setupStandardBoard() {
        Board board = new Board();
        // Black pieces
        board.placePiece(new Rook(Color.BLACK, new Position(0, 0)));
        board.placePiece(new Knight(Color.BLACK, new Position(0, 1)));
        board.placePiece(new Bishop(Color.BLACK, new Position(0, 2)));
        board.placePiece(new Queen(Color.BLACK, new Position(0, 3)));
        board.placePiece(new King(Color.BLACK, new Position(0, 4)));
        board.placePiece(new Bishop(Color.BLACK, new Position(0, 5)));
        board.placePiece(new Knight(Color.BLACK, new Position(0, 6)));
        board.placePiece(new Rook(Color.BLACK, new Position(0, 7)));
        for (int c = 0; c < 8; c++)
            board.placePiece(new Pawn(Color.BLACK, new Position(1, c)));

        // White pieces
        board.placePiece(new Rook(Color.WHITE, new Position(7, 0)));
        board.placePiece(new Knight(Color.WHITE, new Position(7, 1)));
        board.placePiece(new Bishop(Color.WHITE, new Position(7, 2)));
        board.placePiece(new Queen(Color.WHITE, new Position(7, 3)));
        board.placePiece(new King(Color.WHITE, new Position(7, 4)));
        board.placePiece(new Bishop(Color.WHITE, new Position(7, 5)));
        board.placePiece(new Knight(Color.WHITE, new Position(7, 6)));
        board.placePiece(new Rook(Color.WHITE, new Position(7, 7)));
        for (int c = 0; c < 8; c++)
            board.placePiece(new Pawn(Color.WHITE, new Position(6, c)));

        return board;
    }

    public static void main(String[] args) {
        Board board = setupStandardBoard();
        Chess game = new Chess(board);

        System.out.println("=== Chess Game Demo ===\n");
        game.display();

        // Scholar's mate
        int[][] moves = {
            {6, 4, 4, 4},  // White e2->e4
            {1, 4, 3, 4},  // Black e7->e5
            {7, 5, 4, 2},  // White Bf1->c4
            {0, 1, 2, 2},  // Black Nb8->c6
            {7, 3, 3, 7},  // White Qd1->h5
            {0, 6, 2, 5},  // Black Ng8->f6
            {3, 7, 1, 5},  // White Qh5xf7 checkmate
        };

        for (int i = 0; i < moves.length; i++) {
            String color = i % 2 == 0 ? "White" : "Black";
            Position from = new Position(moves[i][0], moves[i][1]);
            Position to = new Position(moves[i][2], moves[i][3]);
            Piece piece = board.getPiece(from.row, from.col);
            String pieceName = piece != null ? piece.getClass().getSimpleName() : "?";
            System.out.println("Move " + (i + 1) + ": " + color + " " + pieceName + " " + from + " -> " + to);

            boolean success = game.makeMove(from, to);
            if (!success) { System.out.println("Move failed!"); break; }
            game.display();

            if (game.getState() == GameState.CHECKMATE || game.getState() == GameState.STALEMATE) {
                System.out.println("Game over: " + game.getState());
                break;
            }
        }
    }
}

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)

Names the patterns and writes most piece move generation, but check validation and undo are vague or implemented by board cloning.

Signals

Names Strategy and Command correctly when asked which patterns apply.
Writes a Piece abstract class with get_pseudo_legal_moves and at least one concrete piece (King or Knight).
Generates pawn forward and diagonal capture moves separately, recognizing the asymmetry.
Implements is_in_check by iterating enemy pieces' moves looking for the king's square.
Detects checkmate as 'in check plus no legal moves' when prompted.

Common gaps at this level

Implements check validation by deep-cloning the board for every candidate move instead of execute/undo.
Puts a switch statement on piece type inside Board.get_legal_moves rather than delegating to the piece.
Creates WhiteKing and BlackKing subclasses, doubling the piece count for no behavioral difference.
Forgets that captures and empty-target moves both must be added for Knight and King.
Misses stalemate detection, treating no-legal-moves as a loss regardless of whether the king is attacked.

Mid-Level Engineer (L4)

Drives the design end-to-end with piece-owned move generation, an execute/undo pair on Board, and a clean two-phase pseudo-legal vs legal split.

Signals

Writes the Piece base with the _slide_moves template before coding Rook, Bishop, and Queen as one-line subclasses.
Implements execute_move and undo_move as exact inverses, both mutating the grid and the captured-piece list.
Splits move generation (Piece) from move validation (MoveValidator) explicitly, naming the two-phase rationale.
Tracks pieces by color in a dict for fast enemy-iteration during is_in_check.
Computes CHECK, CHECKMATE, STALEMATE, and IN_PROGRESS from the two booleans (in_check, has_legal_moves) on the opponent.
Handles Pawn forward-two only from the starting row, and diagonal capture only when an enemy occupies the target.

Common gaps at this level

Does not volunteer castling or en passant as natural extensions unless prompted.
Misses the has_moved flag on King and Rook as the precondition for castling.
Treats AI as 'walk the move tree' without naming alpha-beta pruning or piece-square evaluation.

Senior Engineer (L5+)

Volunteers castling, en passant, AI, and draw rules before being asked, and frames each pattern around the specific failure it prevents.

Signals

Volunteers castling with the has_moved flag, intermediate-square emptiness check, and king-doesn't-pass-through-check verification without prompting.
Volunteers en passant with the last-move tracking and the board-level en_passant_target reset every turn.
Names execute/undo symmetry as the invariant that prevents corrupted board state during check validation, and stresses that the captured-piece list must be restored exactly.
Frames _slide_moves as the template method that compresses Rook, Bishop, and Queen into three direction-set one-liners instead of three full implementations.
Proposes minimax with alpha-beta pruning for AI, naming material plus piece-square tables for the heuristic, and points out that execute/undo is exactly the plumbing the search needs.
Suggests draw-by-repetition via a hash of (piece positions + side to move) tracked across moves, and the 50-move rule via a counter that resets on captures and pawn moves.
Closes with a one-sentence summary that names Strategy for piece moves, Command for execute/undo, Template Method for sliders, and the pseudo-legal vs legal split in under 20 seconds.

Common Mistakes

✗Putting move generation logic in the Board class instead of each piece. You end up with one massive switch statement.
✗Not implementing undo on moves. Without it, check detection requires cloning the entire board for every candidate move.
✗Using inheritance for color (WhiteKing, BlackKing). Color is data, not behavior. Use composition.
✗Forgetting that a move is only legal if it doesn't leave your own king in check, including discovered checks.

Key Points

✓Each piece generates its own pseudo-legal moves. MoveValidator filters out ones that leave the king exposed.
✓Command pattern on Move allows execute/undo. You need undo to test whether a candidate move leaves you in check.
✓Board tracks all pieces by color for fast iteration when checking if any enemy piece attacks the king's square.
✓GameState is computed after every move: if the opponent has no legal moves, it's either checkmate or stalemate.

Related Designs

Games & SimulationsProblem 10 of 11

Games & SimulationsAdvanced

Chess

Each piece owns its move generation via Strategy. Command pattern wraps every move so you can undo it during check validation. Board stays clean.

Key Abstractions

Game

Turn management, game state transitions, coordinates between board and move validation

Board

8x8 grid, executes and undoes moves, tracks piece positions by color

Piece

Abstract base with color, position, and delegated move generation

King / Queen / Rook / Bishop / Knight / Pawn

Concrete pieces, each implementing its own legal move generation

MoveValidator

Filters pseudo-legal moves by checking if they leave the king in check

Move

Value object with from/to squares, captured piece, and special flags (castling, promotion)

GameState

Enum: IN_PROGRESS, CHECK, CHECKMATE, STALEMATE

Class Diagram

Every Piece Knows How It Moves

Requirements

Functional

Standard 8x8 board with all six piece types
Each piece generates its own legal moves based on chess rules
Move validation rejects moves that leave the king in check
Detect check, checkmate, and stalemate after every move
Support basic pawn movement (forward, two-square start, diagonal capture)

Non-Functional

Move generation per piece should be self-contained and independently testable
Check validation should reuse move/undo rather than cloning the board
Adding a new piece type should not require modifying existing piece classes

Design Decisions

Why does each piece own its move generation?

Why Command pattern for moves instead of board cloning?

Why not use inheritance for piece color (WhiteKing, BlackKing)?

Why separate MoveValidator from Board?

Interview Follow-ups

"How would you add castling?" Special-case in King's move generation. Check that the king and rook haven't moved (add a hasMoved flag), that squares between them are empty, and that the king doesn't pass through check. Represent it as a Move with a special flag that triggers both king and rook movement in execute/undo.
"How would you add en passant?" Track the last move. If it was a pawn double-step, the adjacent pawn can capture to the square behind it. Store a board-level enPassantTarget position that resets every turn.
"How would you implement an AI player?" Minimax with alpha-beta pruning. The Game class already produces legal moves. AI evaluates board positions using a heuristic (material count, piece-square tables) and picks the best move.
"How would you handle draw by repetition or the 50-move rule?" Maintain a move history list and a hash of each board position. Three identical position hashes triggers a draw. A counter that resets on captures and pawn moves tracks the 50-move rule.

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 scope and lock the process
5 min
GoalPin down which chess rules are in scope (movement plus check/checkmate, no castling or en passant), then ask the interviewer whether they want a class diagram or code-first.
Do & Say
1. ASK·1Open with: Are castling, en passant, and pawn promotion in scope? I will park them as extensions and cover the six piece types with basic movement plus check, checkmate, and stalemate detection.
2. SAY·2Pin the board model: 8x8 grid, pieces tracked by color for O(enemy_pieces) check detection. Color is data, not behavior, so no WhiteKing class.
3. SAY·3Lock the legality definition: Pseudo-legal moves come from the piece. A move is legal if applying it does not leave the moving side's king in check. That is the two-phase split.
4. SAY·4Park draws and AI: No 50-move rule, no threefold repetition, no minimax AI. Move history is not tracked for this design.
5. ASK·5Ask the process question: Do you want me to sketch a class diagram on the whiteboard first, or jump to code with the Piece-Board-Move relationships expressed in the code? Either way, I want to budget the remaining 40 minutes deliberately.
Interviewer is grading: You park castling, en passant, and promotion explicitly so they do not creep into v1. You name the pseudo-legal vs legal split unprompted before any code starts.
2
Sketch the API and (optionally) the class diagram
5-10 min
GoalLock the public signatures: Piece.get_pseudo_legal_moves, Board.execute_move/undo_move, MoveValidator.is_legal. Draw the diagram only if requested.
Do & Say
1. SAY·1Name the abstractions: Color enum, GameState enum, Position dataclass, Move dataclass, Piece abstract with six concrete subclasses, Board, MoveValidator, Game.
2. WRITE·2Write the Piece signature: abstract get_pseudo_legal_moves(board) -> list[Move] and abstract symbol() -> str. Sliders share a _slide_moves(board, directions) template method. Say: Pseudo-legal means without considering check. That filtering is one level up in MoveValidator.
3. WRITE·3Write the Move dataclass: piece, from_pos, to_pos, captured (Optional). Captured is what makes undo O(1). No deep copy of the board.
4. WRITE·4Write the Board API: execute_move applies a move in place, undo_move reverses it. find_king(color) returns the king's position. get_pieces_by_color(color) iterates by side. Say: execute plus undo is the Command pattern. We use it to test what-if moves during check validation.
5. WRITE·5Write the MoveValidator API: is_in_check(board, color), is_legal(board, move) executes-checks-undoes, has_legal_moves(board, color). Game uses has_legal_moves to detect checkmate and stalemate.
6. WRITE·6Write the Game API: make_move(from_pos, to_pos) -> bool. Returns false on illegal. Internally generates legal moves for the source piece, applies, then asks MoveValidator if opponent is in check and whether opponent has any legal moves. From those two booleans, the state flips to IN_PROGRESS, CHECK, CHECKMATE, or STALEMATE.
7. SAY·7If a diagram was requested, draw Piece at the top with six subclass arrows. Board, MoveValidator, Game in their own boxes. Move connects to Piece. GameState as an enum on the side.
Interviewer is grading: Method signatures are crisp before any code starts. You name execute/undo as the trick that avoids board cloning during check validation. You explain pseudo-legal vs legal as a deliberate two-phase split.
3
Code in this sequence (bottom-up)
25 min
GoalType the code in the order Color/GameState/Position/Move, Piece base with slide template, the six pieces, Board, MoveValidator, Game so each layer has its dependencies defined when referenced.
Do & Say
1. SAY·1Code Color and GameState enums plus the Position frozen dataclass with is_valid checking 0 <= row, col < 8. (~2 min)
2. SAY·2Code Move as a dataclass with piece, from_pos, to_pos, and captured defaulting to None. Say: captured is the only field that makes undo O(1). Without it we would have to snapshot the whole 64-square grid. (~1 min)
3. SAY·3Code the Piece abstract base. Constructor stores color and position. Abstract get_pseudo_legal_moves and abstract symbol. (~1 min)
4. SAY·4Code _slide_moves template. Walks each direction until it hits the edge, a friendly piece (break without adding), or an enemy piece (add capture move and break). Say: Rook, Bishop, Queen all reuse this. No duplication of the slide loop. (~3 min)
5. SAY·5Code King: 8 unit-offset moves, drop the (0,0) self-square, add capture or empty-target moves. Code Queen, Rook, Bishop as one-liners calling _slide_moves with their direction sets. (~3 min)
6. SAY·6Code Knight: 8 L-shape offsets with the same target-validation as King. (~1 min)
7. SAY·7Code Pawn. Direction sign based on color. Forward one, forward two from start_row, diagonal captures only when an enemy is on the diagonal. (~3 min)
8. SAY·8Say while coding Pawn: Pawn is the weird one because forward and capture move differently. That is why each piece owns its own method. (~1 min)
9. SAY·9Code Board layout and helpers. 8x8 grid plus a dict[Color, list[Piece]] for fast color iteration. place_piece writes the grid and appends to the pieces list. find_king scans the color list for an instance of King. (~2 min)
10. SAY·10Code execute_move and undo_move. Both mutate the grid plus the captured-piece list in opposite directions. Say: undo_move is the exact inverse. If execute and undo are not symmetric, check validation will leave a corrupted board. (~3 min)
11. SAY·11Code MoveValidator.is_in_check and has_legal_moves. is_in_check iterates enemy pieces, generates their pseudo-legal moves, returns True if any target is the king's square. has_legal_moves short-circuits at the first legal move. (~2 min)
12. SAY·12Code is_legal. Executes the candidate move on the board, calls is_in_check on the moving side, undoes the move, returns the negation. Say: execute-test-undo pattern. Zero allocations after the Move object itself. (~2 min)
13. SAY·13Code Game init and make_move part one. Constructor takes a Board, sets current_color = WHITE, state = IN_PROGRESS. make_move looks up the source piece, generates legal moves filtered to those ending at to_pos, executes the first match. (~2 min)
14. SAY·14Code make_move state update. Ask MoveValidator about the opponent: in_check and has_moves give IN_PROGRESS, CHECK, CHECKMATE, or STALEMATE. Flip current_color and return True. (~1 min)
15. SAY·15Mentally walk through one execute-undo to confirm symmetry before declaring done. White Pawn at (6,4) moves to (4,4). execute clears (6,4), writes Pawn to (4,4), sets pawn.position = (4,4). undo writes captured (None in this case) to (4,4), writes Pawn back to (6,4), restores pawn.position. Symmetric. (~2 min)
Interviewer is grading: You name _slide_moves as the template method savings for Rook/Bishop/Queen unprompted. You volunteer the execute/undo symmetry as the invariant that prevents corrupted board state. You confirm with a mental walk-through before declaring done.
4
Trade-offs, extensions, and wrap-up
5 min
GoalName two trade-offs, volunteer two extensions, close with one sentence.
Do & Say
1. SAY·1Trade-off one, piece-owned moves over a Board switch: A flat switch in Board on piece type means every new piece edits Board. Piece-owned moves mean a new piece is a new class with zero edits elsewhere.
2. SAY·2Defend the cost: Six subclasses plus the abstract base instead of one Board with six branches. Worth it for the closed-for-modification win.
3. SAY·3Trade-off two, execute/undo over board cloning: Each turn has roughly 30 candidate moves. Cloning an 8x8 grid 30 times per turn for check validation is real garbage pressure. Move plus undo is O(1) per candidate.
4. SAY·4Defend the cost: execute and undo must be exact inverses, including the captured-piece list. Asymmetry leaves a corrupted board.
5. SAY·5Extension to volunteer, castling: Add a has_moved boolean to King and Rook. King.get_pseudo_legal_moves adds the two-square castle move when has_moved is False on both pieces, intermediate squares are empty, and the king does not pass through check.
6. SAY·6Defend castle encoding: Encode it as a Move with a special flag so execute_move handles the rook movement in the same call. Pass-through-check is verified by simulating one-square moves.
7. SAY·7Extension to volunteer, AI player: Minimax with alpha-beta pruning. MoveValidator.has_legal_moves already enumerates all options. The evaluator scores material plus piece-square tables. The Move/undo plumbing we built is exactly what the search needs to walk and unwalk positions.
8. SAY·8Close with one sentence: Strategy on Piece for movement. Command on Move for O(1) undo. Template Method for sliders. And a two-phase pseudo-legal vs legal split that keeps each layer testable on its own.
Interviewer is grading: You name two concrete trade-offs and quantify the cost of the alternative. You volunteer castling and AI as the natural extensions before being asked. You can summarize the design in under 20 seconds.

Code Implementation

from abc import ABC, abstractmethod
from dataclasses import dataclass
from enum import Enum
from typing import Optional


class Color(Enum):
    WHITE = "white"
    BLACK = "black"

    def opposite(self) -> "Color":
        return Color.BLACK if self == Color.WHITE else Color.WHITE


class GameState(Enum):
    IN_PROGRESS = "in_progress"
    CHECK = "check"
    CHECKMATE = "checkmate"
    STALEMATE = "stalemate"


@dataclass(frozen=True)
class Position:
    row: int
    col: int

    def is_valid(self) -> bool:
        return 0 <= self.row < 8 and 0 <= self.col < 8


@dataclass
class Move:
    piece: "Piece"
    from_pos: Position
    to_pos: Position
    captured: Optional["Piece"] = None


class Piece(ABC):
    def __init__(self, color: Color, position: Position):
        self.color = color
        self.position = position

    @abstractmethod
    def get_pseudo_legal_moves(self, board: "Board") -> list[Move]:
        """Generate moves without considering check constraints."""
        ...

    @abstractmethod
    def symbol(self) -> str: ...

    def _slide_moves(self, board: "Board", directions: list[tuple[int, int]]) -> list[Move]:
        """Template method for sliding pieces (rook, bishop, queen)."""
        moves: list[Move] = []
        for dr, dc in directions:
            r, c = self.position.row + dr, self.position.col + dc
            while 0 <= r < 8 and 0 <= c < 8:
                target = Position(r, c)
                occupant = board.get_piece(r, c)
                if occupant is None:
                    moves.append(Move(self, self.position, target))
                elif occupant.color != self.color:
                    moves.append(Move(self, self.position, target, captured=occupant))
                    break
                else:
                    break
                r, c = r + dr, c + dc
        return moves

    def __repr__(self) -> str:
        return f"{self.symbol()}@({self.position.row},{self.position.col})"


class King(Piece):
    def symbol(self) -> str:
        return "K" if self.color == Color.WHITE else "k"

    def get_pseudo_legal_moves(self, board: "Board") -> list[Move]:
        moves: list[Move] = []
        for dr in (-1, 0, 1):
            for dc in (-1, 0, 1):
                if dr == 0 and dc == 0:
                    continue
                target = Position(self.position.row + dr, self.position.col + dc)
                if not target.is_valid():
                    continue
                occupant = board.get_piece(target.row, target.col)
                if occupant is None or occupant.color != self.color:
                    moves.append(Move(self, self.position, target, captured=occupant))
        return moves


class Queen(Piece):
    def symbol(self) -> str:
        return "Q" if self.color == Color.WHITE else "q"

    def get_pseudo_legal_moves(self, board: "Board") -> list[Move]:
        directions = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
        return self._slide_moves(board, directions)


class Rook(Piece):
    def symbol(self) -> str:
        return "R" if self.color == Color.WHITE else "r"

    def get_pseudo_legal_moves(self, board: "Board") -> list[Move]:
        return self._slide_moves(board, [(-1, 0), (1, 0), (0, -1), (0, 1)])


class Bishop(Piece):
    def symbol(self) -> str:
        return "B" if self.color == Color.WHITE else "b"

    def get_pseudo_legal_moves(self, board: "Board") -> list[Move]:
        return self._slide_moves(board, [(-1, -1), (-1, 1), (1, -1), (1, 1)])


class Knight(Piece):
    def symbol(self) -> str:
        return "N" if self.color == Color.WHITE else "n"

    def get_pseudo_legal_moves(self, board: "Board") -> list[Move]:
        moves: list[Move] = []
        offsets = [(-2, -1), (-2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2), (2, -1), (2, 1)]
        for dr, dc in offsets:
            target = Position(self.position.row + dr, self.position.col + dc)
            if not target.is_valid():
                continue
            occupant = board.get_piece(target.row, target.col)
            if occupant is None or occupant.color != self.color:
                moves.append(Move(self, self.position, target, captured=occupant))
        return moves


class Pawn(Piece):
    def symbol(self) -> str:
        return "P" if self.color == Color.WHITE else "p"

    def get_pseudo_legal_moves(self, board: "Board") -> list[Move]:
        moves: list[Move] = []
        direction = -1 if self.color == Color.WHITE else 1
        start_row = 6 if self.color == Color.WHITE else 1

        # Forward one
        one_ahead = Position(self.position.row + direction, self.position.col)
        if one_ahead.is_valid() and board.get_piece(one_ahead.row, one_ahead.col) is None:
            moves.append(Move(self, self.position, one_ahead))
            # Forward two from starting row
            two_ahead = Position(self.position.row + 2 * direction, self.position.col)
            if (self.position.row == start_row
                    and board.get_piece(two_ahead.row, two_ahead.col) is None):
                moves.append(Move(self, self.position, two_ahead))

        # Diagonal captures
        for dc in (-1, 1):
            diag = Position(self.position.row + direction, self.position.col + dc)
            if not diag.is_valid():
                continue
            occupant = board.get_piece(diag.row, diag.col)
            if occupant is not None and occupant.color != self.color:
                moves.append(Move(self, self.position, diag, captured=occupant))

        return moves


class Board:
    def __init__(self):
        self._grid: list[list[Optional[Piece]]] = [[None] * 8 for _ in range(8)]
        self._pieces: dict[Color, list[Piece]] = {Color.WHITE: [], Color.BLACK: []}

    def place_piece(self, piece: Piece) -> None:
        self._grid[piece.position.row][piece.position.col] = piece
        self._pieces[piece.color].append(piece)

    def get_piece(self, row: int, col: int) -> Optional[Piece]:
        return self._grid[row][col]

    def get_pieces_by_color(self, color: Color) -> list[Piece]:
        return list(self._pieces[color])

    def find_king(self, color: Color) -> Position:
        for piece in self._pieces[color]:
            if isinstance(piece, King):
                return piece.position
        raise RuntimeError(f"No {color.value} king on the board")

    def execute_move(self, move: Move) -> None:
        """Apply a move. Modifies board state in place."""
        if move.captured is not None:
            self._pieces[move.captured.color].remove(move.captured)

        self._grid[move.from_pos.row][move.from_pos.col] = None
        self._grid[move.to_pos.row][move.to_pos.col] = move.piece
        move.piece.position = move.to_pos

    def undo_move(self, move: Move) -> None:
        """Reverse a move. Used during check validation."""
        self._grid[move.to_pos.row][move.to_pos.col] = move.captured
        self._grid[move.from_pos.row][move.from_pos.col] = move.piece
        move.piece.position = move.from_pos

        if move.captured is not None:
            self._pieces[move.captured.color].append(move.captured)

    def display(self) -> str:
        rows = []
        for r in range(8):
            row_str = ""
            for c in range(8):
                piece = self._grid[r][c]
                row_str += piece.symbol() if piece else "."
                row_str += " "
            rows.append(f"{8 - r} {row_str}")
        rows.append("  a b c d e f g h")
        return "\n".join(rows)


class MoveValidator:
    def is_in_check(self, board: Board, color: Color) -> bool:
        king_pos = board.find_king(color)
        enemy_color = color.opposite()
        for piece in board.get_pieces_by_color(enemy_color):
            for move in piece.get_pseudo_legal_moves(board):
                if move.to_pos == king_pos:
                    return True
        return False

    def is_legal(self, board: Board, move: Move) -> bool:
        """A move is legal if it doesn't leave the moving player's king in check."""
        board.execute_move(move)
        in_check = self.is_in_check(board, move.piece.color)
        board.undo_move(move)
        return not in_check

    def get_legal_moves(self, board: Board, color: Color) -> list[Move]:
        legal: list[Move] = []
        for piece in board.get_pieces_by_color(color):
            for move in piece.get_pseudo_legal_moves(board):
                if self.is_legal(board, move):
                    legal.append(move)
        return legal

    def has_legal_moves(self, board: Board, color: Color) -> bool:
        for piece in board.get_pieces_by_color(color):
            for move in piece.get_pseudo_legal_moves(board):
                if self.is_legal(board, move):
                    return True
        return False


class Game:
    def __init__(self, board: Board):
        self._board = board
        self._validator = MoveValidator()
        self._current_color = Color.WHITE
        self._state = GameState.IN_PROGRESS

    @property
    def state(self) -> GameState:
        return self._state

    def make_move(self, from_pos: Position, to_pos: Position) -> bool:
        piece = self._board.get_piece(from_pos.row, from_pos.col)
        if piece is None or piece.color != self._current_color:
            print(f"No {self._current_color.value} piece at {from_pos}")
            return False

        legal_moves = [
            m for m in piece.get_pseudo_legal_moves(self._board)
            if m.to_pos == to_pos and self._validator.is_legal(self._board, m)
        ]

        if not legal_moves:
            print(f"Illegal move: {from_pos} -> {to_pos}")
            return False

        move = legal_moves[0]
        self._board.execute_move(move)

        opponent = self._current_color.opposite()
        in_check = self._validator.is_in_check(self._board, opponent)
        has_moves = self._validator.has_legal_moves(self._board, opponent)

        if in_check and not has_moves:
            self._state = GameState.CHECKMATE
        elif in_check:
            self._state = GameState.CHECK
        elif not has_moves:
            self._state = GameState.STALEMATE
        else:
            self._state = GameState.IN_PROGRESS

        self._current_color = opponent
        return True

    def display(self) -> None:
        print(self._board.display())
        print(f"Turn: {self._current_color.value} | State: {self._state.value}")
        print()


def setup_standard_board() -> Board:
    board = Board()
    # Black pieces (rows 0-1)
    piece_order = [Rook, Knight, Bishop, Queen, King, Bishop, Knight, Rook]
    for col, piece_cls in enumerate(piece_order):
        board.place_piece(piece_cls(Color.BLACK, Position(0, col)))
    for col in range(8):
        board.place_piece(Pawn(Color.BLACK, Position(1, col)))

    # White pieces (rows 6-7)
    for col, piece_cls in enumerate(piece_order):
        board.place_piece(piece_cls(Color.WHITE, Position(7, col)))
    for col in range(8):
        board.place_piece(Pawn(Color.WHITE, Position(6, col)))

    return board


if __name__ == "__main__":
    board = setup_standard_board()
    game = Game(board)

    print("=== Chess Game Demo ===\n")
    game.display()

    # Scholar's mate sequence (4-move checkmate)
    moves = [
        # White: King's pawn to e4
        (Position(6, 4), Position(4, 4)),
        # Black: King's pawn to e5
        (Position(1, 4), Position(3, 4)),
        # White: Bishop to c4
        (Position(7, 5), Position(4, 2)),
        # Black: Knight to c6
        (Position(0, 1), Position(2, 2)),
        # White: Queen to h5
        (Position(7, 3), Position(3, 7)),
        # Black: Knight to f6 (trying to block)
        (Position(0, 6), Position(2, 5)),
        # White: Queen takes f7 (checkmate)
        (Position(3, 7), Position(1, 5)),
    ]

    for i, (from_pos, to_pos) in enumerate(moves):
        color = "White" if i % 2 == 0 else "Black"
        piece = board.get_piece(from_pos.row, from_pos.col)
        piece_name = piece.__class__.__name__ if piece else "?"
        print(f"Move {i + 1}: {color} {piece_name} {from_pos} -> {to_pos}")
        success = game.make_move(from_pos, to_pos)
        if not success:
            print("Move failed!")
            break
        game.display()

        if game.state in (GameState.CHECKMATE, GameState.STALEMATE):
            print(f"Game over: {game.state.value}")
            break

import java.util.*;

enum Color {
    WHITE, BLACK;
    Color opposite() { return this == WHITE ? BLACK : WHITE; }
}

enum GameState { IN_PROGRESS, CHECK, CHECKMATE, STALEMATE }

class Position {
    final int row, col;
    Position(int row, int col) { this.row = row; this.col = col; }
    boolean isValid() { return row >= 0 && row < 8 && col >= 0 && col < 8; }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Position p)) return false;
        return row == p.row && col == p.col;
    }

    @Override
    public int hashCode() { return Objects.hash(row, col); }

    @Override
    public String toString() { return "(" + row + "," + col + ")"; }
}

class Move {
    final Piece piece;
    final Position from;
    final Position to;
    final Piece captured;

    Move(Piece piece, Position from, Position to, Piece captured) {
        this.piece = piece;
        this.from = from;
        this.to = to;
        this.captured = captured;
    }
}

abstract class Piece {
    Color color;
    Position position;

    Piece(Color color, Position position) {
        this.color = color;
        this.position = position;
    }

    abstract List<Move> getPseudoLegalMoves(Board board);
    abstract String symbol();

    List<Move> slideMoves(Board board, int[][] directions) {
        List<Move> moves = new ArrayList<>();
        for (int[] dir : directions) {
            int r = position.row + dir[0], c = position.col + dir[1];
            while (r >= 0 && r < 8 && c >= 0 && c < 8) {
                Position target = new Position(r, c);
                Piece occupant = board.getPiece(r, c);
                if (occupant == null) {
                    moves.add(new Move(this, position, target, null));
                } else {
                    if (occupant.color != this.color)
                        moves.add(new Move(this, position, target, occupant));
                    break;
                }
                r += dir[0];
                c += dir[1];
            }
        }
        return moves;
    }
}

class King extends Piece {
    King(Color c, Position p) { super(c, p); }
    String symbol() { return color == Color.WHITE ? "K" : "k"; }

    List<Move> getPseudoLegalMoves(Board board) {
        List<Move> moves = new ArrayList<>();
        for (int dr = -1; dr <= 1; dr++) {
            for (int dc = -1; dc <= 1; dc++) {
                if (dr == 0 && dc == 0) continue;
                Position t = new Position(position.row + dr, position.col + dc);
                if (!t.isValid()) continue;
                Piece occ = board.getPiece(t.row, t.col);
                if (occ == null || occ.color != color)
                    moves.add(new Move(this, position, t, occ));
            }
        }
        return moves;
    }
}

class Queen extends Piece {
    Queen(Color c, Position p) { super(c, p); }
    String symbol() { return color == Color.WHITE ? "Q" : "q"; }

    List<Move> getPseudoLegalMoves(Board board) {
        return slideMoves(board, new int[][]{{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}});
    }
}

class Rook extends Piece {
    Rook(Color c, Position p) { super(c, p); }
    String symbol() { return color == Color.WHITE ? "R" : "r"; }

    List<Move> getPseudoLegalMoves(Board board) {
        return slideMoves(board, new int[][]{{-1,0},{1,0},{0,-1},{0,1}});
    }
}

class Bishop extends Piece {
    Bishop(Color c, Position p) { super(c, p); }
    String symbol() { return color == Color.WHITE ? "B" : "b"; }

    List<Move> getPseudoLegalMoves(Board board) {
        return slideMoves(board, new int[][]{{-1,-1},{-1,1},{1,-1},{1,1}});
    }
}

class Knight extends Piece {
    Knight(Color c, Position p) { super(c, p); }
    String symbol() { return color == Color.WHITE ? "N" : "n"; }

    List<Move> getPseudoLegalMoves(Board board) {
        List<Move> moves = new ArrayList<>();
        int[][] offsets = {{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}};
        for (int[] o : offsets) {
            Position t = new Position(position.row + o[0], position.col + o[1]);
            if (!t.isValid()) continue;
            Piece occ = board.getPiece(t.row, t.col);
            if (occ == null || occ.color != color)
                moves.add(new Move(this, position, t, occ));
        }
        return moves;
    }
}

class Pawn extends Piece {
    Pawn(Color c, Position p) { super(c, p); }
    String symbol() { return color == Color.WHITE ? "P" : "p"; }

    List<Move> getPseudoLegalMoves(Board board) {
        List<Move> moves = new ArrayList<>();
        int dir = color == Color.WHITE ? -1 : 1;
        int startRow = color == Color.WHITE ? 6 : 1;

        Position oneAhead = new Position(position.row + dir, position.col);
        if (oneAhead.isValid() && board.getPiece(oneAhead.row, oneAhead.col) == null) {
            moves.add(new Move(this, position, oneAhead, null));
            Position twoAhead = new Position(position.row + 2 * dir, position.col);
            if (position.row == startRow && board.getPiece(twoAhead.row, twoAhead.col) == null)
                moves.add(new Move(this, position, twoAhead, null));
        }

        for (int dc : new int[]{-1, 1}) {
            Position diag = new Position(position.row + dir, position.col + dc);
            if (!diag.isValid()) continue;
            Piece occ = board.getPiece(diag.row, diag.col);
            if (occ != null && occ.color != color)
                moves.add(new Move(this, position, diag, occ));
        }
        return moves;
    }
}

class Board {
    private final Piece[][] grid = new Piece[8][8];
    private final Map<Color, List<Piece>> pieces = new HashMap<>();

    Board() {
        pieces.put(Color.WHITE, new ArrayList<>());
        pieces.put(Color.BLACK, new ArrayList<>());
    }

    void placePiece(Piece piece) {
        grid[piece.position.row][piece.position.col] = piece;
        pieces.get(piece.color).add(piece);
    }

    Piece getPiece(int row, int col) { return grid[row][col]; }

    List<Piece> getPiecesByColor(Color color) {
        return new ArrayList<>(pieces.get(color));
    }

    Position findKing(Color color) {
        for (Piece p : pieces.get(color))
            if (p instanceof King) return p.position;
        throw new RuntimeException("No " + color + " king found");
    }

    void executeMove(Move move) {
        if (move.captured != null)
            pieces.get(move.captured.color).remove(move.captured);
        grid[move.from.row][move.from.col] = null;
        grid[move.to.row][move.to.col] = move.piece;
        move.piece.position = move.to;
    }

    void undoMove(Move move) {
        grid[move.to.row][move.to.col] = move.captured;
        grid[move.from.row][move.from.col] = move.piece;
        move.piece.position = move.from;
        if (move.captured != null)
            pieces.get(move.captured.color).add(move.captured);
    }

    String display() {
        StringBuilder sb = new StringBuilder();
        for (int r = 0; r < 8; r++) {
            sb.append(8 - r).append(" ");
            for (int c = 0; c < 8; c++) {
                Piece p = grid[r][c];
                sb.append(p != null ? p.symbol() : ".").append(" ");
            }
            sb.append("\n");
        }
        sb.append("  a b c d e f g h");
        return sb.toString();
    }
}

class MoveValidator {
    boolean isInCheck(Board board, Color color) {
        Position kingPos = board.findKing(color);
        for (Piece p : board.getPiecesByColor(color.opposite()))
            for (Move m : p.getPseudoLegalMoves(board))
                if (m.to.equals(kingPos)) return true;
        return false;
    }

    boolean isLegal(Board board, Move move) {
        board.executeMove(move);
        boolean inCheck = isInCheck(board, move.piece.color);
        board.undoMove(move);
        return !inCheck;
    }

    List<Move> getLegalMoves(Board board, Color color) {
        List<Move> legal = new ArrayList<>();
        for (Piece p : board.getPiecesByColor(color))
            for (Move m : p.getPseudoLegalMoves(board))
                if (isLegal(board, m)) legal.add(m);
        return legal;
    }

    boolean hasLegalMoves(Board board, Color color) {
        for (Piece p : board.getPiecesByColor(color))
            for (Move m : p.getPseudoLegalMoves(board))
                if (isLegal(board, m)) return true;
        return false;
    }
}

public class Chess {
    private final Board board;
    private final MoveValidator validator = new MoveValidator();
    private Color currentColor = Color.WHITE;
    private GameState state = GameState.IN_PROGRESS;

    public Chess(Board board) { this.board = board; }

    public GameState getState() { return state; }

    public boolean makeMove(Position from, Position to) {
        Piece piece = board.getPiece(from.row, from.col);
        if (piece == null || piece.color != currentColor) {
            System.out.println("No " + currentColor + " piece at " + from);
            return false;
        }

        Move chosen = null;
        for (Move m : piece.getPseudoLegalMoves(board)) {
            if (m.to.equals(to) && validator.isLegal(board, m)) {
                chosen = m;
                break;
            }
        }

        if (chosen == null) {
            System.out.println("Illegal move: " + from + " -> " + to);
            return false;
        }

        board.executeMove(chosen);

        Color opponent = currentColor.opposite();
        boolean inCheck = validator.isInCheck(board, opponent);
        boolean hasMoves = validator.hasLegalMoves(board, opponent);

        if (inCheck && !hasMoves) state = GameState.CHECKMATE;
        else if (inCheck) state = GameState.CHECK;
        else if (!hasMoves) state = GameState.STALEMATE;
        else state = GameState.IN_PROGRESS;

        currentColor = opponent;
        return true;
    }

    public void display() {
        System.out.println(board.display());
        System.out.println("Turn: " + currentColor + " | State: " + state + "\n");
    }

    static Board setupStandardBoard() {
        Board board = new Board();
        // Black pieces
        board.placePiece(new Rook(Color.BLACK, new Position(0, 0)));
        board.placePiece(new Knight(Color.BLACK, new Position(0, 1)));
        board.placePiece(new Bishop(Color.BLACK, new Position(0, 2)));
        board.placePiece(new Queen(Color.BLACK, new Position(0, 3)));
        board.placePiece(new King(Color.BLACK, new Position(0, 4)));
        board.placePiece(new Bishop(Color.BLACK, new Position(0, 5)));
        board.placePiece(new Knight(Color.BLACK, new Position(0, 6)));
        board.placePiece(new Rook(Color.BLACK, new Position(0, 7)));
        for (int c = 0; c < 8; c++)
            board.placePiece(new Pawn(Color.BLACK, new Position(1, c)));

        // White pieces
        board.placePiece(new Rook(Color.WHITE, new Position(7, 0)));
        board.placePiece(new Knight(Color.WHITE, new Position(7, 1)));
        board.placePiece(new Bishop(Color.WHITE, new Position(7, 2)));
        board.placePiece(new Queen(Color.WHITE, new Position(7, 3)));
        board.placePiece(new King(Color.WHITE, new Position(7, 4)));
        board.placePiece(new Bishop(Color.WHITE, new Position(7, 5)));
        board.placePiece(new Knight(Color.WHITE, new Position(7, 6)));
        board.placePiece(new Rook(Color.WHITE, new Position(7, 7)));
        for (int c = 0; c < 8; c++)
            board.placePiece(new Pawn(Color.WHITE, new Position(6, c)));

        return board;
    }

    public static void main(String[] args) {
        Board board = setupStandardBoard();
        Chess game = new Chess(board);

        System.out.println("=== Chess Game Demo ===\n");
        game.display();

        // Scholar's mate
        int[][] moves = {
            {6, 4, 4, 4},  // White e2->e4
            {1, 4, 3, 4},  // Black e7->e5
            {7, 5, 4, 2},  // White Bf1->c4
            {0, 1, 2, 2},  // Black Nb8->c6
            {7, 3, 3, 7},  // White Qd1->h5
            {0, 6, 2, 5},  // Black Ng8->f6
            {3, 7, 1, 5},  // White Qh5xf7 checkmate
        };

        for (int i = 0; i < moves.length; i++) {
            String color = i % 2 == 0 ? "White" : "Black";
            Position from = new Position(moves[i][0], moves[i][1]);
            Position to = new Position(moves[i][2], moves[i][3]);
            Piece piece = board.getPiece(from.row, from.col);
            String pieceName = piece != null ? piece.getClass().getSimpleName() : "?";
            System.out.println("Move " + (i + 1) + ": " + color + " " + pieceName + " " + from + " -> " + to);

            boolean success = game.makeMove(from, to);
            if (!success) { System.out.println("Move failed!"); break; }
            game.display();

            if (game.getState() == GameState.CHECKMATE || game.getState() == GameState.STALEMATE) {
                System.out.println("Game over: " + game.getState());
                break;
            }
        }
    }
}

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)

Names the patterns and writes most piece move generation, but check validation and undo are vague or implemented by board cloning.

Signals

Names Strategy and Command correctly when asked which patterns apply.
Writes a Piece abstract class with get_pseudo_legal_moves and at least one concrete piece (King or Knight).
Generates pawn forward and diagonal capture moves separately, recognizing the asymmetry.
Implements is_in_check by iterating enemy pieces' moves looking for the king's square.
Detects checkmate as 'in check plus no legal moves' when prompted.

Common gaps at this level

Implements check validation by deep-cloning the board for every candidate move instead of execute/undo.
Puts a switch statement on piece type inside Board.get_legal_moves rather than delegating to the piece.
Creates WhiteKing and BlackKing subclasses, doubling the piece count for no behavioral difference.
Forgets that captures and empty-target moves both must be added for Knight and King.
Misses stalemate detection, treating no-legal-moves as a loss regardless of whether the king is attacked.

Mid-Level Engineer (L4)

Drives the design end-to-end with piece-owned move generation, an execute/undo pair on Board, and a clean two-phase pseudo-legal vs legal split.

Signals

Writes the Piece base with the _slide_moves template before coding Rook, Bishop, and Queen as one-line subclasses.
Implements execute_move and undo_move as exact inverses, both mutating the grid and the captured-piece list.
Splits move generation (Piece) from move validation (MoveValidator) explicitly, naming the two-phase rationale.
Tracks pieces by color in a dict for fast enemy-iteration during is_in_check.
Computes CHECK, CHECKMATE, STALEMATE, and IN_PROGRESS from the two booleans (in_check, has_legal_moves) on the opponent.
Handles Pawn forward-two only from the starting row, and diagonal capture only when an enemy occupies the target.

Common gaps at this level

Does not volunteer castling or en passant as natural extensions unless prompted.
Misses the has_moved flag on King and Rook as the precondition for castling.
Treats AI as 'walk the move tree' without naming alpha-beta pruning or piece-square evaluation.

Senior Engineer (L5+)

Volunteers castling, en passant, AI, and draw rules before being asked, and frames each pattern around the specific failure it prevents.

Signals

Volunteers castling with the has_moved flag, intermediate-square emptiness check, and king-doesn't-pass-through-check verification without prompting.
Volunteers en passant with the last-move tracking and the board-level en_passant_target reset every turn.
Names execute/undo symmetry as the invariant that prevents corrupted board state during check validation, and stresses that the captured-piece list must be restored exactly.
Frames _slide_moves as the template method that compresses Rook, Bishop, and Queen into three direction-set one-liners instead of three full implementations.
Proposes minimax with alpha-beta pruning for AI, naming material plus piece-square tables for the heuristic, and points out that execute/undo is exactly the plumbing the search needs.
Suggests draw-by-repetition via a hash of (piece positions + side to move) tracked across moves, and the 50-move rule via a counter that resets on captures and pawn moves.
Closes with a one-sentence summary that names Strategy for piece moves, Command for execute/undo, Template Method for sliders, and the pseudo-legal vs legal split in under 20 seconds.

Common Mistakes

✗Putting move generation logic in the Board class instead of each piece. You end up with one massive switch statement.
✗Not implementing undo on moves. Without it, check detection requires cloning the entire board for every candidate move.
✗Using inheritance for color (WhiteKing, BlackKing). Color is data, not behavior. Use composition.
✗Forgetting that a move is only legal if it doesn't leave your own king in check, including discovered checks.

Key Points

✓Each piece generates its own pseudo-legal moves. MoveValidator filters out ones that leave the king exposed.
✓Command pattern on Move allows execute/undo. You need undo to test whether a candidate move leaves you in check.
✓Board tracks all pieces by color for fast iteration when checking if any enemy piece attacks the king's square.
✓GameState is computed after every move: if the opponent has no legal moves, it's either checkmate or stalemate.

Key Abstractions

Class Diagram

Every Piece Knows How It Moves

Requirements

Functional

Non-Functional

Design Decisions

Why does each piece own its move generation?

Why Command pattern for moves instead of board cloning?

Why not use inheritance for piece color (WhiteKing, BlackKing)?

Why separate MoveValidator from Board?

Interview Follow-ups

45-Minute LLD Playbook

Clarify scope and lock the process

Sketch the API and (optionally) the class diagram

Code in this sequence (bottom-up)

Trade-offs, extensions, and wrap-up

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

Every Piece Knows How It Moves

Requirements

Functional

Non-Functional

Design Decisions

Why does each piece own its move generation?

Why Command pattern for moves instead of board cloning?

Why not use inheritance for piece color (WhiteKing, BlackKing)?

Why separate MoveValidator from Board?

Interview Follow-ups

45-Minute LLD Playbook

Clarify scope and lock the process

Sketch the API and (optionally) the class diagram

Code in this sequence (bottom-up)

Trade-offs, extensions, and wrap-up

Code Implementation

Interview Grading by Level

Junior Engineer (L3)

Mid-Level Engineer (L4)

Senior Engineer (L5+)

Common Mistakes

Key Points

Related Designs