LLD Series: Splitwise / Expense Sharing (Low-Level Design)

 +--------------------+ 1       * +------------+ 1     * +----------------+
 |       Group        |---------->|  Expense   |------->|     Split      |
 |--------------------|           | id,paidBy  |        | userId, amount |
 | members            |           | total,type |        +----------------+
 | addExpense()       |           +------------+
 | settle()           |
 | simplifiedDebts()  |--has-->  BalanceSheet (owes[debtor][creditor], net[user])
 +----+----------+----+
      |uses      |uses
      v          v
+-----------------------+     +--------------------+
|SplitStrategyFactory   |     |<<iface>>           |
| EnumMap<Type,Strategy>|     | DebtSimplifier     |<|-- GreedyDebtSimplifier
+-----------+-----------+     +--------------------+
            | creates/returns
            v
   <<iface>> SplitStrategy <|-- EqualSplitStrategy
                            <|-- ExactSplitStrategy
                            <|-- PercentSplitStrategy
 Money (static utils: minor units <-> string)     Transfer(from,to,amount)

// SplitwiseException.java
public class SplitwiseException extends RuntimeException {
    public SplitwiseException(String m) { super(m); }
}

// Money.java
import java.math.BigDecimal;
import java.math.RoundingMode;

/** All internal arithmetic is in minor units (paise) as long: no floating point drift, sums always exact. */
public final class Money {
    private Money() {}
    public static long toMinor(String major) { return toMinor(new BigDecimal(major)); }
    public static long toMinor(BigDecimal major) {
        return major.setScale(2, RoundingMode.UNNECESSARY).movePointRight(2).longValueExact();
    }
    public static String format(long minor) {
        return BigDecimal.valueOf(minor, 2).toPlainString();
    }
}

// Split.java
/** One participant's share of an expense, in minor units. */
public final class Split {
    private final String userId;
    private final long amount;
    public Split(String userId, long amount) { this.userId = userId; this.amount = amount; }
    public String userId() { return userId; }
    public long amount() { return amount; }
}

// ExpenseType.java
public enum ExpenseType { EQUAL, EXACT, PERCENT }

// Expense.java
import java.time.Instant;
import java.util.List;

public final class Expense {
    private final String id, description, paidBy;
    private final long total;
    private final ExpenseType type;
    private final List<Split> splits;
    private final Instant createdAt;

    public Expense(String id, String description, String paidBy, long total, ExpenseType type,
                   List<Split> splits, Instant createdAt) {
        this.id = id; this.description = description; this.paidBy = paidBy; this.total = total;
        this.type = type; this.splits = List.copyOf(splits); this.createdAt = createdAt;
    }
    public String id() { return id; }
    public String description() { return description; }
    public String paidBy() { return paidBy; }
    public long total() { return total; }
    public ExpenseType type() { return type; }
    public List<Split> splits() { return splits; }
}

// Transfer.java
/** "from pays to amount" - the output of settlement / simplification. */
public final class Transfer {
    public final String from, to; public final long amount;
    public Transfer(String from, String to, long amount) { this.from = from; this.to = to; this.amount = amount; }
    @Override public String toString() { return from + " pays " + to + " " + Money.format(amount); }
}

// SplitStrategy.java
import java.math.BigDecimal;
import java.util.List;

/**
 * Strategy: turn (total, participants, params) into per-user shares that sum EXACTLY to total.
 * params meaning: EQUAL -> ignored, EXACT -> amounts (major units), PERCENT -> percentages.
 */
public interface SplitStrategy {
    List<Split> split(long totalMinor, List<String> participants, List<BigDecimal> params);
}

// EqualSplitStrategy.java
import java.math.BigDecimal;
import java.util.*;

public final class EqualSplitStrategy implements SplitStrategy {
    @Override
    public List<Split> split(long total, List<String> users, List<BigDecimal> ignored) {
        int n = users.size();
        long base = total / n;
        long remainder = total % n;                       // distribute leftover paise one each to first users
        List<Split> out = new ArrayList<>(n);
        for (int i = 0; i < n; i++) out.add(new Split(users.get(i), base + (i < remainder ? 1 : 0)));
        return out;
    }
}

