Design Splitwise

package com.androidinterview.splitwise.ledger;

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;

// Who owes whom, held pairwise rather than as one net number per person. That
// choice is deliberate. Pairwise is what lets the app answer the question users
// actually ask, which is what do I owe Ana, and net balances can always be
// derived from it. Going the other way is impossible.
//
// Every debt is netted against anything owed the other way as it is recorded,
// so two friends who take turns paying end up with one number instead of a
// growing pile of entries that cancel out.
public final class BalanceSheet {

    private final Map<String, Map<String, Long>> owes = new HashMap<>();

    public synchronized void addDebt(String debtorId, String creditorId, long amount) {
        if (debtorId.equals(creditorId) || amount == 0) {
            return;
        }
        long net = amount + amountOwed(debtorId, creditorId) - amountOwed(creditorId, debtorId);
        clear(debtorId, creditorId);
        clear(creditorId, debtorId);
        if (net > 0) {
            owes.computeIfAbsent(debtorId, key -> new HashMap<>()).put(creditorId, net);
        } else if (net < 0) {
            owes.computeIfAbsent(creditorId, key -> new HashMap<>()).put(debtorId, -net);
        }
    }

    public synchronized long amountOwed(String debtorId, String creditorId) {
        return owes.getOrDefault(debtorId, Map.of()).getOrDefault(creditorId, 0L);
    }

    // Positive means the group owes this person. Negative means they owe it.
    // This is the view the simplifier works from, and deriving it fresh each
    // time means it can never drift from the pairwise truth.
    public synchronized Map<String, Long> netBalances() {
        Map<String, Long> net = new LinkedHashMap<>();
        owes.forEach((debtorId, creditors) -> creditors.forEach((creditorId, amount) -> {
            net.merge(debtorId, -amount, Long::sum);
            net.merge(creditorId, amount, Long::sum);
        }));
        net.values().removeIf(value -> value == 0);
        return net;
    }

    private void clear(String debtorId, String creditorId) {
        Map<String, Long> creditors = owes.get(debtorId);
        if (creditors != null) {
            creditors.remove(creditorId);
            if (creditors.isEmpty()) {
                owes.remove(debtorId);
            }
        }
    }
}

package com.androidinterview.splitwise.ledger;

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;

public final class BalanceSheet {

    private final Map<String, Map<String, Long>> owes = new HashMap<>();

    public synchronized void addDebt(String debtorId, String creditorId, long amount) {
        if (debtorId.equals(creditorId) || amount == 0) {
            return;
        }
        long net = amount + amountOwed(debtorId, creditorId) - amountOwed(creditorId, debtorId);
        clear(debtorId, creditorId);
        clear(creditorId, debtorId);
        if (net > 0) {
            owes.computeIfAbsent(debtorId, key -> new HashMap<>()).put(creditorId, net);
        } else if (net < 0) {
            owes.computeIfAbsent(creditorId, key -> new HashMap<>()).put(debtorId, -net);
        }
    }

    public synchronized long amountOwed(String debtorId, String creditorId) {
        return owes.getOrDefault(debtorId, Map.of()).getOrDefault(creditorId, 0L);
    }

    public synchronized Map<String, Long> netBalances() {
        Map<String, Long> net = new LinkedHashMap<>();
        owes.forEach((debtorId, creditors) -> creditors.forEach((creditorId, amount) -> {
            net.merge(debtorId, -amount, Long::sum);
            net.merge(creditorId, amount, Long::sum);
        }));
        net.values().removeIf(value -> value == 0);
        return net;
    }

    private void clear(String debtorId, String creditorId) {
        Map<String, Long> creditors = owes.get(debtorId);
        if (creditors != null) {
            creditors.remove(creditorId);
            if (creditors.isEmpty()) {
                owes.remove(debtorId);
            }
        }
    }
}

package com.androidinterview.splitwise.model;

import java.util.List;

// An expense is immutable once recorded. Editing one is really deleting it and
// adding a new one, because the ledger has already moved on and a silent edit
// would leave balances that do not match any expense anybody can see.
public record Expense(
        String id,
        String groupId,
        String description,
        String paidByUserId,
        Money total,
        List<Split> splits) implements LedgerEntry {
}

package com.androidinterview.splitwise.model;

import java.util.List;

public record Expense(
        String id,
        String groupId,
        String description,
        String paidByUserId,
        Money total,
        List<Split> splits) implements LedgerEntry {
}

package com.androidinterview.splitwise.model;

import java.util.List;

// Membership and the one currency the group settles in. The balances do not
// live here, because a group's ledger has to be locked and mutated as a unit
// and a value object is the wrong place for that.
//
// The currency sits on the group so the ledger's bare numbers have exactly one
// meaning. A caller cannot ask for a settlement plan in a currency the group
// never spent in.
public record Group(String id, String name, String currency, List<String> memberIds) {
}

package com.androidinterview.splitwise.model;

import java.util.List;

public record Group(String id, String name, String currency, List<String> memberIds) {
}

package com.androidinterview.splitwise.model;

// Everything that ever moved the ledger, in one type. An expense and a
// settlement are both movements, and a balance you cannot explain by listing
// the movements behind it is a balance nobody will trust.
public sealed interface LedgerEntry permits Expense, Settlement {
    String id();
    String groupId();
}

package com.androidinterview.splitwise.model;

public sealed interface LedgerEntry permits Expense, Settlement {
    String id();
    String groupId();
}

package com.androidinterview.splitwise.model;

// Minor units, always. A bill split three ways in floating point does not add
// back up to the bill, and this whole problem is about numbers adding up.
public record Money(String currency, long amount) {
}

package com.androidinterview.splitwise.model;

public record Money(String currency, long amount) {
}

package com.androidinterview.splitwise.model;

// A payment that actually happened, recorded rather than inferred. The ledger
// movement on its own says the debt is smaller. This says who paid it, so the
// balance can be explained to a suspicious friend line by line.
public record Settlement(
        String id,
        String groupId,
        String fromUserId,
        String toUserId,
        Money amount) implements LedgerEntry {
}

package com.androidinterview.splitwise.model;

