The real-world analogy: a physical grid layout
Imagine sitting across a wooden board marked with a 3x3 grid.
- The Board: A physical grid that holds wooden tokens. It has 3 horizontal channels, 3 vertical channels, and 2 diagonals.
- The Counters: Instead of leaning over the board to check all lines every time someone places a token, we place a set of physical weight balances along the edges. When player X puts a token, we drop a 1-pound weight on the corresponding row and column balance. When player O plays, we drop a 1-pound balloon (negative weight). If any balance tilts completely to +3 pounds or -3 pounds, a bell rings—that player has won.
- The Rules (Strategy): You play standard Tic-Tac-Toe. If tomorrow you decide to play Connect-4, you keep the same board grid, but you add a physical gravity slot guide (placement rule) and change the win detector rule from "3-in-a-row" to "4-in-a-row" with gravity.
The ask
Two players alternate marking an N×N grid; the first to place N in a row (horizontal, vertical, or diagonal) wins; a full board with no winner is a draw. Build it with clean OOP, and be ready to extend it to bigger boards and other win rules.
It's tiny, so interviewers judge how you build it, not whether it works. SDE-1: a correct, playable game with turn handling. SDE-2: O(1) win detection and clean class boundaries. SDE-3: an extensibility seam (Strategy for the win rule) so Connect-4 and Gomoku reuse the design, plus input validation and turn enforcement. Asked at Amazon, Microsoft, Adobe, Atlassian; siblings include Snake, Chess, and Minesweeper.
The insight — don't rescan the board
The naive win check rescans rows, columns, and diagonals after every move. Even scanning only the affected lines is O(N) per move. You can do O(1): keep a running counter for each row, each column, and the two diagonals. Mark +1 for player X and −1 for player O. After a move, if any counter the move touched hits |counter| == N, that line is complete — that player just won.
UML Class Diagram
Think it through like the interview
PROBLEMN×N board, two players alternate, N-in-a-row wins, full board is a draw. Clean OOP, fast win detection, extensible to other board games.
- 1
Spec → entities
“What are the nouns, and which one owns the turn order?”
- 2
Make win detection O(1)
“How do I avoid rescanning lines after every move?”
unlocks after the stage above - 3
Build the extensibility seam
“Connect-4 and Gomoku reuse most of this. What varies, and how do I isolate it?”
unlocks after the stage above - 4
Guard the inputs and the turn
“What illegal moves must I reject before touching the board?”
unlocks after the stage above
Implementation
Below are complete, clean implementations featuring O(1) win checking and thread-safety locks to prevent concurrent turn races.
Python
import threading
from typing import List, Optional
class Board:
def __init__(self, n: int):
self.n = n
self.grid = [[None] * n for _ in range(n)]
self.rows = [0] * n
self.cols = [0] * n
self.diag = 0
self.anti_diag = 0
self.lock = threading.Lock()
def place_mark(self, r: int, c: int, player_id: int) -> bool:
with self.lock:
if r < 0 or r >= self.n or c < 0 or c >= self.n or self.grid[r][c] is not None:
raise ValueError("Invalid move location")
self.grid[r][c] = player_id
val = 1 if player_id == 1 else -1
self.rows[r] += val
self.cols[c] += val
if r == c:
self.diag += val
if r + c == self.n - 1:
self.anti_diag += val
return (abs(self.rows[r]) == self.n or
abs(self.cols[c]) == self.n or
abs(self.diag) == self.n or
abs(self.anti_diag) == self.n)
Java
import java.util.concurrent.locks.ReentrantLock;
public class Board {
private final int n;
private final Integer[][] grid;
private final int[] rows;
private final int[] cols;
private int diag = 0;
private int antiDiag = 0;
private final ReentrantLock lock = new ReentrantLock();
public Board(int n) {
this.n = n;
this.grid = new Integer[n][n];
this.rows = new int[n];
this.cols = new int[n];
}
public boolean placeMark(int r, int c, int playerId) {
lock.lock();
try {
if (r < 0 || r >= n || c < 0 || c >= n || grid[r][c] != null) {
throw new IllegalArgumentException("Invalid move location");
}
grid[r][c] = playerId;
int val = (playerId == 1) ? 1 : -1;
rows[r] += val;
cols[c] += val;
if (r == c) diag += val;
if (r + c == n - 1) antiDiag += val;
return Math.abs(rows[r]) == n || Math.abs(cols[c]) == n ||
Math.abs(diag) == n || Math.abs(antiDiag) == n;
} finally {
lock.unlock();
}
}
}
C++
#include <vector>
#include <mutex>
#include <cmath>
#include <stdexcept>
class Board {
private:
int n;
std::vector<std::vector<int>> grid;
std::vector<int> rows;
std::vector<int> cols;
int diag = 0;
int antiDiag = 0;
std::mutex mtx;
public:
Board(int size) : n(size), grid(size, std::vector<int>(size, 0)), rows(size, 0), cols(size, 0) {}
bool placeMark(int r, int c, int playerId) {
std::lock_guard<std::mutex> lock(mtx);
if (r < 0 || r >= n || c < 0 || c >= n || grid[r][c] != 0) {
throw std::invalid_argument("Invalid move location");
}
grid[r][c] = playerId;
int val = (playerId == 1) ? 1 : -1;
rows[r] += val;
cols[c] += val;
if (r == c) diag += val;
if (r + c == n - 1) antiDiag += val;
return std::abs(rows[r]) == n || std::abs(cols[c]) == n ||
std::abs(diag) == n || std::abs(antiDiag) == n;
}
};
TypeScript
type Mark = "X" | "O";
class Board {
private grid: (Mark | null)[][];
private rows: number[]; private cols: number[];
private diag = 0; private anti = 0;
constructor(public readonly n: number) {
this.grid = Array.from({ length: n }, () => Array(n).fill(null));
this.rows = Array(n).fill(0);
this.cols = Array(n).fill(0);
}
isEmpty(r: number, c: number) {
return r >= 0 && r < this.n && c >= 0 && c < this.n && this.grid[r][c] === null;
}
// Returns true if THIS move completed a line — O(1).
place(r: number, c: number, mark: Mark): boolean {
this.grid[r][c] = mark;
const d = mark === "X" ? 1 : -1;
this.rows[r] += d; this.cols[c] += d;
if (r === c) this.diag += d;
if (r + c === this.n - 1) this.anti += d;
const win = this.n;
return Math.abs(this.rows[r]) === win || Math.abs(this.cols[c]) === win
|| Math.abs(this.diag) === win || Math.abs(this.anti) === win;
}
}
class Game {
private board: Board;
private turn: Mark = "X";
private moves = 0;
private over = false;
constructor(n = 3) { this.board = new Board(n); }
move(r: number, c: number): "X wins" | "O wins" | "draw" | "ok" {
if (this.over) throw new Error("Game is over");
if (!this.board.isEmpty(r, c)) throw new Error("Cell taken or out of range");
const won = this.board.place(r, c, this.turn);
this.moves++;
if (won) { this.over = true; return `${this.turn} wins` as const; }
if (this.moves === this.board.n ** 2) { this.over = true; return "draw"; }
this.turn = this.turn === "X" ? "O" : "X";
return "ok";
}
}
Tracking a running sum per row/column/diagonal turns "did this move win?" into four comparisons. Mention the complexity out loud: naive rescans are O(N) per move; counters are O(1) with O(N) space. It's a small board, but the interviewer is checking whether you think about cost.
Interactive Quiz
1.
2.
3.
Complexity & follow-ups
- Gomoku (K-in-a-row on a big M×N): counters don't generalize (a line of K can sit anywhere). Instead, check only the four directions through the last move, counting contiguous same-marks — O(K) per move.
- Connect-4: add gravity (a move drops to the lowest empty row in its column) and check around the landing cell. Board + Game stay; the placement rule and WinningStrategy change.
- Bot player: a
Playerinterface with a human and a minimax/alpha-beta AI implementation — Strategy again. - Networked play: turn tokens + authoritative server state so two clients can't both move.
Design drills
Whiteboard each one out loud for 5–10 minutes before you reveal what a strong answer covers — the gap between your sketch and the checklist is your study list. Progress is saved on this device.
Extend the design to Connect-4 without rewriting Board or Game.
Support Gomoku: 5-in-a-row on a 15×15 board.
Add an AI opponent.