Splitwise: Pluggable Splits and the Balance Sheet

8.1Problem Statement

Design the core engine behind an expense-sharing app like Splitwise: users belong to groups (and can also owe each other directly, outside any group), anyone can record a shared expense — a payer, a total amount, and a set of participants — and the system must track, at all times, exactly who owes whom and by how much. It must also let two people settle up: record a payment that reduces what one owes the other.

The expense itself supports three ways of dividing the bill, and how you divide it is the whole point of the interview:

• EQUAL — split evenly across participants.
• EXACT — each participant is assigned an explicit amount; the amounts must sum to the total.
• PERCENT — each participant is assigned a percentage; the percentages must sum to 100.

Non-functional constraints, stated outright in most versions of this prompt: the split logic must be a Strategy — a SplitStrategy interface — so a new split type drops in without touching the expense-recording code path, and each split type must validate its own inputs (EXACT sums to the total, PERCENT sums to 100) before any balance is touched.

The interface most versions of this prompt hand you is small and worth memorizing, because it bakes in every decision above:

enum class SplitType { EQUAL, EXACT, PERCENT };

class SplitStrategy {                 // Strategy
public:
    virtual std::vector<Split> computeSplits(double amount,
                                             const std::vector<User>& participants,
                                             const std::vector<double>& values) = 0;
    virtual ~SplitStrategy() = default;
};

class ExpenseManager {
public:
    void addExpense(const std::string& payerId,
                    double amount,
                    const std::vector<std::string>& participantIds,
                    SplitType type,
                    const std::vector<double>& values);   // values used by EXACT/PERCENT
    void settleUp(const std::string& fromId, const std::string& toId, double amount);
    std::map<std::string,double> getBalances(const std::string& userId) const;  // +owed, -owes
};

What the interviewer is actually scoring: whether the three split types live behind that one SplitStrategy interface with zero if (type == ...) branching anywhere near the math, whether the balance sheet is a correct pairwise model updated transactionally per expense, and whether getBalances reads as a near-trivial lookup rather than a recomputation over history.

8.2How to Approach

Start by mining the two sentences that decide the whole design. "Split logic must be a Strategy" names the pattern outright — build SplitStrategy plus three concrete classes, and let addExpense pick one by a single map lookup, never an if/else chain. And "validate splits (exact sums to total; percentages sum to 100)" tells you validation is per split type, so it lives inside each strategy, not inside the manager.

From there the nouns in the prompt hand you the class list almost for free. User and Group are dumb identity records. Split is one participant's slice of one expense. Expense is an immutable record of a payer, an amount, and the splits that resulted — it carries no logic, because the math already happened upstream in a strategy. ExpenseManager is the only class with real behavior: it resolves ids, delegates to a strategy, and folds the result into a balance sheet.

SplitStrategy

One interface, three concretes (EqualSplit / ExactSplit / PercentSplit), one client. Each concrete owns both its arithmetic and its own validation rule — the client never branches on the type to do math.

Balance sheet

A nested map of pairwise net balances between every pair of users who have ever transacted, kept antisymmetric so balance[A][B] == -balance[B][A] always holds.

Debt simplification (min-cash-flow)

Collapsing the pairwise sheet into one net figure per person, then greedily paying the largest debtor to the largest creditor until everyone is at zero. A good answer, not a provably minimal one.

Each strategy rejects before it produces anything: EqualSplit just needs a non-empty participant list; ExactSplit requires the given amounts to sum to the expense total; PercentSplit requires the given percentages to sum to 100. All three hand any share back as a plain Split{userId, amount}, and EqualSplit gives the last participant whatever remainder is left after dividing, so the shares always add back up to the original amount instead of drifting off by a cent.

The balance sheet is the other half of the score, and it's where naive answers leak time. The representation that makes every later operation trivial is a nested map keyed by user:

// balance_[A][B] = how much A owes B (positive) or B owes A (negative).
std::unordered_map<std::string,
    std::unordered_map<std::string, double>> balance_;

