Tic-Tac-Toe
easy · game state, turn validation
Brief-reported interview attribution (unverified): Microsoft, Amazon
How to approach an LLD roundRequirements
- 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
Each test has a five-second execution limit. Your practice drafts and solved progress stay in this browser.
Return to the Python interpreter