public record Settlement(
        String id,
        String groupId,
        String fromUserId,
        String toUserId,
        Money amount) implements LedgerEntry {
}

package com.androidinterview.splitwise.model;

// One person's share of one expense. The result of applying a split rule, not
// the rule itself.
public record Split(String userId, Money share) {
}

package com.androidinterview.splitwise.model;

public record Split(String userId, Money share) {
}

package com.androidinterview.splitwise.model;

public record User(String id, String name) {
}

package com.androidinterview.splitwise.model;

public record User(String id, String name) {
}

package com.androidinterview.splitwise.service;

import java.util.List;
import java.util.Map;
import java.util.UUID;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.CopyOnWriteArrayList;

import com.androidinterview.splitwise.ledger.BalanceSheet;
import com.androidinterview.splitwise.model.Expense;
import com.androidinterview.splitwise.model.Group;
import com.androidinterview.splitwise.model.LedgerEntry;
import com.androidinterview.splitwise.model.Money;
import com.androidinterview.splitwise.model.Settlement;
import com.androidinterview.splitwise.model.Split;
import com.androidinterview.splitwise.settlement.DebtSimplifier;
import com.androidinterview.splitwise.settlement.Transfer;
import com.androidinterview.splitwise.split.SplitStrategy;

// The one class the app talks to. One ledger per group, because that is the
// unit people reason about and the unit a settlement covers.
//
// Two levels of safety, and they are separate on purpose. Each ledger has its
// own lock, so two groups never contend. The registries around them are
// concurrent collections, so creating a group cannot race an expense being
// added to another one.
public final class SplitwiseService {

    private final Map<String, Group> groups = new ConcurrentHashMap<>();
    private final Map<String, BalanceSheet> ledgers = new ConcurrentHashMap<>();
    private final List<LedgerEntry> entries = new CopyOnWriteArrayList<>();

    public void createGroup(Group group) {
        groups.put(group.id(), group);
        ledgers.put(group.id(), new BalanceSheet());
    }

    // Recording an expense is two steps that must not come apart. Work out the
    // shares, then move every share into the ledger under the ledger's own
    // lock. The payer's own share is skipped, because nobody owes themselves.
    public Expense addExpense(String groupId, String description, String paidByUserId,
                              Money total, List<String> participantIds, SplitStrategy strategy) {
        Group group = requireGroup(groupId);
        if (!group.currency().equals(total.currency())) {
            throw new IllegalArgumentException("the group settles in " + group.currency());
        }
        List<Split> splits = strategy.split(total, participantIds);
        Expense expense = new Expense(UUID.randomUUID().toString(), groupId, description,
                paidByUserId, total, splits);

        BalanceSheet ledger = ledgers.get(groupId);
        synchronized (ledger) {
            for (Split split : splits) {
                ledger.addDebt(split.userId(), paidByUserId, split.share().amount());
            }
        }
        entries.add(expense);
        return expense;
    }

    // A settlement is just another movement in the ledger, in the opposite
    // direction. Treating it as a special kind of record that erases a debt is
    // how you end up unable to explain a balance to a suspicious friend.
    //
    // The movement alone is not enough. The settlement is recorded next to the
    // expenses, because a payment nobody can point at is exactly the balance
    // that starts the argument.
    public Settlement settleUp(String groupId, String fromUserId, String toUserId, Money amount) {
        Group group = requireGroup(groupId);
        if (!group.currency().equals(amount.currency())) {
            throw new IllegalArgumentException("the group settles in " + group.currency());
        }
        Settlement settlement = new Settlement(UUID.randomUUID().toString(),
                groupId, fromUserId, toUserId, amount);

        BalanceSheet ledger = ledgers.get(groupId);
        synchronized (ledger) {
            ledger.addDebt(toUserId, fromUserId, amount.amount());
        }
        entries.add(settlement);
        return settlement;
    }

    public long amountOwed(String groupId, String debtorId, String creditorId) {
        return ledgers.get(groupId).amountOwed(debtorId, creditorId);
    }

    // Suggestions, computed fresh from the current ledger every time. Caching
    // them would hand somebody a payment plan that a new expense has already
    // invalidated.
    public List<Transfer> suggestSettlement(String groupId) {
        Group group = requireGroup(groupId);
        BalanceSheet ledger = ledgers.get(groupId);
        synchronized (ledger) {
            return DebtSimplifier.simplify(ledger.netBalances(), group.currency());
        }
    }

    // The audit trail, expenses and settlements together and in order. This is
    // what turns a number on a screen into something a friend can check.
    public List<LedgerEntry> historyIn(String groupId) {
        return entries.stream().filter(entry -> entry.groupId().equals(groupId)).toList();
    }

    public List<Expense> expensesIn(String groupId) {
        return historyIn(groupId).stream()
                .filter(entry -> entry instanceof Expense)
                .map(entry -> (Expense) entry)
                .toList();
    }

    private Group requireGroup(String groupId) {
        Group group = groups.get(groupId);
        if (group == null) {
            throw new IllegalArgumentException("no such group");
        }
        return group;
    }
}

package com.androidinterview.splitwise.service;

import java.util.List;
import java.util.Map;
import java.util.UUID;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.CopyOnWriteArrayList;

import com.androidinterview.splitwise.ledger.BalanceSheet;
import com.androidinterview.splitwise.model.Expense;
import com.androidinterview.splitwise.model.Group;
import com.androidinterview.splitwise.model.LedgerEntry;
import com.androidinterview.splitwise.model.Money;
import com.androidinterview.splitwise.model.Settlement;
import com.androidinterview.splitwise.model.Split;
import com.androidinterview.splitwise.settlement.DebtSimplifier;
import com.androidinterview.splitwise.settlement.Transfer;
import com.androidinterview.splitwise.split.SplitStrategy;

public final class SplitwiseService {

    private final Map<String, Group> groups = new ConcurrentHashMap<>();
    private final Map<String, BalanceSheet> ledgers = new ConcurrentHashMap<>();
    private final List<LedgerEntry> entries = new CopyOnWriteArrayList<>();

