LayoffReady

Design Splitwise

Mediumobject-oriented design · design patterns · strategy pattern · greedy · concurrency · java⏱ 16 min readAsked at Amazon, Microsoft, Flipkart, Uber, PhonePeUpdated

Design an expense-sharing app with pluggable equal, exact and percent splits, a consistent balance sheet and a debt simplification algorithm that minimises payments.

Requirements

Splitwise is a favourite because it mixes three skills in one hour: clean modelling (users, groups, expenses, splits), a pluggable rule (how an expense is divided) and a small algorithm (who should pay whom so that everyone is square with the fewest payments).

Functional

  • Users can form groups (a trip, a flat) and add expenses inside a group.
  • Each expense has one payer, a total and a list of participants. It can be split:
    • Equally: $100 among 3 people.
    • By exact amounts: Alice $10, Bob $20, Carol $30, which must add up to the total.
    • By percentages: 40% / 30% / 30%, which must add up to 100%.
  • Show each user's balances: whom they owe and who owes them, per person and in total.
  • Users can settle up (record a payment from one user to another).
  • Simplify debts: compute a small set of payments that clears every balance in the group.

Non-functional

  • Money must be exact: the splits of an expense always add up to the total, to the cent.
  • Two members adding expenses at the same time must not corrupt balances.
  • New split types (shares, adjustments) should plug in without editing existing code.

Out of scope (confirm first)

  • Multi-currency, receipts and images, recurring expenses, notifications, authentication.
Tip

Ask early: "Is there always a single payer?" Multi-payer expenses are a nice extension, but starting with one payer keeps the balance update to one line per participant.

Core Entities

Entity Responsibility Key fields
User A person (immutable value) id, name
Group Members, expense history and the group's balance sheet id, name, members, expenses, sheet, lock
Expense One bill: who paid, how much, how it is split id, description, paidBy, totalCents, type, splits
Split One participant's share of an expense user, amountCents
SplitStrategy Turns a total plus inputs into exact splits interface: EqualSplit, ExactSplit, PercentSplit
SplitStrategyFactory Maps a SplitType to its strategy static of(type)
BalanceSheet Pairwise "who owes whom" ledger, always consistent net map
Transfer A suggested or recorded payment from, to, amountCents
DebtSimplifier Reduces many pairwise debts to few transfers static simplify()
SplitwiseService Facade: groups, expenses, settle-up, balances users, groups

Notice that a Split is computed, not entered. The user enters "40%" and the strategy produces "$80.00"; storing the computed cents means balances never depend on re-running floating-point arithmetic.

Class Diagram

classDiagram
  class User {
    +String id
    +String name
  }
  class Group {
    -String id
    -Set~User~ members
    -List~Expense~ expenses
    -BalanceSheet sheet
    -ReentrantLock lock
  }
  class Expense {
    +String id
    +String description
    +User paidBy
    +long totalCents
    +SplitType type
    +List~Split~ splits
  }
  class Split {
    +User user
    +long amountCents
  }
  class SplitStrategy {
    <<interface>>
    +split(long, Map) List~Split~
  }
  class EqualSplit
  class ExactSplit
  class PercentSplit
  class SplitStrategyFactory {
    +of(SplitType) SplitStrategy
  }
  class BalanceSheet {
    -Map net
    +record(User, User, long) void
    +owes(User, User) long
    +netPositions() Map
    +debts() List~Transfer~
  }
  class Transfer {
    +User from
    +User to
    +long amountCents
  }
  class DebtSimplifier {
    +simplify(Map) List~Transfer~
    +minTransfersExact(Map) int
  }
  class SplitwiseService {
    +createGroup(String, List) Group
    +addExpense(String, String, User, long, SplitType, Map) Expense
    +settleUp(String, User, User, long) void
    +simplifiedDebts(String) List~Transfer~
  }

  Group "1" o-- "many" User
  Group "1" *-- "many" Expense
  Group "1" *-- "1" BalanceSheet
  Expense "1" *-- "many" Split
  Expense --> User
  Split --> User
  SplitStrategy <|.. EqualSplit
  SplitStrategy <|.. ExactSplit
  SplitStrategy <|.. PercentSplit
  SplitStrategyFactory ..> SplitStrategy : creates
  SplitwiseService "1" o-- "many" Group
  SplitwiseService --> SplitStrategyFactory
  SplitwiseService --> DebtSimplifier
  DebtSimplifier ..> Transfer : produces
  BalanceSheet ..> Transfer : produces