// ExactSplitStrategy.java
import java.math.BigDecimal;
import java.util.*;

public final class ExactSplitStrategy implements SplitStrategy {
    @Override
    public List<Split> split(long total, List<String> users, List<BigDecimal> amounts) {
        if (amounts == null || amounts.size() != users.size())
            throw new SplitwiseException("EXACT needs one amount per participant");
        List<Split> out = new ArrayList<>();
        long sum = 0;
        for (int i = 0; i < users.size(); i++) {
            long a = Money.toMinor(amounts.get(i));
            if (a < 0) throw new SplitwiseException("Negative share");
            sum += a;
            out.add(new Split(users.get(i), a));
        }
        if (sum != total)
            throw new SplitwiseException("Exact amounts sum to " + Money.format(sum) + " but total is " + Money.format(total));
        return out;
    }
}

// PercentSplitStrategy.java
import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.*;

public final class PercentSplitStrategy implements SplitStrategy {
    @Override
    public List<Split> split(long total, List<String> users, List<BigDecimal> percents) {
        if (percents == null || percents.size() != users.size())
            throw new SplitwiseException("PERCENT needs one percentage per participant");
        BigDecimal sum = percents.stream().reduce(BigDecimal.ZERO, BigDecimal::add);
        if (sum.compareTo(BigDecimal.valueOf(100)) != 0)
            throw new SplitwiseException("Percentages must add up to 100 but were " + sum.stripTrailingZeros().toPlainString());
        long[] shares = new long[users.size()];
        long assigned = 0;
        for (int i = 0; i < shares.length; i++) {
            shares[i] = BigDecimal.valueOf(total).multiply(percents.get(i))
                    .divide(BigDecimal.valueOf(100), 0, RoundingMode.FLOOR).longValueExact();
            assigned += shares[i];
        }
        for (int i = 0; assigned < total; i = (i + 1) % shares.length) { shares[i]++; assigned++; } // leftover paise
        List<Split> out = new ArrayList<>();
        for (int i = 0; i < shares.length; i++) out.add(new Split(users.get(i), shares[i]));
        return out;
    }
}

// SplitStrategyFactory.java
import java.util.EnumMap;
import java.util.Map;

/** Registry; adding a type = new enum constant + new strategy + one register() call. */
public final class SplitStrategyFactory {
    private final Map<ExpenseType, SplitStrategy> strategies = new EnumMap<>(ExpenseType.class);

    public SplitStrategyFactory() {
        register(ExpenseType.EQUAL, new EqualSplitStrategy());
        register(ExpenseType.EXACT, new ExactSplitStrategy());
        register(ExpenseType.PERCENT, new PercentSplitStrategy());
    }
    public void register(ExpenseType t, SplitStrategy s) { strategies.put(t, s); }
    public SplitStrategy get(ExpenseType t) {
        SplitStrategy s = strategies.get(t);
        if (s == null) throw new SplitwiseException("Unsupported expense type " + t);
        return s;
    }
}

// BalanceSheet.java
import java.util.*;

/**
 * Not thread-safe by itself; the owning Group guards it with its lock.
 * owes[debtor][creditor] > 0 always holds one direction only (opposite debts are netted).
 * net[user] > 0 : user is owed money overall; < 0 : user owes money overall.
 */
public final class BalanceSheet {
    private final Map<String, Map<String, Long>> owes = new TreeMap<>();
    private final Map<String, Long> net = new TreeMap<>();

    public void addDebt(String debtor, String creditor, long amount) {
        if (amount == 0 || debtor.equals(creditor)) return;
        net.merge(creditor, amount, Long::sum);
        net.merge(debtor, -amount, Long::sum);
        long reverse = get(creditor, debtor);
        if (reverse >= amount) {                          // net against opposite direction
            set(creditor, debtor, reverse - amount);
        } else {
            set(creditor, debtor, 0);
            set(debtor, creditor, get(debtor, creditor) + amount - reverse);
        }
    }

