Home › Design Splitwise — Machine Coding Interview

Designing Splitwise — Expense Splitting System

⚡ Difficulty: Medium 🏷️ Patterns: Strategy, Observer, Facade 🏢 Asked at: PhonePe, Flipkart, Amazon, Razorpay

Functional Requirements

  1. Add expenses shared between users with a payer and multiple participants
  2. Multiple split strategies — EQUAL, EXACT (specify amounts), PERCENTAGE
  3. Track balances — who owes whom across all expenses
  4. Simplify debts — minimize the number of transactions needed to settle up
  5. Group expenses — organize expenses under a group (trip, apartment, etc.)
  6. Balance summary — show per-user net balance

Non-Functional Requirements

  1. Thread-safety — concurrent expense additions must not corrupt balances
  2. O(n log n) debt simplification — greedy with heaps
  3. Extensibility — add new split types (SHARE, WEIGHT) without modifying existing code
  4. Correctness — split amounts must always sum to the total expense amount

Core Entities

Entity Description
User Immutable — id, name, email
Group Named collection of users and their shared expenses
Expense Amount, payer, description, split strategy, participants
Split Strategy interface — computes each participant’s share
EqualSplit Divides equally among all participants
ExactSplit Each participant’s amount specified explicitly
PercentageSplit Each participant pays a percentage of total
BalanceSheet Tracks net balances between every pair of users
ExpenseManager Facade — orchestrates expenses, groups, balances, and simplification

Class Diagram

classDiagram
    class Split {
        <<interface>>
        +validate(totalAmount, participants) boolean
        +computeShares(totalAmount, participants) Map~User-Double~
    }
    class EqualSplit
    class ExactSplit
    class PercentageSplit
    class Expense {
        -String id
        -double amount
        -User payer
        -String description
        -Split splitStrategy
        -List~User~ participants
    }
    class BalanceSheet {
        -Map~String-Map~String-Double~~ balances
        +recordDebt(from, to, amount)
        +simplifyDebts() List~Transaction~
    }
    class ExpenseManager {
        -Map~String-User~ users
        -Map~String-Group~ groups
        -BalanceSheet balanceSheet
        +addExpense(expense)
        +getBalance(userId) Map
        +simplify() List~Transaction~
    }
    Split <|.. EqualSplit
    Split <|.. ExactSplit
    Split <|.. PercentageSplit
    Expense --> Split
    ExpenseManager --> BalanceSheet
    ExpenseManager --> Expense

Design Patterns

Pattern Where Why
Strategy Split with Equal/Exact/Percentage Swap split algorithm per expense, no if/else chain
Observer BalanceObserver on balance changes Notify UI or services when debts change
Facade ExpenseManager Single entry point hides balance tracking, group logic, simplification

How It All Fits Together

Here’s what happens when a user adds an expense:

  1. User calls addExpense() on ExpenseManager with amount, payer, participants, and split type
  2. ExpenseManager delegates to the Split strategy to compute each participant’s share
  3. Strategy validates the split (amounts sum to total? percentages sum to 100?)
  4. For each participant (excluding payer): a debt is recorded in the BalanceSheet
  5. BalanceSheet updates the net balance between payer and each participant
  6. All registered BalanceObservers are notified of the change
  7. Lock is released, expense is stored

When a user triggers debt simplification:

  1. BalanceSheet computes the net balance for each user (total owed - total lent)
  2. Users with positive net balance go into a max-heap (creditors)
  3. Users with negative net balance go into a min-heap (debtors)
  4. Greedy: pop the largest creditor and largest debtor, settle the minimum of the two amounts
  5. Push back any remainder, repeat until both heaps are empty
  6. Result: the minimum number of transactions to settle all debts

💡 This greedy approach works because we only care about net flows, not individual expense history. If A owes B $10 and B owes A $3, the net is A→B $7.

Complete Code

User

User is an immutable value object representing a person in the system. Equality is based on id so the same user across different groups is recognized as identical.

package splitwise.model;

public class User {
    private final String id;
    private final String name;
    private final String email;

    public User(String id, String name, String email) {
        this.id = id;
        this.name = name;
        this.email = email;
    }

    public String getId() { return id; }
    public String getName() { return name; }
    public String getEmail() { return email; }

    @Override
    public String toString() { return name + " (" + id + ")"; }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof User)) return false;
        return id.equals(((User) o).id);
    }

    @Override
    public int hashCode() { return id.hashCode(); }
}
from dataclasses import dataclass

@dataclass(frozen=True)
class User:
    id: str
    name: str
    email: str

    def __str__(self):
        return f"{self.name} ({self.id})"
#pragma once
#include <string>
#include <iostream>

class User {
public:
    std::string id;
    std::string name;
    std::string email;

    User(std::string id, std::string name, std::string email)
        : id(std::move(id)), name(std::move(name)), email(std::move(email)) {}

    bool operator==(const User& other) const { return id == other.id; }
    bool operator!=(const User& other) const { return !(*this == other); }

    friend std::ostream& operator<<(std::ostream& os, const User& u) {
        os << u.name << " (" << u.id << ")";
        return os;
    }
};

Transaction

A simple value object representing a settlement — one user pays another a specific amount. Used as the output of debt simplification.

package splitwise.model;

public class Transaction {
    private final User from;
    private final User to;
    private final double amount;

    public Transaction(User from, User to, double amount) {
        this.from = from;
        this.to = to;
        this.amount = amount;
    }

    public User getFrom() { return from; }
    public User getTo() { return to; }
    public double getAmount() { return amount; }

    @Override
    public String toString() {
        return from.getName() + " pays " + to.getName() + ": $" + String.format("%.2f", amount);
    }
}
@dataclass(frozen=True)
class Transaction:
    from_user: User
    to_user: User
    amount: float

    def __str__(self):
        return f"{self.from_user.name} pays {self.to_user.name}: ${self.amount:.2f}"