    public void createGroup(Group group) {
        groups.put(group.id(), group);
        ledgers.put(group.id(), new BalanceSheet());
    }

    public Expense addExpense(String groupId, String description, String paidByUserId,
                              Money total, List<String> participantIds, SplitStrategy strategy) {
        Group group = requireGroup(groupId);
        if (!group.currency().equals(total.currency())) {
            throw new IllegalArgumentException("the group settles in " + group.currency());
        }
        List<Split> splits = strategy.split(total, participantIds);
        Expense expense = new Expense(UUID.randomUUID().toString(), groupId, description,
                paidByUserId, total, splits);

        BalanceSheet ledger = ledgers.get(groupId);
        synchronized (ledger) {
            for (Split split : splits) {
                ledger.addDebt(split.userId(), paidByUserId, split.share().amount());
            }
        }
        entries.add(expense);
        return expense;
    }

    public Settlement settleUp(String groupId, String fromUserId, String toUserId, Money amount) {
        Group group = requireGroup(groupId);
        if (!group.currency().equals(amount.currency())) {
            throw new IllegalArgumentException("the group settles in " + group.currency());
        }
        Settlement settlement = new Settlement(UUID.randomUUID().toString(),
                groupId, fromUserId, toUserId, amount);

        BalanceSheet ledger = ledgers.get(groupId);
        synchronized (ledger) {
            ledger.addDebt(toUserId, fromUserId, amount.amount());
        }
        entries.add(settlement);
        return settlement;
    }

    public long amountOwed(String groupId, String debtorId, String creditorId) {
        return ledgers.get(groupId).amountOwed(debtorId, creditorId);
    }

    public List<Transfer> suggestSettlement(String groupId) {
        Group group = requireGroup(groupId);
        BalanceSheet ledger = ledgers.get(groupId);
        synchronized (ledger) {
            return DebtSimplifier.simplify(ledger.netBalances(), group.currency());
        }
    }

    public List<LedgerEntry> historyIn(String groupId) {
        return entries.stream().filter(entry -> entry.groupId().equals(groupId)).toList();
    }

    public List<Expense> expensesIn(String groupId) {
        return historyIn(groupId).stream()
                .filter(entry -> entry instanceof Expense)
                .map(entry -> (Expense) entry)
                .toList();
    }

    private Group requireGroup(String groupId) {
        Group group = groups.get(groupId);
        if (group == null) {
            throw new IllegalArgumentException("no such group");
        }
        return group;
    }
}

package com.androidinterview.splitwise.settlement;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;

import com.androidinterview.splitwise.model.Money;

// The one piece of real algorithm in this problem.
//
// Take the person who is owed the most and the person who owes the most, settle
// the smaller of the two amounts in a single payment, and repeat. Every round
// takes at least one person to a balance of zero, so it finishes in at most one
// payment fewer than there are people with a non zero balance.
//
// It is not provably the minimum. Finding that means looking for subsets that
// already sum to zero, which is subset sum, which is NP hard. Say so out loud.
// The greedy answer is what every real product ships and the interviewer is
// listening for whether you know the difference.
public final class DebtSimplifier {

    private record Balance(String userId, long amount) {}

    private DebtSimplifier() {
    }

    public static List<Transfer> simplify(Map<String, Long> netBalances, String currency) {
        // Ties are broken by user id so the same input always gives the same
        // suggestions. A settlement screen that reshuffles between two loads
        // looks broken even when it is correct.
        Comparator<Balance> byUser = Comparator.comparing(Balance::userId);
        PriorityQueue<Balance> creditors =
                new PriorityQueue<>(Comparator.comparingLong(Balance::amount).reversed().thenComparing(byUser));
        PriorityQueue<Balance> debtors =
                new PriorityQueue<>(Comparator.comparingLong(Balance::amount).thenComparing(byUser));

        netBalances.forEach((userId, amount) -> {
            if (amount > 0) {
                creditors.add(new Balance(userId, amount));
            } else if (amount < 0) {
                debtors.add(new Balance(userId, amount));
            }
        });

        List<Transfer> transfers = new ArrayList<>();
        while (!creditors.isEmpty() && !debtors.isEmpty()) {
            Balance creditor = creditors.poll();
            Balance debtor = debtors.poll();
            long settled = Math.min(creditor.amount(), -debtor.amount());
            transfers.add(new Transfer(debtor.userId(), creditor.userId(), new Money(currency, settled)));

            long creditorLeft = creditor.amount() - settled;
            long debtorLeft = debtor.amount() + settled;
            if (creditorLeft > 0) {
                creditors.add(new Balance(creditor.userId(), creditorLeft));
            }
            if (debtorLeft < 0) {
                debtors.add(new Balance(debtor.userId(), debtorLeft));
            }
        }
        return transfers;
    }
}

package com.androidinterview.splitwise.settlement;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;

import com.androidinterview.splitwise.model.Money;

public final class DebtSimplifier {

    private record Balance(String userId, long amount) {}

    private DebtSimplifier() {
    }

    public static List<Transfer> simplify(Map<String, Long> netBalances, String currency) {
        Comparator<Balance> byUser = Comparator.comparing(Balance::userId);
        PriorityQueue<Balance> creditors =
                new PriorityQueue<>(Comparator.comparingLong(Balance::amount).reversed().thenComparing(byUser));
        PriorityQueue<Balance> debtors =
                new PriorityQueue<>(Comparator.comparingLong(Balance::amount).thenComparing(byUser));

        netBalances.forEach((userId, amount) -> {
            if (amount > 0) {
                creditors.add(new Balance(userId, amount));
            } else if (amount < 0) {
                debtors.add(new Balance(userId, amount));
            }
        });

        List<Transfer> transfers = new ArrayList<>();
        while (!creditors.isEmpty() && !debtors.isEmpty()) {
            Balance creditor = creditors.poll();
            Balance debtor = debtors.poll();
            long settled = Math.min(creditor.amount(), -debtor.amount());
            transfers.add(new Transfer(debtor.userId(), creditor.userId(), new Money(currency, settled)));

            long creditorLeft = creditor.amount() - settled;
            long debtorLeft = debtor.amount() + settled;
            if (creditorLeft > 0) {
                creditors.add(new Balance(creditor.userId(), creditorLeft));
            }
            if (debtorLeft < 0) {
                debtors.add(new Balance(debtor.userId(), debtorLeft));
            }
        }
        return transfers;
    }
}

