Designing a Vending Machine

Difficulty: Beginner Patterns: State, Strategy, Singleton (inventory) Asked at: PhonePe, Amazon, Flipkart, Uber, Walmart

The vending machine is the textbook problem for the State pattern. The whole point interviewers are testing: can you model a machine whose behaviour for the same action (say, “insert coin”) changes depending on what state it’s in — without a tangle of if (state == ...) checks scattered through every method?

Functional Requirements

  1. Machine holds multiple products, each in a slot with a price and a quantity.
  2. User flow: select a product → insert money → collect product + change.
  3. Accept money in fixed denominations (coins and notes).
  4. Return change when the user overpays, using available denominations.
  5. Allow the user to cancel and get a full refund at any point before dispensing.
  6. Reject selection when the product is out of stock or the machine can’t make change.
  7. Operator can refill inventory and restock the coin float.

Non-Functional Requirements

  1. No invalid transitions — you can’t dispense before paying, can’t pay before selecting.
  2. Never over-dispense — money and inventory stay consistent even on cancel.
  3. Extensibility — adding a new state (e.g. maintenance mode) or a new change algorithm shouldn’t touch existing states.

Core Entities

Entity Description
Coin / Note Enum of accepted denominations (value in cents/paise)
Product Name + price
Slot Holds a product, its price, and remaining quantity
Inventory<T> Generic count-map: products in slots, coins in the float
VendingMachineState Interface — one method per possible user action
IdleState Waiting for a product selection
HasSelectionState Product chosen, waiting for money
HasMoneyState Enough money in; ready to dispense
DispenseState Hands over product + change, resets to idle
ChangeStrategy How to compute change from available denominations
VendingMachine Context — holds current state, inventory, and the money pool

The State Pattern — why it fits

💡 State pattern = let an object alter its behaviour when its internal state changes. The object appears to change its class. Each state is a class; the context delegates every action to its current state object.

A naive vending machine has one giant insertCoin() method full of if (currentState == IDLE) ... else if (currentState == HAS_MONEY) .... Every action method repeats that ladder, and adding a state means editing all of them. The State pattern flips it: each state is a class that knows how to handle every action for that state, including rejecting the ones that don’t make sense. The machine just forwards calls to currentState.

stateDiagram-v2
    [*] --> Idle
    Idle --> HasSelection : selectProduct()
    HasSelection --> HasSelection : insertMoney() (not enough yet)
    HasSelection --> HasMoney : insertMoney() (enough)
    HasMoney --> Dispense : dispense()
    Dispense --> Idle : product + change returned
    HasSelection --> Idle : cancel() (refund)
    HasMoney --> Idle : cancel() (refund)

Class Diagram

classDiagram
    class VendingMachineState {
        <<interface>>
        +selectProduct(String code)
        +insertMoney(int amount)
        +dispense()
        +cancel()
    }

    class VendingMachine {
        -VendingMachineState idle
        -VendingMachineState hasSelection
        -VendingMachineState hasMoney
        -VendingMachineState dispense
        -VendingMachineState current
        -Inventory~String~ products
        -Inventory~Integer~ coins
        -Slot selectedSlot
        -int balance
        -ChangeStrategy changeStrategy
        +selectProduct(String)
        +insertMoney(int)
        +dispense()
        +cancel()
        +setState(VendingMachineState)
    }

    class Slot {
        -Product product
        -int quantity
        +dispenseOne()
    }

    class ChangeStrategy {
        <<interface>>
        +makeChange(int amount, Inventory~Integer~ float) List~Integer~
    }

    class GreedyChangeStrategy {
        +makeChange(int, Inventory) List~Integer~
    }

    VendingMachineState <|.. IdleState
    VendingMachineState <|.. HasSelectionState
    VendingMachineState <|.. HasMoneyState
    VendingMachineState <|.. DispenseState
    VendingMachine --> VendingMachineState : current
    VendingMachine --> Slot
    VendingMachine --> ChangeStrategy
    ChangeStrategy <|.. GreedyChangeStrategy

Design Patterns

Pattern Where Why
State VendingMachineState with four concrete states Behaviour of each action depends on the state; no if/else state ladders. New state = one class.
Strategy ChangeStrategy (greedy today, DP-optimal tomorrow) Swap the change algorithm without touching the machine.
Context VendingMachine holds state + shared data States are stateless singletons; all mutable data lives in one place.