#pragma once
#include "User.h"

class Transaction {
public:
    User from;
    User to;
    double amount;

    Transaction(User from, User to, double amount)
        : from(std::move(from)), to(std::move(to)), amount(amount) {}

    friend std::ostream& operator<<(std::ostream& os, const Transaction& t) {
        os << t.from.name << " pays " << t.to.name << ": $" << t.amount;
        return os;
    }
};

Split (Strategy Interface)

This is the strategy interface that defines how an expense is divided among participants. EqualSplit, ExactSplit, and PercentageSplit are three implementations — but you could add WeightedSplit or ShareSplit without touching any existing code.

💡 Strategy pattern = define a family of algorithms, encapsulate each one, and make them interchangeable. Each expense picks its own split strategy at creation time. Zero if/else branching in ExpenseManager.

package splitwise.strategy;

import splitwise.model.User;
import java.util.List;
import java.util.Map;

public interface Split {
    boolean validate(double totalAmount, List<User> participants);
    Map<User, Double> computeShares(double totalAmount, List<User> participants);
}
from abc import ABC, abstractmethod

class Split(ABC):
    @abstractmethod
    def validate(self, total_amount: float, participants: list[User]) -> bool:
        pass

    @abstractmethod
    def compute_shares(self, total_amount: float, participants: list[User]) -> dict[User, float]:
        pass
#pragma once
#include <vector>
#include <unordered_map>
#include "User.h"

struct UserHash {
    size_t operator()(const User& u) const {
        return std::hash<std::string>{}(u.id);
    }
};

class Split {
public:
    virtual ~Split() = default;
    virtual bool validate(double totalAmount, const std::vector<User>& participants) = 0;
    virtual std::unordered_map<User, double, UserHash> computeShares(
        double totalAmount, const std::vector<User>& participants) = 0;
};

EqualSplit

The simplest strategy — divides the total equally among all participants. Validation just checks that there’s at least one participant.

package splitwise.strategy;

import splitwise.model.User;
import java.util.*;

public class EqualSplit implements Split {

    @Override
    public boolean validate(double totalAmount, List<User> participants) {
        return participants != null && !participants.isEmpty() && totalAmount > 0;
    }

    @Override
    public Map<User, Double> computeShares(double totalAmount, List<User> participants) {
        Map<User, Double> shares = new HashMap<>();
        double each = totalAmount / participants.size();
        for (User u : participants) {
            shares.put(u, each);
        }
        return shares;
    }
}
class EqualSplit(Split):
    def validate(self, total_amount: float, participants: list[User]) -> bool:
        return len(participants) > 0 and total_amount > 0

    def compute_shares(self, total_amount: float, participants: list[User]) -> dict[User, float]:
        each = total_amount / len(participants)
        return {u: each for u in participants}
#pragma once
#include "Split.h"

class EqualSplit : public Split {
public:
    bool validate(double totalAmount, const std::vector<User>& participants) override {
        return !participants.empty() && totalAmount > 0;
    }

    std::unordered_map<User, double, UserHash> computeShares(
            double totalAmount, const std::vector<User>& participants) override {
        std::unordered_map<User, double, UserHash> shares;
        double each = totalAmount / participants.size();
        for (const auto& u : participants) {
            shares[u] = each;
        }
        return shares;
    }
};

ExactSplit

Each participant’s share is specified explicitly. Validation ensures the individual amounts sum exactly to the total expense. This is useful when items have different prices (e.g., everyone ordered different dishes).

package splitwise.strategy;

import splitwise.model.User;
import java.util.*;

public class ExactSplit implements Split {
    private final Map<User, Double> exactAmounts;

    public ExactSplit(Map<User, Double> exactAmounts) {
        this.exactAmounts = exactAmounts;
    }

    @Override
    public boolean validate(double totalAmount, List<User> participants) {
        if (exactAmounts == null || exactAmounts.isEmpty()) return false;
        double sum = exactAmounts.values().stream().mapToDouble(Double::doubleValue).sum();
        return Math.abs(sum - totalAmount) < 0.01;
    }

    @Override
    public Map<User, Double> computeShares(double totalAmount, List<User> participants) {
        return new HashMap<>(exactAmounts);
    }
}
class ExactSplit(Split):
    def __init__(self, exact_amounts: dict[User, float]):
        self._exact_amounts = exact_amounts

    def validate(self, total_amount: float, participants: list[User]) -> bool:
        if not self._exact_amounts:
            return False
        return abs(sum(self._exact_amounts.values()) - total_amount) < 0.01

    def compute_shares(self, total_amount: float, participants: list[User]) -> dict[User, float]:
        return dict(self._exact_amounts)
#pragma once
#include "Split.h"
#include <cmath>

class ExactSplit : public Split {
    std::unordered_map<User, double, UserHash> exactAmounts;

public:
    ExactSplit(std::unordered_map<User, double, UserHash> amounts)
        : exactAmounts(std::move(amounts)) {}

    bool validate(double totalAmount, const std::vector<User>& participants) override {
        if (exactAmounts.empty()) return false;
        double sum = 0;
        for (const auto& [user, amt] : exactAmounts) sum += amt;
        return std::abs(sum - totalAmount) < 0.01;
    }

    std::unordered_map<User, double, UserHash> computeShares(
            double totalAmount, const std::vector<User>& participants) override {
        return exactAmounts;
    }
};

PercentageSplit

Each participant is assigned a percentage of the total. Validation checks that all percentages sum to 100. Useful for unequal splits like rent based on room size.

package splitwise.strategy;

import splitwise.model.User;
import java.util.*;

public class PercentageSplit implements Split {
    private final Map<User, Double> percentages;

