Design an ATM

package com.androidinterview.atm;

import java.util.Map;
import java.util.UUID;

import com.androidinterview.atm.bank.BankService;
import com.androidinterview.atm.cash.CashDispenser;
import com.androidinterview.atm.model.Card;

// The machine. Its public methods are one liners that hand the operation to
// the current state and store whatever state comes back, so the rules about
// what is legal when live in one place and not in here.
public final class Atm {

    private final BankService bank;
    private final CashDispenser dispenser;
    private AtmState state = new AtmState.Idle();

    public Atm(BankService bank, CashDispenser dispenser) {
        this.bank = bank;
        this.dispenser = dispenser;
    }

    public BankService bank() {
        return bank;
    }

    public AtmState state() {
        return state;
    }

    public void insertCard(Card card) {
        state = state.insertCard(this, card);
    }

    public void enterPin(String pin) {
        state = state.enterPin(this, pin);
    }

    // Withdrawing never changes the state, so this returns the notes that came
    // out rather than a state.
    public Map<Integer, Integer> withdraw(long amount) {
        return state.withdraw(this, amount);
    }

    public long balance() {
        return state.balance(this);
    }

    public void ejectCard() {
        state = state.ejectCard(this);
    }

    // The method the whole problem is about. Three steps, in this order, and
    // the order is the answer.
    //
    // Reserve the notes first, so we never debit an account for cash the
    // machine cannot physically hand over. Debit second, because handing out
    // money we failed to charge for is worse than the reverse. Push last, and
    // if the shutter jams, credit the money straight back. That credit is a
    // compensating transaction, and a real machine also journals every step so
    // a disputed withdrawal can be settled the next morning.
    //
    // Package private on purpose. Only a state can call it, so there is no way
    // to move money without going through the state machine.
    Map<Integer, Integer> withdrawFrom(Card card, long amount) {
        Map<Integer, Integer> notes = dispenser.reserve(amount);
        if (notes == null) {
            throw new IllegalStateException("cannot make " + amount + " from the notes left");
        }
        // One id per withdrawal. If the network drops after the bank applied
        // the debit and before we heard back, the retry carries the same id
        // and the bank ignores it.
        String requestId = UUID.randomUUID().toString();
        if (!bank.debit(card.accountNumber(), amount, requestId)) {
            dispenser.putBack(notes);
            throw new IllegalStateException("insufficient funds");
        }
        try {
            dispenser.push(notes);
            return notes;
        } catch (CashDispenser.DispenserException jam) {
            // The notes are physically in the shutter or the reject bin, not
            // back in the cassettes, so they are journalled as rejected rather
            // than added back to the counts.
            bank.credit(card.accountNumber(), amount);
            dispenser.reject(notes);
            throw jam;
        }
    }
}

package com.androidinterview.atm;

import java.util.Map;
import java.util.UUID;

import com.androidinterview.atm.bank.BankService;
import com.androidinterview.atm.cash.CashDispenser;
import com.androidinterview.atm.model.Card;

public final class Atm {

    private final BankService bank;
    private final CashDispenser dispenser;
    private AtmState state = new AtmState.Idle();

    public Atm(BankService bank, CashDispenser dispenser) {
        this.bank = bank;
        this.dispenser = dispenser;
    }

    public BankService bank() {
        return bank;
    }

    public AtmState state() {
        return state;
    }

    public void insertCard(Card card) {
        state = state.insertCard(this, card);
    }

    public void enterPin(String pin) {
        state = state.enterPin(this, pin);
    }

    public Map<Integer, Integer> withdraw(long amount) {
        return state.withdraw(this, amount);
    }

    public long balance() {
        return state.balance(this);
    }

    public void ejectCard() {
        state = state.ejectCard(this);
    }

    Map<Integer, Integer> withdrawFrom(Card card, long amount) {
        Map<Integer, Integer> notes = dispenser.reserve(amount);
        if (notes == null) {
            throw new IllegalStateException("cannot make " + amount + " from the notes left");
        }
        String requestId = UUID.randomUUID().toString();
        if (!bank.debit(card.accountNumber(), amount, requestId)) {
            dispenser.putBack(notes);
            throw new IllegalStateException("insufficient funds");
        }
        try {
            dispenser.push(notes);
            return notes;
        } catch (CashDispenser.DispenserException jam) {
            bank.credit(card.accountNumber(), amount);
            dispenser.reject(notes);
            throw jam;
        }
    }
}

package com.androidinterview.atm;

import java.util.Map;

import com.androidinterview.atm.model.Card;