Design Patterns Used

Pattern Where Why it is justified
Strategy SplitStrategy with EqualSplit, ExactSplit, PercentSplit Each split rule has its own validation and rounding. Adding "by shares" or "plus adjustments" is a new class, not another switch branch in addExpense
Factory SplitStrategyFactory.of(type) The API receives a SplitType from the client; one place maps it to behaviour
Facade SplitwiseService Clients see five verbs; the service coordinates validation, locking and ledger updates
Value objects User, Split, Transfer as records Immutable data is safe to share across threads and easy to compare in tests
Insight

Rounding belongs inside the strategy. $100.01 split four ways cannot be four equal amounts, so EqualSplit gives the leftover cent to the first participant. PercentSplit uses the largest remainder method: floor every share, then hand the leftover cents to the shares with the biggest fractional parts. Either way, the splits always sum to the total exactly.

Java Implementation

The code compiles as a single Main.java (Java 17+). Money is in integer cents and percentages in basis points (2500 = 25.00%) so no floating point touches the ledger.

java
import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.AtomicLong;
import java.util.concurrent.locks.ReentrantLock;

enum SplitType { EQUAL, EXACT, PERCENT }

record User(String id, String name) {
    @Override public String toString() { return name; }
}

record Split(User user, long amountCents) {}

record Transfer(User from, User to, long amountCents) {
    @Override public String toString() { return from + " -> " + to + " " + Money.fmt(amountCents); }
}

final class Money {
    private Money() {}
    static String fmt(long cents) {
        return (cents < 0 ? "-$" : "$") + Math.abs(cents) / 100 + "." + String.format("%02d", Math.abs(cents) % 100);
    }
}

interface SplitStrategy {
    // inputs: participant -> value (ignored for EQUAL, cents for EXACT, basis points for PERCENT), in entry order
    List<Split> split(long totalCents, Map<User, Long> inputs);
}

class EqualSplit implements SplitStrategy {
    public List<Split> split(long total, Map<User, Long> inputs) {
        int n = inputs.size();
        long base = total / n, leftover = total % n;
        List<Split> out = new ArrayList<>();
        int i = 0;
        for (User u : inputs.keySet()) out.add(new Split(u, base + (i++ < leftover ? 1 : 0)));
        return out;
    }
}

class ExactSplit implements SplitStrategy {
    public List<Split> split(long total, Map<User, Long> inputs) {
        long sum = 0;
        for (long v : inputs.values()) {
            if (v < 0) throw new IllegalArgumentException("Negative share");
            sum += v;
        }
        if (sum != total) throw new IllegalArgumentException("Exact shares sum to " + Money.fmt(sum) + ", not " + Money.fmt(total));
        return inputs.entrySet().stream().map(e -> new Split(e.getKey(), e.getValue())).toList();
    }
}

class PercentSplit implements SplitStrategy {
    public List<Split> split(long total, Map<User, Long> inputs) {
        long bpSum = inputs.values().stream().mapToLong(Long::longValue).sum();
        if (bpSum != 10_000) throw new IllegalArgumentException("Percentages sum to " + bpSum / 100.0 + "%, not 100%");
        List<User> users = new ArrayList<>(inputs.keySet());
        long[] amount = new long[users.size()];
        long[] remainder = new long[users.size()];
        long assigned = 0;
        for (int i = 0; i < users.size(); i++) {
            long raw = total * inputs.get(users.get(i));
            amount[i] = raw / 10_000;
            remainder[i] = raw % 10_000;
            assigned += amount[i];
        }
        // Largest remainder method: leftover cents go to the biggest fractional parts.
        Integer[] order = new Integer[users.size()];
        for (int i = 0; i < order.length; i++) order[i] = i;
        Arrays.sort(order, (a, b) -> Long.compare(remainder[b], remainder[a]));
        for (int k = 0; k < total - assigned; k++) amount[order[k]]++;
        List<Split> out = new ArrayList<>();
        for (int i = 0; i < users.size(); i++) out.add(new Split(users.get(i), amount[i]));
        return out;
    }
}