    public PercentageSplit(Map<User, Double> percentages) {
        this.percentages = percentages;
    }

    @Override
    public boolean validate(double totalAmount, List<User> participants) {
        if (percentages == null || percentages.isEmpty()) return false;
        double sum = percentages.values().stream().mapToDouble(Double::doubleValue).sum();
        return Math.abs(sum - 100.0) < 0.01 && totalAmount > 0;
    }

    @Override
    public Map<User, Double> computeShares(double totalAmount, List<User> participants) {
        Map<User, Double> shares = new HashMap<>();
        for (Map.Entry<User, Double> entry : percentages.entrySet()) {
            shares.put(entry.getKey(), totalAmount * entry.getValue() / 100.0);
        }
        return shares;
    }
}
class PercentageSplit(Split):
    def __init__(self, percentages: dict[User, float]):
        self._percentages = percentages

    def validate(self, total_amount: float, participants: list[User]) -> bool:
        if not self._percentages:
            return False
        return abs(sum(self._percentages.values()) - 100.0) < 0.01 and total_amount > 0

    def compute_shares(self, total_amount: float, participants: list[User]) -> dict[User, float]:
        return {u: total_amount * pct / 100.0 for u, pct in self._percentages.items()}
#pragma once
#include "Split.h"
#include <cmath>

class PercentageSplit : public Split {
    std::unordered_map<User, double, UserHash> percentages;

public:
    PercentageSplit(std::unordered_map<User, double, UserHash> pcts)
        : percentages(std::move(pcts)) {}

    bool validate(double totalAmount, const std::vector<User>& participants) override {
        if (percentages.empty()) return false;
        double sum = 0;
        for (const auto& [user, pct] : percentages) sum += pct;
        return std::abs(sum - 100.0) < 0.01 && totalAmount > 0;
    }

    std::unordered_map<User, double, UserHash> computeShares(
            double totalAmount, const std::vector<User>& participants) override {
        std::unordered_map<User, double, UserHash> shares;
        for (const auto& [user, pct] : percentages) {
            shares[user] = totalAmount * pct / 100.0;
        }
        return shares;
    }
};

Expense

An expense records who paid, how much, for what, and how it’s split. It holds a reference to its Split strategy and the list of participants. The expense is immutable once created.

package splitwise.model;

import splitwise.strategy.Split;
import java.util.*;

public class Expense {
    private final String id;
    private final double amount;
    private final User payer;
    private final String description;
    private final Split splitStrategy;
    private final List<User> participants;

    public Expense(String id, double amount, User payer, String description,
                   Split splitStrategy, List<User> participants) {
        this.id = id;
        this.amount = amount;
        this.payer = payer;
        this.description = description;
        this.splitStrategy = splitStrategy;
        this.participants = Collections.unmodifiableList(participants);
    }

    public String getId() { return id; }
    public double getAmount() { return amount; }
    public User getPayer() { return payer; }
    public String getDescription() { return description; }
    public Split getSplitStrategy() { return splitStrategy; }
    public List<User> getParticipants() { return participants; }

    @Override
    public String toString() {
        return description + " — $" + String.format("%.2f", amount) + " paid by " + payer.getName();
    }
}
class Expense:
    def __init__(self, id: str, amount: float, payer: User,
                 description: str, split_strategy: Split, participants: list[User]):
        self.id = id
        self.amount = amount
        self.payer = payer
        self.description = description
        self.split_strategy = split_strategy
        self.participants = list(participants)

    def __str__(self):
        return f"{self.description} — ${self.amount:.2f} paid by {self.payer.name}"
#pragma once
#include <string>
#include <vector>
#include <memory>
#include "User.h"
#include "Split.h"

class Expense {
public:
    std::string id;
    double amount;
    User payer;
    std::string description;
    std::shared_ptr<Split> splitStrategy;
    std::vector<User> participants;

    Expense(std::string id, double amount, User payer, std::string description,
            std::shared_ptr<Split> strategy, std::vector<User> participants)
        : id(std::move(id)), amount(amount), payer(std::move(payer)),
          description(std::move(description)), splitStrategy(std::move(strategy)),
          participants(std::move(participants)) {}

    friend std::ostream& operator<<(std::ostream& os, const Expense& e) {
        os << e.description << " — $" << e.amount << " paid by " << e.payer.name;
        return os;
    }
};

Group

A group holds a set of users and their shared expenses — like a trip or an apartment. It provides a scoped view of expenses for that context.

package splitwise.model;

import java.util.*;

public class Group {
    private final String id;
    private final String name;
    private final List<User> members;
    private final List<Expense> expenses;

    public Group(String id, String name, List<User> members) {
        this.id = id;
        this.name = name;
        this.members = new ArrayList<>(members);
        this.expenses = new ArrayList<>();
    }

    public void addExpense(Expense expense) { expenses.add(expense); }
    public String getId() { return id; }
    public String getName() { return name; }
    public List<User> getMembers() { return Collections.unmodifiableList(members); }
    public List<Expense> getExpenses() { return Collections.unmodifiableList(expenses); }

    @Override
    public String toString() { return name + " (" + members.size() + " members)"; }
}
class Group:
    def __init__(self, id: str, name: str, members: list[User]):
        self.id = id
        self.name = name
        self.members = list(members)
        self.expenses: list[Expense] = []

    def add_expense(self, expense: Expense):
        self.expenses.append(expense)

    def __str__(self):
        return f"{self.name} ({len(self.members)} members)"
#pragma once
#include <string>
#include <vector>
#include "User.h"
#include "Expense.h"

class Group {
public:
    std::string id;
    std::string name;
    std::vector<User> members;
    std::vector<Expense> expenses;

    Group(std::string id, std::string name, std::vector<User> members)
        : id(std::move(id)), name(std::move(name)), members(std::move(members)) {}

