Problem 6: Design Tic-Tac-Toe

The setup

"Design Tic-Tac-Toe. Two players, 3×3 grid, take turns placing X and O. Win by getting three in a row (horizontal, vertical, or diagonal). Detect win/draw."

This problem looks trivial but is asked deliberately. The interviewer is testing whether you can design something simple simply, without over-engineering, while still demonstrating good practices. Resist adding 8 design patterns.

Clarifying questions

Core entities

enum CellValue { EMPTY, X, O }

class Cell {
  int row, col;
  CellValue value;
}

class Board {
  Cell[][] cells;  // 3x3
  
  boolean isEmpty(int row, int col) { ... }
  void place(int row, int col, CellValue value) { ... }
  boolean isFull() { ... }
}

class Player {
  String name;
  CellValue symbol;  // X or O
}

class Game {
  Board board;
  Player playerX, playerO;
  Player currentPlayer;
  GameStatus status;  // IN_PROGRESS, X_WINS, O_WINS, DRAW
  
  MoveResult makeMove(Player player, int row, int col);
  void checkWinCondition();
}

The win-detection logic

Many candidates over-engineer this. The straightforward approach is fine:

class Game {
  private boolean checkWinAfterMove(int row, int col, CellValue symbol) {
    // Check row
    if (allMatch(board.cells[row], symbol)) return true;
    // Check column
    if (allMatchCol(board, col, symbol)) return true;
    // Check diagonals (only if move is on a diagonal)
    if (row == col && allMatchDiagonal(board, symbol)) return true;
    if (row + col == 2 && allMatchAntiDiagonal(board, symbol)) return true;
    return false;
  }
  
  private boolean allMatch(Cell[] row, CellValue symbol) {
    for (Cell c : row) if (c.value != symbol) return false;
    return true;
  }
  // ... similar for column, diagonals
}

Don't reach for the Strategy pattern here. The win condition isn't going to change. Keep the code direct.

Design Decision: extensibility for m×n×k

The interviewer might ask about a generalized version: m×n board, k-in-a-row wins. Now the win detection is parameterised:

class Game {
  int boardRows, boardCols, k;  // need k in a row to win
  
  private boolean checkWinAfterMove(int row, int col, CellValue symbol) {
    // Check four directions through the just-played cell
    return countInDirection(row, col, 0, 1, symbol) + countInDirection(row, col, 0, -1, symbol) - 1 >= k  // horizontal
        || countInDirection(row, col, 1, 0, symbol) + countInDirection(row, col, -1, 0, symbol) - 1 >= k  // vertical
        || countInDirection(row, col, 1, 1, symbol) + countInDirection(row, col, -1, -1, symbol) - 1 >= k  // diagonal
        || countInDirection(row, col, 1, -1, symbol) + countInDirection(row, col, -1, 1, symbol) - 1 >= k;  // anti-diagonal
  }
  
  private int countInDirection(int row, int col, int dr, int dc, CellValue symbol) {
    int count = 0;
    int r = row, c = col;
    while (r >= 0 && r < boardRows && c >= 0 && c < boardCols 
           && board.cells[r][c].value == symbol) {
      count++;
      r += dr;
      c += dc;
    }
    return count;
  }
}

This generalises Tic-Tac-Toe (3,3,3), Connect Four (6,7,4), Gomoku (15,15,5), etc.

Design Decision: Observer pattern (optional)

For UI integration, observers can subscribe to game events:

interface GameObserver {
  void onMoveMade(Move move);
  void onGameEnded(GameStatus result);
}

class Game {
  private List observers;
  
  public MoveResult makeMove(Player p, int row, int col) {
    // ... move logic ...
    Move move = new Move(p, row, col);
    observers.forEach(o -> o.onMoveMade(move));
    if (isGameOver()) {
      observers.forEach(o -> o.onGameEnded(status));
    }
    return ...;
  }
}

For pure engine-only design, observers may be over-engineering. Include them if extension to UI is hinted at.

Cross-examination round 1: efficient win detection

Takeaway

Tic-tac-toe tests restraint. The right design for this problem is minimal: a Board, a Game, a Player, win-detection logic. Adding Strategy / Observer / State machine is over-engineering. The mark of a senior engineer is knowing when not to add complexity. Solve the actual problem, not the imagined more-complex one. Mention extensibility briefly if it comes up, but don't optimise prematurely.