androidinterview.com

Low Level Design (LLD) Interview Questions

Design a Vending Machine

Tier: CommonDifficulty: EasyAsked of: Junior, MidAsked at: Google, Amazon, Microsoft, Apple, Oracle

Design a vending machine where a customer selects an item, inserts money and receives the item. They can cancel before buying and get their money back.

The problem

A drink costs 30 rupees. The customer inserts 40, buys it and receives 10 in change. If they cancel before buying, they receive the full 40 back and stock stays unchanged.

Agree on a small first version. One customer buys one item at a time. Money is represented as whole amounts, change is always available and dispensing succeeds. Limited coin stock and motor failures are follow-ups, not hidden assumptions about a real machine.

How to explain the design

“I store the products, the selected item and the customer's credit. Selection checks stock. Inserting money increases credit. Buying checks that payment is sufficient, reduces stock and returns the change. Cancelling returns the credit. Both buying and cancelling reset the current purchase.”

A Product contains its price and stock. A Purchase contains the item and change. VendingMachine owns the current interaction. No selection means idle, and a selected product means the machine is collecting payment.

Walk through a purchase

  1. Select a drink. Reject the selection if its stock is zero.
  2. Insert 40. The current credit becomes 40.
  3. Buy. Check that 40 covers the price of 30 before changing stock.
  4. Reduce stock by one, return 10 and reset the selection and credit.

Interview implementation

Use fields and checks for these two simple states. Add separate state classes only if the behavior grows enough to justify them.

Java

VendingMachine.java

package interview.vending;

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

public class VendingMachine {
    public record Product(String id, int price, int stock) {}
    public record Purchase(String productId, int change) {}
    private final Map<String, Product> products = new HashMap<>();
    private String selected;
    private int credit;

    public VendingMachine(List<Product> products) {
        for (Product product : products) {
            if (product.price() <= 0 || product.stock() < 0 || this.products.containsKey(product.id())) {
                throw new IllegalArgumentException("Invalid or duplicate product");
            }
            this.products.put(product.id(), product);
        }
    }

    public void select(String id) {
        if (selected != null) throw new IllegalStateException("Finish or cancel the current purchase");
        Product product = products.get(id);
        if (product == null || product.stock() == 0) throw new IllegalArgumentException("Product unavailable");
        selected = id;
    }

    public void insert(int amount) {
        if (selected == null) throw new IllegalStateException("Select a product first");
        if (amount <= 0) throw new IllegalArgumentException("Amount must be positive");
        credit += amount;
    }

    public Purchase buy() {
        Product product = products.get(selected);
        if (product == null) throw new IllegalStateException("Select a product first");
        if (credit < product.price()) throw new IllegalStateException("Not enough money");
        products.put(product.id(), new Product(product.id(), product.price(), product.stock() - 1));
        Purchase purchase = new Purchase(product.id(), credit - product.price());
        selected = null;
        credit = 0;
        return purchase;
    }

    public int cancel() {
        int refund = credit;
        selected = null;
        credit = 0;
        return refund;
    }
}

package interview.vending;

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

public class VendingMachine {
    public record Product(String id, int price, int stock) {}
    public record Purchase(String productId, int change) {}
    private final Map<String, Product> products = new HashMap<>();
    private String selected;
    private int credit;

    public VendingMachine(List<Product> products) {
        for (Product product : products) {
            if (product.price() <= 0 || product.stock() < 0 || this.products.containsKey(product.id())) {
                throw new IllegalArgumentException("Invalid or duplicate product");
            }
            this.products.put(product.id(), product);
        }
    }

    public void select(String id) {
        if (selected != null) throw new IllegalStateException("Finish or cancel the current purchase");
        Product product = products.get(id);
        if (product == null || product.stock() == 0) throw new IllegalArgumentException("Product unavailable");
        selected = id;
    }

    public void insert(int amount) {
        if (selected == null) throw new IllegalStateException("Select a product first");
        if (amount <= 0) throw new IllegalArgumentException("Amount must be positive");
        credit += amount;
    }

    public Purchase buy() {
        Product product = products.get(selected);
        if (product == null) throw new IllegalStateException("Select a product first");
        if (credit < product.price()) throw new IllegalStateException("Not enough money");
        products.put(product.id(), new Product(product.id(), product.price(), product.stock() - 1));
        Purchase purchase = new Purchase(product.id(), credit - product.price());
        selected = null;
        credit = 0;
        return purchase;
    }

    public int cancel() {
        int refund = credit;
        selected = null;
        credit = 0;
        return refund;
    }
}

Kotlin

VendingMachine.kt

package interview.vending

data class Product(val id: String, val price: Int, val stock: Int)
data class Purchase(val productId: String, val change: Int)

class VendingMachine(products: List<Product>) {
    private val products = products.associateBy { it.id }.toMutableMap()
    private var selected: String? = null
    private var credit = 0

    init {
        require(this.products.size == products.size)
        require(products.all { it.price > 0 && it.stock >= 0 })
    }

