Tic-Tac-Toe: O(1) Win Detection Without a Full Board Scan

1.1Problem Statement

Difficulty: Easy · Language: C++ · Pattern focus: Strategy (pluggable win rule), clean board modeling.

Context. Design a 2-player Tic-Tac-Toe game playable on an N×N board (default 3×3).

Functional Requirements

• Two players take alternating turns placing their mark (X / O) on an empty cell.
• The game detects a win (a full row, column, or either diagonal of the same mark) or a draw (board full, no winner).
• Reject invalid moves (occupied cell, out-of-bounds, wrong player's turn) gracefully — no crash, no silent corruption of state.
• Generalize cleanly to N×N — the win condition must not be hardcoded to 3.

Non-Functional Requirements & Constraints

• Win-check should be efficient: do not rescan the entire board after every move. Maintain per-row, per-column, and per-diagonal counters and check in O(1) per move.
• Single-threaded is fine for the base version.

Expected Public Interface

enum class GameStatus { IN_PROGRESS, WIN, DRAW };

class Game {
public:
    Game(int boardSize, std::vector<Player> players);
    void makeMove(int playerId, int row, int col);   // throws/returns error on invalid move
    GameStatus getStatus() const;
    const Player* getWinner() const;                  // nullptr if no winner yet
};

What the Interviewer Is Really Testing

• Clean separation of Board, Cell, Player, Game.
• The O(1) win-check via counters (this is the differentiator from a naive answer).
• Whether your abstractions survive the generalization to N×N.

Follow-Up Questions to Expect

1. Support more than 2 players on a larger board.
2. Make the win rule pluggable (e.g. Connect-Four style "K marks in a row" via a WinningStrategy interface).
3. Add undo / replay of the move history.

The task, in order: spend the first 2–3 minutes writing assumptions and the public interface above, implement the entities and the O(1) win-check, then evolve toward at least one follow-up.

1.2How to Approach

Mine the Constraints First

Before writing a line of code, read the statement the way an interviewer wrote it and extract the constraints that secretly decide your design. Three phrases matter here: "generalize cleanly to N×N" means board size is a parameter and no magic 3 appears anywhere; "do not rescan the entire board … maintain counters, check in O(1)" is the actual differentiator — a naive O(N²) rescan answer is a fail even though it "works"; and "reject invalid moves gracefully" makes validation a first-class responsibility rather than an afterthought. The follow-ups (pluggable win rule, more players, undo) don't need to be built yet, but they tell you where to leave seams.

Nouns Become Classes

Read the prose again and circle the nouns: game, board, cell, player, mark, move, win, draw. Group them by responsibility rather than by vocabulary, and four classes fall out. Player holds an id, name, and mark — pure identity. Cell holds whichever mark sits in one square, the smallest unit of board state. Board owns the grid and the O(1) win-counters — it knows geometry and win-math and nothing about turns. Game owns players, turn order, and status — it orchestrates rules and validates moves, but never touches the grid directly. The split matters because each class now changes for exactly one reason: Board changes if win-detection logic changes, Game changes if turn rules change, and the two never step on each other.

Lock the Public Interface Before Any Internals

The problem statement already hands you the shape of the contract in the "Expected Public Interface" block above. Pin it down before writing any internals — it forces a decision about what the outside world sees and keeps the rest of the design honest. Two decisions are already baked into that interface: an invalid move throws (std::invalid_argument or similar) rather than silently corrupting state or crashing, and getWinner() returns a pointer so "no winner yet" is naturally nullptr rather than a sentinel value. Once the interface is locked, everything behind it is free to change.

Build the Leaves First: Player and Cell

Start with the types that have no dependencies on anything else. A mark is naturally a small enum, and "empty" is a real state that belongs in that enum rather than being modeled as a magic value. Player is a plain bundle of id, name, and mark. Cell is almost trivial — for a 3×3 board you could arguably skip the class entirely — but keeping it makes "what's in a square" explicit and gives a home for future per-cell data such as who played a move and when. Building bottom-up like this means the leaf types are already solid by the time you write the layer that depends on them.

The Key Insight: O(1) Win Detection via Signed Running Sums

This is the heart of the problem, and it's worth spending real thought on. The naive instinct after any move is to rescan the move's row, its column, and the two diagonals for four-in-a-row-of-the-same-mark — that's O(N) per move, and while it's correct, the statement explicitly asks for better, and producing it unprompted is exactly what separates a strong answer from an average one.

The trick: a player wins a line the instant all N cells in that line hold the same mark. Instead of recounting a line every time, keep a running signed tally per line. Map each mark to a delta — X → +1, O → −1 — and maintain rowSum[N], colSum[N], plus two scalars diagSum and antiDiagSum. On a move at (r, c) by a player whose delta is d, update at most four tallies:

rowSum_[r] += d;
colSum_[c] += d;
if (r == c)             diagSum_     += d;  // main diagonal
if (r + c == size_ - 1) antiDiagSum_ += d;  // anti-diagonal

return rowSum_[r] == target
    || colSum_[c] == target
    || (r == c             && diagSum_     == target)
    || (r + c == size_ - 1 && antiDiagSum_ == target);

where target is +size_ for X or -size_ for O. A line of N identical X's sums to exactly +N; N identical O's sums to exactly −N; any mixed line can never reach ±N. Each move touches at most four lines, and each update-and-check is constant time — O(1) per move, full stop, regardless of how large the board grows.

Orchestrate with Game: Validate, Mutate, Transition

Game::makeMove is the rule engine, and it must, in strict order: reject if the game is already over, reject if it isn't this player's turn, reject an out-of-bounds or already-occupied cell, only then delegate the placement to Board, and finally update status — win if Board reports one, else draw if the board is now full, else advance to the next player. Doing every check before mutating any state is what makes "no silent corruption" true rather than aspirational. Two details are worth calling out explicitly in an interview: the round-robin turn advance (turnIdx_ = (turnIdx_ + 1) % players_.size()) already generalizes to N players without hardcoding "2" anywhere, and status transitions live in exactly one place, so nothing outside Game can ever set WIN or DRAW and let the state drift.

Prove It, Then Name the Follow-Up Seams

A short main() that exercises a win and a rejected move afterward is worth more than a paragraph of explanation, and it doubles as your test. Once that's on the board, close by pointing at the seams rather than building them out fully: more players is a data-structure swap inside Board (per-player count arrays, described above) with the turn logic already generalized; a pluggable win rule is a WinningStrategy interface that Game depends on instead of a hardcoded ±N check, turning the current logic into one concrete FullLineStrategy among others (Connect-Four's K-in-a-row becomes a second); and undo/replay falls out almost for free because the counters are reversible — push each move onto a history list, and undo pops it, clears the cell, and subtracts the same deltas that were added. Ending on the pattern name you'd reach for is what proves the abstractions weren't accidental.