package com.androidinterview.splitwise.settlement;

import com.androidinterview.splitwise.model.Money;

// One suggested payment. A suggestion and nothing more, because the app cannot
// move anybody's money.
public record Transfer(String fromUserId, String toUserId, Money amount) {
}

package com.androidinterview.splitwise.settlement;

import com.androidinterview.splitwise.model.Money;

public record Transfer(String fromUserId, String toUserId, Money amount) {
}

package com.androidinterview.splitwise.split;

import java.util.ArrayList;
import java.util.List;

import com.androidinterview.splitwise.model.Money;
import com.androidinterview.splitwise.model.Split;

// The common case, and the one with the detail everybody misses. A bill of one
// hundred split three ways is not three shares of thirty three.
public final class EqualSplit implements SplitStrategy {

    @Override
    public List<Split> split(Money total, List<String> participantIds) {
        int people = participantIds.size();
        if (people == 0) {
            throw new IllegalArgumentException("an expense needs at least one participant");
        }
        long each = total.amount() / people;
        long remainder = total.amount() - each * people;

        // Somebody has to absorb the odd cent. Spreading it over the first few
        // participants keeps the shares summing exactly to the bill and keeps
        // the answer deterministic, which matters more than which friend pays
        // the extra penny.
        List<Split> splits = new ArrayList<>();
        for (int i = 0; i < people; i++) {
            long share = each + (i < remainder ? 1 : 0);
            splits.add(new Split(participantIds.get(i), new Money(total.currency(), share)));
        }
        return splits;
    }
}

package com.androidinterview.splitwise.split;

import java.util.ArrayList;
import java.util.List;

import com.androidinterview.splitwise.model.Money;
import com.androidinterview.splitwise.model.Split;

public final class EqualSplit implements SplitStrategy {

    @Override
    public List<Split> split(Money total, List<String> participantIds) {
        int people = participantIds.size();
        if (people == 0) {
            throw new IllegalArgumentException("an expense needs at least one participant");
        }
        long each = total.amount() / people;
        long remainder = total.amount() - each * people;

        List<Split> splits = new ArrayList<>();
        for (int i = 0; i < people; i++) {
            long share = each + (i < remainder ? 1 : 0);
            splits.add(new Split(participantIds.get(i), new Money(total.currency(), share)));
        }
        return splits;
    }
}

package com.androidinterview.splitwise.split;

import java.util.List;
import java.util.Map;

import com.androidinterview.splitwise.model.Money;
import com.androidinterview.splitwise.model.Split;

// Amounts named per person. The rule carries its own configuration, which is
// why a strategy here is a small object rather than a lambda.
public final class ExactSplit implements SplitStrategy {

    private final Map<String, Long> amounts;

    public ExactSplit(Map<String, Long> amounts) {
        this.amounts = Map.copyOf(amounts);
    }

    @Override
    public List<Split> split(Money total, List<String> participantIds) {
        // Every participant has to be named. Without this a missing person
        // sails through the sum check whenever the others happen to cover the
        // bill, and blows up on the way out with nothing useful to say.
        for (String id : participantIds) {
            if (!amounts.containsKey(id)) {
                throw new IllegalArgumentException("no amount named for " + id);
            }
        }
        long sum = participantIds.stream().mapToLong(id -> amounts.getOrDefault(id, 0L)).sum();
        if (sum != total.amount()) {
            throw new IllegalArgumentException("the named amounts do not add up to the bill");
        }
        return participantIds.stream()
                .map(id -> new Split(id, new Money(total.currency(), amounts.get(id))))
                .toList();
    }
}

package com.androidinterview.splitwise.split;

import java.util.List;
import java.util.Map;

import com.androidinterview.splitwise.model.Money;
import com.androidinterview.splitwise.model.Split;

public final class ExactSplit implements SplitStrategy {

    private final Map<String, Long> amounts;

    public ExactSplit(Map<String, Long> amounts) {
        this.amounts = Map.copyOf(amounts);
    }

    @Override
    public List<Split> split(Money total, List<String> participantIds) {
        for (String id : participantIds) {
            if (!amounts.containsKey(id)) {
                throw new IllegalArgumentException("no amount named for " + id);
            }
        }
        long sum = participantIds.stream().mapToLong(id -> amounts.getOrDefault(id, 0L)).sum();
        if (sum != total.amount()) {
            throw new IllegalArgumentException("the named amounts do not add up to the bill");
        }
        return participantIds.stream()
                .map(id -> new Split(id, new Money(total.currency(), amounts.get(id))))
                .toList();
    }
}

package com.androidinterview.splitwise.split;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;

import com.androidinterview.splitwise.model.Money;
import com.androidinterview.splitwise.model.Split;

// Percentages as basis points, so nobody hands us a double and nobody has to
// argue about whether the shares add to a hundred.
public final class PercentageSplit implements SplitStrategy {

    private static final int FULL = 10000;

    private final Map<String, Integer> basisPoints;

    public PercentageSplit(Map<String, Integer> basisPoints) {
        this.basisPoints = Map.copyOf(basisPoints);
    }

    @Override
    public List<Split> split(Money total, List<String> participantIds) {
        int sum = participantIds.stream().mapToInt(id -> basisPoints.getOrDefault(id, 0)).sum();
        if (sum != FULL) {
            throw new IllegalArgumentException("the percentages do not add up to one hundred");
        }
        // The last participant takes whatever is left, so rounding can never
        // leave the shares a cent short of the bill.
        List<Split> splits = new ArrayList<>();
        long allocated = 0;
        for (int i = 0; i < participantIds.size(); i++) {
            String id = participantIds.get(i);
            boolean last = i == participantIds.size() - 1;
            long nominal = Math.round(total.amount() * basisPoints.getOrDefault(id, 0) / (double) FULL);
            long share = last ? total.amount() - allocated : nominal;
            // The last share absorbs the rounding, and that is all it should
            // absorb. More than a minor unit away from its own percentage means
            // the input was inconsistent, a repeated participant for instance,
            // in a way the sum check could not see.
            if (last && Math.abs(share - nominal) > 1) {
                throw new IllegalArgumentException("the percentages do not match the participants");
            }
            allocated += share;
            splits.add(new Split(id, new Money(total.currency(), share)));
        }
        return splits;
    }
}

