Coin Change

Python data engineering interview problem. Difficulty: advanced. Pattern: Dynamic Programming. About 18 minutes. Part of the Pro drill bank.

Fewest coins to make amount; -1 if impossible. Treat this as a production helper: match the contracted return shape, including empty and duplicate inputs.

A payment service must make an amount with the fewest available coin values, or say that the amount cannot be made. Return the minimum number of coins needed to make amount. Each coin can be reused. Return -1 when no combination reaches the amount. Write coin_change(coins: list, amount: int) -> int. For coins [1,2,5] and amount 11, 5 + 5 + 1 uses 3 coins. The starter file already contains the function name, harness and print lines. Keep them and fill only the function body.

Requirements

• Allow each coin value to be used repeatedly.
• Minimize the number of coins, not their sum.
• Return -1 when the target is impossible.

Constraints

• Coins and amount are non-negative integers.
• Amount 0 needs 0 coins, and the return type is int.

Examples

Input: coin_change([1, 2, 5], 11) Output: 3 5+5+1.

Topics: lakebench, python, dp, unbounded knapsack.

More Python interview questions · All interview problems · Learn data engineering