Google·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Google SWE interview with a game simulation problem. The problem itself was pretty well-defined but the state space and move logic had enough edge cases to keep things interesting for a while.

Questions Asked (1)

Implement a two-player game called Babylon. There are 12 tiles in 4 colors (3 of each), each starting as a stack of height 1. On each turn, a player merges two stacks, which is only legal if the stacks share the same height or the same top color. The merged stack's height is the sum of both, and the top color is whichever stack was placed on top. The player who makes the last legal move wins. Given the initial arrangement of tiles, simulate or analyze the game.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

I spent probably the first five minutes just re-reading the rules because the win condition tripped me up.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify the rules and constraints, especially the initial arrangement and what 'analyze' entails. Then, model the game as a combinatorial game and discuss algorithmic approaches to determine the winner, considering state space and optimal play. Finally, propose a solution with complexity analysis and potential optimizations.

Pro tip: Demonstrate strong problem-solving by breaking down the game into states and transitions, and mention memoization or dynamic programming to handle overlapping subproblems. Also, discuss the trade-offs between exhaustive search and heuristic evaluation if the state space is large.

1. Clarify the problem

Ask clarifying questions about the initial arrangement (e.g., are tiles randomly placed or given?), the definition of 'analyze' (e.g., determine winner for a given state, or find winning strategy?), and constraints (e.g., time limits, input size).

2. Model the game

Represent the game state as a multiset of stacks, each with a height and top color. Define legal moves (merge two stacks if same height or same top color) and the resulting state (new height = sum, new top color = top of the stack placed on top).

3. Analyze game properties

Determine if the game is impartial (both players have same moves) and normal play (last move wins). Consider if there are invariants (e.g., total number of stacks decreases by 1 each move) and the maximum number of moves (11).

4. Design an algorithm

Propose an algorithm to determine the winner from a given initial state. Options: minimax with memoization (state space may be large but manageable for 12 tiles), or dynamic programming over subsets. Discuss complexity and potential pruning.

5. Discuss trade-offs and optimizations

Compare approaches: exhaustive search vs. heuristic evaluation if state space is too large. Mention symmetry reduction, alpha-beta pruning, or bitmask representations. Also, consider if the game can be solved analytically for certain initial arrangements.

Key Points to Mention

Game state representation: stacks as (height, top color) pairs, and the multiset of stacks.
Legal move condition: same height or same top color.
State space size: number of ways to partition 12 tiles into stacks, considering colors and heights.
Minimax algorithm with memoization to avoid recomputing states.
Complexity analysis: worst-case number of states and transitions, and potential for pruning.
Symmetry and invariants: e.g., total height sum is constant, number of stacks decreases by 1 each move.

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