// The lifecycle of the machine, as data. Every operation that moves the machine
// returns the state it is in afterwards, so a transition is a return value and
// never a hidden field write.
//
// The default methods reject. A concrete state overrides only the operations it
// actually allows, which is why there is no if ladder anywhere in the ATM.
public sealed interface AtmState {

    default AtmState insertCard(Atm atm, Card card) {
        throw refuse("insert a card");
    }

    default AtmState enterPin(Atm atm, String pin) {
        throw refuse("enter a PIN");
    }

    default Map<Integer, Integer> withdraw(Atm atm, long amount) {
        throw refuse("withdraw");
    }

    default long balance(Atm atm) {
        throw refuse("check a balance");
    }

    default AtmState ejectCard(Atm atm) {
        throw refuse("eject a card");
    }

    private static IllegalStateException refuse(String operation) {
        return new IllegalStateException("you cannot " + operation + " right now");
    }

    // Waiting for a customer. The only thing that can happen is a card going in.
    record Idle() implements AtmState {
        @Override
        public AtmState insertCard(Atm atm, Card card) {
            return new HasCard(card, 0);
        }
    }

    // A card is in and unverified. The failed attempt count lives here rather
    // than on the machine, so it resets by construction when the card comes out.
    record HasCard(Card card, int failedAttempts) implements AtmState {
        @Override
        public AtmState enterPin(Atm atm, String pin) {
            if (atm.bank().authenticate(card.number(), pin)) {
                return new Authenticated(card);
            }
            if (failedAttempts >= 2) {
                // Third failure. A real machine keeps the card, we just end
                // the session, and either way the state goes back to Idle.
                return new Idle();
            }
            return new HasCard(card, failedAttempts + 1);
        }

        @Override
        public AtmState ejectCard(Atm atm) {
            return new Idle();
        }
    }

    // The customer is verified, so this is the only state where money moves.
    record Authenticated(Card card) implements AtmState {
        @Override
        public Map<Integer, Integer> withdraw(Atm atm, long amount) {
            return atm.withdrawFrom(card, amount);
        }

        @Override
        public long balance(Atm atm) {
            return atm.bank().balanceOf(card.accountNumber());
        }

        @Override
        public AtmState ejectCard(Atm atm) {
            return new Idle();
        }
    }
}

package com.androidinterview.atm;

import java.util.Map;

import com.androidinterview.atm.model.Card;

public sealed interface AtmState {

    default AtmState insertCard(Atm atm, Card card) {
        throw refuse("insert a card");
    }

    default AtmState enterPin(Atm atm, String pin) {
        throw refuse("enter a PIN");
    }

    default Map<Integer, Integer> withdraw(Atm atm, long amount) {
        throw refuse("withdraw");
    }

    default long balance(Atm atm) {
        throw refuse("check a balance");
    }

    default AtmState ejectCard(Atm atm) {
        throw refuse("eject a card");
    }

    private static IllegalStateException refuse(String operation) {
        return new IllegalStateException("you cannot " + operation + " right now");
    }

    record Idle() implements AtmState {
        @Override
        public AtmState insertCard(Atm atm, Card card) {
            return new HasCard(card, 0);
        }
    }

    record HasCard(Card card, int failedAttempts) implements AtmState {
        @Override
        public AtmState enterPin(Atm atm, String pin) {
            if (atm.bank().authenticate(card.number(), pin)) {
                return new Authenticated(card);
            }
            if (failedAttempts >= 2) {
                return new Idle();
            }
            return new HasCard(card, failedAttempts + 1);
        }

        @Override
        public AtmState ejectCard(Atm atm) {
            return new Idle();
        }
    }

    record Authenticated(Card card) implements AtmState {
        @Override
        public Map<Integer, Integer> withdraw(Atm atm, long amount) {
            return atm.withdrawFrom(card, amount);
        }

        @Override
        public long balance(Atm atm) {
            return atm.bank().balanceOf(card.accountNumber());
        }

        @Override
        public AtmState ejectCard(Atm atm) {
            return new Idle();
        }
    }
}

package com.androidinterview.atm.bank;

// The seam that matters. In a real machine every call here is a network round
// trip to the bank, so the ATM must work against an interface it can fake.
//
// Note that debit returns a boolean rather than throwing. Not enough money is
// an expected answer, not an exception. It also takes a request id, so a retry
// after a dropped reply cannot debit the account twice.
public interface BankService {

    boolean authenticate(String cardNumber, String pin);

    long balanceOf(String accountNumber);