final class SplitStrategyFactory {
    private SplitStrategyFactory() {}

    static SplitStrategy of(SplitType type) {
        return switch (type) {
            case EQUAL -> new EqualSplit();
            case EXACT -> new ExactSplit();
            case PERCENT -> new PercentSplit();
        };
    }
}

record Expense(String id, String description, User paidBy, long totalCents, SplitType type, List<Split> splits) {}

// net[a][b] > 0 means b owes a. Kept antisymmetric: net[b][a] == -net[a][b]. Guarded by the group lock.
class BalanceSheet {
    private final Map<User, Map<User, Long>> net = new HashMap<>();

    void record(User creditor, User debtor, long cents) {
        if (creditor.equals(debtor) || cents == 0) return;
        adjust(creditor, debtor, cents);
        adjust(debtor, creditor, -cents);
    }

    private void adjust(User a, User b, long delta) {
        Map<User, Long> row = net.computeIfAbsent(a, k -> new HashMap<>());
        long v = row.getOrDefault(b, 0L) + delta;
        if (v == 0) row.remove(b); else row.put(b, v);
    }

    long owes(User debtor, User creditor) {
        return Math.max(0, net.getOrDefault(creditor, Map.of()).getOrDefault(debtor, 0L));
    }

    Map<User, Long> netPositions() {   // > 0: is owed money overall
        Map<User, Long> pos = new TreeMap<>(Comparator.comparing(User::id));
        net.forEach((u, row) -> {
            long s = row.values().stream().mapToLong(Long::longValue).sum();
            if (s != 0) pos.put(u, s);
        });
        return pos;
    }

    List<Transfer> debts() {
        List<Transfer> out = new ArrayList<>();
        net.forEach((creditor, row) -> row.forEach((debtor, v) -> {
            if (v > 0) out.add(new Transfer(debtor, creditor, v));
        }));
        out.sort(Comparator.comparing((Transfer t) -> t.from().id()).thenComparing(t -> t.to().id()));
        return out;
    }
}

final class DebtSimplifier {
    private DebtSimplifier() {}

    private record Party(User user, long amount) {}

    // Greedy: biggest debtor pays biggest creditor. At most (people with a non-zero balance - 1) transfers.
    static List<Transfer> simplify(Map<User, Long> netPositions) {
        Comparator<Party> biggestFirst = Comparator.comparingLong(Party::amount).reversed()
                .thenComparing(p -> p.user().id());
        PriorityQueue<Party> creditors = new PriorityQueue<>(biggestFirst);
        PriorityQueue<Party> debtors = new PriorityQueue<>(biggestFirst);
        netPositions.forEach((u, v) -> {
            if (v > 0) creditors.add(new Party(u, v));
            else if (v < 0) debtors.add(new Party(u, -v));
        });
        List<Transfer> out = new ArrayList<>();
        while (!creditors.isEmpty() && !debtors.isEmpty()) {
            Party c = creditors.poll(), d = debtors.poll();
            long x = Math.min(c.amount(), d.amount());
            out.add(new Transfer(d.user(), c.user(), x));
            if (c.amount() > x) creditors.add(new Party(c.user(), c.amount() - x));
            if (d.amount() > x) debtors.add(new Party(d.user(), d.amount() - x));
        }
        return out;
    }

    // Exact optimum for small groups: n - (max number of disjoint zero-sum subsets). O(2^n * n).
    static int minTransfersExact(Map<User, Long> netPositions) {
        long[] v = netPositions.values().stream().filter(x -> x != 0).mapToLong(Long::longValue).toArray();
        int n = v.length;
        if (n > 20) throw new IllegalArgumentException("Too many people for the exact algorithm");
        int full = (1 << n) - 1;
        long[] sum = new long[1 << n];
        int[] dp = new int[1 << n];
        for (int mask = 1; mask <= full; mask++) {
            int low = Integer.numberOfTrailingZeros(mask);
            sum[mask] = sum[mask & (mask - 1)] + v[low];
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) dp[mask] = Math.max(dp[mask], dp[mask ^ (1 << i)]);
            }
            if (sum[mask] == 0) dp[mask]++;
        }
        return n == 0 ? 0 : n - dp[full];
    }
}

