0

Design tic-tac-toe

by Frontier Interview· 1 day ago· ⑂ 0 remixes

Question: Design tic-tac-toe

Companies: Amazon

Difficulty: Easy

Problem statement

Model an N-by-N tic-tac-toe game for two players: moves, turn order, and detecting a win or draw efficiently after each move.

Requirements

  • An N-by-N board, N >= 3, chosen when the game is created. N = 3 is the classic game.
  • Two players, X and O. X moves first, and turns alternate strictly.
  • A move places the current player's mark on an empty cell. The game rejects a move that is off the board, on an occupied cell, out of turn, or made after the game has ended.
  • A player wins with N marks in a row: a full row, a full column, or one of the two full diagonals.
  • The game is a draw when every cell is filled and nobody has won.
  • After each move the game reports its state: in progress, X won, O won, or draw.
  • Win detection must be O(1) per move, not a rescan of the board.
  • Out of scope: AI opponents, networking, persistence, a UI, and "K in a row" on a board larger than K (covered under Extensions).

Core objects

  • Mark (enum): X or O. Its value, +1 or -1, is the sign the line counters add.
  • GameState (enum): IN_PROGRESS, X_WON, O_WON, DRAW.
  • Player: a name and the mark it plays.
  • Move (value object): who played which cell. It is stored in the move history.
  • Board: the N x N grid. It places marks, validates cells, and owns the line counters that detect a win.
  • Game: the controller. It holds the board, both players, whose turn it is, the state and the history. It enforces the rules.
  • InvalidMoveError: raised for any illegal move, with a reason.

Class design

{"type":"excalidraw","elements":[
 {"type":"rectangle","id":"game","x":0,"y":150,"width":260,"height":150,"label":{"text":"Game\nboard, players, current\nstate, history\nplay(player, row, col)\ncurrent_player()"}},
 {"type":"rectangle","id":"board","x":500,"y":0,"width":260,"height":170,"label":{"text":"Board\nn, grid, filled\nrows, cols\ndiag, anti_diag\nplace(row, col, mark)\nis_full()"}},
 {"type":"rectangle","id":"player","x":500,"y":230,"width":180,"height":70,"label":{"text":"Player\nname, mark"}},
 {"type":"rectangle","id":"move","x":500,"y":360,"width":200,"height":70,"label":{"text":"Move\nplayer, row, col"}},
 {"type":"rectangle","id":"mark","x":1000,"y":110,"width":180,"height":70,"label":{"text":"Mark (enum)\nX, O"}},
 {"type":"arrow","id":"game-board","x":260,"y":175,"width":240,"height":-90,"start":{"id":"game"},"end":{"id":"board"},"label":{"text":"owns"}},
 {"type":"arrow","id":"game-player","x":260,"y":235,"width":240,"height":30,"start":{"id":"game"},"end":{"id":"player"},"label":{"text":"has"}},
 {"type":"arrow","id":"game-move","x":260,"y":275,"width":240,"height":120,"start":{"id":"game"},"end":{"id":"move"},"label":{"text":"owns"}},
 {"type":"arrow","id":"board-mark","x":760,"y":80,"width":240,"height":55,"start":{"id":"board"},"end":{"id":"mark"},"label":{"text":"uses"}},
 {"type":"arrow","id":"player-mark","x":680,"y":265,"width":320,"height":-105,"start":{"id":"player"},"end":{"id":"mark"},"label":{"text":"uses"}}
]}

Game composes the Board and the move history. Players exist on their own and are only referenced. Board knows nothing about turns or players. It only answers "did this placement complete a line?". That keeps the rules in one place and the geometry in another.

Key flows

1. Start a game: Game checks that the two players hold X and O, creates a Board(n) with all counters (rows[n], cols[n], diag, anti_diag) at zero, and gives the first turn to X.

2. Play a move (Game.play(player, row, col))

  1. Game takes its lock, then checks that the state is IN_PROGRESS and that player is the current player.
  2. Game calls board.place(row, col, mark).
  3. Board checks the bounds and that the cell is empty, writes the mark, and increments filled.
  4. Board adds the mark's sign (+1 for X, -1 for O) to rows[row] and cols[col]. If row == col it adds the sign to diag. If row + col == n - 1 it adds it to anti_diag.
  5. If any counter it touched now has absolute value N, that line holds only this mark, so place returns True (a win).
  6. Game appends a Move, then sets the state: a win sets X_WON or O_WON, a full board sets DRAW, otherwise the turn passes to the other player.

