Google·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

May 2026

Summary

Google SWE coding round with a tricky dynamic programming problem that flips the usual coin change problem on its head. Interesting question, not your typical leetcode grind.

Questions Asked (1)

Given a dp array where dp[i] represents the number of ways to make amount i using some set of coin denominations, reverse-engineer the original coins array. Assume the solution is unique. For example, given dp = [1, 1, 2, 2, 3, 4, 4, 5], recover the coins that produced it.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

This one took me a minute to even understand what they were asking.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, identify the smallest denomination by finding the first index i>0 where dp[i] > 0; that coin must be i. Then, iteratively subtract the contribution of that coin from the dp array to reveal the next smallest coin, repeating until all coins are found. Verify the recovered coins by reconstructing the dp array to ensure uniqueness.

Pro tip: Emphasize that the greedy extraction works because the smallest coin must be the first non-zero dp index, and after removing its effect, the next smallest coin becomes the new first non-zero index. This demonstrates understanding of the DP recurrence and uniqueness assumption.

1. Identify the smallest coin

Scan the dp array from index 1 upward to find the first index i where dp[i] > 0. That index i is the smallest coin denomination.

2. Remove the coin's contribution

For each amount j from i to the maximum amount, subtract dp[j - i] from dp[j] to eliminate the ways that use the coin i. This effectively removes coin i from the set.

3. Repeat until no more coins

After removal, scan again from the next index to find the new first non-zero dp entry, which gives the next smallest coin. Repeat steps 1-2 until all dp entries become zero (except dp[0]=1).

4. Verify the result

Reconstruct the dp array using the recovered coins and compare with the original to ensure correctness. Also check that the solution is unique as assumed.

Key Points to Mention

Dynamic programming for coin change: dp[i] = sum over coins c of dp[i-c].
The smallest coin must be the first index >0 with dp[i] > 0.
Removing a coin's contribution: for j from coin to max, dp[j] -= dp[j - coin].
Uniqueness assumption ensures no ambiguity in coin recovery.
Time complexity: O(n * m) where n is max amount and m is number of coins.
Edge cases: dp[0] = 1 always; if no coins, dp remains [1,0,...].

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