    boolean debit(String accountNumber, long amount, String requestId);

    void credit(String accountNumber, long amount);
}

package com.androidinterview.atm.bank;

public interface BankService {

    boolean authenticate(String cardNumber, String pin);

    long balanceOf(String accountNumber);

    boolean debit(String accountNumber, long amount, String requestId);

    void credit(String accountNumber, long amount);
}

package com.androidinterview.atm.bank;

import java.util.Map;
import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.AtomicLong;

// A stand in for the bank, so the design can be run and tested. The only part
// worth studying is debit.
public final class InMemoryBank implements BankService {

    private final Map<String, String> pins = new ConcurrentHashMap<>();
    private final Map<String, AtomicLong> balances = new ConcurrentHashMap<>();
    // Request ids already applied. A replay of one of these is a no op.
    private final Set<String> applied = ConcurrentHashMap.newKeySet();

    public void open(String cardNumber, String pin, String accountNumber, long balance) {
        pins.put(cardNumber, pin);
        balances.put(accountNumber, new AtomicLong(balance));
    }

    @Override
    public boolean authenticate(String cardNumber, String pin) {
        return pin.equals(pins.get(cardNumber));
    }

    @Override
    public long balanceOf(String accountNumber) {
        return balances.get(accountNumber).get();
    }

    // Check and subtract in one atomic step. Reading the balance, deciding,
    // and then writing it back would lose an update whenever the same account
    // is being drained from net banking at the same moment.
    //
    // A real bank does exactly this in one statement, UPDATE accounts SET
    // balance = balance - ? WHERE number = ? AND balance >= ?, and checks how
    // many rows it changed.
    @Override
    public boolean debit(String accountNumber, long amount, String requestId) {
        if (!applied.add(requestId)) {
            return true; // already applied, so the retry succeeds without moving money
        }
        AtomicLong balance = balances.get(accountNumber);
        while (true) {
            long current = balance.get();
            if (current < amount) {
                applied.remove(requestId); // nothing was applied, so a retry may try again
                return false;
            }
            if (balance.compareAndSet(current, current - amount)) {
                return true;
            }
        }
    }

    @Override
    public void credit(String accountNumber, long amount) {
        balances.get(accountNumber).addAndGet(amount);
    }
}

package com.androidinterview.atm.bank;

import java.util.Map;
import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.AtomicLong;

public final class InMemoryBank implements BankService {

    private final Map<String, String> pins = new ConcurrentHashMap<>();
    private final Map<String, AtomicLong> balances = new ConcurrentHashMap<>();
    private final Set<String> applied = ConcurrentHashMap.newKeySet();

    public void open(String cardNumber, String pin, String accountNumber, long balance) {
        pins.put(cardNumber, pin);
        balances.put(accountNumber, new AtomicLong(balance));
    }

    @Override
    public boolean authenticate(String cardNumber, String pin) {
        return pin.equals(pins.get(cardNumber));
    }

    @Override
    public long balanceOf(String accountNumber) {
        return balances.get(accountNumber).get();
    }

    @Override
    public boolean debit(String accountNumber, long amount, String requestId) {
        if (!applied.add(requestId)) {
            return true;
        }
        AtomicLong balance = balances.get(accountNumber);
        while (true) {
            long current = balance.get();
            if (current < amount) {
                applied.remove(requestId);
                return false;
            }
            if (balance.compareAndSet(current, current - amount)) {
                return true;
            }
        }
    }

    @Override
    public void credit(String accountNumber, long amount) {
        balances.get(accountNumber).addAndGet(amount);
    }
}

package com.androidinterview.atm.cash;

import java.util.LinkedHashMap;
import java.util.Map;

// Owns the note inventory. Everything here is synchronised because the counts
// are shared mutable state, and because planning a withdrawal and then taking
// the notes must not be two separate decisions.
public final class CashDispenser {

    // Stands in for the shutter motor. Flip it to see the compensating credit
    // path run.
    public volatile boolean jammed = false;

    private final NoteDispenser chain;

    // The shutter's journal. What went out of the machine and what a jam left
    // in the reject bin, so the cassette counts only ever describe cassettes.
    private final Map<Integer, Integer> dispensed = new LinkedHashMap<>();
    private final Map<Integer, Integer> rejected = new LinkedHashMap<>();

    public CashDispenser(NoteDispenser chain) {
        this.chain = chain;
    }

    // Plan and take in one locked step. Two calls would be a check then act
    // race, where both see the last note available and only one gets it.
    public synchronized Map<Integer, Integer> reserve(long amount) {
        Map<Integer, Integer> plan = chain.plan(amount);
        if (plan == null) {
            return null;
        }
        chain.take(plan);
        return plan;
    }