    fun select(id: String) {
        check(selected == null) { "Finish or cancel the current purchase" }
        val product = products[id] ?: error("Unknown product")
        check(product.stock > 0) { "Out of stock" }
        selected = id
    }

    fun insert(amount: Int) {
        check(selected != null) { "Select a product first" }
        require(amount > 0)
        credit += amount
    }

    fun buy(): Purchase {
        val product = products[selected] ?: error("Select a product first")
        check(credit >= product.price) { "Not enough money" }
        products[product.id] = product.copy(stock = product.stock - 1)
        val purchase = Purchase(product.id, credit - product.price)
        selected = null
        credit = 0
        return purchase
    }

    fun cancel(): Int {
        val refund = credit
        selected = null
        credit = 0
        return refund
    }
}

package interview.vending

data class Product(val id: String, val price: Int, val stock: Int)
data class Purchase(val productId: String, val change: Int)

class VendingMachine(products: List<Product>) {
    private val products = products.associateBy { it.id }.toMutableMap()
    private var selected: String? = null
    private var credit = 0

    init {
        require(this.products.size == products.size)
        require(products.all { it.price > 0 && it.stock >= 0 })
    }

    fun select(id: String) {
        check(selected == null) { "Finish or cancel the current purchase" }
        val product = products[id] ?: error("Unknown product")
        check(product.stock > 0) { "Out of stock" }
        selected = id
    }

    fun insert(amount: Int) {
        check(selected != null) { "Select a product first" }
        require(amount > 0)
        credit += amount
    }

    fun buy(): Purchase {
        val product = products[selected] ?: error("Select a product first")
        check(credit >= product.price) { "Not enough money" }
        products[product.id] = product.copy(stock = product.stock - 1)
        val purchase = Purchase(product.id, credit - product.price)
        selected = null
        credit = 0
        return purchase
    }

    fun cancel(): Int {
        val refund = credit
        selected = null
        credit = 0
        return refund
    }
}

Follow-up questions

Not enough money?

“I would reject the purchase but keep the selection and inserted money.” The customer can add the missing amount or cancel for a refund. For a product costing 30, inserting 20 and trying to buy should leave stock unchanged and keep the 20 credit.

Limited change?

“I would find an exact combination of available coins before dispensing.” The amount of money alone is not enough. If change is 6 and only coins of 5 and 2 are available, three coins of 2 work while choosing 5 first fails. Keep coin counts, find a valid plan, then commit the purchase and coin changes together. If no plan exists, keep the credit and let the customer add exact money or cancel.

Dispensing fails?

“I would add a dispensing state so a second purchase cannot start while hardware is working.” On a definite failure with no product delivered, keep the item in stock and return the credit. The current buy assumes success, so this extension must delay its stock change and reset until the dispenser reports the outcome. A timeout is uncertain and needs checking before an automatic refund or retry.

What should I test?

“Buying before selection or without enough money should fail without losing credit or stock.” Exact payment should return zero change. Cancelling should return the inserted amount, and cancelling again should return zero. After a successful purchase, a new customer should start with no selection and no credit.

This example checks change and then cancellation using the interview implementation.

Kotlin

val machine = VendingMachine(listOf(Product("water", 30, 2)))
machine.select("water")
machine.insert(50)
println(machine.buy().change) // 20
machine.select("water")
machine.insert(10)
println(machine.cancel()) // 10
println(machine.cancel()) // 0

Java

var machine = new VendingMachine(List.of(new VendingMachine.Product("water", 30, 2)));
machine.select("water");
machine.insert(50);
System.out.println(machine.buy().change()); // 20
machine.select("water");
machine.insert(10);
System.out.println(machine.cancel()); // 10
System.out.println(machine.cancel()); // 0
Extended implementation and optional features

This reference explores a larger scope. Use it after you can explain and write the interview version. Its extra types and features are not required for the scope above.

Java

com.androidinterview.vending.VendingMachine.java

package com.androidinterview.vending;

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

import com.androidinterview.vending.inventory.CoinBank;
import com.androidinterview.vending.inventory.Inventory;
import com.androidinterview.vending.model.Coin;
import com.androidinterview.vending.model.Product;
import com.androidinterview.vending.model.Purchase;
import com.androidinterview.vending.state.VendingMachineState;
import com.androidinterview.vending.state.VendingMachineState.Collecting;
import com.androidinterview.vending.state.VendingMachineState.Dispensing;
import com.androidinterview.vending.state.VendingMachineState.Idle;

// The machine. Every public method starts by checking the state, which is the
// state machine doing its job. There is not one boolean flag in here, and that
// is the point of the whole design.
public final class VendingMachine {

    // Stands in for the motor. Flip it to watch a sale unwind.
    public volatile boolean jammed = false;

    private final Inventory inventory;
    private final CoinBank bank;
    private VendingMachineState state = new Idle();

