Design Tic-Tac-Toe, Low Level Design (LLD) Interview
Tic-tac-toe on a board of any size. Players sit behind one interface, so a person or a bot can play. The board only accepts legal moves. The game owns turns and the result. And the winner check is fast: it never scans the whole board.
Where it shows up
A very common first LLD or machine-coding question in India. It is asked most for SDE1 and SDE2 roles and campus hiring. It is also a common warm-up before a harder design at product companies.
Why this is asked
Everyone knows the rules. So the whole round is about design, not about understanding the problem. It quickly shows if a candidate splits the work well. Who holds the grid? Who decides the turn? Who decides the winner? It shows if they check input instead of trusting it. It shows if they can move from a 3 by 3 board to any size. The follow-up that separates candidates is the winner check. Scanning the whole board after every move is slow. There is a simple way to check in constant time.
Requirements
Functional
- Two players take turns placing X and O on an N by N board, with N at least 3.
- A move is rejected if the cell is off the board or taken. The same player tries again.
- The game ends when a player fills a whole row, column or diagonal, or the board is full (a draw).
- A player can be a person or a bot. The game does not care which.
- Report the status (playing, won, draw) and the winner.
Constraints & non-functional
- Checking for a winner after a move must not scan the whole board. It must take constant time.
- The board is the only thing that changes cells, and it refuses illegal moves.
- Adding a new kind of player, like a smarter bot, must not change the game.
- The design must work for any N, not only 3.
Core classes & entities
Game
Owns the players, the board and the win tracker. It decides whose turn it is and applies a move. It sets the status and the winner.
attrs: board: Board, players: Player[2], tracker: WinTracker, status: GameStatus
methods: playTurn(): boolean, playToEnd(), status(), winner()
Board
An N by N grid. It is the only class that changes cells. It rejects moves off the grid or onto a taken cell.
attrs: n, cells: Symbol[][], filled
methods: isFree(r, c), place(r, c, symbol), isFull(), freeCells()
WinTracker
Keeps a running count for each row, each column and the two diagonals. So a win is found in constant time after each move.
attrs: rows: int[], cols: int[], diag, anti
methods: record(r, c, symbol): boolean
Player
The interface for anyone who can choose a move. That can be a person, a scripted player in tests, or a bot.
methods: symbol(), name(), chooseMove(board)
RandomBot
A simple bot that picks a random free cell. It is used to test the game on thousands of positions.
attrs: symbol, rnd
methods: chooseMove(board)
ScriptedPlayer
Plays a fixed list of moves. It stands in for a person in tests, so games can be replayed exactly.
attrs: name, symbol, moves
methods: chooseMove(board)
Relationships
- Game → composition → Board. A game owns exactly one board.
- Game → composition → WinTracker. The tracker lives and dies with the game.
- Game → aggregation → Player. Players are passed in. The same players could play another game.
- Player → implements → RandomBot. A bot is just another player.
- Player → implements → ScriptedPlayer. Used for tests and replays.
Design patterns used
Strategy in Player with ScriptedPlayer and RandomBot
How a move is chosen changes: a person, a random bot, a smart bot. The game loop stays the same.
Keeping the rules in one place in Board.place and Game.playTurn
Illegal moves are refused in one place. So no caller can put the game into an impossible state.
Update as you go in WinTracker
Do not work out the answer from the whole board each time. Keep counts that each move updates in constant time.
Enums
Key API / methods
boolean Game.playTurn()Asks the current player for a move and applies it. If the move is illegal, it returns false and the same player goes again. If the move ends the game, it sets the status and the winner.
void Board.place(int r, int c, Symbol s)Places a symbol. It throws an error if the cell is off the board or already taken.
boolean WinTracker.record(int r, int c, Symbol s)Adds the move to its row, column and diagonal counts. It returns true if any of those lines is now full. It takes constant time.
Code skeleton
import java.util.*;
// ---------- Enums ----------
enum Symbol { X, O }
enum GameStatus { IN_PROGRESS, WON, DRAW }
// ---------- Players: a human or a bot, behind one interface ----------
interface Player { Symbol symbol(); String name(); int[] chooseMove(Board b); }
final class ScriptedPlayer implements Player { // replays given moves; stands in for a human in tests
private final String name; private final Symbol symbol; private final Deque<int[]> moves;
ScriptedPlayer(String name, Symbol s, int[][] moves) { this.name = name; this.symbol = s; this.moves = new ArrayDeque<>(List.of(moves)); }
public Symbol symbol() { return symbol; }
public String name() { return name; }
public int[] chooseMove(Board b) { return moves.poll(); }
}
final class RandomBot implements Player {
private final Symbol symbol; private final Random rnd;
RandomBot(Symbol s, Random r) { symbol = s; rnd = r; }
public Symbol symbol() { return symbol; }
public String name() { return "Bot " + symbol; }
public int[] chooseMove(Board b) {
List<int[]> free = b.freeCells();
return free.get(rnd.nextInt(free.size()));
}
}
// ---------- Board: an N x N grid that only accepts legal moves ----------
final class Board {
final int n; private final Symbol[][] cells; private int filled;
Board(int n) { if (n < 3) throw new IllegalArgumentException("board must be at least 3x3"); this.n = n; cells = new Symbol[n][n]; }
boolean isFree(int r, int c) { return r >= 0 && r < n && c >= 0 && c < n && cells[r][c] == null; }
void place(int r, int c, Symbol s) {
if (!isFree(r, c)) throw new IllegalArgumentException("cell " + r + "," + c + " is not free");
cells[r][c] = s; filled++;
}
Symbol at(int r, int c) { return cells[r][c]; }
boolean isFull() { return filled == n * n; }
List<int[]> freeCells() { List<int[]> f = new ArrayList<>(); for (int r = 0; r < n; r++) for (int c = 0; c < n; c++) if (cells[r][c] == null) f.add(new int[]{r, c}); return f; }
}
// ---------- Win detection in O(1) per move: running counts, never a board scan ----------
final class WinTracker {
private final int n; private final int[] rows, cols; private int diag, anti;
WinTracker(int n) { this.n = n; rows = new int[n]; cols = new int[n]; }
/** X adds +1, O adds -1. A line whose count reaches +n or -n is complete. */
boolean record(int r, int c, Symbol s) {
int d = (s == Symbol.X) ? 1 : -1;
rows[r] += d; cols[c] += d;
if (r == c) diag += d;
if (r + c == n - 1) anti += d;
return Math.abs(rows[r]) == n || Math.abs(cols[c]) == n || Math.abs(diag) == n || Math.abs(anti) == n;
}
}
// ---------- Game: turns, rules and the final result ----------
final class Game {
final Board board; private final Player[] players; private final WinTracker tracker;
private int turn; private GameStatus status = GameStatus.IN_PROGRESS; private Player winner;
Game(int n, Player first, Player second) {
if (first.symbol() == second.symbol()) throw new IllegalArgumentException("players need different symbols");
board = new Board(n); players = new Player[]{first, second}; tracker = new WinTracker(n);
}
GameStatus status() { return status; }
Optional<Player> winner() { return Optional.ofNullable(winner); }
/** Plays one move for whoever's turn it is. Illegal moves are rejected and the turn does not change. */
boolean playTurn() {
if (status != GameStatus.IN_PROGRESS) throw new IllegalStateException("game is over");
Player p = players[turn % 2];
int[] m = p.chooseMove(board);
if (m == null || !board.isFree(m[0], m[1])) return false;
board.place(m[0], m[1], p.symbol());
if (tracker.record(m[0], m[1], p.symbol())) { status = GameStatus.WON; winner = p; }
else if (board.isFull()) status = GameStatus.DRAW;
turn++;
return true;
}
void playToEnd() { while (status == GameStatus.IN_PROGRESS) if (!playTurn()) throw new IllegalStateException("illegal move"); }
}
// ---------- Demo: the O(1) tracker is checked against a full scan on thousands of games ----------
public class TicTacToe {
public static void main(String[] args) {
Game g = new Game(3, new ScriptedPlayer("Asha", Symbol.X, new int[][]{{0, 0}, {1, 1}, {2, 2}}),
new ScriptedPlayer("Bala", Symbol.O, new int[][]{{0, 1}, {0, 2}}));
g.playToEnd();
check(g.status() == GameStatus.WON && g.winner().get().name().equals("Asha"), "Asha wins on the diagonal in 5 moves");
Game bad = new Game(3, new ScriptedPlayer("A", Symbol.X, new int[][]{{1, 1}, {0, 0}}),
new ScriptedPlayer("B", Symbol.O, new int[][]{{1, 1}}));
bad.playTurn();
check(!bad.playTurn(), "a move on an occupied cell is rejected and the turn does not pass");
int[][] xs = {{0, 0}, {0, 2}, {1, 0}, {1, 2}, {2, 1}}, os = {{0, 1}, {1, 1}, {2, 0}, {2, 2}};
Game draw = new Game(3, new ScriptedPlayer("A", Symbol.X, xs), new ScriptedPlayer("B", Symbol.O, os));
draw.playToEnd();
check(draw.status() == GameStatus.DRAW, "a full board with no line is a draw");
Random rnd = new Random(42); int games = 0, xWins = 0, oWins = 0, draws = 0;
for (int n = 3; n <= 5; n++) for (int i = 0; i < 3_000; i++) {
Game rg = new Game(n, new RandomBot(Symbol.X, rnd), new RandomBot(Symbol.O, rnd));
rg.playToEnd(); games++;
GameStatus scanned = scan(rg.board);
if (scanned != rg.status()) check(false, "tracker and full scan disagree on game " + games);
if (rg.status() == GameStatus.DRAW) draws++; else if (rg.winner().get().symbol() == Symbol.X) xWins++; else oWins++;
}
check(true, games + " random games on 3x3, 4x4 and 5x5: O(1) tracker matches a full board scan every time"
+ " (X " + xWins + ", O " + oWins + ", draws " + draws + ")");
}
/** The slow, obvious check: scan every row, column and diagonal. Used only to verify the tracker. */
static GameStatus scan(Board b) {
int n = b.n;
for (int i = 0; i < n; i++) { if (line(b, i, 0, 0, 1) || line(b, 0, i, 1, 0)) return GameStatus.WON; }
if (line(b, 0, 0, 1, 1) || line(b, 0, n - 1, 1, -1)) return GameStatus.WON;
return b.isFull() ? GameStatus.DRAW : GameStatus.IN_PROGRESS;
}
static boolean line(Board b, int r, int c, int dr, int dc) {
Symbol s = b.at(r, c); if (s == null) return false;
for (int k = 1; k < b.n; k++) if (b.at(r + k * dr, c + k * dc) != s) return false;
return true;
}
static void check(boolean ok, String what) { System.out.println((ok ? " ok " : " FAIL ") + what); if (!ok) System.exit(1); }
}
/* Output of this exact program (javac + java 21, 2026-09-25):
* ok Asha wins on the diagonal in 5 moves
* ok a move on an occupied cell is rejected and the turn does not pass
* ok a full board with no line is a draw
* ok 9000 random games on 3x3, 4x4 and 5x5: O(1) tracker matches a full board scan every time (X 3401, O 2110, draws 3489)
*/How it works
Split the problem into three jobs, and give each job its own class. The Board holds the grid. It is the only thing that changes a cell. It refuses a move off the grid or onto a taken cell. The Game holds the two players. It decides whose turn it is, applies each move and records the result. The Player interface hides how a move is chosen. So a person, a test player and a bot can all play.
The interesting part is finding a win. The obvious way scans every row, column and diagonal after each move. That gets slower as the board grows. The better way keeps running counts. Keep one list of counts for rows and one for columns. Keep two numbers for the diagonals. X adds 1 and O takes away 1. After a move at row r and column c, only that row and that column change. The two diagonals may change too. A line is full exactly when its count reaches N or minus N. This takes constant time per move, and very little memory.
The program does not just claim the tracker is right. It plays 9,000 random games between two bots. It uses boards of 3 by 3, 4 by 4 and 5 by 5. After each game, it runs the slow full-board scan as a second check. The two agree on every game. It also checks a planned diagonal win, a rejected move onto a taken cell, and a full-board draw.
The order of checks matters in one place. After a move, check for a win before checking if the board is full. The last move can be both.
Some good follow-ups to mention. A smart bot is just a new Player, and the Game does not change. Undo can be added with a stack of moves. WinTracker then takes the move away again by doing the opposite sum. And an online game is a Player whose chooseMove waits for a message.
Edge cases & gotchas
- A move on a taken cell or off the board is rejected. The same player moves again.
- The winning move is also the last free cell. It is a win, not a draw, because the win is checked first.
- Both diagonals pass through the centre of an odd board. So one move there updates both.
- A move after the game has ended is refused with an error.
- Two players with the same symbol are rejected when the game is made.
- Boards smaller than 3 by 3 are rejected. The design works the same for 4 by 4, 5 by 5 and larger.