Coding

Coin Change Problem

Asked at

Oracle

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

Stuck? Show a way to structure it+

01Clarify whether every denomination may be reused and whether the goal is minimum coins or number of combinations
02Define dp[a] as the best answer for amount a, with dp[0] = 0 and unreachable amounts set to infinity
03For each amount, relax dp[a] from dp[a - coin] + 1 for every usable coin
04Explain iteration order and return the unreachable sentinel as the required failure value
05Check amount zero, no solution, duplicate denominations, and large amounts

Reference answer

For the standard minimum-coin version, use unbounded dynamic programming. Let dp[a] be the fewest coins needed to make amount a; initialize dp[0] = 0 and every other state to an impossible sentinel larger than any answer. For each amount from 1 through the target, try every coin no larger than the amount and minimize dp[a - coin] + 1. This makes reuse explicit because an earlier amount may already use the same coin. If the final state is still the sentinel, report that no solution exists. Mention that the closely related combinations variant changes the loop order: iterate coins outside amounts to avoid counting permutations. Test target zero, denominations larger than the target, duplicates, and impossible targets. The minimum-coin solution is O(amount × number of coins) time and O(amount) space.

Then expect these follow-ups

What constraint would change your chosen approach?
Tests: constraint adaptation
How would you test the edge cases before implementation?
Tests: implementation extension

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question