1.3Whole Solution

The complete, self-contained, compilable file — entities, the O(1) win-check, the rule engine, and a driver main() that plays out a win and then a rejected move.

#include <iostream>
#include <vector>
#include <string>
#include <stdexcept>

using namespace std;

enum class Mark { EMPTY, X, O };
enum class GameStatus { IN_PROGRESS, WIN, DRAW };

struct Player {
    int id;
    string name;
    Mark mark;
};

struct Cell {
    Mark mark = Mark::EMPTY;
    bool isEmpty() const { return mark == Mark::EMPTY; }
};

class Board {
public:
    Board(int n) {
        size_        = n;
        filled_      = 0;
        diagSum_     = 0;
        antiDiagSum_ = 0;
        grid_.assign(n, vector<Cell>(n));  // n x n empty grid
        rowSum_.assign(n, 0);                    // one running tally per row
        colSum_.assign(n, 0);                    // one running tally per column
    }

    int  size() const { return size_; }
    bool inBounds(int r, int c) const {
        return r >= 0 && r < size_ && c >= 0 && c < size_;
    }
    bool isEmpty(int r, int c) const { return grid_[r][c].isEmpty(); }
    bool isFull()  const { return filled_ == size_ * size_; }

    // Place mark, return true if THIS move completed a line. O(1).
    bool place(int r, int c, Mark mark) {
        grid_[r][c].mark = mark;
        ++filled_;

        int d      = (mark == Mark::X) ?  1     : -1;      // signed delta
        int target = (mark == Mark::X) ?  size_ : -size_;  // full line value

        rowSum_[r] += d;
        colSum_[c] += d;
        if (r == c)             diagSum_     += d;  // main diagonal
        if (r + c == size_ - 1) antiDiagSum_ += d;  // anti-diagonal

        return rowSum_[r] == target
            || colSum_[c] == target
            || (r == c             && diagSum_     == target)
            || (r + c == size_ - 1 && antiDiagSum_ == target);
    }

private:
    int size_;
    vector<vector<Cell>> grid_;
    vector<int> rowSum_, colSum_;
    int diagSum_, antiDiagSum_;
    int filled_;
};

// ---------------------------------------------------------------------------
// Game: rule engine. validate -> mutate -> transition.
// ---------------------------------------------------------------------------
class Game {
public:
    // board_(boardSize) stays in the init list: Board has no default ctor.
    Game(int boardSize, vector<Player> players) : board_(boardSize) {
        if (players.size() < 2)
            throw invalid_argument("need at least 2 players");
        players_ = players;
        turnIdx_ = 0;
        status_  = GameStatus::IN_PROGRESS;
        winner_  = nullptr;
    }

    void makeMove(int playerId, int row, int col) {
        if (status_ != GameStatus::IN_PROGRESS)
            throw logic_error("game is already over");

        Player& current = players_[turnIdx_];
        if (current.id != playerId)
            throw invalid_argument("not this player's turn");
        if (!board_.inBounds(row, col))
            throw invalid_argument("move out of bounds");
        if (!board_.isEmpty(row, col))
            throw invalid_argument("cell already occupied");

        bool won = board_.place(row, col, current.mark);

        if (won) {
            status_ = GameStatus::WIN;
            winner_ = &current;
        } else if (board_.isFull()) {
            status_ = GameStatus::DRAW;
        } else {
            turnIdx_ = (turnIdx_ + 1) % players_.size();  // round-robin
        }
    }

    GameStatus    getStatus() const { return status_; }
    const Player* getWinner() const { return winner_; }

private:
    Board board_;
    vector<Player> players_;
    int turnIdx_;
    GameStatus status_;
    Player* winner_;
};

// ---------------------------------------------------------------------------
// Driver: happy path (win) + an illegal move.
// ---------------------------------------------------------------------------
int main() {
    vector<Player> players = {
        {1, "Alice", Mark::X},
        {2, "Bob",   Mark::O},
    };
    Game game(3, players);

    // X takes the top row -> X wins.
    game.makeMove(1, 0, 0);
    game.makeMove(2, 1, 0);
    game.makeMove(1, 0, 1);
    game.makeMove(2, 1, 1);
    game.makeMove(1, 0, 2);   // top row complete

    if (game.getStatus() == GameStatus::WIN)
        cout << "Winner: " << game.getWinner()->name << "\n";  // Alice

    // Game over -> next move is rejected, not crashed.
    try {
        game.makeMove(2, 2, 2);
    } catch (const exception& e) {
        cout << "Rejected: " << e.what() << "\n";  // game is already over
    }
    return 0;
}