Low-Level Design: Tic-Tac-Toe Game
Tic-Tac-Toe is a common LLD warm-up question that tests your ability to model game state, validate moves, detect win conditions efficiently, and extend to larger board sizes. A good answer covers O(1) win detection using incremental tracking rather than O(n^2) scanning.
Requirements
- N×N board (default 3×3, but generalize)
- Two players: X and O, alternating turns
- Detect win: any row, column, or diagonal filled by one player
- Detect draw: board full with no winner
- Support undo last move
- Support arbitrary N for N-in-a-row to win (e.g., 5×5 with 3-in-a-row)
O(1) Win Detection Strategy
Naive approach: scan all rows, columns, diagonals on each move — O(n) per move. Better: maintain count arrays and update incrementally — O(1) per move.
from enum import Enum
from dataclasses import dataclass, field
from typing import Optional
class Player(Enum):
X = 1
O = -1
class GameStatus(Enum):
IN_PROGRESS = "in_progress"
X_WINS = "x_wins"
O_WINS = "o_wins"
DRAW = "draw"
@dataclass
class Move:
player: Player
row: int
col: int
class TicTacToe:
"""
O(1) win detection using count arrays.
Each cell placement increments the player's count for that row, col, and diagonals.
Win when any count reaches N (or -N for player O).
"""
def __init__(self, n: int = 3, win_length: int = None):
self.n = n
self.win_length = win_length or n # For larger boards: n-in-a-row
self.board = [[None] * n for _ in range(n)]
self.status = GameStatus.IN_PROGRESS
self.current_player = Player.X
self.move_count = 0
self.move_history: list[Move] = []
# Count arrays: X contributes +1, O contributes -1
self.rows = [0] * n
self.cols = [0] * n
self.diag1 = 0 # Top-left to bottom-right diagonal
self.diag2 = 0 # Top-right to bottom-left diagonal
def make_move(self, row: int, col: int) -> GameStatus:
if self.status != GameStatus.IN_PROGRESS:
raise ValueError("Game is already over")
if not (0 <= row < self.n and 0 <= col bool:
if not self.move_history:
return False
if self.status != GameStatus.IN_PROGRESS and self.status != GameStatus.DRAW:
# Also allow undo from completed games
pass
last = self.move_history.pop()
val = last.player.value
# Reverse the move
self.board[last.row][last.col] = None
self.rows[last.row] -= val
self.cols[last.col] -= val
if last.row == last.col:
self.diag1 -= val
if last.row + last.col == self.n - 1:
self.diag2 -= val
self.move_count -= 1
self.current_player = last.player
self.status = GameStatus.IN_PROGRESS
return True
def display(self) -> str:
symbols = {Player.X: 'X', Player.O: 'O', None: '.'}
rows = ['|'.join(symbols[cell] for cell in row) for row in self.board]
return '
'.join(rows)
def get_available_moves(self) -> list[tuple]:
return [(r, c) for r in range(self.n) for c in range(self.n)
if self.board[r][c] is None]Game Session Manager
import uuid
@dataclass
class GameSession:
session_id: str = field(default_factory=lambda: str(uuid.uuid4())[:8])
player_x: str = ""
player_o: str = ""
game: TicTacToe = None
created_at: float = field(default_factory=lambda: __import__('time').time())
class GameManager:
"""Manages multiple concurrent game sessions."""
def __init__(self):
self.sessions: dict[str, GameSession] = {}
def create_game(self, player_x: str, player_o: str,
board_size: int = 3) -> GameSession:
session = GameSession(
player_x=player_x,
player_o=player_o,
game=TicTacToe(n=board_size)
)
self.sessions[session.session_id] = session
return session
def make_move(self, session_id: str, player_name: str,
row: int, col: int) -> dict:
session = self.sessions.get(session_id)
if not session:
raise ValueError("Session not found")
# Validate it's the right player's turn
expected_player = (session.player_x
if session.game.current_player == Player.X
else session.player_o)
if player_name != expected_player:
raise ValueError(f"Not {player_name}'s turn")
status = session.game.make_move(row, col)
return {
'status': status.value,
'board': session.game.display(),
'next_player': (session.player_x if session.game.current_player == Player.X
else session.player_o)
if status == GameStatus.IN_PROGRESS else None
}
def get_session(self, session_id: str) -> GameSession:
return self.sessions.get(session_id)
# AI opponent using minimax
def minimax(game: TicTacToe, is_maximizing: bool,
alpha: float, beta: float) -> int:
"""
Minimax with alpha-beta pruning for optimal Tic-Tac-Toe play.
For NxN boards, depth-limited minimax with heuristic evaluation.
"""
status = game.status
if status == GameStatus.X_WINS: return 10
if status == GameStatus.O_WINS: return -10
if status == GameStatus.DRAW: return 0
if is_maximizing: # X's turn (maximizer)
best = float('-inf')
for row, col in game.get_available_moves():
game.make_move(row, col)
score = minimax(game, False, alpha, beta)
game.undo()
best = max(best, score)
alpha = max(alpha, best)
if beta <= alpha:
break # Prune
return best
else: # O's turn (minimizer)
best = float('inf')
for row, col in game.get_available_moves():
game.make_move(row, col)
score = minimax(game, True, alpha, beta)
game.undo()
best = min(best, score)
beta = min(beta, best)
if beta tuple:
"""Find the best move for the current player using minimax."""
is_x_turn = game.current_player == Player.X
best_score = float('-inf') if is_x_turn else float('inf')
best = None
for row, col in game.get_available_moves():
game.make_move(row, col)
score = minimax(game, not is_x_turn, float('-inf'), float('inf'))
game.undo()
if ((is_x_turn and score > best_score) or
(not is_x_turn and score < best_score)):
best_score = score
best = (row, col)
return bestKey Design Decisions
- O(1) win detection: Increment/decrement count arrays on each move instead of scanning the board. Win condition: any count magnitude reaches win_length.
- Undo via move history stack: Store each move as a Move object; undo reverses counts and restores board cell. Essential for minimax AI and for game replay.
- Player enum with +1/-1 values: Using numeric values (X=+1, O=-1) enables win detection via absolute value — a single threshold check for both players.
- Generalized for N×N: win_length parameter allows 4-in-a-row on a 5×5 board (Connect Four variant).
Interview Extensions
- Connect Four: 7×6 board, 4-in-a-row wins, pieces drop to lowest available row. Add gravity constraint to move validation.
- Gomoku: 15×15 board, first to get exactly 5-in-a-row wins. Requires sliding window scan for 5 (not just count arrays).
- Distributed multiplayer: WebSocket server per game session; event-sourced game state; replay from event log on reconnect.
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”How do you detect a win in Tic-Tac-Toe in O(1) time?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Instead of scanning the entire board after each move (O(n^2)), maintain count arrays: rows[n], cols[n], diag1, diag2. When player X places at (r,c), increment rows[r] and cols[c] by +1 (use -1 for player O). Increment diag1 if r==c, and diag2 if r+c==n-1. After each move, check if abs(rows[r])==n, abs(cols[c])==n, abs(diag1)==n, or abs(diag2)==n. If any equals n in absolute value, the current player wins. This reduces win detection from O(n^2) to O(1) per move, with O(n) space for the count arrays.”}},{“@type”:”Question”,”name”:”How do you implement the minimax algorithm for Tic-Tac-Toe AI?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Minimax recursively explores all game states. The maximizing player (X) picks the move with the highest score; the minimizing player (O) picks the lowest. Base cases: X wins → return +1; O wins → return -1; draw → return 0. Alpha-beta pruning cuts branches that cannot affect the final decision: maintain alpha (best for maximizer so far) and beta (best for minimizer so far). If beta <= alpha, prune — the opponent will never allow this branch. For standard 3×3 Tic-Tac-Toe, the full game tree has 9! = 362,880 leaf nodes; alpha-beta typically reduces explored nodes by 50-90%."}},{"@type":"Question","name":"How do you design a Tic-Tac-Toe system to support multiple concurrent game sessions?","acceptedAnswer":{"@type":"Answer","text":"Use a GameManager class with a dictionary mapping game_id to Board instances. Each game has its own Board (count arrays, move history) and state (current player, game status). Thread safety: use per-game locks (a Lock per game_id entry) to allow concurrent games without blocking each other. Game creation generates a unique UUID. API: create_game() → game_id; make_move(game_id, row, col, player) → status; get_state(game_id) → board snapshot; undo_move(game_id) → restores previous state using the move history stack. This design scales horizontally — shard by game_id across servers."}}]}
🏢 Asked at: Meta Interview Guide 2026: Facebook, Instagram, WhatsApp Engineering
🏢 Asked at: Atlassian Interview Guide
🏢 Asked at: Uber Interview Guide 2026: Dispatch Systems, Geospatial Algorithms, and Marketplace Engineering
🏢 Asked at: Airbnb Interview Guide 2026: Search Systems, Trust and Safety, and Full-Stack Engineering