Design an ATM | androidinterview.com

An ATM is two interesting problems wearing one enclosure. The first is a session that only allows certain operations at certain times, which is what the state pattern is for. The second is a withdrawal that touches money in one place and cash in another, and has to stay honest when one of them fails.

Most candidates model the entities and stop. The marks are in the ordering of the withdrawal steps and in what you do when the dispenser jams after the account has already been debited. Get to that part quickly.

What to clarify first

Ask these before drawing anything. They remove more scope than any other three minutes you will spend.

One machine or a fleet. Almost always one, which removes a whole layer.
Is the bank in scope. It should not be. The bank is an interface you call, and saying that early shows you know where the boundary is.
Do we dispense real denominations. Ask this one for certain. If the answer is yes, note counting is half the problem, and if you do not ask you will design past it.
Deposits, transfers, mini statements, or withdrawal only. Withdrawal and balance is usually enough.
Is the PIN checked locally or at the bank. At the bank. How many attempts before the session ends, and does the machine keep the card.
Daily limits, minimum balance, multiple accounts on one card. Usually out, but ask.
What happens if the shutter jams after the debit. Ask this out loud even if you already know the answer, because it tells the interviewer where you are going.

State the out of scope list too. Card issuing, fraud checks, receipt printing, the screen.

The classes

There are four groups. What a card is, who the bank is, where the cash lives, and the machine that sequences it all.

The card and the bank.

Card is a value with a number and the account it points at. It holds no balance and no PIN. Both belong to the bank, and putting them on the card is the first thing an interviewer will pick at.
BankService is an interface, and it is the single best decision in this design. Every call to it is a network hop in a real machine, so the ATM must be built against something it can fake. It offers authenticate, balance, debit and credit, and debit takes a request id, which is what makes a retry safe.
InMemoryBank is the fake, and it exists so the design can actually run. One method in it matters, and that is debit.

Debit returns a boolean rather than throwing. Not enough money is a normal outcome of a normal request, so it is a return value, not an exception.

The cash.

NoteDispenser is one link in a chain, holding one denomination and a count. It takes as many notes of its own denomination as it can and hands the remainder to the next link.
CashDispenser owns the chain and the lock around it. It can reserve an amount, put reserved notes back, push notes out of the shutter, and send a jammed bundle to the reject bin.

The machine.

AtmState is the session lifecycle, three states. Idle, a card is in but unverified, and authenticated.
Atm is the context. It holds the bank, the dispenser and the current state, and its public methods are thin. Every one of them checks the state, does the work, and moves to the next state.

The relationships are easy to say. The ATM owns a dispenser and uses a bank. The dispenser owns a chain of note links. The state is a field the ATM replaces rather than mutates, so a transition is always a whole new state and never a half updated one.

The machine owns the dispenser and its note chain outright, reaches the bank only through an interface it can fake in a test, and swaps one of three state objects rather than carrying a pile of booleans.

How a withdrawal actually runs

Walk this at the whiteboard, slowly, because this is where the marks are.

A card goes in. The machine is Idle, so the operation is allowed, and it moves to the card inserted state carrying the card. Nothing has been asked of the bank yet.

The customer types a PIN. The machine asks the bank, and the bank answers. On a match it moves to the authenticated state carrying the card. On a miss it moves back to the same state with the failure count raised by one, and on the third failure the session ends. Notice that the failure count lives on the state, not on the machine, so it cannot survive the card being taken out.

Every operation the machine offers belongs to exactly one of these three states, which is why an ATM built this way has no way to be asked for cash before a PIN has been checked.

The customer asks for cash, and now the order of three steps is the whole answer.

Reserve the notes first. The dispenser plans the note breakdown and takes those notes out of its counts in one locked step. If the amount cannot be made from what is in the machine, we stop here, and no money has moved anywhere.
Debit second. The bank subtracts the amount and tells us whether it worked. If it did not, we put the notes back and stop. We never hand out cash we failed to charge for.
Push last. The shutter opens and the notes go out. If that throws, we credit the money straight back to the account. The notes are not put back in the counts, because physically they are in the shutter or the reject bin, so they are journalled as rejected and the counts stay honest.

That credit back is a compensating transaction, and it is worth naming out loud. You cannot make a bank ledger and a physical motor commit together, so the honest design does them in a fixed order and undoes the first when the second fails. Add that a real machine also writes every step to a journal, so a customer who says the cash never came out can be settled the next morning from the log rather than from an argument.

Patterns actually used

State, and this is why the problem gets asked. Without it the machine is a pile of booleans, and every method starts with a check that a card is in and the PIN was right. Those checks drift apart over time and one of them ends up missing.

With the state as an object, an operation that is not allowed simply does not exist in that state. Inserting a card while a card is in fails because the current state has no way to accept it. That is a much stronger guarantee than a check that a future edit might forget.

