Minimum coins to make a target amount
Reported in Supercell European engineering loops. Dynamic programming optimization with unbounded choices.
Interview scenario
Context for Supercell candidates:
Given coin denominations and amount, return the minimum coins needed or -1 if impossible.
Model answer
Try answering aloud first
Cover trade-offs, structure, and a concrete example before revealing the baseline response.
How to frame this at Supercell: Connect your answer to measurable impact, clarity of thought, and trade-offs the team cares about. Below is a strong baseline response you can adapt with your own project examples.
Use bottom-up DP where dp[a] is the minimum coins needed for amount a. Initialize dp[0] = 0 and others as infinity, then relax using each coin.
Transition is dp[a] = min(dp[a], dp[a - coin] + 1) when a - coin >= 0. Final answer is dp[amount] unless it remains infinity.
This approach is O(amount * number_of_coins). Mention why greedy fails for arbitrary denominations like [1,3,4] with amount 6.
Discussion
Comments (0)
Share how this question came up in your loop, or add tips for others preparing.
Log in to comment on this question.