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

IntermediateRejected

Mar 2025

Summary

Google SWE system design round, March R1. Coded up a solution for the Tic-Tac-Toe problem but got rejected. The lesson I took away was that I should've talked through my approach before jumping into code.

Questions Asked (1)

Design a Tic-Tac-Toe system that supports k players on an n x n board. A player wins by placing 3 consecutive marks in a line, regardless of board size. After each move, the system should return the current game status, e.g. which player won or if the game is over.

System DesignAlgorithms & Data StructuresTechnical Trade-offs

Author's notes

I just started coding without really syncing with the interviewer on the approach first.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and constraints, then design a scalable data model and win-checking algorithm. Discuss trade-offs between different approaches and consider extensibility for future features.

Pro tip: Emphasize that the win condition is always 3 consecutive marks, so you can optimize by only checking lines through the last move, reducing time complexity from O(n^2) to O(1) per move.

1. Clarify Requirements and Constraints

Ask about board size limits, number of players, move validation, and expected game status responses. Confirm if players can choose symbols and if the game supports undo or replay.

2. Design Data Model and Game State

Represent the board as a 2D array or hash map, track player positions, and maintain game status. Consider using a move history for undo functionality.

3. Implement Win-Checking Algorithm

After each move, check only lines (horizontal, vertical, diagonal) passing through the placed mark for 3 consecutive same symbols. This ensures O(1) time per move.

4. Handle Game Status and Edge Cases

Return status: ongoing, win (with player), or draw. Handle invalid moves, full board, and multiple winners (if simultaneous, though unlikely with sequential moves).

5. Discuss Scalability and Trade-offs

Compare approaches: full board scan vs. incremental check. Discuss memory vs. time, and how to extend for larger boards or more players.

Key Points to Mention

Time complexity: O(1) per move by checking only lines through the last move.
Space complexity: O(n^2) for board, but can be optimized with sparse representation if board is large and moves are few.
Data structures: 2D array for board, hash map for player positions, or bitboards for efficiency.
Win condition: exactly 3 consecutive marks, not n, so check segments of length 3.
Game status: enum for ongoing, win, draw; include winner ID.
Extensibility: support for undo, replay, AI players, or different win lengths.

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