Why the counters work: a line of N cells reaches +N only if all N cells are X, and -N only if all are O. A mixed line can never reach ±N. Each move touches at most four counters, so the check is O(1) time with O(N) extra memory.

3. Game states

{"type":"excalidraw","elements":[
 {"type":"ellipse","id":"init","x":0,"y":160,"width":100,"height":50,"label":{"text":"start"}},
 {"type":"rectangle","id":"ip","x":200,"y":150,"width":200,"height":70,"label":{"text":"IN_PROGRESS"}},
 {"type":"rectangle","id":"xw","x":640,"y":0,"width":180,"height":70,"label":{"text":"X_WON"}},
 {"type":"rectangle","id":"ow","x":640,"y":150,"width":180,"height":70,"label":{"text":"O_WON"}},
 {"type":"rectangle","id":"draw","x":640,"y":300,"width":180,"height":70,"label":{"text":"DRAW"}},
 {"type":"ellipse","id":"end","x":1020,"y":160,"width":100,"height":50,"label":{"text":"end"}},
 {"type":"arrow","id":"init-ip","x":100,"y":185,"width":100,"height":0,"start":{"id":"init"},"end":{"id":"ip"}},
 {"type":"arrow","id":"ip-ip","x":250,"y":220,"width":100,"height":0,"points":[[0,0],[0,80],[100,80],[100,0]],"start":{"id":"ip"},"end":{"id":"ip"},"label":{"text":"legal move, no line,\ncells left"}},
 {"type":"arrow","id":"ip-xw","x":400,"y":165,"width":240,"height":-130,"start":{"id":"ip"},"end":{"id":"xw"},"label":{"text":"X completes a line"}},
 {"type":"arrow","id":"ip-ow","x":400,"y":185,"width":240,"height":0,"start":{"id":"ip"},"end":{"id":"ow"},"label":{"text":"O completes a line"}},
 {"type":"arrow","id":"ip-draw","x":400,"y":205,"width":240,"height":130,"start":{"id":"ip"},"end":{"id":"draw"},"label":{"text":"last cell filled,\nno line"}},
 {"type":"arrow","id":"xw-end","x":820,"y":35,"width":200,"height":135,"start":{"id":"xw"},"end":{"id":"end"}},
 {"type":"arrow","id":"ow-end","x":820,"y":185,"width":200,"height":0,"start":{"id":"ow"},"end":{"id":"end"}},
 {"type":"arrow","id":"draw-end","x":820,"y":335,"width":200,"height":-135,"start":{"id":"draw"},"end":{"id":"end"}}
]}

Check the win before the draw: the move that fills the last cell can also complete a line, and that is a win.

Code

from __future__ import annotations

import threading
from dataclasses import dataclass, field
from enum import Enum
from typing import List, Optional


class Mark(Enum):
    X = 1
    O = -1  # the value is the sign the line counters add


class GameState(Enum):
    IN_PROGRESS = "in_progress"
    X_WON = "x_won"
    O_WON = "o_won"
    DRAW = "draw"


class InvalidMoveError(Exception):
    pass


@dataclass(frozen=True)
class Player:
    name: str
    mark: Mark


@dataclass(frozen=True)
class Move:
    player: Player
    row: int
    col: int


class Board:
    def __init__(self, n: int) -> None:
        if n < 3:
            raise ValueError("board size must be at least 3")
        self.n = n
        self.grid: List[List[Optional[Mark]]] = [[None] * n for _ in range(n)]
        self.rows = [0] * n
        self.cols = [0] * n
        self.diag = 0
        self.anti_diag = 0
        self.filled = 0

    def is_full(self) -> bool:
        return self.filled == self.n * self.n

    def place(self, row: int, col: int, mark: Mark) -> bool:
        """Place a mark. Return True if it completes a line."""
        if not (0 <= row < self.n and 0 <= col < self.n):
            raise InvalidMoveError(f"({row}, {col}) is off the board")
        if self.grid[row][col] is not None:
            raise InvalidMoveError(f"({row}, {col}) is already taken")
        self.grid[row][col] = mark
        self.filled += 1
        s, n = mark.value, self.n
        self.rows[row] += s
        self.cols[col] += s
        touched = [self.rows[row], self.cols[col]]
        if row == col:
            self.diag += s
            touched.append(self.diag)
        if row + col == n - 1:
            self.anti_diag += s
            touched.append(self.anti_diag)
        return any(abs(t) == n for t in touched)