    public VendingMachine(Inventory inventory, CoinBank bank) {
        this.inventory = inventory;
        this.bank = bank;
    }

    public VendingMachineState state() {
        return state;
    }

    public void insert(Coin coin) {
        if (state instanceof Idle) {
            state = new Collecting(List.of(coin));
        } else if (state instanceof Collecting collecting) {
            List<Coin> coins = new ArrayList<>(collecting.inserted());
            coins.add(coin);
            state = new Collecting(coins);
        } else {
            throw new IllegalStateException("the machine is busy, take your item first");
        }
    }

    // Choosing does not hand anything over. It checks the sale can complete,
    // plans the change, and parks the machine one step from done.
    public void select(String code) {
        if (!(state instanceof Collecting collecting)) {
            throw new IllegalStateException("insert a coin first");
        }
        Product product = inventory.productAt(code)
                .orElseThrow(() -> new IllegalArgumentException("no slot " + code));
        if (!inventory.inStock(code)) {
            throw new IllegalStateException(product.name() + " is sold out");
        }
        int owed = collecting.paid() - product.price();
        if (owed < 0) {
            throw new IllegalStateException("insert " + (-owed) + " more");
        }
        Map<Coin, Integer> change = bank.planChange(owed);
        if (change == null) {
            // We cannot give the right change, so the sale never starts. The
            // refusal carries the coins, because a refusal that only says the
            // coins came back is the exact bug this design exists to avoid.
            List<Coin> refund = collecting.inserted();
            state = new Idle();
            throw new NoChangeException(refund);
        }
        state = new Dispensing(product, collecting.inserted(), change);
    }

    // The step that can fail, and the reason the design is shaped this way.
    //
    // Take the item, turn the motor, and only when the item is physically out
    // does the money change hands. If the motor jams, the item goes back on
    // the shelf and the machine drops back to holding the customer's coins, so
    // they can pick something else or press cancel and get them back. The
    // coins were never mixed into the float, which is what makes that easy.
    public Purchase dispense() {
        if (!(state instanceof Dispensing dispensing)) {
            throw new IllegalStateException("nothing to dispense");
        }
        Product product = dispensing.product();
        if (!inventory.take(product.code())) {
            // Someone restocked the slot to zero between selecting and
            // dispensing. Nothing has moved, so drop back to holding the coins.
            state = new Collecting(dispensing.inserted());
            throw new IllegalStateException(product.name() + " is sold out");
        }
        try {
            push(product);
        } catch (MotorJamException jam) {
            inventory.putBack(product.code());
            state = new Collecting(dispensing.inserted());
            throw jam;
        }
        bank.add(dispensing.inserted());
        bank.take(dispensing.change());
        state = new Idle();
        return new Purchase(product, dispensing.change());
    }

    // Cancel at any point before the motor turns and the coins come straight
    // back, because they were never mixed into the float.
    public List<Coin> cancel() {
        List<Coin> refund = List.of();
        if (state instanceof Collecting collecting) {
            refund = collecting.inserted();
        } else if (state instanceof Dispensing dispensing) {
            refund = dispensing.inserted();
        }
        state = new Idle();
        return refund;
    }

    private void push(Product product) {
        if (jammed) {
            throw new MotorJamException("motor jammed on slot " + product.code());
        }
    }

    // The refusal carries the coins, so a caller cannot handle it and forget to
    // give the money back.
    public static final class NoChangeException extends IllegalStateException {

        private final List<Coin> refund;

        public NoChangeException(List<Coin> refund) {
            super("no change available, coins returned");
            this.refund = List.copyOf(refund);
        }

        public List<Coin> refund() {
            return refund;
        }
    }

    // A jam has its own type so the catch in dispense cannot swallow a check
    // that failed for some other reason.
    public static final class MotorJamException extends IllegalStateException {

        public MotorJamException(String message) {
            super(message);
        }
    }
}

package com.androidinterview.vending;

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

import com.androidinterview.vending.inventory.CoinBank;
import com.androidinterview.vending.inventory.Inventory;
import com.androidinterview.vending.model.Coin;
import com.androidinterview.vending.model.Product;
import com.androidinterview.vending.model.Purchase;
import com.androidinterview.vending.state.VendingMachineState;
import com.androidinterview.vending.state.VendingMachineState.Collecting;
import com.androidinterview.vending.state.VendingMachineState.Dispensing;
import com.androidinterview.vending.state.VendingMachineState.Idle;

public final class VendingMachine {

    public volatile boolean jammed = false;

    private final Inventory inventory;
    private final CoinBank bank;
    private VendingMachineState state = new Idle();

    public VendingMachine(Inventory inventory, CoinBank bank) {
        this.inventory = inventory;
        this.bank = bank;
    }

    public VendingMachineState state() {
        return state;
    }

