Design Tic Tac Toe

01What this prompt is really asking

02Clarifying questions → locked requirements

• You: Players pick a cell (row, col) and place their mark? They: Yes — only empty cells.
• You: Win only, or draws too? They: Three in a row wins; full board = draw.
• You: Occupied cell / wrong turn / move after game over? They: Reject; don’t corrupt state.
• You: UI or backend only? One game? They: Backend logic only; one game is fine.

03Entities: Game, Board, Player

• Game — Board + two Players, current_player, state (IN_PROGRESS / WON / DRAW), optional winner. Entry: make_move(player, row, col).
• Board — 3×3 of marks / empty. place, check_win, is_full, is_empty. No idea whose turn it is.
• Player — name + mark (X / O). Pure data.
• Mark — enum, not a class hierarchy. Two values; don’t invent MarkStrategy.

04Class design from the requirements

from enum import Enum, auto
from typing import Optional

class Mark(Enum):
    X = auto()
    O = auto()

class GameState(Enum):
    IN_PROGRESS = auto()
    WON = auto()
    DRAW = auto()

class Player:
    def __init__(self, name: str, mark: Mark):
        self.name, self.mark = name, mark

class Board:
    SIZE = 3
    # flat index 0..8 or grid[r][c] — pick one and stay consistent
    WIN_LINES = (
        (0, 1, 2), (3, 4, 5), (6, 7, 8),  # rows
        (0, 3, 6), (1, 4, 7), (2, 5, 8),  # cols
        (0, 4, 8), (2, 4, 6),             # diags
    )

    def __init__(self):
        self.cells: list[Optional[Mark]] = [None] * (self.SIZE * self.SIZE)

    # place / check_win / is_full — see implementation

class Game:
    def __init__(self, p1: Player, p2: Player):
        self.board = Board()
        self.p1, self.p2 = p1, p2
        self.current = p1  # X starts
        self.state = GameState.IN_PROGRESS
        self.winner: Optional[Player] = None

    def make_move(self, player: Player, row: int, col: int) -> bool: ...
    def get_current_player(self) -> Player: ...
    def get_game_state(self) -> GameState: ...
    def get_winner(self) -> Optional[Player]: ...

import java.util.*;

enum Mark { X, O }

enum GameState { IN_PROGRESS, WON, DRAW }

class Player {
    String name;
    Mark mark;
    Player(String name, Mark mark) { this.name = name; this.mark = mark; }
}

class Board {
    static final int SIZE = 3;
    // flat index 0..8 or grid[r][c] — pick one and stay consistent
    static final int[][] WIN_LINES = {
        {0, 1, 2}, {3, 4, 5}, {6, 7, 8},  // rows
        {0, 3, 6}, {1, 4, 7}, {2, 5, 8},  // cols
        {0, 4, 8}, {2, 4, 6},             // diags
    };

    Mark[] cells = new Mark[SIZE * SIZE]; // null = empty

    // place / checkWin / isFull — see implementation
}

class Game {
    Board board = new Board();
    Player p1, p2, current;
    GameState state = GameState.IN_PROGRESS;
    Player winner; // nullable

    Game(Player p1, Player p2) {
        this.p1 = p1; this.p2 = p2;
        this.current = p1; // X starts
    }

    boolean makeMove(Player player, int row, int col) { /* ... */ return false; }
    Player getCurrentPlayer() { return current; }
    GameState getGameState() { return state; }
    Player getWinner() { return winner; }
}

05Implementation highlights

def make_move(self, player: Player, row: int, col: int) -> bool:
    if self.state is not GameState.IN_PROGRESS:
        return False
    if player is not self.current:
        return False
    if not self.board.place(row, col, player.mark):
        return False

    if self.board.check_win(player.mark):
        self.state = GameState.WON
        self.winner = player
    elif self.board.is_full():
        self.state = GameState.DRAW
    else:
        self.current = self.p2 if player is self.p1 else self.p1
    return True


def place(self, row: int, col: int, mark: Mark) -> bool:
    if not (0 <= row < self.SIZE and 0 <= col < self.SIZE):
        return False
    i = row * self.SIZE + col
    if self.cells[i] is not None:
        return False
    self.cells[i] = mark
    return True


def check_win(self, mark: Mark) -> bool:
    for a, b, c in self.WIN_LINES:
        if self.cells[a] is mark and self.cells[b] is mark and self.cells[c] is mark:
            return True
    return False


def is_full(self) -> bool:
    return all(c is not None for c in self.cells)

boolean makeMove(Player player, int row, int col) {
    if (state != GameState.IN_PROGRESS) return false;
    if (player != current) return false;
    if (!board.place(row, col, player.mark)) return false;

    if (board.checkWin(player.mark)) {
        state = GameState.WON;
        winner = player;
    } else if (board.isFull()) {
        state = GameState.DRAW;
    } else {
        current = (player == p1) ? p2 : p1;
    }
    return true;
}

boolean place(int row, int col, Mark mark) {
    if (!(0 <= row && row < SIZE && 0 <= col && col < SIZE)) return false;
    int i = row * SIZE + col;
    if (cells[i] != null) return false;
    cells[i] = mark;
    return true;
}

boolean checkWin(Mark mark) {
    for (int[] line : WIN_LINES) {
        if (cells[line[0]] == mark && cells[line[1]] == mark && cells[line[2]] == mark) {
            return true;
        }
    }
    return false;
}

