LLD Question 05

Splitwise

Design a bill-splitting app that supports equal, exact, and percentage splits, tracks a balance ledger, and simplifies debts using a greedy min-cash-flow algorithm.

Learning note

Keeping the balance ledger in canonical form with one direction per pair avoids double-counting and makes debt simplification straightforward.

Problem Statement

Design a bill-splitting system where users can add expenses, split them in different ways, and see who owes whom. The system should also be able to simplify debts to the minimum number of transactions needed to settle all balances.

Functional Requirements

Users can register and be looked up by ID.
Users can be grouped together for shared expenses.
An expense has a total amount, a payer, and a list of splits.
Splits can be equal, exact, or percentage-based.
The system maintains a balance ledger tracking who owes whom.
A user can see all their current balances.
The system can simplify all debts in a group to the fewest transactions.

Core Entities

Entity	Responsibility
`SplitType`	Enum for EQUAL, EXACT, and PERCENTAGE.
`InvalidSplitException`	Thrown when split amounts or percentages are invalid.
`UserNotFoundException`	Thrown when a user ID lookup fails.
`User`	Holds user identity: name, email, and UUID.
`Split`	Pairs a user with their resolved share amount.
`Expense`	Holds total amount, payer, splits, and split type.
`Group`	Owns a list of members and expenses.
`SplitStrategy`	Interface for split calculation logic.
`EqualSplitStrategy`	Divides total equally among all splits.
`ExactSplitStrategy`	Validates that exact amounts sum to the total.
`PercentageSplitStrategy`	Validates percentages sum to 100 and converts to amounts.
`UserService`	Registers users and provides lookups.
`ExpenseService`	Creates expenses, updates the balance ledger, and simplifies debts.
`GroupService`	Creates groups, manages members, and delegates to `ExpenseService`.

Design Decisions

Strategy for Split Calculation

Each split type has its own validation and amount calculation rules. SplitStrategy keeps these rules out of ExpenseService. Adding a new split type means adding a new class without changing existing code.

Canonical Balance Ledger

The ledger stores only one direction per pair. If A owes B Rs 100, the entry is balances[A][B] = 100. The reverse entry balances[B][A] is never created for the same debt. When a new debt is added in the reverse direction, the amounts cancel out instead of stacking.

Greedy Debt Simplification

Given all net balances, the simplification algorithm separates users into creditors and debtors and greedily matches the largest creditor with the largest debtor. This minimizes the total number of transactions needed to settle the group.

Service Layer

UserService, ExpenseService, and GroupService are plain service objects, not singletons. They are wired together in Main. This keeps testing easy and avoids global state.

Main Flow

Register users with UserService.
Create a group with GroupService and add members.
Add an expense via GroupService.addGroupExpense().
ExpenseService resolves the split strategy and calculates amounts.
Balance ledger is updated: each split user owes the payer their share.
Call printGroupBalances() to see raw balances.
Call printSimplifiedDebts() to see the minimum transactions to settle.

Complete Code: Bottom-Up

1. model/SplitType.java

package splitwise.model;
 
public enum SplitType {
    EQUAL,      // divide equally among all participants
    EXACT,      // each user owes an exact specified amount
    PERCENTAGE  // each user owes a percentage of the total
}

2. exception/InvalidSplitException.java

package splitwise.exception;
 
public class InvalidSplitException extends RuntimeException {
    public InvalidSplitException(String message) {
        super(message);
    }
}

3. exception/UserNotFoundException.java

package splitwise.exception;
 
public class UserNotFoundException extends RuntimeException {
    public UserNotFoundException(String message) {
        super(message);
    }
}

4. model/User.java

package splitwise.model;
 
import java.util.UUID;
 
public class User {
    private final String id;
    private final String name;
    private final String email;
 
    public User(String name, String email) {
        this.id = UUID.randomUUID().toString();
        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 + "(" + email + ")";
    }
}

5. model/Split.java

package splitwise.model;
 
// Represents how much one user owes in a particular expense.
public class Split {
    private final User user;
    private double amount; // resolved share for this user
 
    public Split(User user, double amount) {
        this.user = user;
        this.amount = amount;
    }
 