    private long get(String debtor, String creditor) { return owes.getOrDefault(debtor, Map.of()).getOrDefault(creditor, 0L); }
    private void set(String debtor, String creditor, long v) {
        if (v == 0) { Map<String, Long> m = owes.get(debtor); if (m != null) m.remove(creditor); }
        else owes.computeIfAbsent(debtor, k -> new TreeMap<>()).put(creditor, v);
    }

    public List<Transfer> pairwise() {
        List<Transfer> out = new ArrayList<>();
        owes.forEach((d, m) -> m.forEach((c, v) -> out.add(new Transfer(d, c, v))));
        return out;
    }
    public Map<String, Long> netBalances() { return new TreeMap<>(net); }
}

// DebtSimplifier.java
import java.util.List;
import java.util.Map;

public interface DebtSimplifier {
    List<Transfer> simplify(Map<String, Long> netBalances);
}

// GreedyDebtSimplifier.java
import java.util.*;

/**
 * Greedy: repeatedly settle the biggest debtor against the biggest creditor.
 * O(n log n); at most n-1 transfers (each step zeroes at least one person). Not guaranteed minimal -
 * minimising transfers is NP-hard (reduces to partitioning into zero-sum subsets).
 */
public final class GreedyDebtSimplifier implements DebtSimplifier {
    private static final class Entry {
        final String user; long amount;
        Entry(String user, long amount) { this.user = user; this.amount = amount; }
    }

    @Override
    public List<Transfer> simplify(Map<String, Long> net) {
        Comparator<Entry> byAmountDesc = Comparator.<Entry>comparingLong(e -> e.amount).reversed().thenComparing(e -> e.user);
        PriorityQueue<Entry> creditors = new PriorityQueue<>(byAmountDesc);
        PriorityQueue<Entry> debtors = new PriorityQueue<>(byAmountDesc);
        net.forEach((u, v) -> {
            if (v > 0) creditors.add(new Entry(u, v));
            else if (v < 0) debtors.add(new Entry(u, -v));
        });
        List<Transfer> result = new ArrayList<>();
        while (!creditors.isEmpty() && !debtors.isEmpty()) {
            Entry c = creditors.poll(), d = debtors.poll();
            long pay = Math.min(c.amount, d.amount);
            result.add(new Transfer(d.user, c.user, pay));
            c.amount -= pay; d.amount -= pay;
            if (c.amount > 0) creditors.add(c);
            if (d.amount > 0) debtors.add(d);
        }
        return result;
    }
}

// Group.java
import java.math.BigDecimal;
import java.time.Clock;
import java.time.Instant;
import java.util.*;
import java.util.concurrent.locks.ReentrantReadWriteLock;

/**
 * Aggregate root: members + expenses + balance sheet. One RW lock PER GROUP:
 * different groups never contend, and within a group an expense touches many pairs so a
 * per-pair lock would risk deadlock/partial updates. Reads (show balances) share the read lock.
 */
public final class Group {
    private final String id, name;
    private final Set<String> members;
    private final SplitStrategyFactory strategies;
    private final DebtSimplifier simplifier;
    private final Clock clock;
    private final BalanceSheet sheet = new BalanceSheet();
    private final List<Expense> expenses = new ArrayList<>();
    private final ReentrantReadWriteLock lock = new ReentrantReadWriteLock();
    private int seq;

    public Group(String id, String name, Collection<String> members, SplitStrategyFactory strategies,
                 DebtSimplifier simplifier, Clock clock) {
        this.id = id; this.name = name; this.members = new LinkedHashSet<>(members);
        this.strategies = strategies; this.simplifier = simplifier; this.clock = clock;
    }