Data Structures

Component Structure Why
Product slots Map<String, Slot> keyed by code (e.g. "A1") O(1) selection by keypad code
Coin float Map<Integer, Integer> (denomination → count) O(1) update; greedy change walks denominations high→low
State objects One instance each, reused States hold no per-transaction data, so they’re safe to share

Complete Code

Product.java

An immutable value object — just a name and a price (in the smallest currency unit, e.g. paise, to avoid floating-point money bugs).

package vending.model;

public class Product {
    private final String name;
    private final int price; // in paise/cents — never use double for money

    public Product(String name, int price) {
        this.name = name;
        this.price = price;
    }

    public String getName() { return name; }
    public int getPrice() { return price; }

    @Override
    public String toString() { return name + " (₹" + price / 100.0 + ")"; }
}

Slot.java

A slot pairs a product with its remaining quantity. dispenseOne() is the only mutator, and it guards against dispensing from an empty slot — the machine should never hand out what it doesn’t have.

package vending.model;

public class Slot {
    private final Product product;
    private int quantity;

    public Slot(Product product, int quantity) {
        this.product = product;
        this.quantity = quantity;
    }

    public Product getProduct() { return product; }
    public int getQuantity() { return quantity; }
    public boolean isAvailable() { return quantity > 0; }

    public void refill(int count) { quantity += count; }

    public void dispenseOne() {
        if (quantity <= 0) throw new IllegalStateException("Slot empty: " + product.getName());
        quantity--;
    }
}

ChangeStrategy.java (Strategy interface)

Computing change is a swappable algorithm. The greedy version is fine when denominations are canonical (1, 2, 5, 10…); a DP version would be needed for exotic denomination sets. Isolating it behind an interface means the machine doesn’t care which one runs.

package vending.change;

import java.util.List;
import java.util.Map;

public interface ChangeStrategy {
    /**
     * @param amount the change owed, in paise
     * @param floatCoins available denominations (value → count), mutated on success
     * @return the list of denominations to return
     * @throws CannotMakeChangeException if exact change isn't possible
     */
    List<Integer> makeChange(int amount, Map<Integer, Integer> floatCoins);
}

CannotMakeChangeException.java

package vending.change;

public class CannotMakeChangeException extends RuntimeException {
    public CannotMakeChangeException(String message) { super(message); }
}

GreedyChangeStrategy.java

Walks denominations from largest to smallest, taking as many of each as it can. It only commits to the coin float once it knows exact change is possible — so a failed attempt leaves the float untouched.

package vending.change;

import java.util.*;

public class GreedyChangeStrategy implements ChangeStrategy {
    @Override
    public List<Integer> makeChange(int amount, Map<Integer, Integer> floatCoins) {
        List<Integer> denoms = new ArrayList<>(floatCoins.keySet());
        denoms.sort(Collections.reverseOrder());

        List<Integer> result = new ArrayList<>();
        Map<Integer, Integer> used = new HashMap<>();
        int remaining = amount;

        for (int d : denoms) {
            int available = floatCoins.getOrDefault(d, 0);
            int take = Math.min(remaining / d, available);
            for (int i = 0; i < take; i++) result.add(d);
            if (take > 0) used.put(d, take);
            remaining -= take * d;
        }

        if (remaining != 0) {
            throw new CannotMakeChangeException("Cannot make exact change for " + amount);
        }
        // Commit only now that we know it worked.
        used.forEach((d, count) -> floatCoins.merge(d, -count, Integer::sum));
        return result;
    }
}

VendingMachineState.java (State interface)

One method per user action. Every concrete state must decide how to handle each — including the ones it should reject.

package vending.state;

public interface VendingMachineState {
    void selectProduct(String code);
    void insertMoney(int amount);
    void dispense();
    void cancel();
    String name();
}

IdleState.java

The starting state. Only selectProduct does anything meaningful; inserting money or trying to dispense here is a user error and is rejected with a clear message.

package vending.state;

import vending.VendingMachine;
import vending.model.Slot;

public class IdleState implements VendingMachineState {
    private final VendingMachine machine;