    // Reserved notes go back into the cassettes. Only correct before a push
    // has been attempted, because after that the notes are no longer there.
    public synchronized void putBack(Map<Integer, Integer> notes) {
        chain.putBack(notes);
    }

    // The physical push. This is the step that fails after the account has
    // already been debited, which is the whole reason withdrawal needs a
    // compensating credit.
    public synchronized void push(Map<Integer, Integer> notes) {
        if (jammed) {
            throw new DispenserException("shutter jammed");
        }
        notes.forEach((denomination, count) -> dispensed.merge(denomination, count, Integer::sum));
    }

    // A jammed bundle is in the shutter or the reject bin, not in a cassette,
    // so it is journalled here rather than added back to the counts.
    public synchronized void reject(Map<Integer, Integer> notes) {
        notes.forEach((denomination, count) -> rejected.merge(denomination, count, Integer::sum));
    }

    public synchronized Map<Integer, Integer> dispensed() {
        return Map.copyOf(dispensed);
    }

    public synchronized Map<Integer, Integer> rejected() {
        return Map.copyOf(rejected);
    }

    public static final class DispenserException extends RuntimeException {
        public DispenserException(String message) {
            super(message);
        }
    }
}

package com.androidinterview.atm.cash;

import java.util.LinkedHashMap;
import java.util.Map;

public final class CashDispenser {

    public volatile boolean jammed = false;

    private final NoteDispenser chain;

    private final Map<Integer, Integer> dispensed = new LinkedHashMap<>();
    private final Map<Integer, Integer> rejected = new LinkedHashMap<>();

    public CashDispenser(NoteDispenser chain) {
        this.chain = chain;
    }

    public synchronized Map<Integer, Integer> reserve(long amount) {
        Map<Integer, Integer> plan = chain.plan(amount);
        if (plan == null) {
            return null;
        }
        chain.take(plan);
        return plan;
    }

    public synchronized void putBack(Map<Integer, Integer> notes) {
        chain.putBack(notes);
    }

    public synchronized void push(Map<Integer, Integer> notes) {
        if (jammed) {
            throw new DispenserException("shutter jammed");
        }
        notes.forEach((denomination, count) -> dispensed.merge(denomination, count, Integer::sum));
    }

    public synchronized void reject(Map<Integer, Integer> notes) {
        notes.forEach((denomination, count) -> rejected.merge(denomination, count, Integer::sum));
    }

    public synchronized Map<Integer, Integer> dispensed() {
        return Map.copyOf(dispensed);
    }

    public synchronized Map<Integer, Integer> rejected() {
        return Map.copyOf(rejected);
    }

    public static final class DispenserException extends RuntimeException {
        public DispenserException(String message) {
            super(message);
        }
    }
}

package com.androidinterview.atm.cash;

import java.util.LinkedHashMap;
import java.util.Map;

// One link in the note chain, one denomination each, largest first. A link
// takes as many notes as it can and passes the remainder to the next link.
// Adding a new denomination is one more link and no edit anywhere.
//
// plan, take and putBack are package private. Only CashDispenser can call
// them, under its lock, so nothing outside can plan without taking.
public final class NoteDispenser {

    private final int denomination;
    private final NoteDispenser next;
    private int available;

    public NoteDispenser(int denomination, int available, NoteDispenser next) {
        this.denomination = denomination;
        this.available = available;
        this.next = next;
    }

    // The greedy plan for this amount, denomination to note count, or null
    // when the chain cannot make the amount out of what is left.
    //
    // Greedy is what a real machine does and it can fail on stock a smarter
    // search would solve. Say that out loud, then say you would only reach for
    // bounded coin change if the interviewer asks.
    Map<Integer, Integer> plan(long amount) {
        int notes = (int) Math.min(amount / denomination, available);
        long remaining = amount - (long) notes * denomination;

        Map<Integer, Integer> plan = new LinkedHashMap<>();
        if (notes > 0) {
            plan.put(denomination, notes);
        }
        if (remaining == 0) {
            return plan;
        }
        if (next == null) {
            return null; // nothing smaller left, so the amount cannot be made
        }
        Map<Integer, Integer> rest = next.plan(remaining);
        if (rest == null) {
            return null;
        }
        plan.putAll(rest);
        return plan;
    }

    void take(Map<Integer, Integer> plan) {
        available -= plan.getOrDefault(denomination, 0);
        if (next != null) {
            next.take(plan);
        }
    }

