Design Splitwise (Expense Sharing)

public class User {
    private final String userId;
    private final String name;
    private final String email;

    public User(String userId, String name, String email) {
        this.userId = userId;
        this.name = name;
        this.email = email;
    }
    // getters
}

public class Split {
    private final User user;
    private final double amount;

    public Split(User user, double amount) {
        this.user = user;
        this.amount = amount;
    }
    // getters
}

public class Expense {
    private final String expenseId;
    private final double amount;
    private final User paidBy;
    private final List<Split> splits;
    private final String description;
    private final LocalDateTime createdAt;

    public Expense(String id, double amount, User paidBy,
                   List<Split> splits, String description) {
        this.expenseId = id;
        this.amount = amount;
        this.paidBy = paidBy;
        this.splits = List.copyOf(splits); // immutable
        this.description = description;
        this.createdAt = LocalDateTime.now();
    }
}

public class Transaction {
    private final User from;
    private final User to;
    private final double amount;

    public Transaction(User from, User to, double amount) {
        this.from = from;
        this.to = to;
        this.amount = amount;
    }
}

public class ExpenseService {
    private final Map<String, Group> groups = new ConcurrentHashMap<>();
    private final BalanceSheet balanceSheet = new BalanceSheet();
    private final Map<SplitType, SplitStrategy> strategies;

    public ExpenseService() {
        strategies = Map.of(
            SplitType.EQUAL, new EqualSplitStrategy(),
            SplitType.EXACT, new ExactSplitStrategy(),
            SplitType.PERCENTAGE, new PercentageSplitStrategy()
        );
    }

    public void addExpense(String groupId, User paidBy, double amount,
                           SplitType type, List<User> participants,
                           Map<String, Double> params) {
        SplitStrategy strategy = strategies.get(type);
        if (!strategy.validate(amount, participants, params)) {
            throw new IllegalArgumentException("Invalid split parameters");
        }

        List<Split> splits = strategy.split(amount, participants, params);
        Expense expense = new Expense(
            UUID.randomUUID().toString(), amount, paidBy, splits, "Expense"
        );

        groups.get(groupId).addExpense(expense);
        balanceSheet.update(paidBy, splits);
    }

    public Map<String, Double> getUserBalances(String userId) {
        return balanceSheet.getBalancesForUser(userId);
    }

    public List<Transaction> settleUp(String groupId) {
        return balanceSheet.simplifyDebts(
            groups.get(groupId).getMembers()
        );
    }
}

public enum SplitType { EQUAL, EXACT, PERCENTAGE }

public interface SplitStrategy {
    List<Split> split(double amount, List<User> participants,
                      Map<String, Double> params);
    boolean validate(double amount, List<User> participants,
                     Map<String, Double> params);
}

public class EqualSplitStrategy implements SplitStrategy {
    @Override
    public List<Split> split(double amount, List<User> participants,
                             Map<String, Double> params) {
        int n = participants.size();
        double each = Math.floor(amount * 100 / n) / 100.0;
        double remainder = amount - (each * n);

        List<Split> splits = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            double share = (i == 0) ? each + remainder : each;
            splits.add(new Split(participants.get(i), share));
        }
        return splits;
    }

    @Override
    public boolean validate(double amount, List<User> participants,
                            Map<String, Double> params) {
        return amount > 0 && participants.size() > 0;
    }
}

public class ExactSplitStrategy implements SplitStrategy {
    @Override
    public List<Split> split(double amount, List<User> participants,
                             Map<String, Double> params) {
        return participants.stream()
            .map(u -> new Split(u, params.get(u.getUserId())))
            .toList();
    }

    @Override
    public boolean validate(double amount, List<User> participants,
                            Map<String, Double> params) {
        double sum = participants.stream()
            .mapToDouble(u -> params.getOrDefault(u.getUserId(), 0.0))
            .sum();
        return Math.abs(sum - amount) < 0.01;
    }
}

