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

IntermediatePrefer not to say

Jun 2026

Summary

Google SWE coding round with a board game simulation problem. Not the hardest thing I've seen from them but the edge cases definitely got me thinking.

Questions Asked (1)

You have a 1D board of length N where each cell is empty, holds a movable piece, or holds a collectible coin. A piece can move exactly 3 cells to the right: it lands if the destination is empty or has a coin (which gets collected), but can't land on another piece or go out of bounds. You can move any piece any number of times in any order until no moves remain. Return the maximum number of coins you can collect.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

Took me a while to even figure out what kind of problem this was.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the board as a graph where each cell is a node and edges represent legal moves (i+3) if the destination is not a piece. Then, for each connected component, determine the maximum coins collectible by analyzing the sequence of pieces and coins, using dynamic programming or greedy reasoning. Finally, sum the results across components.

Pro tip: Clarify that pieces are indistinguishable and moves are reversible in terms of reachability, so the problem reduces to finding the maximum coins in each independent chain. Emphasize that you can move pieces in any order, so you can plan moves to avoid blocking.

1. Understand the problem and constraints

Restate the rules: pieces move exactly +3, can land on empty or coin, cannot land on piece or out of bounds. Coins are collected and removed. Pieces can move any number of times in any order.

2. Model as a graph or chains

Observe that moves only go from i to i+3, so cells split into 3 independent chains based on index mod 3. Within each chain, pieces and coins are arranged in a sequence.

3. Analyze a single chain

For a chain, determine the maximum coins collectible. Consider the positions of pieces and coins. Since pieces can move rightward, a piece can collect coins to its right until blocked by another piece. The optimal strategy is to move pieces from right to left to avoid blocking.

4. Derive a greedy or DP solution

For each chain, scan from right to left. Maintain the number of pieces seen so far. When encountering a coin, if there is at least one piece to its right that can reach it, collect it. Use a counter or DP to compute maximum coins.

5. Combine results and discuss complexity

Sum the maximum coins from all three chains. The algorithm runs in O(N) time and O(1) extra space. Discuss potential edge cases and trade-offs.

Key Points to Mention

Decomposition into 3 independent chains based on index modulo 3.
Within a chain, pieces can only move right, so coins to the left of all pieces are unreachable.
Greedy strategy: process from right to left, keep track of available pieces, and collect coins when possible.
Proof of optimality: moving pieces from right to left ensures no coin is blocked unnecessarily.
Time and space complexity: O(N) time, O(1) space.
Edge cases: no pieces, no coins, pieces blocking each other, coins at the end.

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