    public User getUser() { return user; }
    public double getAmount() { return amount; }
    public void setAmount(double amount) { this.amount = amount; }
}

6. model/Expense.java

package splitwise.model;
 
import java.util.List;
import java.util.UUID;
 
// An expense paid by one user (paidBy) and split among multiple users.
public class Expense {
    private final String id;
    private final String description;
    private final double totalAmount;
    private final User paidBy;
    private final List<Split> splits;
    private final SplitType splitType;
 
    public Expense(String description, double totalAmount, User paidBy,
                   List<Split> splits, SplitType splitType) {
        this.id = UUID.randomUUID().toString();
        this.description = description;
        this.totalAmount = totalAmount;
        this.paidBy = paidBy;
        this.splits = splits;
        this.splitType = splitType;
    }
 
    public String getId() { return id; }
    public String getDescription() { return description; }
    public double getTotalAmount() { return totalAmount; }
    public User getPaidBy() { return paidBy; }
    public List<Split> getSplits() { return splits; }
    public SplitType getSplitType() { return splitType; }
}

7. model/Group.java

package splitwise.model;
 
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.UUID;
 
// A group of users who share expenses (e.g. "Goa Trip", "Flatmates").
public class Group {
    private final String id;
    private final String name;
    private final List<User> members;
    private final List<Expense> expenses;
 
    public Group(String name) {
        this.id = UUID.randomUUID().toString();
        this.name = name;
        this.members = new ArrayList<>();
        this.expenses = new ArrayList<>();
    }
 
    public String getId() { return id; }
    public String getName() { return name; }
 
    public void addMember(User user) { members.add(user); }
    public List<User> getMembers() { return Collections.unmodifiableList(members); }
 
    public void addExpense(Expense expense) { expenses.add(expense); }
    public List<Expense> getExpenses() { return Collections.unmodifiableList(expenses); }
}

8. strategy/SplitStrategy.java

package splitwise.strategy;
 
import splitwise.model.Split;
 
import java.util.List;
 
public interface SplitStrategy {
    // Given total amount and splits (users already set),
    // populate the amount on each Split.
    void calculateSplits(double totalAmount, List<Split> splits);
}

9. strategy/EqualSplitStrategy.java

package splitwise.strategy;
 
import splitwise.model.Split;
 
import java.util.List;
 
// Divides total equally. Rs 300 among 3 people -> Rs 100 each.
public class EqualSplitStrategy implements SplitStrategy {
 
    @Override
    public void calculateSplits(double totalAmount, List<Split> splits) {
        if (splits == null || splits.isEmpty()) {
            throw new IllegalArgumentException("Splits list cannot be empty.");
        }
        double share = totalAmount / splits.size();
        share = Math.round(share * 100.0) / 100.0;
        for (Split split : splits) {
            split.setAmount(share);
        }
    }
}

10. strategy/ExactSplitStrategy.java

package splitwise.strategy;
 
import splitwise.exception.InvalidSplitException;
import splitwise.model.Split;
 
import java.util.List;
 
// Each user owes an exact pre-specified amount.
// Validation: sum of all exact amounts must equal the total.
public class ExactSplitStrategy implements SplitStrategy {
 
    @Override
    public void calculateSplits(double totalAmount, List<Split> splits) {
        double sum = splits.stream().mapToDouble(Split::getAmount).sum();
        if (Math.abs(sum - totalAmount) > 0.01) {
            throw new InvalidSplitException(
                String.format("Exact amounts sum (%.2f) does not match total (%.2f).", sum, totalAmount)
            );
        }
        // amounts already set by the caller; nothing more to do
    }
}

11. strategy/PercentageSplitStrategy.java

package splitwise.strategy;
 
import splitwise.exception.InvalidSplitException;
import splitwise.model.Split;
 
import java.util.List;
 
// Each Split's amount field is treated as a PERCENTAGE (0-100).
// Validation: percentages must sum to 100.
// After validation, percentages are converted to actual amounts.
public class PercentageSplitStrategy implements SplitStrategy {
 