package com.androidinterview.splitwise.split;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;

import com.androidinterview.splitwise.model.Money;
import com.androidinterview.splitwise.model.Split;

public final class PercentageSplit implements SplitStrategy {

    private static final int FULL = 10000;

    private final Map<String, Integer> basisPoints;

    public PercentageSplit(Map<String, Integer> basisPoints) {
        this.basisPoints = Map.copyOf(basisPoints);
    }

    @Override
    public List<Split> split(Money total, List<String> participantIds) {
        int sum = participantIds.stream().mapToInt(id -> basisPoints.getOrDefault(id, 0)).sum();
        if (sum != FULL) {
            throw new IllegalArgumentException("the percentages do not add up to one hundred");
        }
        List<Split> splits = new ArrayList<>();
        long allocated = 0;
        for (int i = 0; i < participantIds.size(); i++) {
            String id = participantIds.get(i);
            boolean last = i == participantIds.size() - 1;
            long nominal = Math.round(total.amount() * basisPoints.getOrDefault(id, 0) / (double) FULL);
            long share = last ? total.amount() - allocated : nominal;
            if (last && Math.abs(share - nominal) > 1) {
                throw new IllegalArgumentException("the percentages do not match the participants");
            }
            allocated += share;
            splits.add(new Split(id, new Money(total.currency(), share)));
        }
        return splits;
    }
}

package com.androidinterview.splitwise.split;

import java.util.List;

import com.androidinterview.splitwise.model.Money;
import com.androidinterview.splitwise.model.Split;

// How a bill is divided. This is the one genuine seam in the problem, because
// equally, by exact amounts and by percentage are three rules the product ships
// on day one and more arrive later, by shares and by adjustment.
public interface SplitStrategy {
    List<Split> split(Money total, List<String> participantIds);
}

package com.androidinterview.splitwise.split;

import java.util.List;

import com.androidinterview.splitwise.model.Money;
import com.androidinterview.splitwise.model.Split;

public interface SplitStrategy {
    List<Split> split(Money total, List<String> participantIds);
}

package com.androidinterview.splitwise.ledger

import java.util.concurrent.locks.ReentrantLock
import kotlin.concurrent.withLock

// Who owes whom, held pairwise rather than as one net number per person. That
// choice is deliberate. Pairwise answers the question users actually ask, which
// is what do I owe Ana, and net balances can always be derived from it. Going
// the other way is impossible.
//
// Every debt is netted against anything owed the other way as it is recorded, so
// two friends who take turns paying end up with one number instead of a growing
// pile of entries that cancel out.
class BalanceSheet {

    private val owes = mutableMapOf<String, MutableMap<String, Long>>()
    private val guard = ReentrantLock()

    // One expense has to land as one movement, so the caller needs a way to
    // hold the same lock across several debts. The lock is reentrant, so
    // addDebt inside the block takes it again for free, and it stays private so
    // nothing outside can hold it longer than one block.
    fun <T> transact(block: BalanceSheet.() -> T): T = guard.withLock { block() }

    fun addDebt(debtorId: String, creditorId: String, amount: Long) {
        if (debtorId == creditorId || amount == 0L) return
        guard.withLock {
            val net = amount + owedNoLock(debtorId, creditorId) - owedNoLock(creditorId, debtorId)
            clear(debtorId, creditorId)
            clear(creditorId, debtorId)
            when {
                net > 0 -> owes.getOrPut(debtorId) { mutableMapOf() }[creditorId] = net
                net < 0 -> owes.getOrPut(creditorId) { mutableMapOf() }[debtorId] = -net
            }
        }
    }

    fun amountOwed(debtorId: String, creditorId: String): Long =
        guard.withLock { owedNoLock(debtorId, creditorId) }

    // Positive means the group owes this person. Derived fresh every time, so it
    // can never drift from the pairwise truth underneath it.
    fun netBalances(): Map<String, Long> = guard.withLock {
        buildMap<String, Long> {
            owes.forEach { (debtorId, creditors) ->
                creditors.forEach { (creditorId, amount) ->
                    this[debtorId] = (this[debtorId] ?: 0L) - amount
                    this[creditorId] = (this[creditorId] ?: 0L) + amount
                }
            }
        }.filterValues { it != 0L }
    }

    private fun owedNoLock(debtorId: String, creditorId: String) =
        owes[debtorId]?.get(creditorId) ?: 0L

    private fun clear(debtorId: String, creditorId: String) {
        owes[debtorId]?.remove(creditorId)
        if (owes[debtorId]?.isEmpty() == true) owes.remove(debtorId)
    }
}

package com.androidinterview.splitwise.ledger

import java.util.concurrent.locks.ReentrantLock
import kotlin.concurrent.withLock

class BalanceSheet {

    private val owes = mutableMapOf<String, MutableMap<String, Long>>()
    private val guard = ReentrantLock()

    fun <T> transact(block: BalanceSheet.() -> T): T = guard.withLock { block() }

    fun addDebt(debtorId: String, creditorId: String, amount: Long) {
        if (debtorId == creditorId || amount == 0L) return
        guard.withLock {
            val net = amount + owedNoLock(debtorId, creditorId) - owedNoLock(creditorId, debtorId)
            clear(debtorId, creditorId)
            clear(creditorId, debtorId)
            when {
                net > 0 -> owes.getOrPut(debtorId) { mutableMapOf() }[creditorId] = net
                net < 0 -> owes.getOrPut(creditorId) { mutableMapOf() }[debtorId] = -net
            }
        }
    }

    fun amountOwed(debtorId: String, creditorId: String): Long =
        guard.withLock { owedNoLock(debtorId, creditorId) }