The two languages express it differently, and the difference is worth knowing.

In Java each state is a record that implements the operations it allows, and the interface rejects everything else by default. The transition is the return value, so the machine assigns whatever came back.
In Kotlin the states are a sealed interface holding data only, and every operation on the machine is one exhaustive when over the current state. Adding a fourth state turns every one of those whens into a compile error until it is handled, which is exactly the reminder you want.

Chain of responsibility, for the notes. The dispenser is a chain of links from the largest denomination down. Each link takes what it can and passes the rest along. It is a greedy algorithm expressed as objects, and adding a new denomination is one more link and no edit to anything else.

Be honest about its limit. Greedy can fail on stock where an exact answer exists, for example when it burns the last large note and then cannot make the remainder from what is left. Real machines behave this way and refuse the amount. Say that you would only reach for a bounded coin change search if the interviewer asks for it.

Deliberately not used.

No singleton on the machine. There is one physical ATM, so it is defensible, and it still buys nothing. It costs you a test that wants two machines and a fake bank. If exactly one instance is needed, that is the job of whatever wires the application up.
No factory for accounts. A factory that returns a savings or a current account replaces a two arm switch with a class. Add it if account types get real behaviour, not before.
No strategy on withdrawal rules. There is one rule here. If the follow up is that different banks charge different fees, then a fee strategy earns its place and you add it in a minute, which is a good thing to say rather than to build up front.

The implementation

Both languages carry the same design, and the state pattern is where they genuinely differ. The Kotlin keeps the states as data and puts the transitions in the machine, the Java puts the transitions on the states.

Java

com.androidinterview.atm.Atm.java

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;
        }
    }
}

com.androidinterview.atm.AtmState.java

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();
        }
    }
}

com.androidinterview.atm.bank.BankService.java

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);
}

com.androidinterview.atm.bank.InMemoryBank.java

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);
    }
}

com.androidinterview.atm.cash.CashDispenser.java

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);
        }
    }
}

com.androidinterview.atm.cash.NoteDispenser.java

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);
        }
    }
}

com.androidinterview.atm.model.Card.java

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) {}

Kotlin

com.androidinterview.atm.Atm.kt

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
        }
    }
}

com.androidinterview.atm.AtmState.kt

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
}

com.androidinterview.atm.bank.BankService.kt

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)
}

com.androidinterview.atm.bank.InMemoryBank.kt

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)
    }
}

com.androidinterview.atm.cash.CashDispenser.kt

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()
}

com.androidinterview.atm.cash.NoteDispenser.kt

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)
    }
}

com.androidinterview.atm.model.Card.kt

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)

Concurrency and edge cases

Dispensing after the account is already debited. This is the interview. The account and the cash cannot be changed together atomically, so pick an order and make the failure recoverable. Reserve the notes, debit, push, and credit back if the push fails. The customer is briefly short and then whole again, and the journal explains what happened.

Say why the other order is worse. Push first and debit second means a jam costs the customer nothing but a failed debit costs the bank the cash, which is gone and cannot be recalled.

Check then act on the note counts. Asking whether the machine can dispense an amount and then dispensing it is two decisions with a gap between them. Two threads can both be told yes for the last note. That is why plan and take happen inside one lock in the dispenser, and the note chain only exposes them to the dispenser, so there is no public way to do only one of them.

Then give the honest scale answer. One ATM has one customer at the panel, so the dispenser is barely contended. The contention that actually matters is on the account, which is being spent from at the same moment by net banking, a card machine, and another ATM.

Two debits on the same account. Read the balance, decide, write it back, and you have lost an update. The fix is to make the check and the subtraction one operation. In the code that is a compare and set loop. In a real bank it is one update statement with the balance condition in the where clause, and you check how many rows changed. Naming that statement is the answer an interviewer is waiting for.

A retried request. If the network drops after the debit but before the machine hears back, the retry must not debit twice. Give each withdrawal a request id and have the bank ignore one it has already applied. That is idempotency, and it is the word to use. In the code, debit takes the id and the fake bank keeps the set of ids it has already applied.

Other cases worth a sentence each.

An expired or blocked card. The bank rejects it at authenticate, and the machine never leaves the card inserted state.
A wrong PIN three times. The session ends and a real machine keeps the card. The count is on the state, so it cannot leak into the next customer's session.
An amount the notes cannot make. Refuse before touching the account, and tell the customer which multiples are available.
A customer who walks away. A session timeout returns the machine to idle and ejects the card, otherwise the next person is standing at an authenticated screen. The timeout is a scheduler that calls eject card, so it needs no new state.
The machine runs out of cash. Reserve fails, nothing is debited, and the machine can go out of service without any half finished transaction to unwind.