Case Study: Design Tic Tac Toe

1. Requirement Clarification

Mental Model

Connecting isolated components into a resilient, scalable, and observable distributed web.

graph TD
    App[Application Server] -->|Read Request| Cache[(Redis Cache)]
    Cache -- Cache Miss --> DB[(Primary Database)]
    DB -- Return Data --> App
    App -- Write Data --> Cache

Designing Tic Tac Toe is a deceptive Machine Coding problem. The naive solution is easy, but making it scale to an $N \times N$ board with $O(1)$ win checking separates the juniors from the seniors.

Functional Requirements

• Two players take turns placing their markers ('X' and 'O') on an empty cell.
• The game can be played on an $N \times N$ grid (not just 3x3).
• The game announces a winner when a player has $N$ markers in a row, column, or diagonal.
• The game ends in a draw if the board is full and no one has won.

2. Core Entities (Class Identification)

• Board: Manages the grid and empty cells.
• Player: Represents the user and their assigned symbol.
• Game: The orchestrator handling turns and win verification.

3. The O(1) Win Check Optimization

The naive way to check for a win is to scan the entire row, column, and diagonals after every move. This takes $O(N)$ time per move.

The "Staff" Solution: We can do this in $O(1)$ by keeping running totals! Assign Player 1 a value of +1 and Player 2 a value of -1. We maintain arrays for the sums of each row and column, and two integers for the diagonals. If any row sum reaches +N (Player 1 wins) or -N (Player 2 wins), the game is over.

4. Class Design (Java)

public class TicTacToe {
    private int[] rows;
    private int[] cols;
    private int diagonal;
    private int antiDiagonal;
    private int n;

    public TicTacToe(int n) {
        this.n = n;
        this.rows = new int[n];
        this.cols = new int[n];
        this.diagonal = 0;
        this.antiDiagonal = 0;
    }

    /** 
     * Player {player} makes a move at ({row}, {col}).
     * @param player The player, can be either 1 or 2.
     * @return The current winning condition, can be either:
     *         0: No one wins.
     *         1: Player 1 wins.
     *         2: Player 2 wins.
     */
    public int move(int row, int col, int player) {
        int value = (player == 1) ? 1 : -1;

        // Update counts
        rows[row] += value;
        cols[col] += value;
        
        if (row == col) {
            diagonal += value;
        }
        if (col == (n - row - 1)) {
            antiDiagonal += value;
        }

        // Check win condition in O(1)
        if (Math.abs(rows[row]) == n || 
            Math.abs(cols[col]) == n || 
            Math.abs(diagonal) == n || 
            Math.abs(antiDiagonal) == n) {
            return player;
        }

        return 0; // No winner yet
    }
}

5. Verbal Interview Script (Staff Tier)

Interviewer: "How would you extend this to a multiplayer environment where clients connect over the internet?"

You: "To move this from a local CLI game to a distributed system, I would introduce an API Gateway managing WebSocket connections for real-time bidirectional communication. The core TicTacToe class would live on a backend game server. Because the game state must be consistent across both clients, I would use an Event-Driven architecture. When Player 1 clicks a cell, the frontend sends a MoveEvent over the socket. The server validates the move using the $O(1)$ counting logic, updates the state in a fast in-memory cache like Redis, and then broadcasts an UpdateBoardEvent to both Player 1 and Player 2. If the server crashes, the game state can be recovered seamlessly from Redis."

Advanced Architectural Blueprint: The Staff Perspective

In modern high-scale engineering, the primary differentiator between a Senior and a Staff Engineer is the ability to see beyond the local code and understand the Global System Impact. This section provides the exhaustive architectural context required to operate this component at a "MANG" (Meta, Amazon, Netflix, Google) scale.

1. High-Availability and Disaster Recovery (DR)

Every component in a production system must be designed for failure. If this component resides in a single availability zone, it is a liability.

• Multi-Region Active-Active: To achieve "Five Nines" (99.999%) availability, we replicate state across geographical regions using asynchronous replication or global consensus (Paxos/Raft).
• Chaos Engineering: We regularly inject "latency spikes" and "node kills" using tools like Chaos Mesh to ensure the system gracefully degrades without a total outage.

2. The Data Integrity Pillar (Consistency Models)

When managing state, we must choose our position on the CAP theorem spectrum.

3. Observability and "Day 2" Operations

Writing the code is only 10% of the lifecycle. The remaining 90% is spent monitoring and maintaining it.

• Tracing (OpenTelemetry): We use distributed tracing to map the request flow. This is critical when a P99 latency spike occurs in a mesh of 100+ microservices.
• Structured Logging: We avoid unstructured text. Every log line is a JSON object containing correlationId, tenantId, and latencyMs.
• Custom Metrics: We export business-level metrics (e.g., "Orders processed per second") to Prometheus to set up intelligent alerting with PagerDuty.

4. Production Readiness Checklist for Staff Engineers

• Capacity Planning: Have we performed load testing to find the "Breaking Point" of the service?
• Security Hardening: Is all communication encrypted using mTLS (Mutual TLS)?
• Backpressure Propagation: Does the service correctly return HTTP 429 or 503 when its internal thread pools are saturated?
• Idempotency: Can the same request be retried 10 times without side effects? (Critical for Payment systems).

Critical Interview Reflection

When an interviewer asks "How would you improve this?", they are looking for your ability to identify Bottlenecks. Focus on the network I/O, the database locking strategy, or the memory allocation patterns of the JVM. Explain the trade-offs between "Throughput" and "Latency." A Staff Engineer knows that you can never have both at their theoretical maximums.

Optimization Summary:

1. Reduce Context Switching: Use non-blocking I/O (Netty/Project Loom).
2. Minimize GC Pressure: Prefer primitive specialized collections over standard Generics.
3. Data Sharding: Use Consistent Hashing to avoid "Hot Shards."

Technical Trade-offs: Database Choice

Key Takeaways

• Two players take turns placing their markers ('X' and 'O') on an empty cell.
• The game can be played on an $N \times N$ grid (not just 3x3).
• The game announces a winner when a player has $N$ markers in a row, column, or diagonal.

Read Next

• Case Study: Design a Vending Machine