    fun netBalances(): Map<String, Long> = guard.withLock {
        buildMap<String, Long> {
            owes.forEach { (debtorId, creditors) ->
                creditors.forEach { (creditorId, amount) ->
                    this[debtorId] = (this[debtorId] ?: 0L) - amount
                    this[creditorId] = (this[creditorId] ?: 0L) + amount
                }
            }
        }.filterValues { it != 0L }
    }

    private fun owedNoLock(debtorId: String, creditorId: String) =
        owes[debtorId]?.get(creditorId) ?: 0L

    private fun clear(debtorId: String, creditorId: String) {
        owes[debtorId]?.remove(creditorId)
        if (owes[debtorId]?.isEmpty() == true) owes.remove(debtorId)
    }
}

package com.androidinterview.splitwise.model

// Minor units, always. A bill split three ways in floating point does not add
// back up to the bill, and this whole problem is about numbers adding up.
data class Money(val currency: String, val amount: Long)

data class User(val id: String, val name: String)

// Membership and the one currency the group settles in. The ledger does not
// live here, because it has to be locked and mutated as a unit and a value
// object is the wrong place for that.
//
// The currency sits on the group so the ledger's bare numbers have exactly one
// meaning. A caller cannot ask for a settlement plan in a currency the group
// never spent in.
data class Group(val id: String, val name: String, val currency: String, val memberIds: List<String>)

// One person's share of one expense. The result of applying a rule, not the
// rule itself.
data class Split(val userId: String, val share: Money)

// Everything that ever moved the ledger, in one type. An expense and a
// settlement are both movements, and a balance you cannot explain by listing
// the movements behind it is a balance nobody will trust.
sealed interface LedgerEntry {
    val id: String
    val groupId: String
}

// Immutable once recorded. Editing an expense is really deleting it and adding
// a new one, because the ledger has already moved on.
data class Expense(
    override val id: String,
    override val groupId: String,
    val description: String,
    val paidByUserId: String,
    val total: Money,
    val splits: List<Split>,
) : LedgerEntry

// A payment that actually happened, recorded rather than inferred. The ledger
// movement on its own says the debt is smaller. This says who paid it, so the
// balance can be explained to a suspicious friend line by line.
data class Settlement(
    override val id: String,
    override val groupId: String,
    val fromUserId: String,
    val toUserId: String,
    val amount: Money,
) : LedgerEntry

package com.androidinterview.splitwise.model

data class Money(val currency: String, val amount: Long)

data class User(val id: String, val name: String)

data class Group(val id: String, val name: String, val currency: String, val memberIds: List<String>)

data class Split(val userId: String, val share: Money)

sealed interface LedgerEntry {
    val id: String
    val groupId: String
}

data class Expense(
    override val id: String,
    override val groupId: String,
    val description: String,
    val paidByUserId: String,
    val total: Money,
    val splits: List<Split>,
) : LedgerEntry

data class Settlement(
    override val id: String,
    override val groupId: String,
    val fromUserId: String,
    val toUserId: String,
    val amount: Money,
) : LedgerEntry

package com.androidinterview.splitwise.service

import com.androidinterview.splitwise.ledger.BalanceSheet
import com.androidinterview.splitwise.model.Expense
import com.androidinterview.splitwise.model.Group
import com.androidinterview.splitwise.model.LedgerEntry
import com.androidinterview.splitwise.model.Money
import com.androidinterview.splitwise.model.Settlement
import com.androidinterview.splitwise.settlement.Transfer
import com.androidinterview.splitwise.settlement.simplify
import com.androidinterview.splitwise.split.SplitStrategy
import com.androidinterview.splitwise.split.split
import java.util.UUID
import java.util.concurrent.ConcurrentHashMap
import java.util.concurrent.CopyOnWriteArrayList

// The one class the app talks to. One ledger per group, because that is the unit
// people reason about and the unit a settlement covers.
//
// Two levels of safety, and they are separate on purpose. Each ledger has its
// own lock, so two groups never contend. The registries around them are
// concurrent collections, so creating a group cannot race an expense being
// added to another one.
class SplitwiseService {

    private val groups = ConcurrentHashMap<String, Group>()
    private val ledgers = ConcurrentHashMap<String, BalanceSheet>()
    private val entries = CopyOnWriteArrayList<LedgerEntry>()

    fun createGroup(group: Group) {
        groups[group.id] = group
        ledgers[group.id] = BalanceSheet()
    }

    // Work out the shares, then move every one of them into the ledger inside
    // one transaction, so a second expense cannot interleave its debts with
    // this one. The payer's own share is skipped inside addDebt, because nobody
    // owes themselves.
    fun addExpense(
        groupId: String,
        description: String,
        paidByUserId: String,
        total: Money,
        participantIds: List<String>,
        strategy: SplitStrategy,
    ): Expense {
        val group = requireGroup(groupId)
        require(group.currency == total.currency) { "the group settles in ${group.currency}" }
        val splits = strategy.split(total, participantIds)
        val expense = Expense(UUID.randomUUID().toString(), groupId, description, paidByUserId, total, splits)

        ledgers.getValue(groupId).transact {
            splits.forEach { addDebt(it.userId, paidByUserId, it.share.amount) }
        }
        entries += expense
        return expense
    }

    // A settlement is just another movement in the ledger, in the opposite
    // direction. Treating it as a special record that erases a debt is how you
    // end up unable to explain a balance to a suspicious friend.
    //
    // The movement alone is not enough. The settlement is recorded next to the
    // expenses, because a payment nobody can point at is exactly the balance
    // that starts the argument.
    fun settleUp(groupId: String, fromUserId: String, toUserId: String, amount: Money): Settlement {
        val group = requireGroup(groupId)
        require(group.currency == amount.currency) { "the group settles in ${group.currency}" }
        val settlement = Settlement(UUID.randomUUID().toString(), groupId, fromUserId, toUserId, amount)

        ledgers.getValue(groupId).addDebt(toUserId, fromUserId, amount.amount)
        entries += settlement
        return settlement
    }

    fun amountOwed(groupId: String, debtorId: String, creditorId: String): Long =
        ledgers.getValue(groupId).amountOwed(debtorId, creditorId)

