How does the cash dispensing algorithm work in your ATM design?

Direct Answer

The CashDispenser uses a greedy algorithm: it maintains a sorted map of denomination to count (e.g., 100→50 bills, 50→100 bills). For a withdrawal amount, iterate denominations from largest to smallest. For each denomination, dispense min(requestedAmount / denomination, availableCount) bills, subtract from both amount and inventory, repeat until amount reaches zero or no bills remain.

Deep Dive & Architecture

Validate before changing inventory

The dispenser receives an amount and a snapshot of available notes. It first rejects invalid amounts, then builds a note plan without changing the real inventory. A plan is valid only when the note counts do not exceed stock and their total equals the requested amount. Inventory is reduced only after the plan and the bank authorization both succeed.

Largest-first is a useful candidate, not a universal solver

A largest-first pass is fast and often gives a small number of notes, but limited inventory can make it miss a valid combination. Suppose the machine has one 50 note, three 20 notes, and no 10 notes. For 60, greedy takes 50 and fails, while three 20 notes work. A production design can use bounded backtracking or dynamic programming, or use a bank-approved dispensing policy whose note set and stock rules guarantee the simple algorithm.

Plan and commit form one protected operation

Two withdrawals must not reserve the same notes. In one process, the dispenser can lock around validation and commit. With shared or remote inventory, the final update needs a transaction or compare-and-set at the storage boundary. If physical dispensing fails after the bank debit, the workflow records the failure and starts the bank's reversal or reconciliation process rather than pretending the withdrawal completed.

Code Example

class CashDispenser {
    // largest denomination first
    private final TreeMap<Integer,Integer> inventory = new TreeMap<>(Comparator.reverseOrder());

    // returns the bills to hand out, or empty if the amount can't be made
    Optional<Map<Integer,Integer>> dispense(int amount) {
        Map<Integer,Integer> plan = new LinkedHashMap<>();
        int remaining = amount;
        for (var e : inventory.entrySet()) {
            int note = e.getKey(), available = e.getValue();
            int need = Math.min(remaining / note, available);  // greedy take
            if (need > 0) { plan.put(note, need); remaining -= need * note; }
        }
        if (remaining != 0) return Optional.empty();            // cannot make exact amount
        plan.forEach((note, cnt) -> inventory.merge(note, -cnt, Integer::sum)); // commit
        return Optional.of(plan);
    }
}

This is a fast candidate builder, not a complete combination search. Use it only with a validated note policy or add a bounded-search fallback before committing inventory.

Common Mistakes & Pitfalls

• Dispensing before checking feasibility — decrement inventory as you go, then discover you can't finish, leaving inventory corrupted. Build a plan, validate, then commit.
• Ignoring inventory limits — amount / note without min(..., available) over-dispenses notes you don't have.
• Assuming greedy always works — limited stock can defeat it even with familiar note values. Use a bounded search when finding any feasible combination is required.
• Not handling the impossible amount — return empty / reject, don't hand out the wrong total.