Problem 7: Design Splitwise

The setup

"Design Splitwise. Users in groups split expenses (dinner, rent, trips). The system tracks who owes whom; supports equal, exact, and percentage splits; settles debts efficiently."

This problem combines domain modeling (Group, Expense, Split, Balance) with an interesting algorithmic challenge (debt simplification: minimize the number of transactions to settle). Strong candidates handle both well.

Clarifying questions

Core entities

The Split hierarchy — Strategy pattern

Each split type computes per-user amounts differently. Same interface, different algorithms:

abstract class Split {
  User user;
  BigDecimal amount;
}

interface SplitStrategy {
  // For an expense of `totalAmount` paid by `payer`, divide among `participants`
  // and return list of Splits (user → amount they owe)
  List compute(BigDecimal totalAmount, User payer, List participants, Map params);
}

class EqualSplitStrategy implements SplitStrategy {
  public List compute(BigDecimal total, User payer, List participants, Map params) {
    BigDecimal share = total.divide(BigDecimal.valueOf(participants.size()), 2, RoundingMode.HALF_UP);
    return participants.stream()
      .map(u -> new Split(u, share))
      .collect(toList());
  }
}

class ExactSplitStrategy implements SplitStrategy {
  public List compute(BigDecimal total, User payer, List participants, Map params) {
    Map exactAmounts = (Map) params.get("exactAmounts");
    // Validate: sum of exact amounts equals total
    BigDecimal sum = exactAmounts.values().stream().reduce(BigDecimal.ZERO, BigDecimal::add);
    if (!sum.equals(total)) throw new InvalidSplitException("Exact amounts must sum to total");
    return participants.stream()
      .map(u -> new Split(u, exactAmounts.get(u)))
      .collect(toList());
  }
}

class PercentSplitStrategy implements SplitStrategy {
  public List compute(BigDecimal total, User payer, List participants, Map params) {
    Map percentages = (Map) params.get("percentages");
    BigDecimal sumPct = percentages.values().stream().reduce(BigDecimal.ZERO, BigDecimal::add);
    if (sumPct.compareTo(new BigDecimal("100")) != 0) {
      throw new InvalidSplitException("Percentages must sum to 100");
    }
    return participants.stream()
      .map(u -> new Split(u, total.multiply(percentages.get(u)).divide(new BigDecimal("100"))))
      .collect(toList());
  }
}

The Balance Sheet

Track who owes whom. Simple representation: a map from (user, user) pair to balance.

class BalanceSheet {
  // (debtor, creditor) → amount debtor owes creditor
  private Map balances = new HashMap<>();
  
  public void addExpense(User payer, List splits) {
    for (Split split : splits) {
      if (split.user.equals(payer)) continue;  // payer doesn't owe themselves
      // split.user owes payer split.amount
      UserPair pair = new UserPair(split.user, payer);
      balances.merge(pair, split.amount, BigDecimal::add);
      // Optimization: if other direction has balance, net them
      UserPair reverse = new UserPair(payer, split.user);
      if (balances.containsKey(reverse)) {
        BigDecimal owedByPayer = balances.get(reverse);
        BigDecimal owedToPayer = balances.get(pair);
        BigDecimal net = owedToPayer.subtract(owedByPayer);
        if (net.signum() > 0) {
          balances.put(pair, net);
          balances.remove(reverse);
        } else {
          balances.put(reverse, net.abs());
          balances.remove(pair);
        }
      }
    }
  }
  
  public BigDecimal getBalance(User debtor, User creditor) {
    return balances.getOrDefault(new UserPair(debtor, creditor), BigDecimal.ZERO);
  }
  
  public Map getOverallBalance(User user) {
    // Net balance for this user across all their relationships
    Map result = new HashMap<>();
    for (var entry : balances.entrySet()) {
      UserPair pair = entry.getKey();
      BigDecimal amount = entry.getValue();
      if (pair.debtor.equals(user)) {
        result.merge(pair.creditor, amount.negate(), BigDecimal::add);
      } else if (pair.creditor.equals(user)) {
        result.merge(pair.debtor, amount, BigDecimal::add);
      }
    }
    return result;
  }
}

The SplitwiseService

class SplitwiseService {
  private final BalanceSheet balanceSheet;
  private final Map strategies = Map.of(
    SplitType.EQUAL, new EqualSplitStrategy(),
    SplitType.EXACT, new ExactSplitStrategy(),
    SplitType.PERCENT, new PercentSplitStrategy()
  );
  
  public Expense addExpense(User payer, BigDecimal amount, List participants, 
                             SplitType type, Map splitParams) {
    SplitStrategy strategy = strategies.get(type);
    List splits = strategy.compute(amount, payer, participants, splitParams);
    Expense expense = new Expense(payer, amount, splits);
    balanceSheet.addExpense(payer, splits);
    return expense;
  }
  
  public Map getBalanceFor(User user) {
    return balanceSheet.getOverallBalance(user);
  }
}

Design Decision: debt simplification

An interesting algorithmic problem. If A owes B ₹100, B owes C ₹100, then A directly owes C ₹100 — we can eliminate B from the picture. Minimum transaction settlement is an instance of the cash-flow simplification problem.

class DebtSimplifier {
  // Given net balances per user, output minimum-transaction settlement
  public List simplify(Map netBalances) {
    // Positive balance: net creditor (others owe them); negative: net debtor
    PriorityQueue creditors = new PriorityQueue<>((a, b) -> b.amount.compareTo(a.amount));
    PriorityQueue debtors = new PriorityQueue<>((a, b) -> b.amount.compareTo(a.amount));
    
    for (var entry : netBalances.entrySet()) {
      if (entry.getValue().signum() > 0) creditors.offer(new UserAmount(entry.getKey(), entry.getValue()));
      else if (entry.getValue().signum() < 0) debtors.offer(new UserAmount(entry.getKey(), entry.getValue().abs()));
    }
    
    List result = new ArrayList<>();
    while (!creditors.isEmpty() && !debtors.isEmpty()) {
      UserAmount creditor = creditors.poll();
      UserAmount debtor = debtors.poll();
      BigDecimal settled = creditor.amount.min(debtor.amount);
      result.add(new Transaction(debtor.user, creditor.user, settled));
      BigDecimal remCredit = creditor.amount.subtract(settled);
      BigDecimal remDebt = debtor.amount.subtract(settled);
      if (remCredit.signum() > 0) creditors.offer(new UserAmount(creditor.user, remCredit));
      if (remDebt.signum() > 0) debtors.offer(new UserAmount(debtor.user, remDebt));
    }
    return result;
  }
}

This greedy approach (largest creditor matched with largest debtor) doesn't always produce the minimum number of transactions (which is NP-hard in general), but it's a good heuristic that's correct for typical cases.

Cross-examination round 1: floating-point precision

Cross-examination round 2: concurrency

Takeaway

Splitwise is the canonical Strategy-pattern example: split types are interchangeable algorithms with the same shape. The interesting bit beyond the pattern is the balance-sheet bookkeeping and the debt-simplification algorithm. Together they demonstrate that LLD isn't just about classes — it's about modeling the domain accurately and handling the algorithmic concerns that fall out.