What is Interview Forge?

Interview Forge helps you practice mock interviews, follow study plans, track career goals, review learning analytics, and prepare across 36 pages.

Coin Change at Google — Interview Guide

How to approach Coin Change in a Google interview: the optimal approach, what Google interviewers look for, and company-specific tips.

Updated 2026-09MediumDynamic Programming

The problem at Google

Given coin denominations and an amount, return the fewest number of coins needed to make that amount, or -1 if it is impossible.

Google uses this problem to assess algorithmic rigor and generalist problem-solving. Expect Google-specific follow-ups that tie the solution back to production reasoning and the company's engineering bar.

Key concepts

dp[a] = minimum coins to make amount a.
dp[a] = 1 + min(dp[a - coin]) over all coins ≤ a.
Greedy (always take the largest coin) fails on some denominations — interviewers love this counter-example.

Approach

def coin_change(coins, amount):
    dp = [0] + [float('inf')] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], 1 + dp[a - c])
    return dp[amount] if dp[amount] != float('inf') else -1

Complexity

Metric	Value
Time	O(amount × coins)
Space	O(amount)

Unlock the full guide

Premium members get every DSA, system design, company and role interview guide — plus AI practice, mock interviews, and analytics.

Unlock with Premium