    public void insert(Coin coin) {
        if (state instanceof Idle) {
            state = new Collecting(List.of(coin));
        } else if (state instanceof Collecting collecting) {
            List<Coin> coins = new ArrayList<>(collecting.inserted());
            coins.add(coin);
            state = new Collecting(coins);
        } else {
            throw new IllegalStateException("the machine is busy, take your item first");
        }
    }

    public void select(String code) {
        if (!(state instanceof Collecting collecting)) {
            throw new IllegalStateException("insert a coin first");
        }
        Product product = inventory.productAt(code)
                .orElseThrow(() -> new IllegalArgumentException("no slot " + code));
        if (!inventory.inStock(code)) {
            throw new IllegalStateException(product.name() + " is sold out");
        }
        int owed = collecting.paid() - product.price();
        if (owed < 0) {
            throw new IllegalStateException("insert " + (-owed) + " more");
        }
        Map<Coin, Integer> change = bank.planChange(owed);
        if (change == null) {
            List<Coin> refund = collecting.inserted();
            state = new Idle();
            throw new NoChangeException(refund);
        }
        state = new Dispensing(product, collecting.inserted(), change);
    }

    public Purchase dispense() {
        if (!(state instanceof Dispensing dispensing)) {
            throw new IllegalStateException("nothing to dispense");
        }
        Product product = dispensing.product();
        if (!inventory.take(product.code())) {
            state = new Collecting(dispensing.inserted());
            throw new IllegalStateException(product.name() + " is sold out");
        }
        try {
            push(product);
        } catch (MotorJamException jam) {
            inventory.putBack(product.code());
            state = new Collecting(dispensing.inserted());
            throw jam;
        }
        bank.add(dispensing.inserted());
        bank.take(dispensing.change());
        state = new Idle();
        return new Purchase(product, dispensing.change());
    }

    public List<Coin> cancel() {
        List<Coin> refund = List.of();
        if (state instanceof Collecting collecting) {
            refund = collecting.inserted();
        } else if (state instanceof Dispensing dispensing) {
            refund = dispensing.inserted();
        }
        state = new Idle();
        return refund;
    }

    private void push(Product product) {
        if (jammed) {
            throw new MotorJamException("motor jammed on slot " + product.code());
        }
    }

    public static final class NoChangeException extends IllegalStateException {

        private final List<Coin> refund;

        public NoChangeException(List<Coin> refund) {
            super("no change available, coins returned");
            this.refund = List.copyOf(refund);
        }

        public List<Coin> refund() {
            return refund;
        }
    }

    public static final class MotorJamException extends IllegalStateException {

        public MotorJamException(String message) {
            super(message);
        }
    }
}

com.androidinterview.vending.inventory.CoinBank.java

package com.androidinterview.vending.inventory;

import java.util.EnumMap;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

import com.androidinterview.vending.model.Coin;

// The float, the coins the machine can give back. Separate from the coins a
// customer has put in this session, and that separation is the whole reason
// a cancelled sale can return the exact coins that went in.
public final class CoinBank {

    private final Map<Coin, Integer> counts = new EnumMap<>(Coin.class);

    public CoinBank() {
    }

    // A machine is stocked with a float at the start of the day, so seeding one
    // is construction rather than a call somebody can forget to make.
    public CoinBank(List<Coin> initialFloat) {
        add(initialFloat);
    }

    public void add(List<Coin> coins) {
        coins.forEach(coin -> counts.merge(coin, 1, Integer::sum));
    }

    public void take(Map<Coin, Integer> coins) {
        coins.forEach((coin, count) -> counts.merge(coin, -count, Integer::sum));
    }

    // Greedy change, largest coin first, and null when the float cannot make
    // the amount exactly. It plans without taking anything, so a sale that
    // cannot complete costs the float nothing.
    //
    // Greedy is what real machines do, and on an awkward float it can fail
    // where an exact answer exists. That is why machines have an exact change
    // light. Say so, and only write the search if you are asked for it.
    public Map<Coin, Integer> planChange(int amount) {
        Map<Coin, Integer> plan = new LinkedHashMap<>();
        int remaining = amount;
        for (Coin coin : Coin.values()) {
            int take = Math.min(remaining / coin.value, counts.getOrDefault(coin, 0));
            if (take > 0) {
                plan.put(coin, take);
                remaining -= take * coin.value;
            }
        }
        return remaining == 0 ? plan : null;
    }
}

package com.androidinterview.vending.inventory;

import java.util.EnumMap;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

import com.androidinterview.vending.model.Coin;

public final class CoinBank {

    private final Map<Coin, Integer> counts = new EnumMap<>(Coin.class);

    public CoinBank() {
    }

    public CoinBank(List<Coin> initialFloat) {
        add(initialFloat);
    }

    public void add(List<Coin> coins) {
        coins.forEach(coin -> counts.merge(coin, 1, Integer::sum));
    }

    public void take(Map<Coin, Integer> coins) {
        coins.forEach((coin, count) -> counts.merge(coin, -count, Integer::sum));
    }