    @Override
    public void calculateSplits(double totalAmount, List<Split> splits) {
        double totalPercent = splits.stream().mapToDouble(Split::getAmount).sum();
        if (Math.abs(totalPercent - 100.0) > 0.01) {
            throw new InvalidSplitException(
                String.format("Percentages must sum to 100 but got %.2f.", totalPercent)
            );
        }
        for (Split split : splits) {
            double actual = Math.round((split.getAmount() / 100.0) * totalAmount * 100.0) / 100.0;
            split.setAmount(actual);
        }
    }
}

12. service/UserService.java

package splitwise.service;
 
import splitwise.exception.UserNotFoundException;
import splitwise.model.User;
 
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
 
public class UserService {
 
    private final Map<String, User> users = new HashMap<>();
 
    public User registerUser(String name, String email) {
        User user = new User(name, email);
        users.put(user.getId(), user);
        return user;
    }
 
    public User getUserById(String id) {
        User user = users.get(id);
        if (user == null) throw new UserNotFoundException("User not found: " + id);
        return user;
    }
 
    public Collection<User> getAllUsers() {
        return Collections.unmodifiableCollection(users.values());
    }
}

13. service/ExpenseService.java

package splitwise.service;
 
import splitwise.model.*;
import splitwise.strategy.*;
 
import java.util.*;
 
// Core service: creates expenses, updates the balance ledger, simplifies debts.
//
// Balance ledger: balances.get(userId1).get(userId2) = X means
// userId1 owes userId2 X rupees. Only one direction is stored per pair.
public class ExpenseService {
 
    private final Map<String, Map<String, Double>> balances = new HashMap<>();
    private final List<Expense> expenses = new ArrayList<>();
 
    public Expense addExpense(String description, double totalAmount,
                              User paidBy, List<Split> splits, SplitType splitType) {
        SplitStrategy strategy = resolveStrategy(splitType);
        strategy.calculateSplits(totalAmount, splits);
 
        Expense expense = new Expense(description, totalAmount, paidBy, splits, splitType);
        expenses.add(expense);
        updateBalances(expense);
        return expense;
    }
 
    // Positive value: that user owes `user`.
    // Negative value: `user` owes that person.
    public Map<String, Double> getBalancesForUser(User user) {
        Map<String, Double> result = new HashMap<>();
 
        for (Map.Entry<String, Map<String, Double>> outer : balances.entrySet()) {
            String debtorId = outer.getKey();
            if (debtorId.equals(user.getId())) continue;
            Double amt = outer.getValue().get(user.getId());
            if (amt != null && amt > 0.001) {
                result.merge(debtorId, amt, Double::sum);
            }
        }
 
        Map<String, Double> userDebts = balances.getOrDefault(user.getId(), Collections.emptyMap());
        for (Map.Entry<String, Double> entry : userDebts.entrySet()) {
            if (entry.getValue() > 0.001) {
                result.merge(entry.getKey(), -entry.getValue(), Double::sum);
            }
        }
        return result;
    }
 
    // Greedy min-cash-flow algorithm: returns minimum transactions to settle all debts.
    public List<String> simplifyDebts(List<User> users) {
        Map<String, Double> net = new HashMap<>();
        for (User u : users) net.put(u.getId(), 0.0);
 
        for (Map.Entry<String, Map<String, Double>> outer : balances.entrySet()) {
            String debtorId = outer.getKey();
            for (Map.Entry<String, Double> inner : outer.getValue().entrySet()) {
                String creditorId = inner.getKey();
                double amt = inner.getValue();
                net.merge(debtorId, -amt, Double::sum);
                net.merge(creditorId, amt, Double::sum);
            }
        }
 
        Map<String, String> idToName = new HashMap<>();
        for (User u : users) idToName.put(u.getId(), u.getName());
 
        List<String> transactions = new ArrayList<>();
        Deque<Map.Entry<String, Double>> creditors = new ArrayDeque<>();
        Deque<Map.Entry<String, Double>> debtors = new ArrayDeque<>();
 
        for (Map.Entry<String, Double> entry : net.entrySet()) {
            if (entry.getValue() > 0.001)
                creditors.add(new AbstractMap.SimpleEntry<>(entry.getKey(), entry.getValue()));
            else if (entry.getValue() < -0.001)
                debtors.add(new AbstractMap.SimpleEntry<>(entry.getKey(), -entry.getValue()));
        }
 
        while (!creditors.isEmpty() && !debtors.isEmpty()) {
            Map.Entry<String, Double> creditor = creditors.poll();
            Map.Entry<String, Double> debtor   = debtors.poll();
 
            double settleAmt = Math.min(creditor.getValue(), debtor.getValue());
            transactions.add(String.format("%s pays %s %.2f",
                idToName.getOrDefault(debtor.getKey(), debtor.getKey()),
                idToName.getOrDefault(creditor.getKey(), creditor.getKey()),
                settleAmt));
 
            double remainCreditor = creditor.getValue() - settleAmt;
            double remainDebtor   = debtor.getValue()   - settleAmt;
 
            if (remainCreditor > 0.001) creditors.addFirst(new AbstractMap.SimpleEntry<>(creditor.getKey(), remainCreditor));
            if (remainDebtor   > 0.001) debtors.addFirst(new AbstractMap.SimpleEntry<>(debtor.getKey(), remainDebtor));
        }
        return transactions;
    }
 