class Group {
    final String id;
    final String name;
    final Set<User> members;
    final List<Expense> expenses = new ArrayList<>();
    final BalanceSheet sheet = new BalanceSheet();
    final ReentrantLock lock = new ReentrantLock();

    Group(String id, String name, Collection<User> members) {
        this.id = id;
        this.name = name;
        this.members = Set.copyOf(members);
    }
}

class SplitwiseService {
    private final Map<String, Group> groups = new ConcurrentHashMap<>();
    private final AtomicLong sequence = new AtomicLong();

    Group createGroup(String name, List<User> members) {
        Group g = new Group("G" + sequence.incrementAndGet(), name, members);
        groups.put(g.id, g);
        return g;
    }

    Expense addExpense(String groupId, String description, User paidBy, long totalCents,
                       SplitType type, Map<User, Long> inputs) {
        Group g = group(groupId);
        if (totalCents <= 0 || inputs.isEmpty()) throw new IllegalArgumentException("Empty expense");
        if (!g.members.contains(paidBy) || !g.members.containsAll(inputs.keySet())) {
            throw new IllegalArgumentException("Everyone must be a member of " + g.name);
        }
        List<Split> splits = SplitStrategyFactory.of(type).split(totalCents, inputs);   // validate before locking
        Expense e = new Expense("E" + sequence.incrementAndGet(), description, paidBy, totalCents, type, splits);
        g.lock.lock();
        try {   // the expense and all its balance updates become visible together
            g.expenses.add(e);
            for (Split s : splits) g.sheet.record(paidBy, s.user(), s.amountCents());
        } finally {
            g.lock.unlock();
        }
        return e;
    }

    void settleUp(String groupId, User from, User to, long cents) {
        Group g = group(groupId);
        g.lock.lock();
        try {
            long owed = g.sheet.owes(from, to);
            if (cents <= 0 || cents > owed) {
                throw new IllegalArgumentException(from + " owes " + to + " " + Money.fmt(owed) + "; cannot pay " + Money.fmt(cents));
            }
            g.sheet.record(from, to, cents);   // paying reduces the debt like a reverse expense
        } finally {
            g.lock.unlock();
        }
    }

    List<Transfer> debts(String groupId) { return read(groupId, s -> s.debts()); }
    Map<User, Long> netPositions(String groupId) { return read(groupId, BalanceSheet::netPositions); }
    List<Transfer> simplifiedDebts(String groupId) { return DebtSimplifier.simplify(netPositions(groupId)); }

    private <T> T read(String groupId, java.util.function.Function<BalanceSheet, T> f) {
        Group g = group(groupId);
        g.lock.lock();
        try { return f.apply(g.sheet); } finally { g.lock.unlock(); }
    }

    private Group group(String id) {
        Group g = groups.get(id);
        if (g == null) throw new IllegalArgumentException("Unknown group " + id);
        return g;
    }
}

public class Main {
    static Map<User, Long> of(Object... kv) {
        Map<User, Long> m = new LinkedHashMap<>();
        for (int i = 0; i < kv.length; i += 2) m.put((User) kv[i], ((Number) kv[i + 1]).longValue());
        return m;
    }

