Google·Software Engineer·Technical Phone Screen·Senior

Senior

May 2026

Summary

Google SWE interview with a surprisingly tricky combinatorial game theory problem dressed up as a tile-stacking puzzle. The problem had a lot of moving parts and figuring out what even constitutes a valid state took a while.

Questions Asked (1)

You have 12 stacks of tiles, each starting at height 1 with one of 4 colors (3 tiles per color). Two players alternate turns, and each turn a player must merge one full stack onto another. A merge is legal if the two stacks share the same height or the same top color. The merged stack's height is the sum of both, and the top color comes from whichever stack was placed on top. The player who can't move loses. Implement the game, determine the winner from a starting configuration, or build the move logic.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The rules sound manageable until you start implementing and realize the state space is genuinely large.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the game as a state-space search with memoization, using bitmasks or tuples to represent stacks and their top colors. Implement legal move generation and minimax with alpha-beta pruning to determine the winner. Discuss trade-offs between exhaustive search and heuristic evaluation for larger configurations.

Pro tip: Emphasize that the game is impartial and finite, so Sprague-Grundy theory could apply if the game decomposes, but here the merge mechanic couples stacks, making direct minimax with memoization more practical. Mention that memoization is crucial to avoid exponential blowup.

1. Clarify rules and constraints

Confirm the initial setup: 12 stacks, each height 1, 3 tiles per color (so 4 colors total). Ensure understanding of legal merges: same height or same top color, and that the merged stack's top color is from the stack placed on top.

2. Design state representation

Represent each stack as a tuple (height, top_color) and the game state as a sorted tuple of such stacks to canonicalize. Use this for memoization and to detect terminal states (no legal moves).

3. Implement move generation

For each pair of stacks, check if they share height or top color. Generate all legal merged stacks, considering both orders (which stack goes on top) to capture different resulting top colors.

4. Implement minimax with memoization

Use recursive minimax: a state is winning if any move leads to a losing state for the opponent. Memoize results to avoid recomputation. Optionally add alpha-beta pruning if branching factor is high.

5. Analyze complexity and optimize

Discuss state space size and potential optimizations like symmetry reduction, bitmask encoding, or iterative deepening. Consider if the game can be decomposed into independent subgames for Sprague-Grundy.

Key Points to Mention

State representation and canonicalization to reduce memoization overhead
Legal move generation considering both merge orders
Minimax algorithm with memoization (and alpha-beta pruning)
Terminal state detection: no legal moves means current player loses
Complexity analysis: state space size, branching factor, and memoization benefits
Potential application of Sprague-Grundy theory if game decomposes (but note coupling)

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