    void putBack(Map<Integer, Integer> plan) {
        available += plan.getOrDefault(denomination, 0);
        if (next != null) {
            next.putBack(plan);
        }
    }
}

package com.androidinterview.atm.cash;

import java.util.LinkedHashMap;
import java.util.Map;

public final class NoteDispenser {

    private final int denomination;
    private final NoteDispenser next;
    private int available;

    public NoteDispenser(int denomination, int available, NoteDispenser next) {
        this.denomination = denomination;
        this.available = available;
        this.next = next;
    }

    Map<Integer, Integer> plan(long amount) {
        int notes = (int) Math.min(amount / denomination, available);
        long remaining = amount - (long) notes * denomination;

        Map<Integer, Integer> plan = new LinkedHashMap<>();
        if (notes > 0) {
            plan.put(denomination, notes);
        }
        if (remaining == 0) {
            return plan;
        }
        if (next == null) {
            return null;
        }
        Map<Integer, Integer> rest = next.plan(remaining);
        if (rest == null) {
            return null;
        }
        plan.putAll(rest);
        return plan;
    }

    void take(Map<Integer, Integer> plan) {
        available -= plan.getOrDefault(denomination, 0);
        if (next != null) {
            next.take(plan);
        }
    }

    void putBack(Map<Integer, Integer> plan) {
        available += plan.getOrDefault(denomination, 0);
        if (next != null) {
            next.putBack(plan);
        }
    }
}

package com.androidinterview.atm.model;

// A card is a value. It carries no balance and no PIN, because the bank owns
// both. All the card does is point at an account.
public record Card(String number, String accountNumber) {}

package com.androidinterview.atm.model;

public record Card(String number, String accountNumber) {}

package com.androidinterview.atm

import java.util.UUID

import com.androidinterview.atm.bank.BankService
import com.androidinterview.atm.cash.CashDispenser
import com.androidinterview.atm.cash.DispenserException
import com.androidinterview.atm.model.Card

// The machine. Every public method is one exhaustive when over the sealed
// state. The branches that allow the operation do the work and produce the
// next state, the rest refuse. Add a fourth state and every one of these
// stops compiling until it says what happens there.
class Atm(private val bank: BankService, private val dispenser: CashDispenser) {

    var state: AtmState = AtmState.Idle
        private set

    fun insertCard(card: Card) {
        state = when (state) {
            is AtmState.Idle -> AtmState.HasCard(card)
            is AtmState.HasCard, is AtmState.Authenticated -> refuse("insert a card")
        }
    }

    fun enterPin(pin: String) {
        state = when (val current = state) {
            is AtmState.Idle, is AtmState.Authenticated -> refuse("enter a PIN")
            is AtmState.HasCard -> when {
                bank.authenticate(current.card.number, pin) -> AtmState.Authenticated(current.card)
                // Third failure ends the session. A real machine keeps the
                // card, and either way we are back at Idle.
                current.failedAttempts >= 2 -> AtmState.Idle
                else -> current.copy(failedAttempts = current.failedAttempts + 1)
            }
        }
    }

    fun balance(): Long = when (val current = state) {
        is AtmState.Idle, is AtmState.HasCard -> refuse("check a balance")
        is AtmState.Authenticated -> bank.balanceOf(current.card.accountNumber)
    }

    // Withdrawing never changes the state, so this returns the notes that came
    // out rather than a state.
    fun withdraw(amount: Long): Map<Int, Int> = when (val current = state) {
        is AtmState.Idle, is AtmState.HasCard -> refuse("withdraw")
        is AtmState.Authenticated -> withdrawFrom(current.card, amount)
    }

    fun ejectCard() {
        state = when (state) {
            is AtmState.Idle -> refuse("eject a card")
            is AtmState.HasCard, is AtmState.Authenticated -> AtmState.Idle
        }
    }

    private fun refuse(operation: String): Nothing =
        throw IllegalStateException("you cannot $operation right now")