    public Expense addExpense(String description, String paidBy, String total, ExpenseType type,
                              List<String> participants, List<BigDecimal> params) {
        long totalMinor = Money.toMinor(total);
        if (totalMinor <= 0) throw new SplitwiseException("Amount must be positive");
        if (participants.isEmpty() || new HashSet<>(participants).size() != participants.size())
            throw new SplitwiseException("Participants must be non-empty and unique");
        // compute outside the lock: pure function, so validation failures never touch shared state
        List<Split> splits = strategies.get(type).split(totalMinor, participants, params);

        lock.writeLock().lock();
        try {
            requireMember(paidBy);
            participants.forEach(this::requireMember);
            Expense e = new Expense(id + "-E" + (++seq), description, paidBy, totalMinor, type, splits, Instant.now(clock));
            for (Split s : splits) sheet.addDebt(s.userId(), paidBy, s.amount());   // all-or-nothing under write lock
            expenses.add(e);
            return e;
        } finally { lock.writeLock().unlock(); }
    }

    /** "from" hands cash to "to": reduces what from owes to. */
    public void settle(String from, String to, String amount) {
        long a = Money.toMinor(amount);
        lock.writeLock().lock();
        try {
            requireMember(from); requireMember(to);
            sheet.addDebt(to, from, a);
        } finally { lock.writeLock().unlock(); }
    }

    public List<Transfer> pairwiseBalances() {
        lock.readLock().lock();
        try { return sheet.pairwise(); } finally { lock.readLock().unlock(); }
    }
    public Map<String, Long> netBalances() {
        lock.readLock().lock();
        try { return sheet.netBalances(); } finally { lock.readLock().unlock(); }
    }
    public List<Transfer> simplifiedDebts() {
        return simplifier.simplify(netBalances());
    }
    public int expenseCount() {
        lock.readLock().lock();
        try { return expenses.size(); } finally { lock.readLock().unlock(); }
    }
    private void requireMember(String u) {
        if (!members.contains(u)) throw new SplitwiseException("Not a member of " + name + ": " + u);
    }
}

// Main.java
import java.math.BigDecimal;
import java.time.Clock;
import java.util.*;
import java.util.concurrent.*;

public class Main {
    static List<BigDecimal> nums(String... v) { return Arrays.stream(v).map(BigDecimal::new).collect(java.util.stream.Collectors.toList()); }

    static void show(Group g) {
        System.out.println("  pairwise:");
        g.pairwiseBalances().forEach(t -> System.out.println("    " + t.from + " owes " + t.to + " " + Money.format(t.amount)));
        System.out.println("  net: " + fmt(g.netBalances()));
    }
    static String fmt(Map<String, Long> m) {
        StringBuilder sb = new StringBuilder();
        m.forEach((k, v) -> sb.append(k).append('=').append(Money.format(v)).append(' '));
        return sb.toString().trim();
    }