@dataclass
class Game:
    player_x: Player
    player_o: Player
    n: int = 3
    board: Board = field(init=False)
    state: GameState = field(init=False, default=GameState.IN_PROGRESS)
    history: List[Move] = field(init=False, default_factory=list)
    _turn: Player = field(init=False)
    _lock: threading.Lock = field(init=False, default_factory=threading.Lock)

    def __post_init__(self) -> None:
        if self.player_x.mark is not Mark.X or self.player_o.mark is not Mark.O:
            raise ValueError("player_x must play X and player_o must play O")
        self.board = Board(self.n)
        self._turn = self.player_x

    def current_player(self) -> Player:
        return self._turn

    def play(self, player: Player, row: int, col: int) -> GameState:
        with self._lock:
            if self.state is not GameState.IN_PROGRESS:
                raise InvalidMoveError("the game is over")
            if player != self._turn:
                raise InvalidMoveError(f"it is {self._turn.name}'s turn")
            won = self.board.place(row, col, player.mark)
            self.history.append(Move(player, row, col))
            if won:
                self.state = GameState.X_WON if player.mark is Mark.X else GameState.O_WON
            elif self.board.is_full():
                self.state = GameState.DRAW
            else:
                self._turn = self.player_o if self._turn is self.player_x else self.player_x
            return self.state


if __name__ == "__main__":
    alice, bob = Player("Alice", Mark.X), Player("Bob", Mark.O)
    game = Game(alice, bob, n=3)
    for who, r, c in [(alice, 0, 0), (bob, 1, 1), (alice, 0, 1), (bob, 2, 2), (alice, 0, 2)]:
        print(who.name, (r, c), game.play(who, r, c).value)
    try:
        game.play(bob, 2, 0)
    except InvalidMoveError as e:
        print("rejected:", e)  # rejected: the game is over

Edge cases the code handles: off-board and occupied cells (the board is unchanged on rejection), moving out of turn, moving after the game ends, a last move that both fills the board and wins (reported as a win), the center cell of an odd board (it updates both diagonals), and two players with the same mark (rejected at construction). The lock makes play safe when two requests arrive at once, for example from two clients of a game server.

Design patterns

  • Separation of concerns (controller + model): Game owns the rules (turns, states). Board owns the geometry and the win detection. Each can be tested on its own, and a UI or network layer only talks to Game.
  • Value objects: Player and Move are frozen dataclasses. A history of immutable moves is safe to share, and it is the basis for replay and undo.
  • Enums instead of strings or booleans: Mark and GameState make illegal values impossible. The +1/-1 sign used by the counters is the Mark value, so the encoding lives on the type that owns it.
  • No State or Strategy pattern is used in the base design. Four states with one transition function do not need state classes. A Strategy becomes useful only with the extensions below.

Extensions

  • K in a row on an N x N board (Gomoku-style): whole-line counters no longer work. Put the win check behind a WinRule interface (Strategy). The K-in-a-row rule, after each move, walks the four directions from the new cell and counts consecutive equal marks. That is O(K) per move. Board stays the same apart from delegating the check.
  • Undo / replay: the counters are reversible. Pop the last Move, clear its cell, subtract its sign from the same counters, decrement filled, give the turn back, and set the state to IN_PROGRESS. Replay is a fold of play over the history.
  • Computer opponent: add a PlayerStrategy interface with choose_move(board) -> (row, col). A human strategy reads input. A bot strategy can be random, rule-based (win, block, center, corner), or minimax with alpha-beta for N = 3. Game does not change.
  • Early draw detection: track whether each line is "dead", which means it already holds both marks. Keep per-line counts of X and O, not one signed sum. When every line is dead, declare a draw before the board fills.
  • Many concurrent games on a server: a GameManager maps game ids to Games. Each game has its own lock, so games never block each other. Persist the move history (not the grid) and rebuild the counters on load.

Interviewer expectations

Mid-level (L4)

  • Clean Board / Game / Player split, with enums for marks and state.
  • Correct turn order and validation of bounds, occupied cells, and moves after the end.
  • A correct win check, even if it first scans the row, column and diagonals of the last move (O(N)).

Senior (L5)

  • Reaches the O(1) counter approach without hints, and explains why a mixed line can never reach ±N.
  • Gets the diagonal conditions right, including the center cell, and checks the win before the draw.
  • Keeps the rules in Game and the geometry in Board, and can add undo by reversing the counters.

Staff (L6+)

  • Says early that the counter trick depends on "N in a row", and plans a pluggable win rule for K < N.
  • Discusses concurrency and persistence for a game server: a lock per game, an event-sourced move history, and idempotent move requests.
  • Weighs trade-offs openly, for example O(N) counter memory against O(K) local scans, and which extensions are worth building now.

Sign in to comment, vote or remix.