    // The method the whole problem is about. Three steps, in this order, and
    // the order is the answer.
    //
    // Reserve the notes first, so we never debit an account for cash the
    // machine cannot hand over. Debit second, because handing out money we
    // failed to charge for is worse than the reverse. Push last, and if the
    // shutter jams, credit the money straight back. That credit is a
    // compensating transaction, and a real machine journals every step so a
    // disputed withdrawal can be settled the next morning.
    private fun withdrawFrom(card: Card, amount: Long): Map<Int, Int> {
        val account = card.accountNumber
        val notes = checkNotNull(dispenser.reserve(amount)) {
            "cannot make $amount from the notes left"
        }
        // One id per withdrawal. If the reply is lost after the bank applied
        // the debit, the retry carries the same id and the bank ignores it.
        val requestId = UUID.randomUUID().toString()
        if (!bank.debit(account, amount, requestId)) {
            dispenser.putBack(notes)
            error("insufficient funds")
        }
        return try {
            dispenser.push(notes)
            notes
        } catch (jam: DispenserException) {
            // The notes are in the shutter or the reject bin, not back in the
            // cassettes, so they are journalled as rejected, not put back.
            bank.credit(account, amount)
            dispenser.reject(notes)
            throw jam
        }
    }
}

package com.androidinterview.atm

import java.util.UUID

import com.androidinterview.atm.bank.BankService
import com.androidinterview.atm.cash.CashDispenser
import com.androidinterview.atm.cash.DispenserException
import com.androidinterview.atm.model.Card

class Atm(private val bank: BankService, private val dispenser: CashDispenser) {

    var state: AtmState = AtmState.Idle
        private set

    fun insertCard(card: Card) {
        state = when (state) {
            is AtmState.Idle -> AtmState.HasCard(card)
            is AtmState.HasCard, is AtmState.Authenticated -> refuse("insert a card")
        }
    }

    fun enterPin(pin: String) {
        state = when (val current = state) {
            is AtmState.Idle, is AtmState.Authenticated -> refuse("enter a PIN")
            is AtmState.HasCard -> when {
                bank.authenticate(current.card.number, pin) -> AtmState.Authenticated(current.card)
                current.failedAttempts >= 2 -> AtmState.Idle
                else -> current.copy(failedAttempts = current.failedAttempts + 1)
            }
        }
    }

    fun balance(): Long = when (val current = state) {
        is AtmState.Idle, is AtmState.HasCard -> refuse("check a balance")
        is AtmState.Authenticated -> bank.balanceOf(current.card.accountNumber)
    }

    fun withdraw(amount: Long): Map<Int, Int> = when (val current = state) {
        is AtmState.Idle, is AtmState.HasCard -> refuse("withdraw")
        is AtmState.Authenticated -> withdrawFrom(current.card, amount)
    }

    fun ejectCard() {
        state = when (state) {
            is AtmState.Idle -> refuse("eject a card")
            is AtmState.HasCard, is AtmState.Authenticated -> AtmState.Idle
        }
    }

    private fun refuse(operation: String): Nothing =
        throw IllegalStateException("you cannot $operation right now")

    private fun withdrawFrom(card: Card, amount: Long): Map<Int, Int> {
        val account = card.accountNumber
        val notes = checkNotNull(dispenser.reserve(amount)) {
            "cannot make $amount from the notes left"
        }
        val requestId = UUID.randomUUID().toString()
        if (!bank.debit(account, amount, requestId)) {
            dispenser.putBack(notes)
            error("insufficient funds")
        }
        return try {
            dispenser.push(notes)
            notes
        } catch (jam: DispenserException) {
            bank.credit(account, amount)
            dispenser.reject(notes)
            throw jam
        }
    }
}

package com.androidinterview.atm

import com.androidinterview.atm.model.Card

// The lifecycle of the machine, as data and nothing else. The transitions live
// in the machine as an exhaustive when per operation, which is the Kotlin
// shape of the state pattern. Adding a fourth state turns every one of those
// whens into a compile error until it is handled, and that is better than a
// runtime surprise.
sealed interface AtmState {

    // Waiting for a customer. The only thing that can happen is a card going in.
    data object Idle : AtmState

    // A card is in and unverified. The failed attempt count lives here rather
    // than on the machine, so it resets by construction when the card leaves.
    data class HasCard(val card: Card, val failedAttempts: Int = 0) : AtmState

    // Verified, so this is the only state in which money moves.
    data class Authenticated(val card: Card) : AtmState
}

package com.androidinterview.atm

import com.androidinterview.atm.model.Card

sealed interface AtmState {

    data object Idle : AtmState

    data class HasCard(val card: Card, val failedAttempts: Int = 0) : AtmState

    data class Authenticated(val card: Card) : AtmState
}

package com.androidinterview.atm.bank

// The seam that matters. Every call here is a network round trip in a real
// machine, so the ATM has to work against something it can fake.
//
// debit returns a Boolean rather than throwing, because not enough money is an
// expected answer and not an exception. It takes a request id so a retry after
// a dropped reply cannot debit twice.
interface BankService {
    fun authenticate(cardNumber: String, pin: String): Boolean
    fun balanceOf(accountNumber: String): Long
    fun debit(accountNumber: String, amount: Long, requestId: String): Boolean
    fun credit(accountNumber: String, amount: Long)
}

