Google·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

May 2026

Summary

Google SWE interview that centered on a generalized Tic-Tac-Toe design problem. The twist of supporting k players on an n x n board with a fixed 3-in-a-row win condition made it less straightforward than the classic version, and the expectation to discuss complexity before touching code caught me a bit off guard.

Questions Asked (1)

Design a Tic-Tac-Toe system that supports k players on an n x n board, where a player wins by forming exactly 3 consecutive marks in a straight line. After each move, the system should return the current game status.

System DesignAlgorithms & Data StructuresTechnical Trade-offs

Author's notes

My first instinct was to scan the whole board after every move, which they pushed back on pretty quickly.

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 consecutive marks for each player in all directions. Focus on the win condition of exactly 3 consecutive marks, which requires careful handling of boundaries and overlines. Discuss trade-offs between time and space complexity, and consider scalability for large n and k.

Pro tip: Emphasize that 'exactly 3' means you must check both ends of a potential run to ensure it doesn't extend to 4 or more, which is a common pitfall. Also, mention that for k > 2, the game can end in a draw even if no player wins, so you need to track total moves.

1. Clarify Requirements and Constraints

Ask about expected board sizes, number of players, and performance requirements. Confirm that a win requires exactly 3 consecutive marks, not 3 or more.

2. Design Data Structures

Propose maintaining counts of consecutive marks for each player in all 4 directions (horizontal, vertical, two diagonals) for each cell. Alternatively, use a hash map to track runs, but consider memory vs. speed trade-offs.

3. Implement Move and Win Check

For each move, update the counts for the placed mark and check if it forms exactly 3 consecutive marks in any direction. Ensure to check both ends to avoid overlines.

4. Handle Game Status and Edge Cases

Return status: win, draw (board full or no possible winning moves), or ongoing. For k > 2, draw can occur before board is full if no player can win.

5. Analyze Complexity and Optimize

Discuss time complexity per move (O(1) with precomputed counts) and space complexity (O(n^2 * k) for counts). Suggest optimizations like only tracking active runs or using bitwise operations for small n.

Key Points to Mention

Exactly 3 consecutive marks: must check both ends to prevent counting runs of 4 or more.
Data structure: maintain directional counts per player per cell to achieve O(1) move validation.
Draw conditions: board full or no possible winning move for any player (especially for k > 2).
Trade-offs: memory vs. speed; alternative approaches like scanning lines after each move (O(n) per move).
Scalability: handling large n and k; potential use of sparse representations if board is large but moves are few.
Edge cases: moves at boundaries, multiple simultaneous wins (if possible), and invalid moves.

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