Applying one expense is then a batch of pairwise increments, nothing more: for every split except the payer's own (nobody owes themselves), balance_[participant][payer] += share and its mirror balance_[payer][participant] -= share keep the sheet antisymmetric. Settling up is the identical increment run in the paying direction — an expense and a payment are the same mechanism wearing two names. And because the outer key is the user, getBalances(userId) is a one-line read of balance_[userId], never a scan over history.

The headline follow-up, debt simplification, reuses the balance sheet rather than recomputing anything: sum each user's row into one net figure (creditor positive, debtor negative — the whole group always nets to zero), then greedily match the largest debtor against the largest creditor, transfer min(debt, credit), and repeat until both lists are exhausted. This collapses however many pairwise edges existed down to at most n−1 transactions for n people with a nonzero net. The honest caveat, worth saying unprompted: this greedy approach gives a good answer, not a provably minimal one — minimizing the transaction count exactly is NP-hard, closer to a partition problem than a graph one.

Two smaller follow-ups fall out of the same shape once you see it. Multi-currency just means storing each expense in its native currency and converting to a group base currency at record time via an injected ExchangeRateProvider — itself another Strategy — so the balance sheet math never changes. Editing or deleting an expense is reversible for the same reason settle-up is trivial: because the balance updates are increments rather than a recomputation, deleting an expense is just subtracting the same pairwise amounts you originally added, and editing is delete-then-re-add.

8.3Whole Solution

Everything above merged into one program: the three strategies with their per-type validation, the balance-sheet-backed ExpenseManager, the debt-simplification follow-up, and a driver that exercises EQUAL, EXACT, a rejected PERCENT, settle-up, and the simplified settle-up plan.

#include <algorithm>
#include <cmath>
#include <iostream>
#include <map>
#include <memory>
#include <stdexcept>
#include <string>
#include <unordered_map>
#include <vector>

// =====================================================================
// Enums & leaf records -- dumb data, no logic. The math happens either
// inside a SplitStrategy or inside ExpenseManager's balance sheet.
// =====================================================================

enum class SplitType { EQUAL, EXACT, PERCENT };

struct User {
    std::string id;
    std::string name;
};

// A Group just scopes "who owes whom" queries to a set of members;
// the balance sheet itself stays global and per-user-pair (see below).
struct Group {
    std::string name;
    std::vector<std::string> memberIds;
};

// One participant's slice of one expense.
struct Split {
    std::string userId;
    double amount = 0.0;   // this participant's share (>= 0)
};

// An immutable record of one shared cost. Carries no logic -- the
// math already happened in whichever SplitStrategy produced `splits`.
struct Expense {
    std::string payerId;
    double amount = 0.0;
    std::vector<Split> splits;   // sum of split.amount == amount
};

// =====================================================================
// SplitStrategy -- the interface -- plus its three concrete algorithms.
// Each concrete class owns both the math AND the validation rule for
// its type; ExpenseManager never branches on SplitType to do math.
// =====================================================================

class SplitStrategy {
public:
    virtual ~SplitStrategy() = default;
    virtual std::vector<Split> computeSplits(double amount,
                                              const std::vector<User>& participants,
                                              const std::vector<double>& values) = 0;
};

// EQUAL: ignore `values`, divide evenly. The last participant absorbs
// the rounding remainder so the splits always sum exactly to `amount`.
class EqualSplit : public SplitStrategy {
public:
    std::vector<Split> computeSplits(double amount,
                                      const std::vector<User>& participants,
                                      const std::vector<double>& /*values*/) override {
        if (participants.empty())
            throw std::invalid_argument("no participants");

        std::vector<Split> splits;
        double share = amount / participants.size();
        double assigned = 0.0;
        for (std::size_t i = 0; i < participants.size(); ++i) {
            // last participant gets the remainder so the sum is exact
            double s = (i + 1 == participants.size()) ? (amount - assigned) : share;
            splits.push_back({participants[i].id, s});
            assigned += s;
        }
        return splits;
    }
};