    void addExpense(const Expense& expense) { expenses.push_back(expense); }

    friend std::ostream& operator<<(std::ostream& os, const Group& g) {
        os << g.name << " (" << g.members.size() << " members)";
        return os;
    }
};

BalanceSheet

The core accounting engine. Tracks net balances between every pair of users using a nested map: balances[A][B] = X means A owes B $X. When a new debt is recorded, it automatically nets against any existing reverse debt (if B already owed A, it reduces that first).

💡 We store directed net balances rather than individual transactions. This means getBalance(userId) is O(n) where n = number of users, not number of expenses. The tradeoff: we lose individual expense history in the balance sheet (but Expense objects are stored separately).

The debt simplification algorithm uses a greedy approach with heaps:

package splitwise.core;

import splitwise.model.Transaction;
import splitwise.model.User;

import java.util.*;

public class BalanceSheet {
    // balances[A_id][B_id] = amount A owes B (positive means A owes B)
    private final Map<String, Map<String, Double>> balances = new HashMap<>();
    private final Map<String, User> userMap = new HashMap<>();

    public void recordDebt(User from, User to, double amount) {
        if (amount <= 0 || from.equals(to)) return;
        userMap.putIfAbsent(from.getId(), from);
        userMap.putIfAbsent(to.getId(), to);

        // Net the balances: if to already owes from, reduce that first
        double reverseDebt = getDirectDebt(to.getId(), from.getId());
        if (reverseDebt >= amount) {
            setDebt(to.getId(), from.getId(), reverseDebt - amount);
        } else {
            setDebt(to.getId(), from.getId(), 0);
            double existing = getDirectDebt(from.getId(), to.getId());
            setDebt(from.getId(), to.getId(), existing + (amount - reverseDebt));
        }
    }

    public Map<String, Double> getBalanceForUser(String userId) {
        Map<String, Double> result = new HashMap<>();
        // What this user owes others (negative for them)
        Map<String, Double> owes = balances.getOrDefault(userId, Collections.emptyMap());
        for (Map.Entry<String, Double> e : owes.entrySet()) {
            if (e.getValue() > 0.01) result.put(e.getKey(), -e.getValue());
        }
        // What others owe this user (positive for them)
        for (Map.Entry<String, Map<String, Double>> entry : balances.entrySet()) {
            if (entry.getKey().equals(userId)) continue;
            double amt = entry.getValue().getOrDefault(userId, 0.0);
            if (amt > 0.01) result.put(entry.getKey(), amt);
        }
        return result;
    }

    public List<Transaction> simplifyDebts() {
        // Step 1: Compute net balance for each user
        Map<String, Double> netBalance = new HashMap<>();
        for (Map.Entry<String, Map<String, Double>> entry : balances.entrySet()) {
            String fromId = entry.getKey();
            for (Map.Entry<String, Double> debt : entry.getValue().entrySet()) {
                String toId = debt.getKey();
                double amt = debt.getValue();
                if (amt < 0.01) continue;
                netBalance.merge(fromId, -amt, Double::sum);  // from owes, so negative
                netBalance.merge(toId, amt, Double::sum);     // to is owed, so positive
            }
        }

        // Step 2: Separate into creditors (positive) and debtors (negative)
        // Max-heap for creditors, min-heap (max of abs) for debtors
        PriorityQueue<double[]> creditors = new PriorityQueue<>((a, b) -> Double.compare(b[1], a[1]));
        PriorityQueue<double[]> debtors = new PriorityQueue<>((a, b) -> Double.compare(a[1], b[1]));

        List<String> userIds = new ArrayList<>(netBalance.keySet());
        for (String uid : userIds) {
            double bal = netBalance.get(uid);
            if (bal > 0.01) creditors.offer(new double[]{userIds.indexOf(uid), bal});
            else if (bal < -0.01) debtors.offer(new double[]{userIds.indexOf(uid), bal});
        }

        // Step 3: Greedy matching
        List<Transaction> transactions = new ArrayList<>();
        while (!creditors.isEmpty() && !debtors.isEmpty()) {
            double[] creditor = creditors.poll();
            double[] debtor = debtors.poll();

            double settle = Math.min(creditor[1], -debtor[1]);
            User fromUser = userMap.get(userIds.get((int) debtor[0]));
            User toUser = userMap.get(userIds.get((int) creditor[0]));
            transactions.add(new Transaction(fromUser, toUser, settle));

            creditor[1] -= settle;
            debtor[1] += settle;

            if (creditor[1] > 0.01) creditors.offer(creditor);
            if (debtor[1] < -0.01) debtors.offer(debtor);
        }
        return transactions;
    }

    private double getDirectDebt(String fromId, String toId) {
        return balances.getOrDefault(fromId, Collections.emptyMap()).getOrDefault(toId, 0.0);
    }

    private void setDebt(String fromId, String toId, double amount) {
        balances.computeIfAbsent(fromId, k -> new HashMap<>()).put(toId, amount);
    }
}
import heapq
from collections import defaultdict

