These are the notes for Low-Level Design (LLD) episode 57, the first full machine-coding problem of the course. In episodes 55 and 56 we learned how to attack a machine-coding round and how to answer the follow-up questions. Now we use all of it on the classic warm-up: Tic-Tac-Toe. We start with the obvious code and watch it break, then build a real design: game modelling with Board, Cell, Piece, Player and Game, turn management, win detection in O(1) with row and column counters, a game state enum, and a pluggable player strategy so a human vs bot player game needs no change to the core classes.
How the code was run: every program with javac Main.java && java -cp . Main on OpenJDK 21 (the programs that read the keyboard were given their input on standard input). Every output below is the real output.
1. The problem (the brief)
Tic-Tac-Toe is a two-player game on a grid, usually 3 x 3.
- Two players, X and O, take turns. X moves first.
- A move puts your mark in an empty square.
- You win with a full row, a full column, or a full diagonal of your mark.
- If every square is filled and nobody has a line, it's a draw.
As episode 55 taught, clarify before you code. Good clarifying questions here:
| Question | Our assumption |
|---|---|
| Is the board always 3 x 3? | No: any size n x n |
| Can a computer play? | Yes: human or bot players |
| What happens on an invalid move? | It is refused (an exception), never silently accepted |
| Do we need a graphical screen? | No: a console demo with a main method |
2. The real-life idea: a notebook game
Asha and Ravi play in the back page of a school notebook. Ravi, losing, writes his O over Asha's X: nobody stops him, because nobody owns the "square must be empty" rule. Their friend Neha is the referee; she checks rows and columns, forgets one diagonal, and calls a win a draw. Then they try a 1000 x 1000 grid, and Neha rechecks every line after every move: the game takes forever.
Each of these is a real bug in the obvious code. And the fixes come from the notebook too:
| In the notebook | In the design |
|---|---|
| The drawn grid, which knows which squares are filled | Board (the grid and its rules) |
| One square, like row 2, column 3 | Cell (a position: record Cell(int row, int col)) |
| The marks X and O; only two kinds exist | Piece (enum Piece { X, O }) |
| Asha and Ravi, who choose moves | Player |
| Neha the referee: whose turn, apply the move, declare the result | Game |
| Neha's tally in the margin beside each row, column and corner | Row, column and diagonal counters (O(1) win check) |
3. The obvious way, and how it breaks
Everything in main: a char array of 9 cells (index 0 to 8, row by row), a list of moves, X and O alternating, and a hand-written win check.
public class Main {
public static void main(String[] args) {
char[] b = " ".toCharArray(); // 9 cells, all empty
int[] moves = {4, 0, 2, 1, 6}; // cell numbers, turns alternate X, O
char turn = 'X';
for (int m : moves) { b[m] = turn; turn = (turn == 'X') ? 'O' : 'X'; }
for (int r = 0; r < 3; r++) System.out.println(" " + b[3*r] + " | " + b[3*r+1] + " | " + b[3*r+2]);
String result = "Draw";
for (int r = 0; r < 3; r++) // rows
if (b[3*r] != ' ' && b[3*r] == b[3*r+1] && b[3*r+1] == b[3*r+2]) result = b[3*r] + " wins";
for (int c = 0; c < 3; c++) // columns
if (b[c] != ' ' && b[c] == b[c+3] && b[c+3] == b[c+6]) result = b[c] + " wins";
if (b[0] != ' ' && b[0] == b[4] && b[4] == b[8]) result = b[0] + " wins"; // one diagonal
System.out.println("Result: " + result);
}
}
Output:
O | O | X
| X |
X | |
Result: Draw
X holds cells 2, 4 and 6: the top right, the centre and the bottom left. That is the anti-diagonal (the diagonal from top right to bottom left), so X has won. The program says Draw, because nobody wrote the anti-diagonal check.
Change the moves to {4, 4, 8}: X takes the centre, then O plays the same cell.
int[] moves = {4, 4, 8};
Output:
| |
| O |
| | X
Result: Draw
O is in the centre and X's mark is gone, with no complaint.
Why it failed
- A plain
chararray lets any write happen. There is no rule keeper. - The win check was copy-pasted by hand, so one line was forgotten.
- Turns, the board and the result are tangled together in
main.
4. Game modelling
Game modelling means turning the things and rules of a game into classes, so that every rule has an owner. Start with noun analysis (episode 20): the nouns of the brief are candidate classes.
Nouns in the brief: grid, square, mark, player, game. They become:
| Class | Kind | Owns |
|---|---|---|
Piece |
enum |
The two marks, X and O, and other() (X ↔ O) |
Cell |
record |
A position: row, col |
Board |
class | The grid, the "cell must be empty" rule, the win counters |
Player |
interface | How the next move is chosen |
Game |
class | The board, whose turn it is, and the game state |
Why these kinds?
- An enum is a type with a fixed list of values. There are exactly two marks, never a third, so
Pieceis an enum. The compiler then rejects anything that isn'tXorO. - A record is a short class whose only job is to carry values; Java writes the constructor, the getters (
row(),col()),equals,hashCodeandtoStringfor you. That's why a cell prints asCell[row=1, col=1]. - An interface is a contract: a list of methods a class promises to have.
Playeris one, so any kind of player can plug in.
The class diagram
Game ──owns──▶ Board ──made of──▶ Cell
│ │
│ asks └─ holds ─▶ Piece (X / O)
▼
Player (interface)
├─ HumanPlayer (reads the keyboard)
└─ BotPlayer (picks a free cell)
Game also owns: turn (Piece), state (GameState)
Read it as: a Game has a Board (composition: the board lives and dies with the game); the Board is made of cells, each holding a Piece or nothing; the Game asks a Player for each move; HumanPlayer and BotPlayer implement Player.
5. A Board that refuses bad moves
enum Piece { X, O } // a player's mark
record Cell(int row, int col) {} // one square, by position
class Board {
private final int n;
private final Piece[][] grid; // null = empty
Board(int n) { this.n = n; this.grid = new Piece[n][n]; }
boolean isFree(Cell c) { return grid[c.row()][c.col()] == null; }
void place(Cell c, Piece p) {
if (c.row() < 0 || c.row() >= n || c.col() < 0 || c.col() >= n)
throw new IllegalArgumentException("cell " + c + " is off the board");
if (!isFree(c))
throw new IllegalStateException("cell " + c + " already has " + grid[c.row()][c.col()]);
grid[c.row()][c.col()] = p;
}
void print() {
for (Piece[] row : grid) {
for (Piece p : row) System.out.print(p == null ? " ." : " " + p);
System.out.println();
}
}
}
public class Main {
public static void main(String[] args) {
Board board = new Board(3);
board.place(new Cell(1, 1), Piece.X);
board.print();
board.place(new Cell(1, 1), Piece.O); // O tries X's centre
}
}
Output:
. . .
. X .
. . .
Exception in thread "main" java.lang.IllegalStateException: cell Cell[row=1, col=1] already has X
at Board.place(Main.java:12)
at Main.main(Main.java:27)
nullin the grid means "empty".placeguards the rules: a cell outside the grid throwsIllegalArgumentException(a bad argument), a taken cell throwsIllegalStateException(the object is not in a state where this is allowed).- An exception is Java's way of stopping normal flow and saying "this should not happen"; uncaught, it prints its message and the stack trace (the chain of method calls, with line numbers).
- The rule now lives in one place, so no code path can overwrite a cell.
6. Win detection: from O(n²) to O(n) to O(1)
Big-O, in plain words
Big-O notation describes how the work grows as the input grows. Here the input is n, the board size.
- O(n²) ("O of n squared"): the work grows with n × n. Double n, four times the work.
- O(n): the work grows in step with n.
- O(1) ("constant time"): the work stays the same, however big n is.
The full scan
The safe obvious way: after every move, check every row, every column and both diagonals. This program counts the cells it reads.
public class Main {
static long reads = 0; // how many cells we looked at
static boolean fullScanWins(char[][] g, char p) { // check EVERY row, column, diagonal
int n = g.length; boolean d1 = true, d2 = true;
for (int i = 0; i < n; i++) {
boolean row = true, col = true;
for (int j = 0; j < n; j++) {
reads += 2;
if (g[i][j] != p) row = false;
if (g[j][i] != p) col = false;
}
if (row || col) return true;
reads += 2;
if (g[i][i] != p) d1 = false;
if (g[i][n - 1 - i] != p) d2 = false;
}
return d1 || d2;
}
public static void main(String[] args) {
for (int n : new int[]{3, 1000}) {
char[][] g = new char[n][n];
reads = 0;
for (int m = 0; m < 10; m++) { g[m % n][(2 * m) % n] = 'X'; fullScanWins(g, 'X'); } // no line yet
System.out.printf("n=%d: %,d cells read per move%n", n, reads / 10);
}
}
}
Output:
n=3: 24 cells read per move
n=1000: 2,002,000 cells read per move
About 2n² + 2n cells per move: O(n²). A 1000 x 1000 game can have a million moves, each reading two million cells.
Insight 1: only the last move can make a line
A new line can only be completed by the move just played. So check only the last move's row, its column, and the diagonals it is on: about 4n cells, O(n).
Insight 2: counters (O(1))
Don't read cells at all. Keep:
rows[i]: a counter for each row,cols[j]: a counter for each column,diag: the main diagonal (top left to bottom right, cells whererow == col),anti: the anti-diagonal (top right to bottom left, cells whererow + col == n - 1).
When X plays, add +1 to its row, its column, and any diagonal it is on. When O plays, add -1.
- A line full of X has counter
n; full of O, counter-n. - A mixed line has both +1s and -1s, so it can never reach
nor-n. - So: if
|counter| == nafter a move, that move just won.
That is 4 updates and 4 comparisons per move, for any board size: O(1). Memory: 2n + 2 integers, O(n).
enum Piece { X, O }
record Cell(int row, int col) {}
class WinTracker { // O(1) win check with counters
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]; }
boolean record(Cell c, Piece p) { // true if this move wins
int v = (p == Piece.X) ? 1 : -1; // X counts up, O counts down
rows[c.row()] += v;
cols[c.col()] += v;
if (c.row() == c.col()) diag += v;
if (c.row() + c.col() == n - 1) anti += v;
return Math.abs(rows[c.row()]) == n || Math.abs(cols[c.col()]) == n
|| Math.abs(diag) == n || Math.abs(anti) == n;
}
}
public class Main {
public static void main(String[] args) {
WinTracker t = new WinTracker(3);
Cell[] moves = { new Cell(1, 1), new Cell(0, 0), new Cell(0, 2), new Cell(0, 1), new Cell(2, 0) };
Piece p = Piece.X;
for (Cell c : moves) {
boolean won = t.record(c, p);
System.out.println(p + " plays " + c + (won ? " -> " + p + " WINS" : ""));
p = (p == Piece.X) ? Piece.O : Piece.X;
}
}
}
Output:
X plays Cell[row=1, col=1]
O plays Cell[row=0, col=0]
X plays Cell[row=0, col=2]
O plays Cell[row=0, col=1]
X plays Cell[row=2, col=0] -> X WINS
The same game the first program called a draw: the anti-diagonal counter reached 3.
Counter values for that game (n = 3):
| Move | rows | cols | diag | anti |
|---|---|---|---|---|
| X (1,1) | [0, 1, 0] | [0, 1, 0] | 1 | 1 |
| O (0,0) | [-1, 1, 0] | [-1, 1, 0] | 0 | 1 |
| X (0,2) | [0, 1, 0] | [-1, 1, 1] | 0 | 2 |
| O (0,1) | [-1, 1, 0] | [-1, 0, 1] | 0 | 2 |
| X (2,0) | [-1, 1, 1] | [0, 0, 1] | 0 | 3 → win |
| Approach | Work per move | Extra memory |
|---|---|---|
| Full scan | O(n²) | none |
| Last move's lines | O(n) | none |
| Counters | O(1) | O(n) |
7. Game state enum and turn management
The game state is the stage the game is in right now. Tic-Tac-Toe has four:
IN_PROGRESS ──win by X──▶ X_WON
│──────win by O──▶ O_WON
└──board full────▶ DRAW
Only IN_PROGRESS allows moves; the other three are final. A game state enum (enum GameState { IN_PROGRESS, X_WON, O_WON, DRAW }) makes these the only possible values: no misspelt string like "X won " can sneak in, and a switch over it can list every case.
Turn management means tracking whose move it is and switching it in exactly one place, after a valid move. Piece.other() gives O for X and X for O.
enum Piece { X, O; Piece other() { return this == X ? O : X; } }
enum GameState { IN_PROGRESS, X_WON, O_WON, DRAW } record Cell(int row, int col) {}
class Board { // the grid + the O(1) counters
final int n; private final Piece[][] g; private final int[] rows, cols; private int diag, anti, filled;
Board(int n) { this.n = n; g = new Piece[n][n]; rows = new int[n]; cols = new int[n]; }
boolean place(Cell c, Piece p) { // true if this move wins
int r = c.row(), k = c.col(), v = (p == Piece.X) ? 1 : -1;
if (g[r][k] != null) throw new IllegalStateException(c + " is taken");
g[r][k] = p; filled++; rows[r] += v; cols[k] += v; if (r == k) diag += v; if (r + k == n - 1) anti += v;
return Math.abs(rows[r]) == n || Math.abs(cols[k]) == n || Math.abs(diag) == n || Math.abs(anti) == n;
}
boolean isFull() { return filled == n * n; }
}
class Game { // owns the board, the turn and the state
private final Board board; private Piece turn = Piece.X; private GameState state = GameState.IN_PROGRESS;
Game(int n) { board = new Board(n); } GameState state() { return state; } Piece turn() { return turn; }
void play(Cell c) {
if (state != GameState.IN_PROGRESS) throw new IllegalStateException("game over: " + state);
if (board.place(c, turn)) state = (turn == Piece.X) ? GameState.X_WON : GameState.O_WON;
else if (board.isFull()) state = GameState.DRAW;
turn = turn.other(); // turn management in ONE place
}
}
public class Main { public static void main(String[] args) {
Game game = new Game(3);
int[][] moves = { {1, 1}, {0, 0}, {0, 2}, {0, 1}, {2, 0}, {2, 2} }; // the last one comes after the win
for (int[] m : moves) { Piece who = game.turn(); game.play(new Cell(m[0], m[1]));
System.out.println(who + " plays (" + m[0] + "," + m[1] + ") state: " + game.state()); }
}}
Output:
X plays (1,1) state: IN_PROGRESS
O plays (0,0) state: IN_PROGRESS
X plays (0,2) state: IN_PROGRESS
O plays (0,1) state: IN_PROGRESS
X plays (2,0) state: X_WON
Exception in thread "main" java.lang.IllegalStateException: game over: X_WON
at Game.play(Main.java:18)
at Main.main(Main.java:27)
The sixth move came after the win, and the Game refused it.
Note the order inside play: (1) refuse if the game is over, (2) place (the Board refuses a taken cell), (3) update the state, (4) switch the turn. If the board throws, the turn is not switched, so the same player tries again.
8. Pluggable player strategy: human vs bot
The classic follow-up: "Let me play against the computer." The quick fix, if (isBot) ... else ... inside Game, edits the core class for every new kind of player.
Ask what varies: how a move is chosen. Make it an interface:
interface Player { Cell nextMove(Board b); }
HumanPlayerreads "row col" from the keyboard with aScanner(Java's class for reading text input, here fromSystem.in, the standard input).BotPlayerchooses by itself; the simplest bot takes the first free cell, row by row.
This is the Strategy pattern (episode 34): a family of interchangeable algorithms behind one interface. A pluggable player strategy means you plug in any player without touching Board, the game loop or the win check.
import java.util.*;
enum Piece { X, O; Piece other() { return this == X ? O : X; } } record Cell(int row, int col) {}
class Board { // same Board, plus isFree
final int n; private final Piece[][] g; private final int[] rows, cols; private int diag, anti, filled;
Board(int n) { this.n = n; g = new Piece[n][n]; rows = new int[n]; cols = new int[n]; }
boolean isFree(int r, int k) { return g[r][k] == null; } boolean isFull() { return filled == n * n; }
boolean place(Cell c, Piece p) { // true if this move wins
int r = c.row(), k = c.col(), v = (p == Piece.X) ? 1 : -1;
if (!isFree(r, k)) throw new IllegalStateException(c + " is taken");
g[r][k] = p; filled++; rows[r] += v; cols[k] += v; if (r == k) diag += v; if (r + k == n - 1) anti += v;
return Math.abs(rows[r]) == n || Math.abs(cols[k]) == n || Math.abs(diag) == n || Math.abs(anti) == n;
}
}
interface Player { Cell nextMove(Board b); } // the strategy: HOW a move is chosen
class HumanPlayer implements Player { // types "row col" on the keyboard
private final Scanner in = new Scanner(System.in);
public Cell nextMove(Board b) { return new Cell(in.nextInt(), in.nextInt()); }
}
class BotPlayer implements Player { public Cell nextMove(Board b) { // simplest bot: first free cell
for (int r = 0; r < b.n; r++) for (int k = 0; k < b.n; k++) if (b.isFree(r, k)) return new Cell(r, k);
throw new IllegalStateException("no free cell"); } }
public class Main { public static void main(String[] args) {
Board board = new Board(3); Player[] players = { new HumanPlayer(), new BotPlayer() }; // X human, O bot
for (Piece turn = Piece.X; ; turn = turn.other()) { // the game loop
Cell c = players[turn.ordinal()].nextMove(board); boolean won = board.place(c, turn);
System.out.println(turn + " plays " + c.row() + "," + c.col() + (won ? " -> " + turn + " WINS" : ""));
if (won) break; if (board.isFull()) { System.out.println("DRAW"); break; }
}
}}
Input (one move per line, "row col"):
1 1
0 2
2 0
Output:
X plays 1,1
O plays 0,0
X plays 0,2
O plays 0,1
X plays 2,0 -> X WINS
The game loop is the for loop in main: ask the current player, place the move, print, stop on a win or a draw, switch turn. players[turn.ordinal()] picks the player: ordinal() is an enum value's position (X is 0, O is 1).
Bot vs bot: one line
Board board = new Board(3); Player[] players = { new BotPlayer(), new BotPlayer() }; // X human, O bot
(The comment is left over from the human version; only the array changed.) Output:
X plays 0,0
O plays 0,1
X plays 0,2
O plays 1,0
X plays 1,1
O plays 1,2
X plays 2,0 -> X WINS
X wins on the seventh move of the game, on the anti-diagonal. A new kind of player cost one line.
9. Interview follow-ups
| Follow-up | Answer |
|---|---|
| n x n board | Already works: every counter uses n |
| Win with k in a row (k < n), e.g. five in a row on 15 x 15 | Full-line counters no longer fit. Walk out from the last move in 4 directions (across, down, two diagonals), both ways, up to k cells: O(k) per move (code in the practice section) |
| 3 or more players | A list of pieces and a turn index (turn = (turn + 1) % players); one set of counters per player |
| Undo | Store each move as a command (episode 36) on a stack; undo pops it, clears the cell and reverses its +1 / -1 (code in the practice section) |
| An unbeatable bot | A new Player using minimax: a search that tries every possible future move, assuming the opponent always plays their best, and picks the move with the best guaranteed result |
| Invalid human input | Validate, print a message and ask again (the mini project does this) |
| A GUI or a web page | Only a new front end that calls Game.play; the model doesn't change |
| Thread safety (two clients) | Make play synchronized, or have one thread own the game and receive moves on a queue (episodes 46-50) |
Common mistakes
| Mistake | What you see | Why | Fix |
|---|---|---|---|
| Forgetting the anti-diagonal | Result: Draw while X holds cells 2, 4, 6 |
Hand-copied checks | Counters for both diagonals |
| Writing into any cell | O silently replaces X | No rule owner | Board.place checks the cell is free |
| Full scan after every move | n=1000: 2,002,000 cells read per move |
O(n²) per move | Row, column and diagonal counters: O(1) |
| Playing on after the game ended | java.lang.IllegalStateException: game over: X_WON |
The state is already final | Show the result; start a new Game |
| Human types a taken cell | java.lang.IllegalStateException: Cell[row=0, col=0] is taken |
Input not validated | Validate, then ask again |
Using strings for state ("X_WON") |
Typos compile and silently never match | No fixed set of values | enum GameState |
| Same sign for both players in counters | A mixed line can "win" | X and O must cancel out | X adds +1, O adds -1 |
| Switching the turn before validating | The wrong player moves after a refused move | Turn switched in two places | Switch once, after a valid move |
The "taken cell" crash is real: with the human typing 1 1 and then 0 0 (the bot's cell), the episode's program prints:
X plays 1,1
O plays 0,0
Exception in thread "main" java.lang.IllegalStateException: Cell[row=0, col=0] is taken
at Board.place(Main.java:9)
at Main.main(Main.java:25)
Mini project: a patient human and a blocking bot
Goal: the human is asked again on a bad cell instead of crashing, and the bot wins if it can, otherwise blocks your winning cell, otherwise takes the first free cell. The trick is wouldWin: it uses the counters to ask "would this move win?" without changing anything. Player.nextMove now also receives the piece it plays.
import java.util.*;
enum Piece { X, O; Piece other() { return this == X ? O : X; } }
record Cell(int row, int col) {}
class Board {
final int n;
private final Piece[][] g;
private final int[] rows, cols;
private int diag, anti, filled;
Board(int n) { this.n = n; g = new Piece[n][n]; rows = new int[n]; cols = new int[n]; }
boolean inside(int r, int k) { return r >= 0 && r < n && k >= 0 && k < n; }
boolean isFree(int r, int k) { return g[r][k] == null; }
boolean isFull() { return filled == n * n; }
// true if placing p at (r, k) WOULD win, without changing anything
boolean wouldWin(int r, int k, Piece p) {
int v = (p == Piece.X) ? 1 : -1, target = v * n;
return rows[r] + v == target || cols[k] + v == target
|| (r == k && diag + v == target) || (r + k == n - 1 && anti + v == target);
}
boolean place(Cell c, Piece p) {
int r = c.row(), k = c.col(), v = (p == Piece.X) ? 1 : -1;
if (!inside(r, k)) throw new IllegalArgumentException(c + " is off the board");
if (!isFree(r, k)) throw new IllegalStateException(c + " is taken");
g[r][k] = p; filled++;
rows[r] += v; cols[k] += v;
if (r == k) diag += v;
if (r + k == n - 1) anti += v;
return Math.abs(rows[r]) == n || Math.abs(cols[k]) == n || Math.abs(diag) == n || Math.abs(anti) == n;
}
}
interface Player { Cell nextMove(Board b, Piece me); }
class HumanPlayer implements Player { // asks again instead of crashing
private final Scanner in;
HumanPlayer(Scanner in) { this.in = in; }
public Cell nextMove(Board b, Piece me) {
while (true) {
int r = in.nextInt(), k = in.nextInt();
if (b.inside(r, k) && b.isFree(r, k)) return new Cell(r, k);
System.out.println(" (" + r + "," + k + ") is not a free cell, try again");
}
}
}
class BlockingBot implements Player { // win if you can, else block, else first free
public Cell nextMove(Board b, Piece me) {
for (Piece who : new Piece[]{me, me.other()})
for (int r = 0; r < b.n; r++)
for (int k = 0; k < b.n; k++)
if (b.isFree(r, k) && b.wouldWin(r, k, who)) return new Cell(r, k);
for (int r = 0; r < b.n; r++)
for (int k = 0; k < b.n; k++)
if (b.isFree(r, k)) return new Cell(r, k);
throw new IllegalStateException("no free cell");
}
}
public class Main {
public static void main(String[] args) {
Board board = new Board(3);
Player[] players = { new HumanPlayer(new Scanner(System.in)), new BlockingBot() };
for (Piece turn = Piece.X; ; turn = turn.other()) {
Cell c = players[turn.ordinal()].nextMove(board, turn);
boolean won = board.place(c, turn);
System.out.println(turn + " plays " + c.row() + "," + c.col() + (won ? " -> " + turn + " WINS" : ""));
if (won) break;
if (board.isFull()) { System.out.println("DRAW"); break; }
}
}
}
Input:
1 1
1 1
0 2
2 1
1 2
0 1
Output:
X plays 1,1
O plays 0,0
(1,1) is not a free cell, try again
X plays 0,2
O plays 2,0
X plays 2,1
O plays 1,0 -> O WINS
The human's second 1 1 was refused and asked again. After X's 0,2, the bot blocked the anti-diagonal at 2,0; after X's 2,1, the bot saw its own win in column 0 and took it. (The remaining input lines were never needed.)
Practice
1. Why does a counter of n mean the line is full of X, and why can a mixed line never win?
Answer
Each X adds +1 and each O adds -1. A line has n cells, so the counter can only reach n if all n cells are X (and -n if all are O). One O in the line pulls the maximum down to n - 2, so a mixed line can never reach ±n.
2. Which counters change when X plays the centre of a 3 x 3 board?
Answer
rows[1], cols[1], diag (because 1 == 1) and anti (because 1 + 1 == 3 - 1). The centre is the only cell of an odd-sized board on both diagonals.
3. Write a win check for k in a row on an n x n board that does O(k) work per move.
Answer
public class Main {
// after placing p at (r, c): is there a run of k equal marks through (r, c)? O(k) work
static boolean wins(char[][] g, int r, int c, int k) {
int n = g.length; char p = g[r][c];
int[][] dirs = { {0, 1}, {1, 0}, {1, 1}, {1, -1} }; // across, down, two diagonals
for (int[] d : dirs) {
int count = 1;
for (int s = -1; s <= 1; s += 2) { // walk both ways
int i = r + s * d[0], j = c + s * d[1];
while (i >= 0 && i < n && j >= 0 && j < n && g[i][j] == p && count < k) {
count++; i += s * d[0]; j += s * d[1];
}
}
if (count >= k) return true;
}
return false;
}
public static void main(String[] args) {
char[][] g = new char[15][15]; // 15 x 15, five in a row
int[][] xs = { {7, 3}, {7, 4}, {7, 6}, {7, 7} };
for (int[] m : xs) g[m[0]][m[1]] = 'X';
System.out.println("4 in the row, win? " + wins(g, 7, 7, 5));
g[7][5] = 'X'; // fill the gap
System.out.println("gap filled at (7,5), win? " + wins(g, 7, 5, 5));
}
}
Output:
4 in the row, win? false
gap filled at (7,5), win? true
4. Add undo to the counter board.
Answer
Each move is stored as a Move record (a command) on a stack (ArrayDeque). Undo pops the last move, clears its cell and applies the opposite sign.
import java.util.*;
enum Piece { X, O }
record Cell(int row, int col) {}
record Move(Cell cell, Piece piece) {} // a command we can reverse
class Board {
final int n; private final Piece[][] g; private final int[] rows, cols; private int diag, anti;
private final Deque<Move> history = new ArrayDeque<>(); // a stack of moves
Board(int n) { this.n = n; g = new Piece[n][n]; rows = new int[n]; cols = new int[n]; }
private void apply(Cell c, int v) {
rows[c.row()] += v; cols[c.col()] += v;
if (c.row() == c.col()) diag += v;
if (c.row() + c.col() == n - 1) anti += v;
}
void place(Cell c, Piece p) {
if (g[c.row()][c.col()] != null) throw new IllegalStateException(c + " is taken");
g[c.row()][c.col()] = p; apply(c, p == Piece.X ? 1 : -1); history.push(new Move(c, p));
}
void undo() {
Move m = history.pop(); // the last move
g[m.cell().row()][m.cell().col()] = null;
apply(m.cell(), m.piece() == Piece.X ? -1 : 1); // reverse the +1 / -1
}
String counters() { return "rows=" + Arrays.toString(rows) + " cols=" + Arrays.toString(cols) + " diag=" + diag + " anti=" + anti; }
}
public class Main {
public static void main(String[] args) {
Board b = new Board(3);
b.place(new Cell(1, 1), Piece.X);
b.place(new Cell(0, 0), Piece.O);
System.out.println("after 2 moves: " + b.counters());
b.undo();
System.out.println("after undo: " + b.counters());
b.place(new Cell(0, 0), Piece.X); // the cell is free again
System.out.println("X re-plays 0,0: " + b.counters());
}
}
Output:
after 2 moves: rows=[-1, 1, 0] cols=[-1, 1, 0] diag=0 anti=1
after undo: rows=[0, 1, 0] cols=[0, 1, 0] diag=1 anti=1
X re-plays 0,0: rows=[1, 1, 0] cols=[1, 1, 0] diag=2 anti=1
5. The interviewer asks for three players, X, O and Z. What changes?
Answer
Piece gets a third value; other() is replaced by a turn index (turn + 1) % 3. The ±1 trick only works for two players, so keep one set of counters per player (rows[player][i] and so on) and win when a counter reaches n. Board.place and the Player interface stay the same.
6. Where would you put the rule "X always moves first"?
Answer
In Game, as the initial value of turn (private Piece turn = Piece.X;). It's a rule of the game, and Game owns the turn. Neither Board nor Player should know it.
Quick quiz
On a 3 x 3 board, counters start at 0. X plays (0,0), O plays (1,1), X plays (2,2). What is diag, and does anyone win?
Answer
diag = 1, nobody wins yet. All three cells are on the main diagonal: +1 - 1 + 1 = 1. A win needs |diag| = 3, so this mixed diagonal can never win.
Interview questions
- How do you check for a win in O(1)? Keep a counter per row, per column and for both diagonals; X adds +1, O adds -1; after a move, check whether any of the four counters it touched has absolute value n.
- Why is
Cella record andPiecean enum? A cell is just a pair of values (a record gives equals, hashCode and toString for free); a piece has a fixed set of two values (an enum makes any other value impossible). - Who should own the turn: Board, Player or Game? Game. The board only knows the grid; players only choose moves; the game applies the rules of turn order.
- How would you add a computer player? Behind a
Playerinterface (Strategy pattern): add aBotPlayerclass; the game loop doesn't change. - What changes for five in a row on a big board? Full-line counters stop working; check outward from the last move in four directions, O(k).
- How would you support undo? Store moves as commands on a stack; undo clears the cell and reverses the counter updates (and resets the state to
IN_PROGRESS). - Is a singleton
Gamea good idea? No: you may want several games at once (or in tests). Create aGameper match.
Glossary
| Term | Meaning, with an example |
|---|---|
| Tic-Tac-Toe | A two-player game on a grid; three of your marks in a line wins |
| Machine-coding round | An interview round where you design and code a small working system in about 60-120 minutes |
| Game modelling | Turning a game's things and rules into classes so every rule has an owner: grid → Board |
| Noun analysis | Picking candidate classes from the nouns of the requirements: "grid, square, mark, player" |
| Board | The class that holds the grid and its rules: refuses a taken cell, keeps the win counters |
| Cell | One square, identified by its position: new Cell(1, 1) is the centre of a 3 x 3 board |
| Piece | A player's mark: enum Piece { X, O } |
| Player | The interface for "whoever chooses the next move": Cell nextMove(Board b) |
| Game | The class that owns the board, the turn and the state, and applies each move |
| Enum | A type with a fixed list of values: GameState.DRAW |
| Record | A short class that only carries values; Java writes its constructor, getters, equals, hashCode, toString |
| Interface | A contract listing methods a class promises to have: HumanPlayer implements Player |
| Exception | Java's way of stopping normal flow because something should not happen |
| IllegalArgumentException | Thrown when a method gets a bad argument: a cell off the board |
| IllegalStateException | Thrown when the object is not in a state that allows the call: a taken cell, a finished game |
| Stack trace | The chain of method calls (with line numbers) printed with an uncaught exception |
| Turn management | Tracking whose move it is and switching it in one place, after a valid move |
| Game state | The stage the game is in: IN_PROGRESS, X_WON, O_WON or DRAW |
| Game state enum | An enum listing every game state, so no other value can exist |
| Final state | A state that allows no more moves: X_WON, O_WON, DRAW |
| Diagonal (main) | Cells from top left to bottom right, where row == col |
| Anti-diagonal | Cells from top right to bottom left, where row + col == n - 1 |
| Full scan | Checking every row, column and diagonal after each move: O(n²) |
| Big-O notation | How the work grows with the input size: O(1), O(n), O(n²) |
| O(1), constant time | Work that doesn't grow with n: 4 counter updates per move |
| O(n) | Work that grows in step with n: checking the last move's lines |
| O(n²) | Work that grows with n × n: reading the whole board |
| Win detection in O(1) with row and column counters | X adds +1, O adds -1 to its row, column and diagonals; a counter whose absolute value equals n means a win |
| Counter | An integer kept up to date as things happen, so you never have to recount |
| Strategy pattern | A family of interchangeable algorithms behind one interface (episode 34) |
| Pluggable player strategy | Players as Player implementations you can swap without changing the game |
| Human vs bot player | A HumanPlayer reading the keyboard against a BotPlayer choosing by itself |
| Scanner | Java's class for reading text input: new Scanner(System.in).nextInt() |
| Standard input (stdin) | The program's input stream: the keyboard, or the compiler's input box |
| Game loop | The loop that repeats "ask the player, apply the move, check the result, switch turn" |
| ordinal() | An enum value's position in its list: Piece.X.ordinal() is 0 |
| Minimax | A search that tries every future move, assuming the opponent plays their best, to pick the best guaranteed move |
| Command (for undo) | A move stored as an object so it can be reversed later (episode 36) |
| k in a row | A variant where k marks in a line win (k can be smaller than n), like five in a row |
Summary
- The obvious code (a
chararray and hand-copied checks) called a win a draw and let O overwrite X. - Game modelling gave each rule an owner:
Board,Cell,Piece,Player,Game. - The Board refuses taken cells, so the rule lives in one place.
- Win detection went from a full scan (O(n²)), to the last move's lines (O(n)), to counters (O(1)): X +1, O -1,
|count| == nwins. - A GameState enum says when the game is over; the turn switches in one place.
- The Player interface (Strategy pattern) lets a human or a bot plug in: bot vs bot was a one-line change.
Next episode: Design Snake and Ladder, with dice, snakes, ladders, a game loop, and randomness you can control in tests.