boolean isFull() {
    for (Mark c : cells) if (c == null) return false;
    return true;
}

06Verification trace

1. Empty board; current = P1 (X).
2. P1 → (0,0); P2 → (0,1); P1 → (1,1); P2 → (0,2).
3. P1 → (2,2) completes (0,0)/(1,1)/(2,2) → state=WON, winner=P1.
4. P2 tries (1,0) → rejected because state ≠ IN_PROGRESS.
5. Also narrate: occupied (0,0) rejected earlier; wrong-turn attempt rejected.

• Happy: X places (0,0),(1,1),(2,2) with O elsewhere → diagonal win.
• Failure: Move on occupied cell rejected; move after WIN rejected.
• Concurrency: Two clients click — Game lock around make_move preserves alternating turns.

07Extensibility follow-ups

• N×N / K-in-a-row — Board(n, k). For N=3,K=3 keep the line table; for larger N, scan from the last move along H/V/diag like Connect Four instead of enumerating every line.
• Undo / history — choke point is Game.make_move. Push (player, row, col); undo clears the cell, restores turn, recomputes state (or store prior state on the stack).
• Bot opponent — keep Player as data; BotEngine.choose_move(game) -> (row, col) (random empty cell, or minimax — the state space is tiny). Game loop passes the choice into make_move.
• Best-of-N match — Match object owns score + creates a fresh Game per round; don’t stuff rematch into Board.

08Common interview pitfalls

• Checking win but not draw — full board labeled wrongly.
• Allowing overwrite of occupied cells.
• Not validating turn order (X moves twice).
• Hardcoding only rows — forgetting columns/diagonals (or vice versa).
• Giant if-else for eight lines without a lines list — brittle extensions.
• Restart that doesn’t clear board + status + turn.

09Interview script (say this)

1. 3×3, X and O, alternate, eight win lines, draw if full with no winner.
2. Game owns Board and current player; make_move(r,c).
3. Reject occupied / out of bounds / game over.
4. After move: check win lines through cell; else draw; else swap.
5. Trace: X wins on diagonal; draw sequence; illegal second move on cell.

10Extra verification traces

WIN_LINES = [(0,1,2),(3,4,5),(6,7,8),(0,3,6),(1,4,7),(2,5,8),(0,4,8),(2,4,6)]

def make_move(self, idx):
    if self.status != "PLAY" or self.board[idx] is not None:
        raise RuntimeError("illegal")
    self.board[idx] = self.turn
    if any(all(self.board[i]==self.turn for i in line) for line in WIN_LINES):
        self.status = "WIN"; return
    if all(c is not None for c in self.board):
        self.status = "DRAW"; return
    self.turn = "O" if self.turn == "X" else "X"

static final int[][] WIN_LINES = {
    {0,1,2},{3,4,5},{6,7,8},{0,3,6},{1,4,7},{2,5,8},{0,4,8},{2,4,6}
};

void makeMove(int idx) {
    if (!"PLAY".equals(status) || board[idx] != null) {
        throw new RuntimeException("illegal");
    }
    board[idx] = turn;
    for (int[] line : WIN_LINES) {
        if (board[line[0]] == turn && board[line[1]] == turn && board[line[2]] == turn) {
            status = "WIN";
            return;
        }
    }
    boolean full = true;
    for (Object c : board) if (c == null) { full = false; break; }
    if (full) { status = "DRAW"; return; }
    turn = "X".equals(turn) ? "O" : "X";
}

11Staff-level follow-ups

• NxN / K-in-a-row? — Generalize board size + win scanner.
• Undo? — Stack of moves; pop restores cell and turn.
• Online ratings? — MatchResult emitter; Game stays pure rules.
• Misère variant? — OutcomePolicy plug-in.

12Complete solution notes (Tic Tac Toe)

from threading import Lock

class GameService:
    def __init__(self):
        self.games: dict[str, object] = {}
        self._locks: dict[str, Lock] = {}
        self._map_lock = Lock()

    def _lock_for(self, game_id: str) -> Lock:
        with self._map_lock:
            return self._locks.setdefault(game_id, Lock())

    def make_move(self, game_id: str, *args):
        with self._lock_for(game_id):
            return self.games[game_id].make_move(*args)

# Different game ids → different locks → parallel matches.

import java.util.*;
import java.util.concurrent.locks.ReentrantLock;

class GameService {
    Map<String, Object> games = new HashMap<>();
    Map<String, ReentrantLock> locks = new HashMap<>();
    private final ReentrantLock mapLock = new ReentrantLock();

    ReentrantLock lockFor(String gameId) {
        mapLock.lock();
        try {
            return locks.computeIfAbsent(gameId, k -> new ReentrantLock());
        } finally {
            mapLock.unlock();
        }
    }

    Object makeMove(String gameId, Object... args) {
        ReentrantLock lock = lockFor(gameId);
        lock.lock();
        try {
            // return games.get(gameId).makeMove(...);
            return null;
        } finally {
            lock.unlock();
        }
    }
}

// Different game ids → different locks → parallel matches.

13Concurrency cases

• Two HTTP moves on one game — without per-game lock, turn checks race.
• Spectators reading board — copy board under lock or accept briefly stale reads.
• Matchmaking — separate lock from game rules lock.