    public static void main(String[] args) {
        User alice = new User("u1", "Alice"), bob = new User("u2", "Bob"),
             carol = new User("u3", "Carol"), dan = new User("u4", "Dan");
        SplitwiseService app = new SplitwiseService();
        Group trip = app.createGroup("Goa Trip", List.of(alice, bob, carol, dan));

        Expense hotel = app.addExpense(trip.id, "Hotel", alice, 30_000, SplitType.EQUAL, of(alice, 0, bob, 0, carol, 0));
        Expense dinner = app.addExpense(trip.id, "Dinner", bob, 10_001, SplitType.EQUAL, of(alice, 0, bob, 0, carol, 0, dan, 0));
        Expense cab = app.addExpense(trip.id, "Cab", carol, 6_000, SplitType.EXACT, of(alice, 1_000, bob, 2_000, carol, 3_000));
        Expense tickets = app.addExpense(trip.id, "Tickets", dan, 20_000, SplitType.PERCENT, of(alice, 4_000, bob, 3_000, dan, 3_000));
        Expense snacks = app.addExpense(trip.id, "Snacks", carol, 1_000, SplitType.PERCENT, of(alice, 3_333, bob, 3_333, dan, 3_334));
        for (Expense e : List.of(hotel, dinner, cab, tickets, snacks)) {
            System.out.println(e.description() + " " + Money.fmt(e.totalCents()) + " paid by " + e.paidBy() + " (" + e.type() + "): "
                    + e.splits().stream().map(s -> s.user() + " " + Money.fmt(s.amountCents())).toList());
        }

        for (String label : List.of("Exact mismatch", "Bad percent")) {
            try {
                if (label.startsWith("Exact")) app.addExpense(trip.id, "Fuel", dan, 5_000, SplitType.EXACT, of(alice, 1_000, dan, 3_000));
                else app.addExpense(trip.id, "Fuel", dan, 5_000, SplitType.PERCENT, of(alice, 5_000, dan, 4_000));
            } catch (IllegalArgumentException ex) {
                System.out.println(label + " rejected: " + ex.getMessage());
            }
        }

        List<Transfer> raw = app.debts(trip.id);
        System.out.println("Pairwise debts (" + raw.size() + "): " + raw);
        Map<User, Long> net = app.netPositions(trip.id);
        System.out.println("Net positions: " + net.entrySet().stream().map(e -> e.getKey() + " " + Money.fmt(e.getValue())).toList());
        List<Transfer> simple = app.simplifiedDebts(trip.id);
        System.out.println("Simplified (" + simple.size() + "): " + simple);
        System.out.println("Exact minimum transfers: " + DebtSimplifier.minTransfersExact(net));

        app.settleUp(trip.id, bob, alice, 5_000);
        System.out.println("After Bob pays Alice $50.00: " + app.debts(trip.id));
        try {
            app.settleUp(trip.id, carol, dan, 1_000);
        } catch (IllegalArgumentException ex) {
            System.out.println("Settle rejected: " + ex.getMessage());
        }
    }
}

Demo output

text
Hotel $300.00 paid by Alice (EQUAL): [Alice $100.00, Bob $100.00, Carol $100.00]
Dinner $100.01 paid by Bob (EQUAL): [Alice $25.01, Bob $25.00, Carol $25.00, Dan $25.00]
Cab $60.00 paid by Carol (EXACT): [Alice $10.00, Bob $20.00, Carol $30.00]
Tickets $200.00 paid by Dan (PERCENT): [Alice $80.00, Bob $60.00, Dan $60.00]
Snacks $10.00 paid by Carol (PERCENT): [Alice $3.33, Bob $3.33, Dan $3.34]
Exact mismatch rejected: Exact shares sum to $40.00, not $50.00
Bad percent rejected: Percentages sum to 90.0%, not 100%
Pairwise debts (6): [Alice -> Dan $80.00, Bob -> Alice $74.99, Bob -> Dan $35.00, Carol -> Alice $86.67, Carol -> Bob $1.67, Dan -> Carol $3.34]
Net positions: [Alice $81.66, Bob -$108.32, Carol -$85.00, Dan $111.66]
Simplified (3): [Bob -> Dan $108.32, Carol -> Alice $81.66, Carol -> Dan $3.34]
Exact minimum transfers: 3
After Bob pays Alice $50.00: [Alice -> Dan $80.00, Bob -> Alice $24.99, Bob -> Dan $35.00, Carol -> Alice $86.67, Carol -> Bob $1.67, Dan -> Carol $3.34]
Settle rejected: Carol owes Dan $0.00; cannot pay $10.00

