Google·Software Engineer·Onsite - Coding / Algorithms·Intermediate

IntermediatePrefer not to say

Jun 2026Munich

Summary

Google SWE onsite in Munich, first NG round. The problem was a two-player tile-stack merge game called Babylon: implement the full game from scratch including legal-move detection and state transitions. Coding it cleanly in 45 minutes was rough and the interviewer had to drop hints to keep things moving.

Questions Asked (1)

Implement a two-player tile-stack merge game from scratch. The board starts with 12 height-1 stacks across 4 colors (3 tiles each). On each turn a player merges two stacks under specific legality constraints: same height OR matching top color. The player with no legal move loses. Build the full game: state representation, legal move enumeration, move execution, and terminal detection.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

This wrecked my pacing.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the rules and constraints, then design a clean state representation and modular functions for legal moves, move execution, and terminal detection. Discuss algorithmic choices (e.g., bitmask vs. object) and trade-offs, and consider game-theoretic aspects like win/loss states and potential optimizations.

Pro tip: Demonstrate foresight by mentioning how your design supports future extensions (e.g., AI opponent, larger boards) and by analyzing time/space complexity of each operation.

1. Clarify requirements and constraints

Ask questions to confirm rules: initial setup, merge legality, turn order, and win condition. Clarify if stacks can be merged in any order or if there are additional constraints.

2. Design state representation

Choose a data structure to represent stacks (e.g., list of stacks, each stack as a list of colors). Consider encoding for efficiency (e.g., bitmask per color) and discuss trade-offs.

3. Implement legal move enumeration

Write a function that iterates over all pairs of stacks and checks legality: same height OR matching top color. Return list of valid moves.

4. Implement move execution and terminal detection

Define a function to apply a move: merge two stacks (order? concatenate tiles) and update state. Terminal detection: if no legal moves for current player, game over.

5. Analyze complexity and discuss optimizations

Analyze time/space complexity of each operation. Discuss potential optimizations (e.g., caching legal moves, using union-find for connected components) and trade-offs.

Key Points to Mention

State representation: list of stacks vs. bitmask encoding, and trade-offs in memory and speed.
Legal move enumeration: O(n^2) naive approach, possible optimizations using grouping by height or top color.
Move execution: merging stacks (concatenation order) and updating state efficiently.
Terminal detection: checking if any legal moves exist; can be integrated with move enumeration.
Game theory: recognizing that the game is finite and acyclic, so win/loss can be determined via recursion or DP.
Complexity analysis: time and space for each operation, and overall game tree size.

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