public class PercentageSplitStrategy implements SplitStrategy {
    @Override
    public List<Split> split(double amount, List<User> participants,
                             Map<String, Double> params) {
        return participants.stream()
            .map(u -> new Split(u,
                amount * params.get(u.getUserId()) / 100.0))
            .toList();
    }

    @Override
    public boolean validate(double amount, List<User> participants,
                            Map<String, Double> params) {
        double totalPercent = participants.stream()
            .mapToDouble(u -> params.getOrDefault(u.getUserId(), 0.0))
            .sum();
        return Math.abs(totalPercent - 100.0) < 0.01;
    }
}

public class BalanceSheet {
    // balanceGraph[A][B] > 0 means A owes B that amount
    private final Map<String, Map<String, Double>> balanceGraph =
        new ConcurrentHashMap<>();

    public void update(User paidBy, List<Split> splits) {
        for (Split split : splits) {
            if (split.getUser().equals(paidBy)) continue;

            String payerId = paidBy.getUserId();
            String owerId = split.getUser().getUserId();

            // owerId owes payerId
            addBalance(owerId, payerId, split.getAmount());
            // net off: reduce reverse direction
            addBalance(payerId, owerId, -split.getAmount());
        }
    }

    private synchronized void addBalance(String from, String to, double amount) {
        balanceGraph
            .computeIfAbsent(from, k -> new ConcurrentHashMap<>())
            .merge(to, amount, Double::sum);
    }

    public Map<String, Double> getBalancesForUser(String userId) {
        Map<String, Double> result = new HashMap<>();
        Map<String, Double> owes = balanceGraph.getOrDefault(userId, Map.of());
        owes.forEach((other, amt) -> {
            if (Math.abs(amt) > 0.01) result.put(other, amt);
        });
        return result;
    }

    /**
     * Greedy settlement: minimize number of transactions.
     * 1. Compute net balance for each user
     * 2. Repeatedly settle max creditor with max debtor
     */
    public List<Transaction> simplifyDebts(List<User> members) {
        // Step 1: compute net amounts
        Map<String, Double> netBalance = new HashMap<>();
        Map<String, User> userMap = new HashMap<>();
        for (User u : members) {
            userMap.put(u.getUserId(), u);
            netBalance.put(u.getUserId(), 0.0);
        }

        for (var entry : balanceGraph.entrySet()) {
            String from = entry.getKey();
            for (var inner : entry.getValue().entrySet()) {
                String to = inner.getKey();
                double amt = inner.getValue();
                if (members.stream().anyMatch(m ->
                        m.getUserId().equals(from))) {
                    netBalance.merge(from, -amt, Double::sum);
                    netBalance.merge(to, amt, Double::sum);
                }
            }
        }

        // Step 2: greedy matching
        List<Transaction> transactions = new ArrayList<>();
        PriorityQueue<Map.Entry<String, Double>> creditors =
            new PriorityQueue<>((a, b) ->
                Double.compare(b.getValue(), a.getValue()));
        PriorityQueue<Map.Entry<String, Double>> debtors =
            new PriorityQueue<>(Comparator.comparingDouble(
                Map.Entry::getValue));

        netBalance.forEach((uid, amt) -> {
            if (amt > 0.01) creditors.offer(Map.entry(uid, amt));
            else if (amt < -0.01) debtors.offer(Map.entry(uid, amt));
        });

        while (!creditors.isEmpty() && !debtors.isEmpty()) {
            var creditor = creditors.poll();
            var debtor = debtors.poll();

            double settled = Math.min(
                creditor.getValue(), -debtor.getValue());
            transactions.add(new Transaction(
                userMap.get(debtor.getKey()),
                userMap.get(creditor.getKey()),
                settled
            ));

            double credRem = creditor.getValue() - settled;
            double debtRem = debtor.getValue() + settled;

            if (credRem > 0.01)
                creditors.offer(Map.entry(creditor.getKey(), credRem));
            if (debtRem < -0.01)
                debtors.offer(Map.entry(debtor.getKey(), debtRem));
        }
        return transactions;
    }
}