    public List<Expense> getAllExpenses() {
        return Collections.unmodifiableList(expenses);
    }
 
    private SplitStrategy resolveStrategy(SplitType type) {
        return switch (type) {
            case EQUAL      -> new EqualSplitStrategy();
            case EXACT      -> new ExactSplitStrategy();
            case PERCENTAGE -> new PercentageSplitStrategy();
        };
    }
 
    private void updateBalances(Expense expense) {
        User paidBy = expense.getPaidBy();
        for (Split split : expense.getSplits()) {
            User owes = split.getUser();
            if (owes.getId().equals(paidBy.getId())) continue;
            addDebt(owes.getId(), paidBy.getId(), split.getAmount());
        }
    }
 
    private void addDebt(String debtorId, String creditorId, double amount) {
        double reverseDebt = balances
            .getOrDefault(creditorId, Collections.emptyMap())
            .getOrDefault(debtorId, 0.0);
 
        if (reverseDebt > 0) {
            double net = reverseDebt - amount;
            if (net > 0.001) {
                balances.get(creditorId).put(debtorId, net);
            } else if (net < -0.001) {
                balances.get(creditorId).put(debtorId, 0.0);
                balances.computeIfAbsent(debtorId, k -> new HashMap<>())
                        .merge(creditorId, -net, Double::sum);
            } else {
                balances.get(creditorId).put(debtorId, 0.0);
            }
        } else {
            balances.computeIfAbsent(debtorId, k -> new HashMap<>())
                    .merge(creditorId, amount, Double::sum);
        }
    }
}

14. service/GroupService.java

package splitwise.service;
 
import splitwise.model.*;
 
import java.util.*;
 
public class GroupService {
 
    private final Map<String, Group> groups = new HashMap<>();
    private final ExpenseService expenseService;
 
    public GroupService(ExpenseService expenseService) {
        this.expenseService = expenseService;
    }
 
    public Group createGroup(String name) {
        Group group = new Group(name);
        groups.put(group.getId(), group);
        return group;
    }
 
    public void addMemberToGroup(Group group, User user) {
        group.addMember(user);
    }
 
    public Expense addGroupExpense(Group group, String description, double amount,
                                   User paidBy, List<Split> splits, SplitType splitType) {
        Expense expense = expenseService.addExpense(description, amount, paidBy, splits, splitType);
        group.addExpense(expense);
        return expense;
    }
 
    public Group getGroup(String groupId) {
        return groups.get(groupId);
    }
 
    public void printGroupBalances(Group group) {
        System.out.println("\n=== Balances for group: " + group.getName() + " ===");
        for (User member : group.getMembers()) {
            Map<String, Double> balanceMap = expenseService.getBalancesForUser(member);
            for (Map.Entry<String, Double> entry : balanceMap.entrySet()) {
                boolean inGroup = group.getMembers().stream()
                    .anyMatch(u -> u.getId().equals(entry.getKey()));
                if (!inGroup) continue;
 
                String otherName = group.getMembers().stream()
                    .filter(u -> u.getId().equals(entry.getKey()))
                    .findFirst().map(User::getName).orElse(entry.getKey());
 
                if (entry.getValue() > 0.001) {
                    System.out.printf("  %s is owed %.2f by %s%n",
                        member.getName(), entry.getValue(), otherName);
                }
            }
        }
    }
 