class BalanceSheet:
    def __init__(self):
        # balances[from_id][to_id] = amount from owes to
        self._balances: dict[str, dict[str, float]] = defaultdict(lambda: defaultdict(float))
        self._user_map: dict[str, User] = {}

    def record_debt(self, from_user: User, to_user: User, amount: float):
        if amount <= 0 or from_user == to_user:
            return
        self._user_map[from_user.id] = from_user
        self._user_map[to_user.id] = to_user

        # Net against reverse debt
        reverse = self._balances[to_user.id][from_user.id]
        if reverse >= amount:
            self._balances[to_user.id][from_user.id] = reverse - amount
        else:
            self._balances[to_user.id][from_user.id] = 0
            self._balances[from_user.id][to_user.id] += (amount - reverse)

    def get_balance_for_user(self, user_id: str) -> dict[str, float]:
        result = {}
        # What this user owes others
        for to_id, amt in self._balances[user_id].items():
            if amt > 0.01:
                result[to_id] = -amt
        # What others owe this user
        for from_id, debts in self._balances.items():
            if from_id == user_id:
                continue
            amt = debts.get(user_id, 0)
            if amt > 0.01:
                result[from_id] = amt
        return result

    def simplify_debts(self) -> list[Transaction]:
        # Step 1: Net balances
        net: dict[str, float] = defaultdict(float)
        for from_id, debts in self._balances.items():
            for to_id, amt in debts.items():
                if amt < 0.01:
                    continue
                net[from_id] -= amt
                net[to_id] += amt

        # Step 2: Separate creditors and debtors
        # Max-heap for creditors (negate for heapq), min-heap for debtors
        creditors = []  # (-amount, user_id) — max-heap via negation
        debtors = []    # (amount, user_id) — min-heap (most negative first)

        for uid, bal in net.items():
            if bal > 0.01:
                heapq.heappush(creditors, (-bal, uid))
            elif bal < -0.01:
                heapq.heappush(debtors, (bal, uid))

        # Step 3: Greedy matching
        transactions = []
        while creditors and debtors:
            credit_amt, credit_id = heapq.heappop(creditors)
            debt_amt, debt_id = heapq.heappop(debtors)

            settle = min(-credit_amt, -debt_amt)
            from_user = self._user_map[debt_id]
            to_user = self._user_map[credit_id]
            transactions.append(Transaction(from_user, to_user, round(settle, 2)))

            remainder_credit = -credit_amt - settle
            remainder_debt = -debt_amt - settle

            if remainder_credit > 0.01:
                heapq.heappush(creditors, (-remainder_credit, credit_id))
            if remainder_debt > 0.01:
                heapq.heappush(debtors, (-remainder_debt, debt_id))

        return transactions
#pragma once
#include <unordered_map>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
#include "User.h"
#include "Transaction.h"

class BalanceSheet {
    // balances[fromId][toId] = amount from owes to
    std::unordered_map<std::string, std::unordered_map<std::string, double>> balances;
    std::unordered_map<std::string, User> userMap;

    double getDirectDebt(const std::string& fromId, const std::string& toId) {
        auto it = balances.find(fromId);
        if (it == balances.end()) return 0;
        auto it2 = it->second.find(toId);
        return it2 == it->second.end() ? 0 : it2->second;
    }

    void setDebt(const std::string& fromId, const std::string& toId, double amount) {
        balances[fromId][toId] = amount;
    }

public:
    void recordDebt(const User& from, const User& to, double amount) {
        if (amount <= 0 || from == to) return;
        userMap.emplace(from.id, from);
        userMap.emplace(to.id, to);

        double reverse = getDirectDebt(to.id, from.id);
        if (reverse >= amount) {
            setDebt(to.id, from.id, reverse - amount);
        } else {
            setDebt(to.id, from.id, 0);
            double existing = getDirectDebt(from.id, to.id);
            setDebt(from.id, to.id, existing + (amount - reverse));
        }
    }

    std::vector<Transaction> simplifyDebts() {
        // Net balances
        std::unordered_map<std::string, double> net;
        for (auto& [fromId, debts] : balances) {
            for (auto& [toId, amt] : debts) {
                if (amt < 0.01) continue;
                net[fromId] -= amt;
                net[toId] += amt;
            }
        }

        // Max-heap for creditors, max-heap (by abs) for debtors
        using Pair = std::pair<double, std::string>;
        std::priority_queue<Pair> creditors;
        std::priority_queue<Pair> debtors;

        for (auto& [uid, bal] : net) {
            if (bal > 0.01) creditors.push({bal, uid});
            else if (bal < -0.01) debtors.push({-bal, uid});
        }

        std::vector<Transaction> transactions;
        while (!creditors.empty() && !debtors.empty()) {
            auto [creditAmt, creditId] = creditors.top(); creditors.pop();
            auto [debtAmt, debtId] = debtors.top(); debtors.pop();

            double settle = std::min(creditAmt, debtAmt);
            transactions.emplace_back(userMap.at(debtId), userMap.at(creditId), settle);

            if (creditAmt - settle > 0.01) creditors.push({creditAmt - settle, creditId});
            if (debtAmt - settle > 0.01) debtors.push({debtAmt - settle, debtId});
        }
        return transactions;
    }
};

BalanceObserver

Observer interface for balance change notifications. UI components, notification services, or logging can implement this to react when debts change — without the core system knowing about them.

💡 Observer pattern = decouple the “what happened” from “who cares.” ExpenseManager fires events; any number of observers can listen without modifying the manager.

package splitwise.observer;

import splitwise.model.Expense;

public interface BalanceObserver {
    void onExpenseAdded(Expense expense);
    void onBalanceChanged(String userId, double newNetBalance);
}
class BalanceObserver:
    def on_expense_added(self, expense: Expense):
        pass

    def on_balance_changed(self, user_id: str, new_net_balance: float):
        pass
#pragma once
#include <string>
#include "Expense.h"

class BalanceObserver {
public:
    virtual ~BalanceObserver() = default;
    virtual void onExpenseAdded(const Expense& expense) = 0;
    virtual void onBalanceChanged(const std::string& userId, double newNetBalance) = 0;
};

ExpenseManager (Facade)

The single entry point for all operations. It orchestrates user registration, group creation, expense addition, balance queries, and debt simplification. All public methods are thread-safe via ReentrantLock.

💡 Facade pattern = provide a simplified interface to a complex subsystem. Clients call addExpense() on the manager — they never interact directly with BalanceSheet, Split strategies, or Groups.

package splitwise;