package com.androidinterview.atm.bank

interface BankService {
    fun authenticate(cardNumber: String, pin: String): Boolean
    fun balanceOf(accountNumber: String): Long
    fun debit(accountNumber: String, amount: Long, requestId: String): Boolean
    fun credit(accountNumber: String, amount: Long)
}

package com.androidinterview.atm.bank

import java.util.concurrent.ConcurrentHashMap
import java.util.concurrent.atomic.AtomicLong

// A stand in for the bank so the design runs. Only debit is worth studying.
class InMemoryBank : BankService {

    private val pins = ConcurrentHashMap<String, String>()
    private val balances = ConcurrentHashMap<String, AtomicLong>()
    // Request ids already applied. A replay of one of these is a no op.
    private val applied = ConcurrentHashMap.newKeySet<String>()

    fun open(cardNumber: String, pin: String, accountNumber: String, balance: Long) {
        pins[cardNumber] = pin
        balances[accountNumber] = AtomicLong(balance)
    }

    override fun authenticate(cardNumber: String, pin: String) = pins[cardNumber] == pin

    override fun balanceOf(accountNumber: String) = balances.getValue(accountNumber).get()

    // Check and subtract in one atomic step. Read, decide, write back would
    // lose an update whenever the same account is being drained from net
    // banking at the same moment.
    //
    // A real bank does this in one statement, UPDATE accounts SET balance =
    // balance - ? WHERE number = ? AND balance >= ?, and checks the row count.
    override fun debit(accountNumber: String, amount: Long, requestId: String): Boolean {
        // Already applied, so the retry succeeds without moving money again.
        if (!applied.add(requestId)) return true
        val balance = balances.getValue(accountNumber)
        while (true) {
            val current = balance.get()
            if (current < amount) {
                applied.remove(requestId) // nothing was applied, a retry may try again
                return false
            }
            if (balance.compareAndSet(current, current - amount)) return true
        }
    }

    override fun credit(accountNumber: String, amount: Long) {
        balances.getValue(accountNumber).addAndGet(amount)
    }
}

package com.androidinterview.atm.bank

import java.util.concurrent.ConcurrentHashMap
import java.util.concurrent.atomic.AtomicLong

class InMemoryBank : BankService {

    private val pins = ConcurrentHashMap<String, String>()
    private val balances = ConcurrentHashMap<String, AtomicLong>()
    private val applied = ConcurrentHashMap.newKeySet<String>()

    fun open(cardNumber: String, pin: String, accountNumber: String, balance: Long) {
        pins[cardNumber] = pin
        balances[accountNumber] = AtomicLong(balance)
    }

    override fun authenticate(cardNumber: String, pin: String) = pins[cardNumber] == pin

    override fun balanceOf(accountNumber: String) = balances.getValue(accountNumber).get()

    override fun debit(accountNumber: String, amount: Long, requestId: String): Boolean {
        if (!applied.add(requestId)) return true
        val balance = balances.getValue(accountNumber)
        while (true) {
            val current = balance.get()
            if (current < amount) {
                applied.remove(requestId)
                return false
            }
            if (balance.compareAndSet(current, current - amount)) return true
        }
    }

    override fun credit(accountNumber: String, amount: Long) {
        balances.getValue(accountNumber).addAndGet(amount)
    }
}

package com.androidinterview.atm.cash

class DispenserException(message: String) : RuntimeException(message)

// Owns the note inventory. The counts are shared mutable state, so planning
// and taking happen together under one lock.
class CashDispenser(private val chain: NoteDispenser) {

    // Stands in for the shutter motor. Flip it to watch the compensating
    // credit run.
    @Volatile
    var jammed: Boolean = false

    // The shutter's journal. What left the machine and what a jam left in the
    // reject bin, so the cassette counts only ever describe cassettes.
    private val dispensed = mutableMapOf<Int, Int>()
    private val rejected = mutableMapOf<Int, Int>()

    // Plan and take in one locked step. Two calls would be a check then act
    // race, where both callers see the last note and only one gets it.
    @Synchronized
    fun reserve(amount: Long): Map<Int, Int>? = chain.plan(amount)?.also { chain.take(it) }

    // Reserved notes go back into the cassettes. Only right before a push has
    // been attempted, because after that the notes are no longer there.
    @Synchronized
    fun putBack(notes: Map<Int, Int>) = chain.putBack(notes)

