Tic-Tac-Toe

easy · game state, turn validation

Brief-reported interview attribution (unverified): Microsoft, Amazon

How to approach an LLD round

Requirements

  • Functional: alternate X and O, reject out-of-turn, out-of-bounds and occupied moves, detect a win or a draw, and freeze the game once it is over.
  • Non-functional: the rules must be testable without the game loop (the board is independent of the turn order); the game is a single instance.
  • Out of scope: AI opponent, network play, undo.

Statement

Implement a 3×3 Tic-Tac-Toe game. X moves first. move returns "ok" for a legal move, "invalid" for an illegal one, "X wins" / "O wins" when a move completes a row, column, or diagonal, and "draw" when the board is full with no winner.

class TicTacToe:
    def __init__(self):
    def move(self, player, row, col):
        # player: "X" or "O"; row, col: 0-2
        # -> "ok" | "invalid" | "X wins" | "O wins" | "draw"
    def board(self):
        # -> 3x3 list of lists, "" for an empty cell
    def current_player(self):
        # -> "X" or "O"
    def status(self):
        # -> "in progress" | "X wins" | "O wins" | "draw"

Rules. An illegal move (wrong player's turn, out of bounds, occupied cell, or any move after the game is over) returns "invalid" and does not change the turn or the board. A win is checked after every legal move; a draw is checked only when the board is full and nobody has won.

Tests use explicit inputs and injected clocks/callbacks. No network, real threads or application-server execution is involved.

Class design (SOLID)

Board (the 3×3 grid and the win check; SRP). TicTacToe (turn order and game status; SRP) — it delegates the grid to Board. No pattern is forced here; splitting the rules from the state is the point.

Public demo

# Public demo: run after implementing the class API above.
g = TicTacToe()
print(g.move('O', 0, 0))
print(g.move('X', 3, 0))

Reference solution and hidden tests

Locked. Open the interactive editor and attempt the problem; the reference, hidden test descriptions, pattern explanation and complexity are available only after an explicit reveal.

Concurrency

One game, one player at a time — there is no shared mutable state beyond the game object itself. In a server version, hold one game per room and guard move with a lock per game so two players cannot move simultaneously.

Trade-offs & extensions

The win check scans all lines (constant, 3×3). Extending: generalise Board to N×N with a K-in-a-row rule; for the special K=N full-row/column/diagonal rule, counters support O(1) win checks per move, and add a Player interface so a human or an AI can take a turn.

Starter code

class Board:

    def __init__(self):
        """Initialize the state described in the problem."""
        pass

    def get(self, row, col):
        """Implement the return value and rules in the API contract."""
        pass

    def place(self, player, row, col):
        """Implement the return value and rules in the API contract."""
        pass

    def is_full(self):
        """Implement the return value and rules in the API contract."""
        pass

    def winner(self, player):
        """Implement the return value and rules in the API contract."""
        pass

    def copy_grid(self):
        """Implement the return value and rules in the API contract."""
        pass

class TicTacToe:

    def __init__(self):
        """Initialize the state described in the problem."""
        pass

    def current_player(self):
        '''-> "X" or "O"'''
        pass

    def status(self):
        '''-> "in progress" | "X wins" | "O wins" | "draw"'''
        pass

    def board(self):
        """-> 3x3 list of lists, "" for an empty cell"""
        pass

    def move(self, player, row, col):
        '''player: "X" or "O"; row, col: 0-2 -> "ok" | "invalid" | "X wins" | "O wins" | "draw"'''
        pass
Loading editor…

Each test has a five-second execution limit. Your practice drafts and solved progress stay in this browser.

Return to the Python interpreter

3 comments

Seed comments are jokes from TryGetValue’s fictional characters, not real user posts.

Your posts stay in this browser, for this problem only. They are not shared with other visitors.

  1. TryGetValueCharacter joke · No posting date

    I solved this in O(1). Then I remembered I actually have to write the code. O(n) regrets.

  2. The GraderCharacter joke · No posting date

    Your solution is correct. Your variable names are a crime scene.

  3. TryGetValueCharacter joke · No posting date

    I found the bug. It was me. I was the bug.