    public Map<Coin, Integer> planChange(int amount) {
        Map<Coin, Integer> plan = new LinkedHashMap<>();
        int remaining = amount;
        for (Coin coin : Coin.values()) {
            int take = Math.min(remaining / coin.value, counts.getOrDefault(coin, 0));
            if (take > 0) {
                plan.put(coin, take);
                remaining -= take * coin.value;
            }
        }
        return remaining == 0 ? plan : null;
    }
}

com.androidinterview.vending.inventory.Inventory.java

package com.androidinterview.vending.inventory;

import java.util.HashMap;
import java.util.Map;
import java.util.Optional;

import com.androidinterview.vending.model.Product;

// The slots and how many of each are left. It owns stock and nothing else, so
// nothing else in the machine is allowed to change a count.
public final class Inventory {

    private final Map<String, Product> products = new HashMap<>();
    private final Map<String, Integer> counts = new HashMap<>();

    public void load(Product product, int count) {
        products.put(product.code(), product);
        counts.merge(product.code(), count, Integer::sum);
    }

    public Optional<Product> productAt(String code) {
        return Optional.ofNullable(products.get(code));
    }

    public boolean inStock(String code) {
        return counts.getOrDefault(code, 0) > 0;
    }

    // Take is optimistic and putBack undoes it. The machine takes the item
    // before the motor turns and puts it back if the motor fails, so a jam
    // never sells the same can twice.
    //
    // The guard lives here rather than at the call site, because this class
    // owns the count and a read followed by a write somewhere else is exactly
    // the shape that drives a slot negative.
    public boolean take(String code) {
        int left = counts.getOrDefault(code, 0);
        if (left <= 0) {
            return false;
        }
        counts.put(code, left - 1);
        return true;
    }

    public void putBack(String code) {
        counts.merge(code, 1, Integer::sum);
    }
}

package com.androidinterview.vending.inventory;

import java.util.HashMap;
import java.util.Map;
import java.util.Optional;

import com.androidinterview.vending.model.Product;

public final class Inventory {

    private final Map<String, Product> products = new HashMap<>();
    private final Map<String, Integer> counts = new HashMap<>();

    public void load(Product product, int count) {
        products.put(product.code(), product);
        counts.merge(product.code(), count, Integer::sum);
    }

    public Optional<Product> productAt(String code) {
        return Optional.ofNullable(products.get(code));
    }

    public boolean inStock(String code) {
        return counts.getOrDefault(code, 0) > 0;
    }

    public boolean take(String code) {
        int left = counts.getOrDefault(code, 0);
        if (left <= 0) {
            return false;
        }
        counts.put(code, left - 1);
        return true;
    }

    public void putBack(String code) {
        counts.merge(code, 1, Integer::sum);
    }
}

com.androidinterview.vending.model.Coin.java

package com.androidinterview.vending.model;

// Coins the machine accepts, largest first, which is the order change is made
// in. Everything in this design counts in whole units, because a vending
// machine has no concept of half a coin.
public enum Coin {
    FIFTY(50),
    TWENTY(20),
    TEN(10),
    FIVE(5);

    public final int value;

    Coin(int value) {
        this.value = value;
    }
}

package com.androidinterview.vending.model;

public enum Coin {
    FIFTY(50),
    TWENTY(20),
    TEN(10),
    FIVE(5);

    public final int value;

    Coin(int value) {
        this.value = value;
    }
}

com.androidinterview.vending.model.Product.java

package com.androidinterview.vending.model;

// What sits in a slot. The code is what the customer types, so it is the
// identity, and the price lives with the product rather than in a table
// somewhere else.
public record Product(String code, String name, int price) {}

package com.androidinterview.vending.model;

public record Product(String code, String name, int price) {}

com.androidinterview.vending.model.Purchase.java

package com.androidinterview.vending.model;

import java.util.Map;

// What falls out of the machine. The product and the coins that come back with
// it, together, because the customer gets both or neither.
public record Purchase(Product product, Map<Coin, Integer> change) {}

package com.androidinterview.vending.model;

import java.util.Map;

public record Purchase(Product product, Map<Coin, Integer> change) {}

com.androidinterview.vending.state.VendingMachineState.java

package com.androidinterview.vending.state;

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

import com.androidinterview.vending.model.Coin;
import com.androidinterview.vending.model.Product;

// What the machine is doing right now, as data. Three states, and every one of
// them carries exactly what that situation needs and nothing more.
//
// The transitions live in the machine rather than on these records, because
// every transition here needs the stock and the float, and those belong to the
// machine. A state that needs to be handed the whole machine to do its job is
// not really a state, it is a method with extra steps.
public sealed interface VendingMachineState {

    // Nothing owed, nothing owing.
    record Idle() implements VendingMachineState {}

    // Coins are in and no choice has been made. The coins are held as a list
    // and not added to the float, because until the product comes out they
    // still belong to the customer.
    record Collecting(List<Coin> inserted) implements VendingMachineState {