    // The physical push, and the step that fails after the account has already
    // been debited. That is the whole reason withdrawal needs a compensating
    // credit behind it.
    @Synchronized
    fun push(notes: Map<Int, Int>) {
        if (jammed) throw DispenserException("shutter jammed")
        notes.forEach { (denomination, count) -> dispensed.merge(denomination, count, Int::plus) }
    }

    // A jammed bundle is in the shutter or the reject bin, not in a cassette,
    // so it is journalled here rather than added back to the counts.
    @Synchronized
    fun reject(notes: Map<Int, Int>) {
        notes.forEach { (denomination, count) -> rejected.merge(denomination, count, Int::plus) }
    }

    @Synchronized
    fun dispensed(): Map<Int, Int> = dispensed.toMap()

    @Synchronized
    fun rejected(): Map<Int, Int> = rejected.toMap()
}

package com.androidinterview.atm.cash

class DispenserException(message: String) : RuntimeException(message)

class CashDispenser(private val chain: NoteDispenser) {

    @Volatile
    var jammed: Boolean = false

    private val dispensed = mutableMapOf<Int, Int>()
    private val rejected = mutableMapOf<Int, Int>()

    @Synchronized
    fun reserve(amount: Long): Map<Int, Int>? = chain.plan(amount)?.also { chain.take(it) }

    @Synchronized
    fun putBack(notes: Map<Int, Int>) = chain.putBack(notes)

    @Synchronized
    fun push(notes: Map<Int, Int>) {
        if (jammed) throw DispenserException("shutter jammed")
        notes.forEach { (denomination, count) -> dispensed.merge(denomination, count, Int::plus) }
    }

    @Synchronized
    fun reject(notes: Map<Int, Int>) {
        notes.forEach { (denomination, count) -> rejected.merge(denomination, count, Int::plus) }
    }

    @Synchronized
    fun dispensed(): Map<Int, Int> = dispensed.toMap()

    @Synchronized
    fun rejected(): Map<Int, Int> = rejected.toMap()
}

package com.androidinterview.atm.cash

// One link in the note chain, one denomination each, largest first. A link
// takes as many notes as it can and passes the remainder down. Adding a
// denomination is one more link and no edit anywhere.
//
// plan, take and putBack are internal. Only CashDispenser calls them, under
// its lock, so nothing outside can plan without taking.
class NoteDispenser(
    private val denomination: Int,
    private var available: Int,
    private val next: NoteDispenser? = null,
) {
    // The greedy plan for this amount, or null when the chain cannot make it
    // from what is left. Greedy is what a real machine does, and it can fail
    // on stock that a bounded coin change search would solve. Say so, then
    // only write the search if the interviewer asks.
    internal fun plan(amount: Long): Map<Int, Int>? {
        val notes = minOf(amount / denomination, available.toLong()).toInt()
        val remaining = amount - notes.toLong() * denomination
        val mine = if (notes > 0) mapOf(denomination to notes) else emptyMap()
        if (remaining == 0L) return mine
        val rest = next?.plan(remaining) ?: return null
        return mine + rest
    }

    internal fun take(plan: Map<Int, Int>) {
        available -= plan[denomination] ?: 0
        next?.take(plan)
    }

    internal fun putBack(plan: Map<Int, Int>) {
        available += plan[denomination] ?: 0
        next?.putBack(plan)
    }
}

package com.androidinterview.atm.cash

class NoteDispenser(
    private val denomination: Int,
    private var available: Int,
    private val next: NoteDispenser? = null,
) {
    internal fun plan(amount: Long): Map<Int, Int>? {
        val notes = minOf(amount / denomination, available.toLong()).toInt()
        val remaining = amount - notes.toLong() * denomination
        val mine = if (notes > 0) mapOf(denomination to notes) else emptyMap()
        if (remaining == 0L) return mine
        val rest = next?.plan(remaining) ?: return null
        return mine + rest
    }

    internal fun take(plan: Map<Int, Int>) {
        available -= plan[denomination] ?: 0
        next?.take(plan)
    }

    internal fun putBack(plan: Map<Int, Int>) {
        available += plan[denomination] ?: 0
        next?.putBack(plan)
    }
}

package com.androidinterview.atm.model

// A card is a value. It holds no balance and no PIN, because the bank owns
// both. All it does is point at an account.
data class Card(val number: String, val accountNumber: String)

package com.androidinterview.atm.model

data class Card(val number: String, val accountNumber: String)