Google·Software Engineer·Onsite - System Design / Architecture·Senior

SeniorPrefer not to say

May 2026

Summary

Google SWE design round, got hit with a generalized Tic-Tac-Toe problem that sounds easy until you realize n can be huge and they care about your complexity story. Came out feeling okay but not great.

Questions Asked (1)

Design a Tic-Tac-Toe system that supports k players on an n×n board where the win condition is 3 consecutive marks in any direction (horizontal, vertical, main diagonal, anti-diagonal). Each move should return whether the current player won, the game is still going, or the board is full with no winner.

System DesignAlgorithms & Data StructuresTechnical Trade-offs

Author's notes

My first instinct was to store the whole board and scan after every move, which they immediately pushed back on since n can be arbitrarily large.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and constraints, then design a data structure that efficiently tracks moves and checks for wins. Focus on the win condition of 3 consecutive marks and how to generalize to k players and n×n board, discussing time/space trade-offs and edge cases.

Pro tip: Emphasize that you can optimize win checking by only examining lines through the last move, reducing complexity from O(n^2) to O(1) per move. Also, mention that the board can be represented as a 2D array with player IDs, and win detection can be done by checking four directions from the last move.

1. Clarify Requirements

Ask about constraints: board size n, number of players k, win condition (exactly 3 or at least 3?), and whether moves are guaranteed valid. Confirm return values: win, ongoing, draw.

2. Design Data Structures

Propose a 2D array (n×n) to store player IDs (0 for empty). Optionally, maintain counts of moves per player or per line for optimization.

3. Implement Move and Win Check

For each move, place the mark, then check only the four lines (horizontal, vertical, two diagonals) passing through the placed cell for 3 consecutive marks of the same player. Return the appropriate status.

4. Handle Edge Cases and Optimizations

Consider board full detection (maintain a move counter), invalid moves, and potential optimizations like early termination or incremental win checks.

5. Discuss Trade-offs and Scalability

Compare time/space complexity of naive vs optimized approaches. Discuss how the solution scales with n and k, and potential concurrency issues if multiple players move simultaneously.

Key Points to Mention

Time complexity: O(1) per move if checking only lines through the last move, vs O(n^2) if scanning entire board.
Space complexity: O(n^2) for the board, which is optimal for storing the game state.
Win condition: exactly 3 consecutive marks, not more, so need to check for runs of length 3.
Handling k players: board stores player IDs, and win check compares against the current player's ID.
Board full detection: maintain a move counter to avoid scanning the board each time.
Edge cases: n < 3 (no possible win), k > n^2 (impossible to fill board), and invalid moves.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.