    // Suggestions, computed fresh from the current ledger every time. Caching
    // them would hand somebody a payment plan a new expense has already
    // invalidated.
    fun suggestSettlement(groupId: String): List<Transfer> =
        simplify(ledgers.getValue(groupId).netBalances(), requireGroup(groupId).currency)

    // The audit trail, expenses and settlements together and in order. This is
    // what turns a number on a screen into something a friend can check.
    fun historyIn(groupId: String): List<LedgerEntry> = entries.filter { it.groupId == groupId }

    fun expensesIn(groupId: String): List<Expense> = historyIn(groupId).filterIsInstance<Expense>()

    private fun requireGroup(groupId: String): Group =
        requireNotNull(groups[groupId]) { "no such group" }
}

package com.androidinterview.splitwise.service

import com.androidinterview.splitwise.ledger.BalanceSheet
import com.androidinterview.splitwise.model.Expense
import com.androidinterview.splitwise.model.Group
import com.androidinterview.splitwise.model.LedgerEntry
import com.androidinterview.splitwise.model.Money
import com.androidinterview.splitwise.model.Settlement
import com.androidinterview.splitwise.settlement.Transfer
import com.androidinterview.splitwise.settlement.simplify
import com.androidinterview.splitwise.split.SplitStrategy
import com.androidinterview.splitwise.split.split
import java.util.UUID
import java.util.concurrent.ConcurrentHashMap
import java.util.concurrent.CopyOnWriteArrayList

class SplitwiseService {

    private val groups = ConcurrentHashMap<String, Group>()
    private val ledgers = ConcurrentHashMap<String, BalanceSheet>()
    private val entries = CopyOnWriteArrayList<LedgerEntry>()

    fun createGroup(group: Group) {
        groups[group.id] = group
        ledgers[group.id] = BalanceSheet()
    }

    fun addExpense(
        groupId: String,
        description: String,
        paidByUserId: String,
        total: Money,
        participantIds: List<String>,
        strategy: SplitStrategy,
    ): Expense {
        val group = requireGroup(groupId)
        require(group.currency == total.currency) { "the group settles in ${group.currency}" }
        val splits = strategy.split(total, participantIds)
        val expense = Expense(UUID.randomUUID().toString(), groupId, description, paidByUserId, total, splits)

        ledgers.getValue(groupId).transact {
            splits.forEach { addDebt(it.userId, paidByUserId, it.share.amount) }
        }
        entries += expense
        return expense
    }

    fun settleUp(groupId: String, fromUserId: String, toUserId: String, amount: Money): Settlement {
        val group = requireGroup(groupId)
        require(group.currency == amount.currency) { "the group settles in ${group.currency}" }
        val settlement = Settlement(UUID.randomUUID().toString(), groupId, fromUserId, toUserId, amount)

        ledgers.getValue(groupId).addDebt(toUserId, fromUserId, amount.amount)
        entries += settlement
        return settlement
    }

    fun amountOwed(groupId: String, debtorId: String, creditorId: String): Long =
        ledgers.getValue(groupId).amountOwed(debtorId, creditorId)

    fun suggestSettlement(groupId: String): List<Transfer> =
        simplify(ledgers.getValue(groupId).netBalances(), requireGroup(groupId).currency)

    fun historyIn(groupId: String): List<LedgerEntry> = entries.filter { it.groupId == groupId }

    fun expensesIn(groupId: String): List<Expense> = historyIn(groupId).filterIsInstance<Expense>()

    private fun requireGroup(groupId: String): Group =
        requireNotNull(groups[groupId]) { "no such group" }
}

package com.androidinterview.splitwise.settlement

import com.androidinterview.splitwise.model.Money
import java.util.PriorityQueue

// One suggested payment. A suggestion and nothing more, because the app cannot
// move anybody's money.
data class Transfer(val fromUserId: String, val toUserId: String, val amount: Money)

private data class Balance(val userId: String, val amount: Long)

// The one piece of real algorithm in this problem.
//
// Take the person who is owed the most and the person who owes the most, settle
// the smaller of the two amounts in a single payment, and repeat. Every round
// zeroes at least one person, so it finishes in at most one payment fewer than
// there are people with a non zero balance.
//
// It is not provably the minimum. Finding that means looking for subsets that
// already sum to zero, which is subset sum, which is NP hard. Say so out loud.
// The greedy answer is what every real product ships.
fun simplify(netBalances: Map<String, Long>, currency: String): List<Transfer> {
    // Ties broken by user id, so the same ledger always produces the same
    // suggestions. A settlement screen that reshuffles between two loads looks
    // broken even when it is correct.
    val creditors = PriorityQueue<Balance>(compareByDescending<Balance> { it.amount }.thenBy { it.userId })
    val debtors = PriorityQueue<Balance>(compareBy<Balance> { it.amount }.thenBy { it.userId })

    netBalances.forEach { (userId, amount) ->
        when {
            amount > 0 -> creditors += Balance(userId, amount)
            amount < 0 -> debtors += Balance(userId, amount)
        }
    }

    return buildList {
        while (creditors.isNotEmpty() && debtors.isNotEmpty()) {
            val creditor = creditors.poll()
            val debtor = debtors.poll()
            val settled = minOf(creditor.amount, -debtor.amount)
            add(Transfer(debtor.userId, creditor.userId, Money(currency, settled)))

            (creditor.amount - settled).takeIf { it > 0 }
                ?.let { creditors += Balance(creditor.userId, it) }
            (debtor.amount + settled).takeIf { it < 0 }
                ?.let { debtors += Balance(debtor.userId, it) }
        }
    }
}

package com.androidinterview.splitwise.settlement

import com.androidinterview.splitwise.model.Money
import java.util.PriorityQueue

data class Transfer(val fromUserId: String, val toUserId: String, val amount: Money)

private data class Balance(val userId: String, val amount: Long)

