Tic Tac Toe

A deceptively small prompt that interviewers like precisely because it is small - there is nowhere to hide a design decision behind volume of code. The one twist worth building for: the board size and the win condition should not be nailed to 3 and "3 in a row".

Requirements

Functional

Two players take turns placing their symbol on an empty cell.
After each move, the game reports whether that move won, drew the game, or play continues.
The board size is configurable - not hardcoded to 3x3.

Non-functional

Checking for a win after a move should not rescan the entire board - only the cells that could possibly be affected by the move just played.
Supporting a different win condition (say, a 5x5 board where 4 in a row wins instead of 5) should mean adding a class, not editing Game.

Design

Board only knows how to store and report symbols in a grid - it has no idea what "winning" means. WinningStrategy owns that question entirely, which is what lets a 5x5-board-needs-4-in-a-row variant exist as a second implementation instead of an if branch inside Game. Game itself just alternates players, forwards each move to Board, and asks the strategy whether that move ended the game.

1The referee only ever talks to the game - never to the board or a strategy directly.
2The board stores the mark and rejects the move if the cell was already taken.
3The game hands the just-played cell to the strategy - it never inspects the grid itself.
4The strategy walks outward from that cell in four directions, reading symbols as it goes.
5If nobody won, the game hands the turn to the other player.
6WON, DRAW or IN_PROGRESS - the referee reacts, the game never prints anything itself.

The strategy only ever looks at the cell that was just played and walks outward from it in four directions (horizontal, vertical, two diagonals) - never the whole board. A win can only involve the most recent move, so there is nothing to gain by looking anywhere else.

Class diagram

implementsuses

Game orchestrates; Board stores; WinningStrategy decides. The board's size and the win length are both just numbers passed in.

Code

import java.util.*;
 
enum Symbol { EMPTY, X, O }
enum GameStatus { IN_PROGRESS, WON, DRAW }
 
class Player {
    final String name;
    final Symbol symbol;
 
    Player(String name, Symbol symbol) {
        this.name = name;
        this.symbol = symbol;
    }
}
 
class Board {
    private final Symbol[][] grid;
    final int size;
 
    Board(int size) {
        this.size = size;
        grid = new Symbol[size][size];
        for (Symbol[] row : grid) Arrays.fill(row, Symbol.EMPTY);
    }
 
    boolean placeMark(int row, int col, Symbol symbol) {
        if (grid[row][col] != Symbol.EMPTY) return false;
        grid[row][col] = symbol;
        return true;
    }
 
    Symbol getSymbolAt(int row, int col) {
        if (row < 0 || row >= size || col < 0 || col >= size) return Symbol.EMPTY;
        return grid[row][col];
    }
 
    boolean isFull() {
        for (Symbol[] row : grid)
            for (Symbol s : row)
                if (s == Symbol.EMPTY) return false;
        return true;
    }
}
 
interface WinningStrategy {
    boolean hasWinner(Board board, int row, int col);
}
 
class LineWinningStrategy implements WinningStrategy {
    private final int winLength;
    private static final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {1, 1}, {1, -1}};
 
    LineWinningStrategy(int winLength) {
        this.winLength = winLength;
    }
 
    public boolean hasWinner(Board board, int row, int col) {
        Symbol symbol = board.getSymbolAt(row, col);
        for (int[] dir : DIRECTIONS) {
            int count = 1;
            count += countDirection(board, row, col, dir[0], dir[1], symbol);
            count += countDirection(board, row, col, -dir[0], -dir[1], symbol);
            if (count >= winLength) return true;
        }
        return false;
    }
 
    private int countDirection(Board board, int row, int col, int dRow, int dCol, Symbol symbol) {
        int count = 0;
        int r = row + dRow, c = col + dCol;
        while (board.getSymbolAt(r, c) == symbol && symbol != Symbol.EMPTY) {
            count++;
            r += dRow;
            c += dCol;
        }
        return count;
    }
}
 
class Game {
    private final Board board;
    private final List<Player> players;
    private final WinningStrategy winStrategy;
    private int currentPlayer = 0;
 
    Game(Board board, List<Player> players, WinningStrategy winStrategy) {
        this.board = board;
        this.players = players;
        this.winStrategy = winStrategy;
    }
 
    GameStatus playTurn(int row, int col) {
        Player player = players.get(currentPlayer);
        if (!board.placeMark(row, col, player.symbol)) {
            throw new IllegalArgumentException("Cell already occupied");
        }
        if (winStrategy.hasWinner(board, row, col)) return GameStatus.WON;
        if (board.isFull()) return GameStatus.DRAW;
        currentPlayer = (currentPlayer + 1) % players.size();
        return GameStatus.IN_PROGRESS;
    }
}

Design decisions

WinningStrategy is an interface, not a method on Board. Board answering "did this move win?" would force it to also know about win-length rules, coupling storage to a policy that changes far more often than storage does. Split apart, a Gomoku-style variant is one new LineWinningStrategy(winLength=4) instance, not a rewrite.
The win check scans outward from the last move instead of the whole board. A full board scan is O(n^2) per move and gets slower as the board grows; scanning four directions from one cell is O(n) regardless of board size, because a win can only ever include the cell that was just played.
Board exposes placeMark/getSymbolAt, never the raw grid. Nothing outside Board can put a mark somewhere without going through the one method that also checks the cell is empty - the invariant "a filled cell never gets overwritten" lives in exactly one place.
What's missing for a real system: undo/redo, a spectator or replay feed, and an AI opponent (which would slot in as another Player implementation, since nothing about Game assumes a human is driving either side) are all out of scope for a 45-minute round but worth naming if asked "what would you add next."

Common follow-ups

How would you add an AI opponent? As another participant driving playTurn - nothing about Game assumes a human is behind either side, so the interviewer wants you to notice the seam is already there rather than invent a new one.
How would you support undo? Game would need to track move history (row, col, symbol) and Board would need a way to clear one cell, which it does not expose today - worth naming as a real gap rather than pretending it's free.
What if you wanted a "Gomoku on an infinite board" variant? Board's fixed-size array would become a sparse structure (a set of occupied coordinates); getSymbolAt's out-of-bounds case already treats a missing cell as empty, so most of LineWinningStrategy's scanning logic carries over unchanged.
Why does hasWinner take (board, row, col) instead of just board? A win can only ever involve the last move played, so passing that move lets the strategy skip scanning the whole board. Drop the coordinates and you're back to an O(n^2) full-board scan.

Check yourself

Question 1 of 4

Why is WinningStrategy an interface rather than a method on Board?

Requirements​

Design​

Class diagram​

Code​

Design decisions​

Common follow-ups​