import splitwise.core.BalanceSheet;
import splitwise.model.*;
import splitwise.observer.BalanceObserver;
import splitwise.strategy.Split;

import java.util.*;
import java.util.concurrent.CopyOnWriteArrayList;
import java.util.concurrent.locks.ReentrantLock;

public class ExpenseManager {
    private final Map<String, User> users = new HashMap<>();
    private final Map<String, Group> groups = new HashMap<>();
    private final List<Expense> expenses = new ArrayList<>();
    private final BalanceSheet balanceSheet = new BalanceSheet();
    private final ReentrantLock lock = new ReentrantLock();
    private final List<BalanceObserver> observers = new CopyOnWriteArrayList<>();

    public void addUser(User user) {
        lock.lock();
        try {
            users.put(user.getId(), user);
        } finally { lock.unlock(); }
    }

    public void createGroup(String groupId, String name, List<User> members) {
        lock.lock();
        try {
            Group group = new Group(groupId, name, members);
            groups.put(groupId, group);
            for (User u : members) users.putIfAbsent(u.getId(), u);
        } finally { lock.unlock(); }
    }

    public void addExpense(String expenseId, double amount, User payer,
                           String description, Split splitStrategy,
                           List<User> participants, String groupId) {
        lock.lock();
        try {
            if (!splitStrategy.validate(amount, participants)) {
                throw new IllegalArgumentException("Invalid split: amounts do not match total");
            }

            Expense expense = new Expense(expenseId, amount, payer, description,
                                          splitStrategy, participants);
            expenses.add(expense);

            if (groupId != null && groups.containsKey(groupId)) {
                groups.get(groupId).addExpense(expense);
            }

            // Compute shares and record debts
            Map<User, Double> shares = splitStrategy.computeShares(amount, participants);
            for (Map.Entry<User, Double> entry : shares.entrySet()) {
                User participant = entry.getKey();
                double share = entry.getValue();
                if (!participant.equals(payer) && share > 0) {
                    balanceSheet.recordDebt(participant, payer, share);
                }
            }

            // Notify observers
            for (BalanceObserver obs : observers) {
                obs.onExpenseAdded(expense);
            }
        } finally { lock.unlock(); }
    }

    public Map<String, Double> getBalance(String userId) {
        lock.lock();
        try {
            return balanceSheet.getBalanceForUser(userId);
        } finally { lock.unlock(); }
    }

    public List<Transaction> simplifyDebts() {
        lock.lock();
        try {
            return balanceSheet.simplifyDebts();
        } finally { lock.unlock(); }
    }

    public void addObserver(BalanceObserver observer) {
        observers.add(observer);
    }

    public Group getGroup(String groupId) {
        return groups.get(groupId);
    }

    public List<Expense> getAllExpenses() {
        return Collections.unmodifiableList(expenses);
    }
}
import threading

class ExpenseManager:
    def __init__(self):
        self._users: dict[str, User] = {}
        self._groups: dict[str, Group] = {}
        self._expenses: list[Expense] = []
        self._balance_sheet = BalanceSheet()
        self._lock = threading.Lock()
        self._observers: list[BalanceObserver] = []

    def add_user(self, user: User):
        with self._lock:
            self._users[user.id] = user

    def create_group(self, group_id: str, name: str, members: list[User]):
        with self._lock:
            group = Group(group_id, name, members)
            self._groups[group_id] = group
            for u in members:
                self._users.setdefault(u.id, u)

    def add_expense(self, expense_id: str, amount: float, payer: User,
                    description: str, split_strategy: Split,
                    participants: list[User], group_id: str = None):
        with self._lock:
            if not split_strategy.validate(amount, participants):
                raise ValueError("Invalid split: amounts do not match total")

            expense = Expense(expense_id, amount, payer, description,
                              split_strategy, participants)
            self._expenses.append(expense)

            if group_id and group_id in self._groups:
                self._groups[group_id].add_expense(expense)

            # Compute shares and record debts
            shares = split_strategy.compute_shares(amount, participants)
            for participant, share in shares.items():
                if participant != payer and share > 0:
                    self._balance_sheet.record_debt(participant, payer, share)

            # Notify observers
            for obs in self._observers:
                obs.on_expense_added(expense)

    def get_balance(self, user_id: str) -> dict[str, float]:
        with self._lock:
            return self._balance_sheet.get_balance_for_user(user_id)

    def simplify_debts(self) -> list[Transaction]:
        with self._lock:
            return self._balance_sheet.simplify_debts()

    def add_observer(self, observer: BalanceObserver):
        self._observers.append(observer)

    def get_group(self, group_id: str) -> Group:
        return self._groups.get(group_id)

    def get_all_expenses(self) -> list[Expense]:
        return list(self._expenses)
#pragma once
#include <mutex>
#include <vector>
#include <unordered_map>
#include <memory>
#include <stdexcept>
#include "User.h"
#include "Group.h"
#include "Expense.h"
#include "BalanceSheet.h"
#include "BalanceObserver.h"
#include "Split.h"

class ExpenseManager {
    std::unordered_map<std::string, User> users;
    std::unordered_map<std::string, Group> groups;
    std::vector<Expense> expenses;
    BalanceSheet balanceSheet;
    std::mutex mtx;
    std::vector<BalanceObserver*> observers;

public:
    void addUser(const User& user) {
        std::lock_guard<std::mutex> lock(mtx);
        users.emplace(user.id, user);
    }

    void createGroup(const std::string& groupId, const std::string& name,
                     const std::vector<User>& members) {
        std::lock_guard<std::mutex> lock(mtx);
        groups.emplace(groupId, Group(groupId, name, members));
        for (const auto& u : members) users.emplace(u.id, u);
    }