// EXACT: values[i] is participant i's amount; must sum to `amount`.
class ExactSplit : public SplitStrategy {
public:
    std::vector<Split> computeSplits(double amount,
                                      const std::vector<User>& participants,
                                      const std::vector<double>& values) override {
        if (values.size() != participants.size())
            throw std::invalid_argument("one exact value per participant required");

        double sum = 0.0;
        for (double v : values) sum += v;
        if (std::abs(sum - amount) > kEps)
            throw std::invalid_argument("exact splits must sum to the total");

        std::vector<Split> splits;
        for (std::size_t i = 0; i < participants.size(); ++i)
            splits.push_back({participants[i].id, values[i]});
        return splits;
    }
private:
    static constexpr double kEps = 1e-9;
};

// PERCENT: values[i] is participant i's percentage; must sum to 100.
class PercentSplit : public SplitStrategy {
public:
    std::vector<Split> computeSplits(double amount,
                                      const std::vector<User>& participants,
                                      const std::vector<double>& values) override {
        if (values.size() != participants.size())
            throw std::invalid_argument("one percentage per participant required");

        double sum = 0.0;
        for (double v : values) sum += v;
        if (std::abs(sum - 100.0) > kEps)
            throw std::invalid_argument("percentages must sum to 100");

        std::vector<Split> splits;
        for (std::size_t i = 0; i < participants.size(); ++i)
            splits.push_back({participants[i].id, amount * values[i] / 100.0});
        return splits;
    }
private:
    static constexpr double kEps = 1e-9;
};

// =====================================================================
// ExpenseManager -- the client. Reads like a sentence: resolve, then
// delegate to a strategy, then fold the result into the balance sheet.
// =====================================================================

class ExpenseManager {
public:
    ExpenseManager() {
        strategies_[SplitType::EQUAL]   = std::make_unique<EqualSplit>();
        strategies_[SplitType::EXACT]   = std::make_unique<ExactSplit>();
        strategies_[SplitType::PERCENT] = std::make_unique<PercentSplit>();
    }

    void addUser(const std::string& id, const std::string& name) {
        users_[id] = {id, name};
    }

    void addGroup(const std::string& groupName, const std::vector<std::string>& memberIds) {
        groups_[groupName] = {groupName, memberIds};
    }

    void addExpense(const std::string& payerId,
                    double amount,
                    const std::vector<std::string>& participantIds,
                    SplitType type,
                    const std::vector<double>& values) {
        // 1. resolve participants
        std::vector<User> participants;
        for (const auto& pid : participantIds)
            participants.push_back(users_.at(pid));   // throws if unknown

        // 2. delegate the math to the strategy (it validates internally)
        std::vector<Split> splits =
            strategies_.at(type)->computeSplits(amount, participants, values);

        // 3. keep the immutable record (needed to reverse an edit/delete)
        expenses_.push_back({payerId, amount, splits});

        // 4. fold splits into the pairwise balance sheet
        for (const auto& s : splits) {
            if (s.userId == payerId) continue;        // you don't owe yourself
            balance_[s.userId][payerId] += s.amount;
            balance_[payerId][s.userId] -= s.amount;
        }
    }

    void settleUp(const std::string& fromId, const std::string& toId, double amount) {
        // `from` pays `to`, reducing what `from` owes `to`. Same antisymmetric
        // increment as addExpense -- a payment and an expense share one mechanism.
        balance_[fromId][toId] -= amount;
        balance_[toId][fromId] += amount;
    }

    // +ve => the other user owes `userId`; -ve => `userId` owes the other user.
    std::map<std::string, double> getBalances(const std::string& userId) const {
        std::map<std::string, double> out;
        auto it = balance_.find(userId);
        if (it == balance_.end()) return out;
        for (const auto& [other, owed] : it->second)
            if (std::abs(owed) > 1e-9)                 // hide settled (zero) pairs
                out[other] = -owed;   // stored "userId owes other"; flip to the API's sign
        return out;
    }

    // Net position of every user with a nonzero balance: total owed to
    // them (+) or owed by them (-), collapsing the whole pairwise sheet
    // into one number per person. Feeds the debt-simplification follow-up.
    std::unordered_map<std::string, double> netBalances() const {
        std::unordered_map<std::string, double> net;
        for (const auto& [user, others] : balance_)
            for (const auto& [other, owed] : others)
                net[user] -= owed;   // owed = "user owes other"; net credit is the negative
        return net;
    }

private:
    std::unordered_map<std::string, User> users_;
    std::unordered_map<std::string, Group> groups_;
    std::vector<Expense> expenses_;
    std::unordered_map<SplitType, std::unique_ptr<SplitStrategy>> strategies_;
    // balance_[A][B] = how much A owes B (positive), or B owes A (if negative).
    // Kept antisymmetric: balance_[A][B] == -balance_[B][A] always.
    std::unordered_map<std::string, std::unordered_map<std::string, double>> balance_;
};