        public int paid() {
            return inserted.stream().mapToInt(coin -> coin.value).sum();
        }
    }

    // A choice has been made and the change has been planned, but the motor
    // has not turned yet. This is the state that exists so a failed dispense
    // has somewhere to fail from.
    record Dispensing(Product product, List<Coin> inserted, Map<Coin, Integer> change)
            implements VendingMachineState {}
}

package com.androidinterview.vending.state;

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

import com.androidinterview.vending.model.Coin;
import com.androidinterview.vending.model.Product;

public sealed interface VendingMachineState {

    record Idle() implements VendingMachineState {}

    record Collecting(List<Coin> inserted) implements VendingMachineState {

        public int paid() {
            return inserted.stream().mapToInt(coin -> coin.value).sum();
        }
    }

    record Dispensing(Product product, List<Coin> inserted, Map<Coin, Integer> change)
            implements VendingMachineState {}
}

Kotlin

com.androidinterview.vending.VendingMachine.kt

package com.androidinterview.vending

import com.androidinterview.vending.inventory.CoinBank
import com.androidinterview.vending.inventory.Inventory
import com.androidinterview.vending.model.Coin
import com.androidinterview.vending.model.Product
import com.androidinterview.vending.model.Purchase
import com.androidinterview.vending.state.VendingMachineState
import com.androidinterview.vending.state.VendingMachineState.Collecting
import com.androidinterview.vending.state.VendingMachineState.Dispensing
import com.androidinterview.vending.state.VendingMachineState.Idle

// The machine. Every public method starts by checking the state, and those
// checks are the state machine doing its job. There is not one boolean flag in
// here, which is the entire point of the design.
class VendingMachine(private val inventory: Inventory, private val bank: CoinBank) {

    // Stands in for the motor. Flip it to watch a sale unwind.
    @Volatile
    var jammed: Boolean = false

    var state: VendingMachineState = Idle
        private set

    fun insert(coin: Coin) {
        state = when (val current = state) {
            is Idle -> Collecting(listOf(coin))
            is Collecting -> Collecting(current.inserted + coin)
            is Dispensing -> error("the machine is busy, take your item first")
        }
    }

    // Choosing hands nothing over. It checks the sale can complete, plans the
    // change, and parks the machine one step from done.
    fun select(code: String) {
        val current = state
        check(current is Collecting) { "insert a coin first" }

        val product = requireNotNull(inventory.productAt(code)) { "no slot $code" }
        check(inventory.inStock(code)) { "${product.name} is sold out" }

        val owed = current.paid - product.price
        check(owed >= 0) { "insert ${-owed} more" }

        val change = bank.planChange(owed)
        if (change == null) {
            // We cannot give the right change, so the sale never starts. The
            // refusal carries the coins, because a refusal that only says the
            // coins came back is the exact bug this design exists to avoid.
            val refund = current.inserted
            state = Idle
            throw NoChangeException(refund)
        }
        state = Dispensing(product, current.inserted, change)
    }

    // The step that can fail, and the reason the design is shaped this way.
    //
    // Take the item, turn the motor, and only once the item is physically out
    // does the money change hands. If the motor jams, the item goes back on the
    // shelf and the machine drops back to holding the customer's coins, so they
    // can choose something else or press cancel. The coins were never mixed
    // into the float, which is what makes that easy.
    fun dispense(): Purchase {
        val current = state
        check(current is Dispensing) { "nothing to dispense" }

        if (!inventory.take(current.product.code)) {
            // Someone restocked the slot to zero between selecting and
            // dispensing. Nothing has moved, so drop back to holding the coins.
            state = Collecting(current.inserted)
            error("${current.product.name} is sold out")
        }
        try {
            push(current.product)
        } catch (jam: MotorJamException) {
            inventory.putBack(current.product.code)
            state = Collecting(current.inserted)
            throw jam
        }
        bank.add(current.inserted)
        bank.take(current.change)
        state = Idle
        return Purchase(current.product, current.change)
    }

    // Cancel any time before the motor turns and the coins come straight back,
    // because they were never mixed into the float.
    fun cancel(): List<Coin> {
        val refund = when (val current = state) {
            is Collecting -> current.inserted
            is Dispensing -> current.inserted
            is Idle -> emptyList()
        }
        state = Idle
        return refund
    }

    private fun push(product: Product) {
        if (jammed) throw MotorJamException("motor jammed on slot ${product.code}")
    }

    // The refusal carries the coins, so a caller cannot handle it and forget to
    // give the money back.
    class NoChangeException(val refund: List<Coin>) :
        IllegalStateException("no change available, coins returned")

    // A jam has its own type so the catch in dispense cannot swallow a check
    // that failed for some other reason.
    class MotorJamException(message: String) : IllegalStateException(message)
}

package com.androidinterview.vending