    void addExpense(const std::string& expenseId, double amount, const User& payer,
                    const std::string& description, std::shared_ptr<Split> splitStrategy,
                    const std::vector<User>& participants, const std::string& groupId = "") {
        std::lock_guard<std::mutex> lock(mtx);
        if (!splitStrategy->validate(amount, participants)) {
            throw std::invalid_argument("Invalid split: amounts do not match total");
        }

        Expense expense(expenseId, amount, payer, description, splitStrategy, participants);
        expenses.push_back(expense);

        if (!groupId.empty()) {
            auto it = groups.find(groupId);
            if (it != groups.end()) it->second.addExpense(expense);
        }

        auto shares = splitStrategy->computeShares(amount, participants);
        for (const auto& [participant, share] : shares) {
            if (participant != payer && share > 0) {
                balanceSheet.recordDebt(participant, payer, share);
            }
        }

        for (auto* obs : observers) obs->onExpenseAdded(expense);
    }

    std::vector<Transaction> simplifyDebts() {
        std::lock_guard<std::mutex> lock(mtx);
        return balanceSheet.simplifyDebts();
    }

    void addObserver(BalanceObserver* obs) { observers.push_back(obs); }
};

Demo (Runnable)

The demo proves the entire system works end-to-end: creates users, forms a group, adds expenses with all three split types, shows individual balances, and runs debt simplification to minimize transactions.

package splitwise;

import splitwise.model.*;
import splitwise.observer.BalanceObserver;
import splitwise.strategy.*;

import java.util.*;

public class Demo {
    public static void main(String[] args) {
        System.out.println("══════ SPLITWISE DEMO ══════\n");

        ExpenseManager manager = new ExpenseManager();
        manager.addObserver(new BalanceObserver() {
            public void onExpenseAdded(Expense e) {
                System.out.println("  📝 Expense added: " + e);
            }
            public void onBalanceChanged(String uid, double bal) {}
        });

        // Create users
        User alice = new User("u1", "Alice", "alice@email.com");
        User bob = new User("u2", "Bob", "bob@email.com");
        User charlie = new User("u3", "Charlie", "charlie@email.com");
        User diana = new User("u4", "Diana", "diana@email.com");

        manager.addUser(alice);
        manager.addUser(bob);
        manager.addUser(charlie);
        manager.addUser(diana);

        // Create a trip group
        manager.createGroup("g1", "Goa Trip",
            Arrays.asList(alice, bob, charlie, diana));
        System.out.println("Group created: Goa Trip\n");

        // --- EQUAL SPLIT ---
        System.out.println("--- Equal Split: Dinner $240 paid by Alice ---");
        manager.addExpense("e1", 240.0, alice, "Dinner",
            new EqualSplit(),
            Arrays.asList(alice, bob, charlie, diana), "g1");

        // --- EXACT SPLIT ---
        System.out.println("\n--- Exact Split: Shopping $500 paid by Bob ---");
        Map<User, Double> exactAmounts = new HashMap<>();
        exactAmounts.put(alice, 100.0);
        exactAmounts.put(bob, 200.0);
        exactAmounts.put(charlie, 50.0);
        exactAmounts.put(diana, 150.0);
        manager.addExpense("e2", 500.0, bob, "Shopping",
            new ExactSplit(exactAmounts),
            Arrays.asList(alice, bob, charlie, diana), "g1");

        // --- PERCENTAGE SPLIT ---
        System.out.println("\n--- Percentage Split: Hotel $1000 paid by Charlie ---");
        Map<User, Double> percentages = new HashMap<>();
        percentages.put(alice, 30.0);
        percentages.put(bob, 30.0);
        percentages.put(charlie, 20.0);
        percentages.put(diana, 20.0);
        manager.addExpense("e3", 1000.0, charlie, "Hotel",
            new PercentageSplit(percentages),
            Arrays.asList(alice, bob, charlie, diana), "g1");

        // --- BALANCES ---
        System.out.println("\n--- Balances ---");
        for (User u : Arrays.asList(alice, bob, charlie, diana)) {
            Map<String, Double> bal = manager.getBalance(u.getId());
            System.out.println("  " + u.getName() + ":");
            for (Map.Entry<String, Double> e : bal.entrySet()) {
                String label = e.getValue() > 0 ? "is owed" : "owes";
                System.out.printf("    %s $%.2f (user %s)%n", label,
                    Math.abs(e.getValue()), e.getKey());
            }
        }

        // --- SIMPLIFY DEBTS ---
        System.out.println("\n--- Simplified Debts (Minimum Transactions) ---");
        List<Transaction> simplified = manager.simplifyDebts();
        for (Transaction t : simplified) {
            System.out.println("  " + t);
        }
        System.out.println("  Total transactions: " + simplified.size());

        System.out.println("\n══════ DONE ══════");
    }
}
def demo():
    print("══════ SPLITWISE DEMO ══════\n")

    class ConsolePrinter(BalanceObserver):
        def on_expense_added(self, expense):
            print(f"  📝 Expense added: {expense}")
        def on_balance_changed(self, user_id, new_net_balance):
            pass

    manager = ExpenseManager()
    manager.add_observer(ConsolePrinter())

    # Create users
    alice = User("u1", "Alice", "alice@email.com")
    bob = User("u2", "Bob", "bob@email.com")
    charlie = User("u3", "Charlie", "charlie@email.com")
    diana = User("u4", "Diana", "diana@email.com")

    manager.add_user(alice)
    manager.add_user(bob)
    manager.add_user(charlie)
    manager.add_user(diana)

    # Create a trip group
    manager.create_group("g1", "Goa Trip", [alice, bob, charlie, diana])
    print("Group created: Goa Trip\n")

    # --- EQUAL SPLIT ---
    print("--- Equal Split: Dinner $240 paid by Alice ---")
    manager.add_expense("e1", 240.0, alice, "Dinner",
        EqualSplit(), [alice, bob, charlie, diana], "g1")

    # --- EXACT SPLIT ---
    print("\n--- Exact Split: Shopping $500 paid by Bob ---")
    exact_amounts = {alice: 100.0, bob: 200.0, charlie: 50.0, diana: 150.0}
    manager.add_expense("e2", 500.0, bob, "Shopping",
        ExactSplit(exact_amounts), [alice, bob, charlie, diana], "g1")

    # --- PERCENTAGE SPLIT ---
    print("\n--- Percentage Split: Hotel $1000 paid by Charlie ---")
    percentages = {alice: 30.0, bob: 30.0, charlie: 20.0, diana: 20.0}
    manager.add_expense("e3", 1000.0, charlie, "Hotel",
        PercentageSplit(percentages), [alice, bob, charlie, diana], "g1")

    # --- BALANCES ---
    print("\n--- Balances ---")
    for u in [alice, bob, charlie, diana]:
        bal = manager.get_balance(u.id)
        print(f"  {u.name}:")
        for other_id, amount in bal.items():
            label = "is owed" if amount > 0 else "owes"
            print(f"    {label} ${abs(amount):.2f} (user {other_id})")

    # --- SIMPLIFY DEBTS ---
    print("\n--- Simplified Debts (Minimum Transactions) ---")
    simplified = manager.simplify_debts()
    for t in simplified:
        print(f"  {t}")
    print(f"  Total transactions: {len(simplified)}")

    print("\n══════ DONE ══════")