Walkthrough of the key decisions:

  • $100.01 split four ways leaves one cent over; EqualSplit gives it to the first participant, so the shares still add up exactly.
  • The 33.33% / 33.33% / 33.34% snack split shows the largest remainder method: no cent is lost or invented.
  • Invalid inputs (exact shares that do not add up, percentages that total 90%) are rejected before any balance changes.
  • Five expenses produce six pairwise debts. Net positions sum to zero ($81.66 + $111.66 = $108.32 + $85.00), and the greedy simplifier settles everything in three transfers, which matches the exact optimum here.
  • Settle-up reduces exactly one pair. Paying someone you do not owe is rejected.

Debt simplification algorithm

After a few expenses, a group has a tangle of pairwise debts. Two observations make simplification easy to reason about:

  1. Only net positions matter. If Bob owes Alice $10 and Alice owes Carol $10, Bob can pay Carol directly. For each person, compute net = (owed to them) - (they owe). Nets always sum to zero.
  2. Any set of transfers that brings every net to zero is a valid settlement. The goal is to use as few as possible.

Greedy (what Splitwise-style apps do in practice). Put creditors and debtors in two max-heaps. Repeatedly match the largest debtor with the largest creditor and transfer min(debt, credit). Each step zeroes at least one person, so there are at most k - 1 transfers for k people with non-zero nets, in O(k log k) time.

Exact minimum (bonus). Greedy is not always optimal. The true minimum is k - m, where m is the largest number of disjoint zero-sum subgroups you can split the people into, because each subgroup of size s needs exactly s - 1 transfers. Finding m is NP-hard in general (it generalises subset sum), but a bitmask DP over subsets solves it for groups of up to roughly 20 people, as minTransfersExact shows.

Warning

Simplification can make Bob pay Dan even though Bob never shared an expense with Dan. Net positions are unchanged, so everyone ends up square, but present it as an opt-in group setting and keep the original pairwise ledger as the source of truth.

Concurrency Considerations

  • Atomic expense. An expense touches several balance pairs. If two expenses interleave updates without a lock, a reader could see half an expense, or a lost update could corrupt a pair. Each Group owns a ReentrantLock; addExpense appends the expense and applies every split under it, so the expense is all-or-nothing.
  • Validate outside the lock. Split computation and membership checks are pure, so they run before acquiring the lock, keeping the critical section tiny.
  • Partitioning. Locks are per group, so unrelated groups never contend. Readers take the same lock to get a consistent snapshot; for heavy read traffic, switch to a ReadWriteLock or publish an immutable snapshot after each write.
  • Settle-up races. settleUp checks "Bob owes Alice at least $50" and records the payment under the same lock, so two simultaneous settlements cannot overpay.
  • Retries. A mobile client that times out may resend "add expense". Accept a client-generated idempotency key and ignore duplicates.

In a database-backed design, store expenses and splits in an append-only ledger and update a balances(group_id, user_a, user_b, amount) table in the same transaction. To avoid deadlocks when one expense updates several balance rows, always update rows in a fixed order (for example, sorted by user pair). Balances can always be rebuilt from the ledger, which makes audits and bug fixes safe.

Extensions

Requirement Change
Split by shares (2:1:1) New ShareSplit strategy plus a SplitType.SHARES; no other class changes
Multiple payers Expense gets a List<Payment>; balance update credits each payer by their contribution
Expenses outside any group Treat "friends" as an implicit two-person group, or keep one global sheet keyed by user pair
Multi-currency Store currency per expense; keep balances per currency, convert only for display
Edit or delete an expense Apply the reverse of the old splits, then the new splits, in one locked step; keep history for audit
Notifications and activity feed Observer: the service publishes ExpenseAdded and SettledUp events
Recurring expenses (rent) Scheduler creates expenses from a template each period

Interview Tips

  • Start with entities and the single-payer assumption; draw the class diagram before writing code.
  • Show the Strategy pattern for split types and put validation and rounding inside each strategy.
  • Use integer cents and basis points; mention the leftover-cent problem before the interviewer does.
  • Explain the balance sheet invariant (antisymmetric pairwise map, nets sum to zero).
  • For simplification, present the greedy heap algorithm, state its bound, and mention that the exact optimum is NP-hard with a bitmask DP for small groups.
  • Finish with concurrency: per-group locking, atomic multi-row updates and idempotent retries.

References

My notes saved in this browser