import com.androidinterview.vending.inventory.CoinBank
import com.androidinterview.vending.inventory.Inventory
import com.androidinterview.vending.model.Coin
import com.androidinterview.vending.model.Product
import com.androidinterview.vending.model.Purchase
import com.androidinterview.vending.state.VendingMachineState
import com.androidinterview.vending.state.VendingMachineState.Collecting
import com.androidinterview.vending.state.VendingMachineState.Dispensing
import com.androidinterview.vending.state.VendingMachineState.Idle

class VendingMachine(private val inventory: Inventory, private val bank: CoinBank) {

    @Volatile
    var jammed: Boolean = false

    var state: VendingMachineState = Idle
        private set

    fun insert(coin: Coin) {
        state = when (val current = state) {
            is Idle -> Collecting(listOf(coin))
            is Collecting -> Collecting(current.inserted + coin)
            is Dispensing -> error("the machine is busy, take your item first")
        }
    }

    fun select(code: String) {
        val current = state
        check(current is Collecting) { "insert a coin first" }

        val product = requireNotNull(inventory.productAt(code)) { "no slot $code" }
        check(inventory.inStock(code)) { "${product.name} is sold out" }

        val owed = current.paid - product.price
        check(owed >= 0) { "insert ${-owed} more" }

        val change = bank.planChange(owed)
        if (change == null) {
            val refund = current.inserted
            state = Idle
            throw NoChangeException(refund)
        }
        state = Dispensing(product, current.inserted, change)
    }

    fun dispense(): Purchase {
        val current = state
        check(current is Dispensing) { "nothing to dispense" }

        if (!inventory.take(current.product.code)) {
            state = Collecting(current.inserted)
            error("${current.product.name} is sold out")
        }
        try {
            push(current.product)
        } catch (jam: MotorJamException) {
            inventory.putBack(current.product.code)
            state = Collecting(current.inserted)
            throw jam
        }
        bank.add(current.inserted)
        bank.take(current.change)
        state = Idle
        return Purchase(current.product, current.change)
    }

    fun cancel(): List<Coin> {
        val refund = when (val current = state) {
            is Collecting -> current.inserted
            is Dispensing -> current.inserted
            is Idle -> emptyList()
        }
        state = Idle
        return refund
    }

    private fun push(product: Product) {
        if (jammed) throw MotorJamException("motor jammed on slot ${product.code}")
    }

    class NoChangeException(val refund: List<Coin>) :
        IllegalStateException("no change available, coins returned")

    class MotorJamException(message: String) : IllegalStateException(message)
}

com.androidinterview.vending.inventory.CoinBank.kt

package com.androidinterview.vending.inventory

import com.androidinterview.vending.model.Coin

// The float, the coins the machine can give back. It is deliberately separate
// from the coins a customer has put in this session, and that separation is
// what lets a cancelled sale return the exact coins that went in.
class CoinBank(coins: List<Coin> = emptyList()) {

    private val counts = coins.groupingBy { it }.eachCount().toMutableMap()

    fun add(coins: List<Coin>) = coins.forEach { counts.merge(it, 1, Int::plus) }

    fun take(coins: Map<Coin, Int>) = coins.forEach { (coin, n) -> counts.merge(coin, -n, Int::plus) }

    // Greedy change, largest coin first, and null when the float cannot make
    // the amount exactly. It plans without taking anything, so a sale that
    // cannot complete costs the float nothing.
    //
    // Greedy is what real machines do, and on an awkward float it can fail
    // where an exact answer exists. That is what the exact change light is
    // for. Say so, and only write the search if you are asked.
    fun planChange(amount: Int): Map<Coin, Int>? {
        var remaining = amount
        val plan = mutableMapOf<Coin, Int>()
        for (coin in Coin.entries) {
            val take = minOf(remaining / coin.value, counts[coin] ?: 0)
            if (take > 0) {
                plan[coin] = take
                remaining -= take * coin.value
            }
        }
        return plan.takeIf { remaining == 0 }
    }
}

package com.androidinterview.vending.inventory

import com.androidinterview.vending.model.Coin

class CoinBank(coins: List<Coin> = emptyList()) {

    private val counts = coins.groupingBy { it }.eachCount().toMutableMap()

    fun add(coins: List<Coin>) = coins.forEach { counts.merge(it, 1, Int::plus) }

    fun take(coins: Map<Coin, Int>) = coins.forEach { (coin, n) -> counts.merge(coin, -n, Int::plus) }

    fun planChange(amount: Int): Map<Coin, Int>? {
        var remaining = amount
        val plan = mutableMapOf<Coin, Int>()
        for (coin in Coin.entries) {
            val take = minOf(remaining / coin.value, counts[coin] ?: 0)
            if (take > 0) {
                plan[coin] = take
                remaining -= take * coin.value
            }
        }
        return plan.takeIf { remaining == 0 }
    }
}

com.androidinterview.vending.inventory.Inventory.kt

package com.androidinterview.vending.inventory

import com.androidinterview.vending.model.Product

// The slots and how many of each are left. It owns stock and nothing else, so
// nothing else in the machine may change a count.
class Inventory {

