Coin Change
Prompt
A vending backend has to dispense change using a fixed set of coin denominations, and we want to hand out the fewest coins possible. Given the denominations and a target amount, find the minimum number of coins that sum to it.
How this round runs
I haven't said whether the coin set is the usual one or arbitrary, or what to do when the amount can't be made — clarify before coding, and expect me to twist the question once you have the minimum working.
Model answer
Clarify first: is the coin set arbitrary, or guaranteed to be a "canonical"
system like US coins? Is each denomination available in unlimited quantity? What
do we return when the amount is unreachable — -1, an exception?
Tempting first move is greedy — always take the largest coin that fits. It's
fast, but it's wrong for arbitrary sets: with coins [1, 3, 4] and amount 6,
greedy takes 4 + 1 + 1 = 3 coins, but 3 + 3 = 2 is better. So I'll name
greedy, show why it fails, and switch to DP.
Build dp[a] = the fewest coins to make amount a. Base case dp[0] = 0; every
other entry starts at infinity. For each amount, try every coin and take the best
sub-result plus one. O(amount * numCoins) time, O(amount) space.
function coinChange(coins, amount) {
const dp = new Array(amount + 1).fill(Infinity);
dp[0] = 0;
for (let a = 1; a <= amount; a++) {
for (const coin of coins) {
if (coin <= a && dp[a - coin] + 1 < dp[a]) {
dp[a] = dp[a - coin] + 1;
}
}
}
return dp[amount] === Infinity ? -1 : dp[amount];
}
Dry-run on [1, 2, 5], amount 5: dp goes 0, 1, 1, 2, 2, 1 — dp[5] = 1 (a
single 5-coin).
- Asked whether the coin set is arbitrary and what to return when unreachable
- Named greedy, gave a concrete counter-example, then moved to DP
- Defined the dp state and base case clearly (dp[0] = 0, rest infinity)
- Stated O(amount * numCoins) time, O(amount) space, and dry-ran the table
- Count the number of distinct ways to make the amount instead of the minimum → iterate coins on the outer loop and sum, don't minimize
- Reconstruct which coins were used, not just the count → store the chosen coin per amount and walk back from dp[amount]