Design Tic-Tac-Toe (N×N, Human & Bot Strategies)
In a 45-minute LLD interview, the interviewer evaluates two core competencies: algorithmic efficiency under OOP encapsulation (achieving O(1) win checking on an N × N grid rather than O(N) row/column/diagonal scanning) and behavioral decoupling via Strategy (swapping scripted human inputs vs greedy/minimax bots without altering the turn loop). Scope the solution to an arbitrary N × N grid with two or more players, turn alternation via a FIFO queue, coordinate validation, and constant-time win/draw detection. Mention time-limited turns, move undo/redo via the Command pattern, and Connect-Four / Gomoku sliding windows as natural follow-up extensions.
Problem statement & clarifying requirements
Design an extensible, object-oriented Tic-Tac-Toe game supporting an arbitrary N × N grid, two or more players with customizable symbols, and pluggable player decision strategies (such as human scripted input, heuristic greedy bots, or minimax bots). Win checking after every move must execute in strict O(1) time complexity rather than scanning the board.
The board dimension is configurable as N × N (defaulting to 3, but fully supporting 4, 5, or larger). All win calculations must remain O(1) irrespective of N.
Use the Strategy pattern (MoveStrategy). Each player encapsulates their own strategy instance (e.g. ScriptedMoveStrategy for human or test replay, GreedyBotStrategy for autonomous bots).
The GameEngine maintains a FIFO turn queue (std::deque<std::unique_ptr<Player>>). At each turn, the front player acts and is rotated to the back if the game continues.
The game ends in a WIN when any player completes an entire row, column, main diagonal, or anti-diagonal. It ends in a DRAW when all N^2 cells are occupied without a winner.
First, sketch the design yourself
Spend 5 minutes listing the classes, who owns whom, and which interface hides the part that changes.
- 1.
Do not rescan all N rows and columns on every turn (O(N)). Maintain running row, column, diagonal, and anti-diagonal counters per player to check winning conditions in O(1) time.
- 2.
Strictly honor the Single Responsibility Principle (SRP):
Boardmanages grid state and win tracking;MoveStrategydetermines where to place;GameEnginecontrols the turn loop. - 3.
Support extensibility for AI algorithms: a bot player should be swappable at runtime simply by providing an alternate implementation of
MoveStrategywithout touchingGameEngine.
How to think through this problem (5-step walkthrough)
In a 45-minute LLD interview, the interviewer evaluates two core competencies: algorithmic efficiency under OOP encapsulation (achieving O(1) win checking on an N × N grid rather than O(N) row/column/diagonal scanning) and behavioral decoupling via Strategy (swapping scripted human inputs vs greedy/minimax bots without altering the turn loop). Scope the solution to an arbitrary N × N grid with two or more players, turn alternation via a FIFO queue, coordinate validation, and constant-time win/draw detection. Mention time-limited turns, move undo/redo via the Command pattern, and Connect-Four / Gomoku sliding windows as natural follow-up extensions.
Not every noun in the prompt deserves its own class. Separate dumb data structs from stateful managers, and turn trivial nouns into fields or enums.
MoveSimple struct Move { int row; int col; } representing 0-indexed cell coordinates. Pure immutable value struct without identity or lifecycle.
BoardOwns the N × N grid matrix and maintains incremental win-tracking telemetry (rowCount_, colCount_, diagCount_, antiDiagCount_) per player symbol to validate moves and evaluate victory in O(1) time.
MoveStrategyPluggable algorithm contract (getMove(board, symbol)) separating move selection from player identity. Enables runtime switching between scripted test moves, human console input, and bot heuristics (Strategy pattern).
PlayerRepresents an active participant with display name, marker symbol (char), and an owned std::unique_ptr<MoveStrategy>.
GameEngineCoordinates game lifecycle, manages the turn queue (std::deque<std::unique_ptr<Player>>), queries player moves, delegates to Board, and declares terminal outcomes (Win, Draw).
WinningLine / TurnCounterTrap noun — beginners often construct separate WinningLine, WinDetector, or TurnCounter classes with heavyweight lists of coordinates. An integer counter array per row/column/diagonal on Board and a simple modulo/deque turn rotation in GameEngine achieve the exact same behavior with zero allocation overhead and O(1) updates.
A naive implementation places everything in a single TicTacToeGame class with a 2D char[3][3] board and hardcodes std::cin >> r >> c inside a loop. After each turn, it loops through all N rows, N columns, and 2 diagonals (O(N) operations per turn, degrading to O(N^2) for naive cell comparisons). Supporting an arbitrary N × N board breaks the hardcoded loops; adding a greedy or minimax bot requires scattering if (isBot) checks throughout the input handling; and testing edge cases without interactive keyboard entry becomes virtually impossible.
Hardcoding console input or branching with if (player.isBot) inside the turn loop violates OCP and requires rewriting game loop code for every new opponent difficulty.
Scanning every row, column, and diagonal on each move creates O(N) latency on large boards (100 × 100) and couples victory rules to grid traversal loops.
Using an integer index turn = (turn + 1) % numPlayers paired with indexed array lookups makes dynamic player disqualification or round-robin skip rules brittle.
- ✓
Grid boundary and occupancy invariant:
Board::isValidMove(r, c)must guarantee $0 ≤ r < N and 0 ≤ c < N$ andgrid_[r][c] == ' 'before any counter mutation occurs. - ✓
Constant-time win invariant: Every player symbol maps to integer vectors
rowCount_[symbol][r]andcolCount_[symbol][c]plus diagonal scalars. A move triggers a win if and only if any of those counters reaches N, tested in strict O(1) time. - ✓
Ownership:
GameEngineuniquely ownsBoardand the player queue (std::deque<std::unique_ptr<Player>>). EachPlayeruniquely owns itsstd::unique_ptr<MoveStrategy>.
Entities & design patterns used
Unlock Full UML Diagram & C++23 Solution
The complete UML diagram, production-ready C++23 code, follow-up extensions, and design pitfall analysis are part of Brute2Best Pro. All 7 foundation chapters are 100% free.
First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.