// =====================================================================
// Follow-up: debt simplification (min-cash-flow / greedy). Collapses the
// pairwise graph into net[user] figures, then greedily settles the
// largest debtor against the largest creditor. This is a GOOD answer,
// not a provably MINIMAL one -- exact minimization is NP-hard.
// =====================================================================

std::vector<std::pair<std::string, double>> simplifyDebts(
        std::unordered_map<std::string, double> net) {
    std::vector<std::pair<std::string, double>> creditors, debtors, txns;
    for (const auto& [u, v] : net) {
        if (v >  1e-9) creditors.push_back({u, v});
        if (v < -1e-9) debtors.push_back({u, -v});   // store as positive owed
    }
    // "largest debtor against largest creditor" needs both sorted descending.
    auto byAmountDesc = [](const auto& a, const auto& b) { return a.second > b.second; };
    std::sort(debtors.begin(), debtors.end(), byAmountDesc);
    std::sort(creditors.begin(), creditors.end(), byAmountDesc);

    std::size_t i = 0, j = 0;
    while (i < debtors.size() && j < creditors.size()) {
        double pay = std::min(debtors[i].second, creditors[j].second);
        txns.push_back({debtors[i].first + " -> " + creditors[j].first, pay});
        debtors[i].second   -= pay;
        creditors[j].second -= pay;
        if (debtors[i].second   < 1e-9) ++i;
        if (creditors[j].second < 1e-9) ++j;
    }
    return txns;
}

// =====================================================================
// Driver -- exercises all three strategies, a settle-up, one rejected
// (invalid) split, and the debt-simplification follow-up.
// =====================================================================

int main() {
    ExpenseManager mgr;
    mgr.addUser("alice", "Alice");
    mgr.addUser("bob",   "Bob");
    mgr.addUser("carol", "Carol");
    mgr.addGroup("weekend-trip", {"alice", "bob", "carol"});

    // Alice pays 90, split EQUALLY among all three -> bob & carol owe 30 each.
    mgr.addExpense("alice", 90.0, {"alice", "bob", "carol"}, SplitType::EQUAL, {});

    // Bob pays 100, EXACT: alice 60, bob 40 (sums to 100).
    mgr.addExpense("bob", 100.0, {"alice", "bob"}, SplitType::EXACT, {60.0, 40.0});

    std::cout << "-- alice's balances --\n";
    for (const auto& [other, amt] : mgr.getBalances("alice"))
        std::cout << "  alice vs " << other << ": " << amt << "\n";   // bob: -30

    // Carol settles her 30 to Alice.
    mgr.settleUp("carol", "alice", 30.0);
    std::cout << "-- alice's balances after carol settles --\n";
    for (const auto& [other, amt] : mgr.getBalances("alice"))
        std::cout << "  alice vs " << other << ": " << amt << "\n";   // carol pair now hidden

    // Carol pays 60, split EQUALLY among all three -> alice & bob now owe carol 20 each.
    mgr.addExpense("carol", 60.0, {"alice", "bob", "carol"}, SplitType::EQUAL, {});

    // Invalid PERCENT (sums to 90, not 100) is rejected, not silently applied.
    try {
        mgr.addExpense("alice", 50.0, {"alice", "bob"}, SplitType::PERCENT, {40.0, 50.0});
    } catch (const std::exception& e) {
        std::cout << "Rejected: " << e.what() << "\n";
    }

    // Follow-up: three pairwise edges now exist (alice-bob, alice-carol,
    // bob-carol). Debt simplification should collapse them into fewer txns.
    std::cout << "-- simplified settle-up plan --\n";
    for (const auto& [route, amt] : simplifyDebts(mgr.netBalances()))
        std::cout << "  " << route << " : " << amt << "\n";   // 2 txns, not 3

    return 0;
}