    public IdleState(VendingMachine machine) { this.machine = machine; }

    @Override
    public void selectProduct(String code) {
        Slot slot = machine.getSlot(code);
        if (slot == null) { System.out.println("✗ No such product: " + code); return; }
        if (!slot.isAvailable()) { System.out.println("✗ Out of stock: " + slot.getProduct().getName()); return; }
        machine.setSelectedSlot(slot);
        System.out.println("→ Selected " + slot.getProduct() + ". Please insert money.");
        machine.setState(machine.getHasSelectionState());
    }

    @Override public void insertMoney(int amount) { System.out.println("✗ Select a product first."); }
    @Override public void dispense() { System.out.println("✗ Select a product first."); }
    @Override public void cancel() { System.out.println("Nothing to cancel."); }
    @Override public String name() { return "IDLE"; }
}

HasSelectionState.java

A product is chosen. Money accumulates here; once the balance reaches the price, the machine advances to HasMoney. Note that selecting again just replaces the choice, and cancel refunds whatever’s been inserted.

package vending.state;

import vending.VendingMachine;

public class HasSelectionState implements VendingMachineState {
    private final VendingMachine machine;

    public HasSelectionState(VendingMachine machine) { this.machine = machine; }

    @Override
    public void selectProduct(String code) {
        // Allow re-selecting while no money is in; delegate to idle logic.
        machine.setState(machine.getIdleState());
        machine.selectProduct(code);
    }

    @Override
    public void insertMoney(int amount) {
        machine.addToBalance(amount);
        int price = machine.getSelectedSlot().getProduct().getPrice();
        System.out.println("  Balance: ₹" + machine.getBalance() / 100.0 + " / ₹" + price / 100.0);
        if (machine.getBalance() >= price) {
            System.out.println("→ Enough money in. Press dispense.");
            machine.setState(machine.getHasMoneyState());
        }
    }

    @Override public void dispense() { System.out.println("✗ Insert more money first."); }

    @Override
    public void cancel() {
        machine.refundBalance();
        machine.reset();
        machine.setState(machine.getIdleState());
    }

    @Override public String name() { return "HAS_SELECTION"; }
}

HasMoneyState.java

Enough money is in. dispense is now valid: it tries to compute change before committing anything, drops the product, returns the change, and resets. If change can’t be made, the whole transaction is refunded — the machine never keeps money it can’t complete a sale for.

package vending.state;

import vending.VendingMachine;
import vending.change.CannotMakeChangeException;
import vending.model.Slot;

import java.util.List;

public class HasMoneyState implements VendingMachineState {
    private final VendingMachine machine;

    public HasMoneyState(VendingMachine machine) { this.machine = machine; }

    @Override public void selectProduct(String code) { System.out.println("✗ Finish or cancel the current purchase first."); }
    @Override public void insertMoney(int amount) { machine.addToBalance(amount); System.out.println("  Extra money accepted; will be returned as change."); }

    @Override
    public void dispense() {
        machine.setState(machine.getDispenseState());
        machine.dispense(); // delegate the actual work to the dispense state
    }

    @Override
    public void cancel() {
        machine.refundBalance();
        machine.reset();
        machine.setState(machine.getIdleState());
    }

    @Override public String name() { return "HAS_MONEY"; }
}

DispenseState.java

The transactional core. Order matters: compute change first (this can fail), and only then drop the product and bank the money. On failure, refund and abort — leaving inventory and float exactly as they were.

package vending.state;

import vending.VendingMachine;
import vending.change.CannotMakeChangeException;
import vending.model.Slot;

import java.util.List;

public class DispenseState implements VendingMachineState {
    private final VendingMachine machine;

    public DispenseState(VendingMachine machine) { this.machine = machine; }

    @Override public void selectProduct(String code) { System.out.println("✗ Dispensing, please wait."); }
    @Override public void insertMoney(int amount) { System.out.println("✗ Dispensing, please wait."); }

