← Google Interview Insights

Google·Machine Learning Engineer·Technical Phone Screen·Senior

Senior
May 2026

Summary

Went through a coding round for an MLE role at Google, got a dynamic programming problem that looked like a math puzzle at first glance. Not the most brutal interview I've had but it required more careful thinking than I expected.

Questions Asked (1)

Q1

Given an array of coin denominations and a target amount, return the total number of combinations of coins that sum to that amount. You have unlimited coins of each type. Return 0 if it's not possible.

Algorithms & Data Structures
Author's notes

Classic unbounded knapsack variant but I kept second-guessing whether order mattered (it doesn't, combinations not permutations).

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Recognize this as the classic Coin Change 2 problem and solve it with dynamic programming. Define dp[i] as the number of ways to make amount i, initialize dp[0] = 1, and for each coin, iterate through amounts from coin to target, adding dp[amount - coin] to dp[amount]. This ensures combinations are counted once regardless of order.

Pro tip: Emphasize that iterating coins in the outer loop and amounts in the inner loop prevents counting permutations (e.g., [1,2] and [2,1] as different), which is crucial for combinations. Also, mention that for large targets, space can be optimized to a 1D array, and time complexity is O(n * target).

1. Clarify the problem

Confirm that order does not matter (combinations, not permutations) and that coins can be reused unlimited times. Ask about constraints (e.g., target size, number of denominations) to guide algorithm choice.

2. Define the DP state

Let dp[i] represent the number of ways to make amount i using the given coin denominations. Initialize dp[0] = 1 (one way to make amount 0: use no coins) and all other dp[i] = 0.

3. Determine iteration order

Iterate over each coin in the outer loop, and for each coin, iterate over amounts from coin to target in the inner loop. This order ensures each combination is counted once, avoiding permutations.

4. Apply the recurrence

For each amount i and coin c, update dp[i] += dp[i - c]. This accumulates the number of ways to form amount i by adding coin c to all combinations that sum to i - c.

5. Return the result

After processing all coins, dp[target] holds the total number of combinations. If dp[target] is 0, return 0; otherwise, return dp[target].

Key Points to Mention

  • Dynamic programming with a 1D array for space optimization.
  • Time complexity O(n * target) and space complexity O(target), where n is the number of coin denominations.
  • The importance of loop order: coins outer, amounts inner, to count combinations instead of permutations.
  • Base case: dp[0] = 1, representing the empty combination.
  • Handling edge cases: target = 0 (return 1), empty denominations (return 0 if target > 0), or no combination possible (return 0).
  • Potential follow-up: if asked for minimum coins, that's a different problem (Coin Change 1) with a different DP recurrence.

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