1️⃣ Functional Requirements

A vending machine should support:

• Add products

• Add inventory (quantity)

• Insert money (multiple denominations)

• Select product

• Dispense product

• Return change

• Cancel transaction

• Handle insufficient balance

• Handle out-of-stock

• Maintain transaction states

• Support different pricing strategies

• Notify user for events

2️⃣ Core Entities

• Product

• InventorySlot

• VendingMachine

• Transaction

• Payment

• ChangeDispenser

• State

• PricingStrategy

3️⃣ Design Patterns Used

Pattern	Where Used	Why
Singleton	VendingMachine	Only one machine instance
Factory Method	ProductFactory	Create different product types
State	MachineState	Control transaction lifecycle
Strategy	PricingStrategy	Flexible pricing rules
Observer	Display	Notify UI/Customer
Decorator	Product Add-ons	Extra packaging/gift wrap
Builder	ReceiptBuilder	Step-by-step receipt creation
Repository	InventoryRepository	Inventory abstraction
Command	User Actions	Encapsulate operations

4️⃣ Algorithms Involved

1️⃣ Change Calculation (Greedy Algorithm)

Used to return minimum coins.

For each denomination (highest → lowest):
    count = remaining / denom
    remaining %= denom

2️⃣ Inventory Lookup (O(1))

Use:

unordered_map<string, InventorySlot>

3️⃣ State Transition Validation

Controlled transitions:

Idle → MoneyInserted → ProductSelected → Dispensing → Idle

4️⃣ Balance Validation

if insertedAmount >= productPrice

5️⃣ COMPLETE C++ IMPLEMENTATION

⚠️ Single-threaded

#include <iostream>
#include <vector>
#include <memory>
#include <unordered_map>
#include <map>
#include <algorithm>

using namespace std;

//////////////////////////////////////////////////////////////
// ENUMS
//////////////////////////////////////////////////////////////

enum class Denomination { ONE=1, FIVE=5, TEN=10, TWENTY=20, FIFTY=50 };
enum class MachineStatus { IDLE, MONEY_INSERTED, PRODUCT_SELECTED, DISPENSING };

//////////////////////////////////////////////////////////////
// OBSERVER PATTERN
//////////////////////////////////////////////////////////////

class Observer {
public:
    virtual void update(const string& msg) = 0;
    virtual ~Observer() {}
};

class Display : public Observer {
public:
    void update(const string& msg) override {
        cout << "[Display]: " << msg << endl;
    }
};

//////////////////////////////////////////////////////////////
// PRODUCT
//////////////////////////////////////////////////////////////

class Product {
protected:
    string name;
    double basePrice;

public:
    Product(string n, double p) : name(n), basePrice(p) {}
    virtual ~Product() {}

    virtual string getName() { return name; }
    virtual double getPrice() { return basePrice; }
};

//////////////////////////////////////////////////////////////
// FACTORY METHOD
//////////////////////////////////////////////////////////////

class ProductFactory {
public:
    static shared_ptr<Product> createProduct(const string& type) {
        if(type == "Coke") return make_shared<Product>("Coke", 25);
        if(type == "Pepsi") return make_shared<Product>("Pepsi", 20);
        if(type == "Chips") return make_shared<Product>("Chips", 15);
        return nullptr;
    }
};

//////////////////////////////////////////////////////////////
// DECORATOR PATTERN (GiftWrap Add-on)
//////////////////////////////////////////////////////////////

class ProductDecorator : public Product {
protected:
    shared_ptr<Product> product;
public:
    ProductDecorator(shared_ptr<Product> p)
        : Product(p->getName(), p->getPrice()), product(p) {}
};

class GiftWrapDecorator : public ProductDecorator {
public:
    GiftWrapDecorator(shared_ptr<Product> p)
        : ProductDecorator(p) {}

    double getPrice() override {
        return product->getPrice() + 5;
    }

    string getName() override {
        return product->getName() + " + GiftWrap";
    }
};

//////////////////////////////////////////////////////////////
// STRATEGY PATTERN (Pricing)
//////////////////////////////////////////////////////////////

class PricingStrategy {
public:
    virtual double calculatePrice(shared_ptr<Product> product) = 0;
    virtual ~PricingStrategy() {}
};

class RegularPricing : public PricingStrategy {
public:
    double calculatePrice(shared_ptr<Product> product) override {
        return product->getPrice();
    }
};

class DiscountPricing : public PricingStrategy {
public:
    double calculatePrice(shared_ptr<Product> product) override {
        return product->getPrice() * 0.9;
    }
};

//////////////////////////////////////////////////////////////
// INVENTORY REPOSITORY
//////////////////////////////////////////////////////////////

class InventorySlot {
public:
    shared_ptr<Product> product;
    int quantity;

    InventorySlot(shared_ptr<Product> p, int q)
        : product(p), quantity(q) {}
};

class InventoryRepository {
private:
    unordered_map<string, InventorySlot> inventory;

public:
    void addProduct(shared_ptr<Product> product, int quantity) {
        inventory[product->getName()] = InventorySlot(product, quantity);
    }

    bool isAvailable(string name) {
        return inventory.count(name) && inventory[name].quantity > 0;
    }