    public static void main(String[] args) throws Exception {
        Group trip = new Group("G1", "Goa Trip", List.of("A", "B", "C", "D"),
                new SplitStrategyFactory(), new GreedyDebtSimplifier(), Clock.systemUTC());

        trip.addExpense("Hotel", "A", "1000", ExpenseType.EQUAL, List.of("A", "B", "C", "D"), null);
        trip.addExpense("Dinner", "B", "600", ExpenseType.EXACT, List.of("A", "B", "C"), nums("100", "200", "300"));
        trip.addExpense("Cab", "C", "1000", ExpenseType.PERCENT, List.of("A", "B", "C"), nums("40", "30", "30"));
        trip.addExpense("Snacks", "D", "100", ExpenseType.EQUAL, List.of("A", "B", "C"), null);   // 33.34 / 33.33 / 33.33
        System.out.println("== After 4 expenses ==");
        show(trip);

        System.out.println("== Simplified (minimum-ish transfers) ==");
        trip.simplifiedDebts().forEach(t -> System.out.println("  " + t));

        System.out.println("== Validation errors ==");
        try { trip.addExpense("Bad", "A", "500", ExpenseType.EXACT, List.of("A", "B"), nums("100", "100")); }
        catch (SplitwiseException e) { System.out.println("  " + e.getMessage()); }
        try { trip.addExpense("Bad", "A", "500", ExpenseType.PERCENT, List.of("A", "B"), nums("60", "60")); }
        catch (SplitwiseException e) { System.out.println("  " + e.getMessage()); }
        try { trip.addExpense("Bad", "Z", "500", ExpenseType.EQUAL, List.of("A", "B"), null); }
        catch (SplitwiseException e) { System.out.println("  " + e.getMessage()); }
        System.out.println("  expenses recorded (failed ones left no trace): " + trip.expenseCount());

        System.out.println("== Settle: first simplified transfer is paid ==");
        Transfer first = trip.simplifiedDebts().get(0);
        trip.settle(first.from, first.to, Money.format(first.amount));
        trip.simplifiedDebts().forEach(t -> System.out.println("  " + t));

        System.out.println("== Concurrency: 8 threads x 500 expenses ==");
        Group g2 = new Group("G2", "Flat", List.of("X", "Y", "Z"), new SplitStrategyFactory(), new GreedyDebtSimplifier(), Clock.systemUTC());
        ExecutorService pool = Executors.newFixedThreadPool(8);
        List<Future<?>> fs = new ArrayList<>();
        for (int t = 0; t < 8; t++) {
            final String payer = List.of("X", "Y", "Z").get(t % 3);
            fs.add(pool.submit(() -> {
                for (int i = 0; i < 500; i++)
                    g2.addExpense("e", payer, "100.01", ExpenseType.EQUAL, List.of("X", "Y", "Z"), null);
            }));
        }
        for (Future<?> f : fs) f.get();
        pool.shutdown();
        long sum = g2.netBalances().values().stream().mapToLong(Long::longValue).sum();
        System.out.println("  expenses=" + g2.expenseCount() + " net=" + fmt(g2.netBalances()) + " sum(net)=" + sum + " (must be 0)");
    }
}

== After 4 expenses ==
  pairwise:
    A owes C 150.00
    B owes A 150.00
    B owes D 33.33
    C owes D 33.33
    D owes A 216.66
  net: A=216.66 B=-183.33 C=116.67 D=-150.00
== Simplified (minimum-ish transfers) ==
  B pays A 183.33
  D pays C 116.67
  D pays A 33.33
== Validation errors ==
  Exact amounts sum to 200.00 but total is 500.00
  Percentages must add up to 100 but were 120
  Not a member of Goa Trip: Z
  expenses recorded (failed ones left no trace): 4
== Settle: first simplified transfer is paid ==
  D pays C 116.67
  D pays A 33.33
== Concurrency: 8 threads x 500 expenses ==
  expenses=4000 net=X=16655.00 Y=16655.00 Z=-33310.00 sum(net)=0 (must be 0)

addExpense(Dinner, paidBy=B, 600, EXACT, [A,B,C], [100,200,300])
Client      Group               Factory/Strategy           BalanceSheet
 |--add---->|                        |                           |
 |          |-validate total>0, participants unique            |
 |          |--get(EXACT)----------->|                          |
 |          |--split(60000, users, params)-> validates sum, returns [A:10000,B:20000,C:30000]
 |          |  (exception here => nothing changed)             |
 |          |-writeLock()                                      |
 |          |-requireMember(payer, participants)               |
 |          |-for each split: addDebt(user -> payer, amt)----->| net[B]+=, net[A]-=, owes netted
 |          |-unlock                                           |

net:  A=+216.66  B=-183.33  C=+116.67  D=-150.00
creditors max-heap: A 216.66, C 116.67      debtors max-heap: B 183.33, D 150.00
step1: max creditor A(216.66) vs max debtor B(183.33) -> B pays A 183.33 ; A left 33.33
step2: max creditor C(116.67) vs max debtor D(150)    -> D pays C 116.67 ; D left 33.33
step3: A(33.33) vs D(33.33)                           -> D pays A 33.33