    public void printSimplifiedDebts(Group group) {
        System.out.println("\n=== Simplified settlements for group: " + group.getName() + " ===");
        List<String> settlements = expenseService.simplifyDebts(group.getMembers());
        if (settlements.isEmpty()) {
            System.out.println("  All settled up!");
        } else {
            settlements.forEach(s -> System.out.println("  " + s));
        }
    }
}

15. Main.java

package splitwise;
 
import splitwise.model.*;
import splitwise.service.*;
 
import java.util.Arrays;
import java.util.List;
 
public class Main {
 
    public static void main(String[] args) {
 
        UserService    userService    = new UserService();
        ExpenseService expenseService = new ExpenseService();
        GroupService   groupService   = new GroupService(expenseService);
 
        User alice = userService.registerUser("Alice", "alice@example.com");
        User bob   = userService.registerUser("Bob",   "bob@example.com");
        User carol = userService.registerUser("Carol", "carol@example.com");
        User dave  = userService.registerUser("Dave",  "dave@example.com");
 
        // Non-group: coffee Rs 200, paid by Alice, split equally -> Bob owes Rs 100
        System.out.println("\n--- Coffee Rs 200 (EQUAL, paid by Alice) ---");
        List<Split> coffeeSplits = Arrays.asList(new Split(alice, 0), new Split(bob, 0));
        expenseService.addExpense("Coffee", 200, alice, coffeeSplits, SplitType.EQUAL);
 
        Group trip = groupService.createGroup("Goa Trip");
        groupService.addMemberToGroup(trip, alice);
        groupService.addMemberToGroup(trip, bob);
        groupService.addMemberToGroup(trip, carol);
        groupService.addMemberToGroup(trip, dave);
 
        // Hotel Rs 3000 paid by Alice, split equally -> each owes Rs 750
        System.out.println("\n--- Hotel Rs 3000 (EQUAL, paid by Alice) ---");
        List<Split> equalSplits = Arrays.asList(
            new Split(alice, 0), new Split(bob, 0),
            new Split(carol, 0), new Split(dave, 0)
        );
        groupService.addGroupExpense(trip, "Hotel", 3000, alice, equalSplits, SplitType.EQUAL);
 
        // Dinner Rs 1200 paid by Bob, exact split
        System.out.println("\n--- Dinner Rs 1200 (EXACT, paid by Bob) ---");
        List<Split> exactSplits = Arrays.asList(
            new Split(bob, 300), new Split(carol, 500), new Split(dave, 400)
        );
        groupService.addGroupExpense(trip, "Dinner", 1200, bob, exactSplits, SplitType.EXACT);
 
        // Cab Rs 1000 paid by Carol, percentage split: Alice=40%, Bob=30%, Carol=20%, Dave=10%
        System.out.println("\n--- Cab Rs 1000 (PERCENTAGE, paid by Carol) ---");
        List<Split> percentSplits = Arrays.asList(
            new Split(alice, 40), new Split(bob, 30),
            new Split(carol, 20), new Split(dave, 10)
        );
        groupService.addGroupExpense(trip, "Cab", 1000, carol, percentSplits, SplitType.PERCENTAGE);
 
        groupService.printGroupBalances(trip);
        groupService.printSimplifiedDebts(trip);
    }
}

What I Learned

A canonical ledger that stores only one direction per pair avoids double-counting and simplifies debt calculation.
The greedy min-cash-flow algorithm settles a group in at most N-1 transactions by always pairing the largest creditor with the largest debtor.
Strategy pattern keeps each split type isolated so validation rules never bleed into ExpenseService.
Services wired through constructors instead of singletons make each component easy to test in isolation.

Possible Improvements

Add a Settlement model to record who paid whom and when.
Add currency support so groups can track multi-currency expenses.
Add an ExpenseCategory enum for filtering expenses by type.
Add tests for percentage rounding, exact mismatch, and debt cancellation edge cases.