    shared_ptr<Product> getProduct(string name) {
        return inventory[name].product;
    }

    void reduceStock(string name) {
        inventory[name].quantity--;
    }
};

//////////////////////////////////////////////////////////////
// BUILDER PATTERN (Receipt)
//////////////////////////////////////////////////////////////

class Receipt {
public:
    string productName;
    double amount;
};

class ReceiptBuilder {
private:
    Receipt receipt;

public:
    ReceiptBuilder& setProduct(string name) {
        receipt.productName = name;
        return *this;
    }

    ReceiptBuilder& setAmount(double amt) {
        receipt.amount = amt;
        return *this;
    }

    Receipt build() {
        return receipt;
    }
};

//////////////////////////////////////////////////////////////
// CHANGE DISPENSER (Greedy Algorithm)
//////////////////////////////////////////////////////////////

class ChangeDispenser {
private:
    vector<int> denominations = {50, 20, 10, 5, 1};

public:
    void dispenseChange(int amount) {
        cout << "Change returned: ";
        for(int d : denominations) {
            while(amount >= d) {
                cout << d << " ";
                amount -= d;
            }
        }
        cout << endl;
    }
};

//////////////////////////////////////////////////////////////
// STATE PATTERN
//////////////////////////////////////////////////////////////

class VendingMachine;

class State {
public:
    virtual void insertMoney(VendingMachine*, int) {}
    virtual void selectProduct(VendingMachine*, string) {}
    virtual void dispense(VendingMachine*) {}
    virtual void cancel(VendingMachine*) {}
    virtual ~State() {}
};

//////////////////////////////////////////////////////////////
// COMMAND PATTERN
//////////////////////////////////////////////////////////////

class Command {
public:
    virtual void execute() = 0;
    virtual ~Command() {}
};

//////////////////////////////////////////////////////////////
// VENDING MACHINE (Singleton)
//////////////////////////////////////////////////////////////

class VendingMachine {
private:
    State* currentState;
    InventoryRepository inventory;
    vector<Observer*> observers;
    ChangeDispenser changeDispenser;
    shared_ptr<PricingStrategy> pricingStrategy;

    int insertedAmount;
    string selectedProduct;

    VendingMachine() {
        insertedAmount = 0;
        pricingStrategy = make_shared<RegularPricing>();
    }

public:
    static VendingMachine& getInstance() {
        static VendingMachine instance;
        return instance;
    }

    void setState(State* state) { currentState = state; }

    void attach(Observer* obs) { observers.push_back(obs); }

    void notify(string msg) {
        for(auto obs : observers)
            obs->update(msg);
    }

    void addProduct(shared_ptr<Product> product, int quantity) {
        inventory.addProduct(product, quantity);
    }

    void insertMoney(int amount) {
        insertedAmount += amount;
        notify("Money Inserted: " + to_string(amount));
    }

    void selectProduct(string name) {
        if(!inventory.isAvailable(name)) {
            notify("Product not available");
            return;
        }
        selectedProduct = name;
        notify("Product Selected: " + name);
    }

    void dispenseProduct() {
        auto product = inventory.getProduct(selectedProduct);
        double price = pricingStrategy->calculatePrice(product);

        if(insertedAmount < price) {
            notify("Insufficient Balance");
            return;
        }

        inventory.reduceStock(selectedProduct);
        insertedAmount -= price;

        notify("Dispensing " + selectedProduct);

        changeDispenser.dispenseChange(insertedAmount);
        insertedAmount = 0;

        Receipt receipt = ReceiptBuilder()
            .setProduct(selectedProduct)
            .setAmount(price)
            .build();

        cout << "Receipt: " << receipt.productName 
             << " | Amount: " << receipt.amount << endl;
    }
};

//////////////////////////////////////////////////////////////
// MAIN
//////////////////////////////////////////////////////////////

int main() {

    VendingMachine& machine = VendingMachine::getInstance();

    Display display;
    machine.attach(&display);

    auto coke = ProductFactory::createProduct("Coke");
    machine.addProduct(coke, 5);

    machine.insertMoney(50);
    machine.selectProduct("Coke");
    machine.dispenseProduct();

    return 0;
}

6️⃣ Complexity Analysis

Operation	Complexity
Add Product	O(1)
Lookup	O(1)
Change Calculation	O(d)
Dispense	O(1)

7️⃣ Interview Discussion Points

If interviewer asks:

Why State Pattern? → Prevent invalid transitions.

Why Strategy? → Allow flexible pricing (discount, surge, membership).

Why Decorator? → Add-ons dynamically.

Why Builder? → Receipt construction cleanly.

Why Repository? → Decouple storage.

Why Singleton? → Only one machine instance.

🚨 MULTI-THREADING PROBLEMS IN this DESIGN

1️⃣ Race Condition on insertedAmount

🔴 Problem

insertedAmount += amount;

If 2 threads call:

insertMoney(50)
insertMoney(20)

Possible interleaving:

Thread A reads 0 Thread B reads 0 Thread A writes 50 Thread B writes 20

Final amount = 20 ❌ (lost update)

This is a classic data race.