if __name__ == "__main__":
    demo()
#include <iostream>
#include <vector>
#include <memory>
#include "ExpenseManager.h"
#include "EqualSplit.h"
#include "ExactSplit.h"
#include "PercentageSplit.h"

class ConsolePrinter : public BalanceObserver {
public:
    void onExpenseAdded(const Expense& e) override {
        std::cout << "  📝 Expense added: " << e << "\n";
    }
    void onBalanceChanged(const std::string& uid, double bal) override {}
};

int main() {
    std::cout << "══════ SPLITWISE DEMO ══════\n\n";

    ExpenseManager manager;
    ConsolePrinter printer;
    manager.addObserver(&printer);

    // Create users
    User alice("u1", "Alice", "alice@email.com");
    User bob("u2", "Bob", "bob@email.com");
    User charlie("u3", "Charlie", "charlie@email.com");
    User diana("u4", "Diana", "diana@email.com");

    manager.addUser(alice);
    manager.addUser(bob);
    manager.addUser(charlie);
    manager.addUser(diana);

    // Create group
    manager.createGroup("g1", "Goa Trip", {alice, bob, charlie, diana});
    std::cout << "Group created: Goa Trip\n\n";

    // --- EQUAL SPLIT ---
    std::cout << "--- Equal Split: Dinner $240 paid by Alice ---\n";
    manager.addExpense("e1", 240.0, alice, "Dinner",
        std::make_shared<EqualSplit>(),
        {alice, bob, charlie, diana}, "g1");

    // --- EXACT SPLIT ---
    std::cout << "\n--- Exact Split: Shopping $500 paid by Bob ---\n";
    std::unordered_map<User, double, UserHash> exactAmounts = {
        {alice, 100.0}, {bob, 200.0}, {charlie, 50.0}, {diana, 150.0}
    };
    manager.addExpense("e2", 500.0, bob, "Shopping",
        std::make_shared<ExactSplit>(exactAmounts),
        {alice, bob, charlie, diana}, "g1");

    // --- PERCENTAGE SPLIT ---
    std::cout << "\n--- Percentage Split: Hotel $1000 paid by Charlie ---\n";
    std::unordered_map<User, double, UserHash> pcts = {
        {alice, 30.0}, {bob, 30.0}, {charlie, 20.0}, {diana, 20.0}
    };
    manager.addExpense("e3", 1000.0, charlie, "Hotel",
        std::make_shared<PercentageSplit>(pcts),
        {alice, bob, charlie, diana}, "g1");

    // --- SIMPLIFY DEBTS ---
    std::cout << "\n--- Simplified Debts (Minimum Transactions) ---\n";
    auto simplified = manager.simplifyDebts();
    for (const auto& t : simplified) {
        std::cout << "  " << t << "\n";
    }
    std::cout << "  Total transactions: " << simplified.size() << "\n";

    std::cout << "\n══════ DONE ══════\n";
    return 0;
}

Debt Simplification — Algorithm Walkthrough

flowchart LR
    A[Compute Net Balances] --> B[Separate Creditors and Debtors]
    B --> C[Max-Heap Creditors]
    B --> D[Min-Heap Debtors]
    C --> E[Greedy: Match Largest Creditor with Largest Debtor]
    D --> E
    E --> F[Settle min of both amounts]
    F --> G{Both heaps empty?}
    G -->|No| E
    G -->|Yes| H[Return Minimal Transactions]

Example: Alice is owed $100, Bob is owed $50, Charlie owes $80, Diana owes $70.

How to Extend

Feature Implementation
Weighted Split New WeightedSplit — divide proportionally by weight values
Settlement Track settled transactions, reduce balances accordingly
Expense Editing Reverse old splits, apply new splits atomically
Currency Support Decorator on Split that converts amounts before computing
Recurring Expenses Scheduler that calls addExpense() on a cron

What Interviewers Look For

  1. ✅ Strategy pattern for split types — no if/else chains
  2. ✅ Debt simplification — greedy with heaps, O(n log n)
  3. ✅ Thread-safety — locks on all mutable shared state
  4. ✅ Validation — splits must sum to total before recording
  5. ✅ Observer — decoupled notifications on balance changes
  6. ✅ Facade — ExpenseManager hides subsystem complexity
  7. ✅ Runnable demo — all three split types exercised end-to-end

💬 Comments