fun simplify(netBalances: Map<String, Long>, currency: String): List<Transfer> {
    val creditors = PriorityQueue<Balance>(compareByDescending<Balance> { it.amount }.thenBy { it.userId })
    val debtors = PriorityQueue<Balance>(compareBy<Balance> { it.amount }.thenBy { it.userId })

    netBalances.forEach { (userId, amount) ->
        when {
            amount > 0 -> creditors += Balance(userId, amount)
            amount < 0 -> debtors += Balance(userId, amount)
        }
    }

    return buildList {
        while (creditors.isNotEmpty() && debtors.isNotEmpty()) {
            val creditor = creditors.poll()
            val debtor = debtors.poll()
            val settled = minOf(creditor.amount, -debtor.amount)
            add(Transfer(debtor.userId, creditor.userId, Money(currency, settled)))

            (creditor.amount - settled).takeIf { it > 0 }
                ?.let { creditors += Balance(creditor.userId, it) }
            (debtor.amount + settled).takeIf { it < 0 }
                ?.let { debtors += Balance(debtor.userId, it) }
        }
    }
}

package com.androidinterview.splitwise.split

import com.androidinterview.splitwise.model.Money
import com.androidinterview.splitwise.model.Split
import kotlin.math.abs
import kotlin.math.roundToLong

// A sealed hierarchy rather than an open interface, and this is the one place
// the two languages diverge on purpose. Each rule carries its own configuration
// as a data class, and one exhaustive when covers all of them.
//
// Name the tradeoff, because it is real. A sealed set is closed, so nobody
// outside this module can add a rule. That is right here, since the product
// defines the split rules, and it would be wrong for something a plugin should
// extend.
sealed interface SplitStrategy {
    data object Equally : SplitStrategy
    data class ExactAmounts(val amounts: Map<String, Long>) : SplitStrategy
    data class Percentages(val basisPoints: Map<String, Int>) : SplitStrategy
}

private const val FULL_IN_BASIS_POINTS = 10_000

fun SplitStrategy.split(total: Money, participantIds: List<String>): List<Split> = when (this) {

    // The common case, and the one with the detail everybody misses. A bill of
    // one hundred split three ways is not three shares of thirty three.
    // Somebody absorbs the odd cent, and spreading it over the first few keeps
    // the shares summing exactly to the bill and keeps the answer the same on
    // every run.
    SplitStrategy.Equally -> {
        require(participantIds.isNotEmpty()) { "an expense needs at least one participant" }
        val each = total.amount / participantIds.size
        val remainder = total.amount - each * participantIds.size
        participantIds.mapIndexed { index, id ->
            Split(id, Money(total.currency, each + if (index < remainder) 1 else 0))
        }
    }

    is SplitStrategy.ExactAmounts -> {
        // Every participant has to be named. Without this a missing person
        // sails through the sum check whenever the others happen to cover the
        // bill, and blows up on the way out with nothing useful to say.
        participantIds.firstOrNull { it !in amounts }?.let {
            throw IllegalArgumentException("no amount named for $it")
        }
        val named = participantIds.sumOf { amounts.getValue(it) }
        require(named == total.amount) { "the named amounts do not add up to the bill" }
        participantIds.map { Split(it, Money(total.currency, amounts.getValue(it))) }
    }

    // The last participant takes whatever is left, so rounding can never leave
    // the shares a cent short of the bill.
    is SplitStrategy.Percentages -> {
        require(participantIds.sumOf { basisPoints[it] ?: 0 } == FULL_IN_BASIS_POINTS) {
            "the percentages do not add up to one hundred"
        }
        var allocated = 0L
        participantIds.mapIndexed { index, id ->
            val nominal =
                (total.amount * (basisPoints[id] ?: 0) / FULL_IN_BASIS_POINTS.toDouble()).roundToLong()
            val last = index == participantIds.lastIndex
            val share = if (last) total.amount - allocated else nominal
            // The last share absorbs the rounding, and that is all it should
            // absorb. More than a minor unit away from its own percentage means
            // the input was inconsistent, a repeated participant for instance,
            // in a way the sum check could not see.
            require(!last || abs(share - nominal) <= 1) {
                "the percentages do not match the participants"
            }
            allocated += share
            Split(id, Money(total.currency, share))
        }
    }
}

package com.androidinterview.splitwise.split

import com.androidinterview.splitwise.model.Money
import com.androidinterview.splitwise.model.Split
import kotlin.math.abs
import kotlin.math.roundToLong

sealed interface SplitStrategy {
    data object Equally : SplitStrategy
    data class ExactAmounts(val amounts: Map<String, Long>) : SplitStrategy
    data class Percentages(val basisPoints: Map<String, Int>) : SplitStrategy
}

private const val FULL_IN_BASIS_POINTS = 10_000

fun SplitStrategy.split(total: Money, participantIds: List<String>): List<Split> = when (this) {

    SplitStrategy.Equally -> {
        require(participantIds.isNotEmpty()) { "an expense needs at least one participant" }
        val each = total.amount / participantIds.size
        val remainder = total.amount - each * participantIds.size
        participantIds.mapIndexed { index, id ->
            Split(id, Money(total.currency, each + if (index < remainder) 1 else 0))
        }
    }

    is SplitStrategy.ExactAmounts -> {
        participantIds.firstOrNull { it !in amounts }?.let {
            throw IllegalArgumentException("no amount named for $it")
        }
        val named = participantIds.sumOf { amounts.getValue(it) }
        require(named == total.amount) { "the named amounts do not add up to the bill" }
        participantIds.map { Split(it, Money(total.currency, amounts.getValue(it))) }
    }

    is SplitStrategy.Percentages -> {
        require(participantIds.sumOf { basisPoints[it] ?: 0 } == FULL_IN_BASIS_POINTS) {
            "the percentages do not add up to one hundred"
        }
        var allocated = 0L
        participantIds.mapIndexed { index, id ->
            val nominal =
                (total.amount * (basisPoints[id] ?: 0) / FULL_IN_BASIS_POINTS.toDouble()).roundToLong()
            val last = index == participantIds.lastIndex
            val share = if (last) total.amount - allocated else nominal
            require(!last || abs(share - nominal) <= 1) {
                "the percentages do not match the participants"
            }
            allocated += share
            Split(id, Money(total.currency, share))
        }
    }
}