    @Override
    public void dispense() {
        Slot slot = machine.getSelectedSlot();
        int price = slot.getProduct().getPrice();
        int changeOwed = machine.getBalance() - price;

        try {
            // 1. Work out change BEFORE touching stock or money.
            List<Integer> change = machine.getChangeStrategy()
                    .makeChange(changeOwed, machine.getCoinFloat());

            // 2. Commit: drop product, bank the money paid.
            slot.dispenseOne();
            machine.bankBalance(); // the inserted coins now belong to the float

            System.out.println("✓ Dispensed: " + slot.getProduct().getName());
            if (!change.isEmpty()) System.out.println("✓ Change returned: " + change);
        } catch (CannotMakeChangeException e) {
            System.out.println("✗ " + e.getMessage() + " — refunding.");
            machine.refundBalance();
        } finally {
            machine.reset();
            machine.setState(machine.getIdleState());
        }
    }

    @Override public void cancel() { System.out.println("✗ Too late to cancel."); }
    @Override public String name() { return "DISPENSE"; }
}

VendingMachine.java (Context)

The context owns the four state singletons, the inventory, the coin float, and the in-flight transaction data (selectedSlot, balance). Every public action just forwards to current — the machine itself contains no branching on state.

package vending;

import vending.change.ChangeStrategy;
import vending.change.GreedyChangeStrategy;
import vending.model.Product;
import vending.model.Slot;
import vending.state.*;

import java.util.*;

public class VendingMachine {
    // States (created once, reused)
    private final VendingMachineState idle = new IdleState(this);
    private final VendingMachineState hasSelection = new HasSelectionState(this);
    private final VendingMachineState hasMoney = new HasMoneyState(this);
    private final VendingMachineState dispenseState = new DispenseState(this);
    private VendingMachineState current = idle;

    // Data
    private final Map<String, Slot> slots = new HashMap<>();
    private final Map<Integer, Integer> coinFloat = new HashMap<>(); // denomination → count
    private ChangeStrategy changeStrategy = new GreedyChangeStrategy();

    // In-flight transaction
    private Slot selectedSlot;
    private int balance;      // money inserted this transaction (paise)
    private final List<Integer> insertedCoins = new ArrayList<>();

    // ─── Public actions: delegate to current state ───────────
    public void selectProduct(String code) { current.selectProduct(code); }
    public void dispense()                  { current.dispense(); }
    public void cancel()                    { current.cancel(); }

    public void insertMoney(int denomination) {
        coinFloatCandidate(denomination); // remember it so we can refund exact coins
        current.insertMoney(denomination);
    }

    // ─── State accessors (used by states) ────────────────────
    public VendingMachineState getIdleState() { return idle; }
    public VendingMachineState getHasSelectionState() { return hasSelection; }
    public VendingMachineState getHasMoneyState() { return hasMoney; }
    public VendingMachineState getDispenseState() { return dispenseState; }
    public void setState(VendingMachineState s) { this.current = s; }
    public String currentStateName() { return current.name(); }

    // ─── Transaction data (used by states) ───────────────────
    public Slot getSlot(String code) { return slots.get(code); }
    public Slot getSelectedSlot() { return selectedSlot; }
    public void setSelectedSlot(Slot s) { this.selectedSlot = s; }
    public int getBalance() { return balance; }
    public void addToBalance(int amount) { balance += amount; }
    public ChangeStrategy getChangeStrategy() { return changeStrategy; }
    public void setChangeStrategy(ChangeStrategy s) { this.changeStrategy = s; }
    public Map<Integer, Integer> getCoinFloat() { return coinFloat; }

    private void coinFloatCandidate(int denomination) { insertedCoins.add(denomination); }

    /** The coins inserted this transaction become part of the float (sale committed). */
    public void bankBalance() {
        for (int c : insertedCoins) coinFloat.merge(c, 1, Integer::sum);
    }

    /** Give the inserted coins back to the user (cancel / cannot-make-change). */
    public void refundBalance() {
        if (!insertedCoins.isEmpty()) System.out.println("✓ Refunded: " + insertedCoins);
    }

    public void reset() {
        selectedSlot = null;
        balance = 0;
        insertedCoins.clear();
    }

    // ─── Operator / setup ────────────────────────────────────
    public void addSlot(String code, Product product, int qty) { slots.put(code, new Slot(product, qty)); }
    public void addCoins(int denomination, int count) { coinFloat.merge(denomination, count, Integer::sum); }
}

