The Coin Vault

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
L4
Asked in
Perplexity

Problem

A cash register makes change from a fixed set of coin denominations, always reaching for the largest coin that still fits the amount it has left to give, with unlimited supply of each denomination. Given a target amount and the available coins (in any order), return how many coins the register hands out following that largest-first rule. Return -1 if that rule leaves a remainder it can never land on exactly.

Exact change only - and you want to use as few coins as possible.

Example 1

Input:

amount = 11, coins = [1,5,10]

Output:

2

Example 2

Input:

amount = 8, coins = [1,5,10]

Output:

4

Worked solution and explanation

What this really is

This is the coin-change problem stripped of its safety net: you reach for the largest coin that fits, over and over, and report what that rule spends. The trap is that everyone's reflex is to find the *true* minimum, and that is a different number. On coins [1, 3, 4] for 6, the register hands out 4 + 1 + 1 (three coins) while the optimal mix is 3 + 3 (two). Worse, largest-first can paint itself into a corner: coins [3, 4] for 6 takes the 4, is left with 2, and no coin fits, so an exact combination the greedy rule can't reach must return -1. Candidates who resist the urge to 'improve' the answer with dynamic programming, and who remember to emit -1 when the rule strands a remainder, are the ones who actually understood the ask.

Break down the requirements

Step 1: Order the denominations largest-first

Coins may be unsorted, so sort a copy descending. Sorting once is cheaper and clearer than scanning for the next-largest coin on every step.

Step 2: Peel the largest coin that still fits

For each denomination, integer-divide the remaining amount to take every copy that fits in one shot, then subtract what you spent. Unlimited supply means you never cap the count per coin.

Step 3: Detect the stranded remainder

After the pass, a nonzero remainder means the largest-first rule could not land exactly, so return -1 rather than searching for a rescue combination.

The solution

Greedy coin selection with descending denominations
def make_change_greedy(amount: int, coins: list) -> int:
    remaining = amount
    total_coins = 0
    for coin in sorted(coins, reverse=True):
        if remaining <= 0:
            break
        count = remaining // coin
        total_coins += count
        remaining -= count * coin
    if remaining != 0:
        return -1
    return total_coins

Common follow-up questions