    private val products = mutableMapOf<String, Product>()
    private val counts = mutableMapOf<String, Int>()

    fun load(product: Product, count: Int) {
        products[product.code] = product
        counts.merge(product.code, count, Int::plus)
    }

    fun productAt(code: String): Product? = products[code]

    fun inStock(code: String): Boolean = (counts[code] ?: 0) > 0

    // take is optimistic and putBack undoes it. The machine takes the item
    // before the motor turns and puts it back if the motor fails, so a jam
    // never sells the same can twice.
    //
    // The guard lives here rather than at the call site, because this class
    // owns the count and a read followed by a write somewhere else is exactly
    // the shape that drives a slot negative.
    fun take(code: String): Boolean {
        val left = counts[code] ?: 0
        if (left <= 0) return false
        counts[code] = left - 1
        return true
    }

    fun putBack(code: String) {
        counts.merge(code, 1, Int::plus)
    }
}

package com.androidinterview.vending.inventory

import com.androidinterview.vending.model.Product

class Inventory {

    private val products = mutableMapOf<String, Product>()
    private val counts = mutableMapOf<String, Int>()

    fun load(product: Product, count: Int) {
        products[product.code] = product
        counts.merge(product.code, count, Int::plus)
    }

    fun productAt(code: String): Product? = products[code]

    fun inStock(code: String): Boolean = (counts[code] ?: 0) > 0

    fun take(code: String): Boolean {
        val left = counts[code] ?: 0
        if (left <= 0) return false
        counts[code] = left - 1
        return true
    }

    fun putBack(code: String) {
        counts.merge(code, 1, Int::plus)
    }
}

com.androidinterview.vending.model.Coin.kt

package com.androidinterview.vending.model

// Coins the machine accepts, largest first, which is the order change is made
// in. Everything here counts in whole units, because a vending machine has no
// concept of half a coin.
enum class Coin(val value: Int) {
    FIFTY(50),
    TWENTY(20),
    TEN(10),
    FIVE(5),
}

package com.androidinterview.vending.model

enum class Coin(val value: Int) {
    FIFTY(50),
    TWENTY(20),
    TEN(10),
    FIVE(5),
}

com.androidinterview.vending.model.Product.kt

package com.androidinterview.vending.model

// What sits in a slot. The code is what the customer types, so it is the
// identity, and the price lives with the product rather than in a table
// somewhere else.
data class Product(val code: String, val name: String, val price: Int)

package com.androidinterview.vending.model

data class Product(val code: String, val name: String, val price: Int)

com.androidinterview.vending.model.Purchase.kt

package com.androidinterview.vending.model

// What falls out of the machine, the product and the coins that come back with
// it, because the customer gets both or neither.
data class Purchase(val product: Product, val change: Map<Coin, Int>)

package com.androidinterview.vending.model

data class Purchase(val product: Product, val change: Map<Coin, Int>)

com.androidinterview.vending.state.VendingMachineState.kt

package com.androidinterview.vending.state

import com.androidinterview.vending.model.Coin
import com.androidinterview.vending.model.Product

// What the machine is doing right now, as data. Three states, and each carries
// exactly what that situation needs and nothing more.
//
// The transitions live in the machine rather than on these types, because every
// transition needs the stock and the float and the machine owns both. A state
// that has to be handed the whole machine to do its job is not a state, it is
// a method with extra steps.
sealed interface VendingMachineState {

    // Nothing owed, nothing owing.
    data object Idle : VendingMachineState

    // Coins are in and no choice has been made. They are held as a list rather
    // than added to the float, because until the product comes out they still
    // belong to the customer.
    data class Collecting(val inserted: List<Coin>) : VendingMachineState {
        val paid: Int get() = inserted.sumOf { it.value }
    }

    // A choice is made and the change is planned, but the motor has not turned.
    // This state exists so that a failed dispense has somewhere to fail from.
    data class Dispensing(
        val product: Product,
        val inserted: List<Coin>,
        val change: Map<Coin, Int>,
    ) : VendingMachineState
}

package com.androidinterview.vending.state

import com.androidinterview.vending.model.Coin
import com.androidinterview.vending.model.Product

sealed interface VendingMachineState {

    data object Idle : VendingMachineState

    data class Collecting(val inserted: List<Coin>) : VendingMachineState {
        val paid: Int get() = inserted.sumOf { it.value }
    }

    data class Dispensing(
        val product: Product,
        val inserted: List<Coin>,
        val change: Map<Coin, Int>,
    ) : VendingMachineState
}

Watch

16. Design Vending Machine (Hindi) | LLD of Vending Machine | State Design Pattern | LLD question (opens in a new tab)Concept && Coding - by Shrayansh
Design a Vending Machine | LLD | State Design Patterns | OOPS | Java (opens in a new tab)Riddhi Dutta
State Design Pattern | Build Vending Machine (UML & Code) | System Design (opens in a new tab)Coder Army