Demo.java (Runnable end-to-end)

Drives the machine through a happy path, an out-of-stock rejection, a cancel-and-refund, and a can’t-make-change refund — proving the state transitions and money handling all hold together.

package vending;

import vending.model.Product;

public class Demo {
    public static void main(String[] args) {
        VendingMachine m = new VendingMachine();
        // Prices in paise: ₹25.00 = 2500
        m.addSlot("A1", new Product("Coke", 2500), 2);
        m.addSlot("A2", new Product("Water", 2000), 0);   // out of stock
        m.addSlot("B1", new Product("Chips", 3000), 5);
        m.addCoins(500, 5);   // ₹5 x5
        m.addCoins(1000, 5);  // ₹10 x5

        System.out.println("=== Happy path: buy Coke with exact-ish money ===");
        m.selectProduct("A1");        // → HAS_SELECTION
        m.insertMoney(1000);          // ₹10
        m.insertMoney(1000);          // ₹20
        m.insertMoney(1000);          // ₹30 → HAS_MONEY
        m.dispense();                 // dispense Coke, return ₹5 change → IDLE

        System.out.println("\n=== Out of stock ===");
        m.selectProduct("A2");        // rejected, stays IDLE

        System.out.println("\n=== Cancel and refund ===");
        m.selectProduct("B1");
        m.insertMoney(1000);
        m.cancel();                   // refund ₹10 → IDLE

        System.out.println("\n=== State after transactions ===");
        System.out.println("Current state: " + m.currentStateName());

        System.out.println("\n=== Cannot make change (drain the float) ===");
        // Empty the float of small coins, then overpay so change is impossible.
        VendingMachine m2 = new VendingMachine();
        m2.addSlot("C1", new Product("Gum", 1500), 1); // ₹15
        m2.addCoins(1000, 0); // no coins at all
        m2.selectProduct("C1");
        m2.insertMoney(1000);
        m2.insertMoney(1000); // ₹20 in, owes ₹5 change but float is empty
        m2.dispense();        // cannot make change → refund, stays consistent
    }
}

Sequence Diagram — Buy a Product

sequenceDiagram
    participant User
    participant VM as VendingMachine
    participant S as Current State
    participant CS as ChangeStrategy

    User->>VM: selectProduct("A1")
    VM->>S: selectProduct("A1")  [IdleState]
    S->>VM: setState(HasSelection)
    User->>VM: insertMoney(x3)
    VM->>S: insertMoney()  [HasSelectionState]
    S->>VM: setState(HasMoney) when balance ≥ price
    User->>VM: dispense()
    VM->>S: dispense()  [DispenseState]
    S->>CS: makeChange(overpaid, float)
    CS-->>S: [denominations]
    S->>VM: dispenseOne() + bankBalance()
    S->>VM: setState(Idle)
    VM-->>User: product + change

How to Extend

Extension Implementation
Card / UPI payment New insertMoney-equivalent action; a PaymentStrategy alongside the states
Maintenance mode New MaintenanceState that rejects all customer actions; operator toggles it
Optimal change Swap in a DPChangeStrategy — DP over denominations for non-canonical sets
Multi-item cart Track a list of selected slots; sum prices before the money state
Low-stock alerts Observer on Slot.dispenseOne() notifying an operator dashboard
Audit log Decorator around each state logging entry/exit

What Interviewers Look For

  1. ✅ State pattern — one class per state, no if (state == X) ladders in the machine
  2. ✅ Invalid transitions rejected cleanly — dispensing before paying returns a message, not a crash
  3. ✅ Money as integers — paise/cents, never double
  4. ✅ Change computed before committing — inventory/float stay consistent on failure
  5. ✅ Refund correctness — cancel and can’t-make-change both leave the machine unchanged
  6. ✅ Strategy for change — swappable algorithm, not hardcoded greedy logic
  7. ✅ Runnable demo — happy path, out-of-stock, cancel, and change-failure all shown
SystemCraft
Written by SystemCraft Interview Prep Platform

Free system design, LLD, and DSA resources built by engineers who went through the interview grind at Indian and international tech companies.

Discussion

Newest first
You
0 / 2000

Free system design + DSA prep. If it helped you crack an interview, consider supporting.