Splitwise Expense Splitter

Split an expense between friends and work out who pays whom to settle up. This is the most frequently set 90-minute machine-coding round because it looks like an CRUD exercise and then is not: money must be exact (100 / 3 is not a number your language gives you for free), split rules arrive one at a time while you are already coding, and the settlement step is a small algorithm, not a loop over a list. Evaluators watch for three things: a design that absorbs a new split type without a rewrite, an invariant that shares always sum to the total, and clean enough structure that tests keep passing while requirements change under them.

Target behaviour

Build until your program prints this.

> add-user alice
> add-user bob
> add-user carol
> spend 9000 alice "team lunch" equal alice bob carol
alice paid 90.00 for 'team lunch' split 3 ways
> spend 4500 bob "taxi" exact bob=0 carol=4500
bob paid 45.00 for 'taxi'; carol owes it all
> balances
carol owes 7500  (75.00)
bob   owes 3000  (30.00)
alice is owed   10500  (105.00)
> settle
carol pays alice 7500
bob   pays alice 3000

Amounts are cents internally and printed as decimal only at the edge — the same rule the Expense Tracker CLI teaches.

Splits as strategies

Every split rule answers one question: given a total and the participants, who owes how much? That is a strategy interface, and each rule is one small class.

public interface SplitStrategy {
    Map<String, Long> split(long totalCents, List<Participant> participants);
}

public record Participant(String userId, long exactCents, int percent) {
    public static Participant plain(String userId) { return new Participant(userId, 0, 0); }
}

Equal split is where the famous problem lives: 9000 / 3 divides cleanly, but 10000 / 3 is 3333.33 recurring. Distribute the remainder cents to the first participants, one cent each — the sum is then exact and deterministic.

public final class EqualSplit implements SplitStrategy {
    @Override
    public Map<String, Long> split(long total, List<Participant> ps) {
        Map<String, Long> out = new LinkedHashMap<>();
        long base = total / ps.size(), leftover = total % ps.size();
        for (int i = 0; i < ps.size(); i++)
            out.put(ps.get(i).userId(), base + (i < leftover ? 1 : 0));
        return out;
    }
}

Exact split takes the amounts from the participants; percent split multiplies and divides. They share the shape and differ in one method — that is the whole point of the pattern.

public final class ExactSplit implements SplitStrategy {
    @Override
    public Map<String, Long> split(long total, List<Participant> ps) {
        Map<String, Long> out = new LinkedHashMap<>();
        ps.forEach(p -> out.put(p.userId(), p.exactCents()));
        return out;
    }
}

A registry — just a map — replaces any switch on type, so registering "shares" later is one line with no existing class edited.

public static final Map<String, SplitStrategy> STRATEGIES = Map.of(
    "equal", new EqualSplit(), "exact", new ExactSplit(), "percent", new PercentSplit());

Invariants, enforced in one place

The service, not the strategies, owns the rules that keep money honest: shares must sum to the total, percents to 100, and participants must exist. Validate the strategy's output too — a sum check after splitting catches bugs in any strategy, including the one you add in the last ten minutes.

static Map<String, Long> checked(SplitStrategy s, long total, List<Participant> ps) {
    Map<String, Long> shares = s.split(total, ps);
    long sum = shares.values().stream().mapToLong(Long::longValue).sum();
    if (sum != total)
        throw new IllegalArgumentException("split sums to " + sum + ", total is " + total);
    return shares;
}

Balances

Do not store running balances — they are a projection, and projections drift. Store expenses as events and compute the net position: the payer's balance goes up by the total, each participant's down by their share. Zero means settled.

public Map<String, Long> balances() {
    Map<String, Long> net = new HashMap<>();
    for (Expense e : expenses) {
        net.merge(e.payerId(), e.totalCents(), Long::sum);
        e.shares().forEach((u, s) -> net.merge(u, -s, Long::sum));
    }
    return net;
}

Expense is an immutable record: (String id, String payerId, String description, long totalCents, Map<String, Long> shares). Asking "what does bob owe alice specifically?" is a different question — the pairwise ledger — and the follow-up interviewers love: the net balances answer is correct even though intermediate pairwise debts were netted away.

Settlement with greedy cash flow

To settle, repeatedly match the largest debtor against the largest creditor for the smaller of the two amounts. Two priority queues do it: one ordered most-negative-first, one most-positive-first.

static List<Payment> settleUp(Map<String, Long> net) {
    record Pair(String user, long amount) {}
    var debtors = new PriorityQueue<Pair>(Comparator.comparingLong(Pair::amount));
    var creditors = new PriorityQueue<Pair>((a, b) -> Long.compare(b.amount(), a.amount()));
    net.forEach((u, v) -> {
        if (v < 0) debtors.add(new Pair(u, v));
        if (v > 0) creditors.add(new Pair(u, v));
    });
    List<Payment> payments = new ArrayList<>();
    while (!debtors.isEmpty() && !creditors.isEmpty()) {
        var d = debtors.poll();
        var c = creditors.poll();
        long amount = Math.min(-d.amount(), c.amount());
        payments.add(new Payment(d.user(), c.user(), amount));
        if (-d.amount() > amount) debtors.add(new Pair(d.user(), d.amount() + amount));
        if (c.amount() > amount) creditors.add(new Pair(c.user(), c.amount() - amount));
    }
    return payments;
}

Payment(String from, String to, long cents). The greedy sweep is easy to explain and always settles everyone; be honest in the interview that it is not guaranteed to be the minimum number of transfers — that is an NP-hard graph problem — it is the minimum anyone expects in 90 minutes.

The REPL

A read-eval-print loop keeps the demo interactive without any framework: read a line, split on whitespace ( honour quoted text with a tiny helper), dispatch to a command method.

try (var in = new BufferedReader(new InputStreamReader(System.in))) {
    String line;
    System.out.print("> ");
    while ((line = in.readLine()) != null) {
        try {
            System.out.println(Command.dispatch(Splitter.tokenize(line), service));
        } catch (Exception e) {
            System.out.println("error: " + e.getMessage());
        }
        System.out.print("> ");
    }
}

One try/catch at the top is deliberate: a malformed command prints an error and returns to the prompt. A round is lost more often to an unhandled exception killing the demo than to a missing feature.

If they ask about concurrency

The REPL is single-threaded and that is the right scope for the round. The follow-up "what if two gateways hit this as a service" has a two-part answer: wrap spend in synchronized (balances derive from the expense list, so the list append and any validation must be one atomic step), and note that switching the list to a CopyOnWriteArrayList alone is not enough — check-then-act pairs still need a lock. Say the word "compound action" and you have answered the real question.

Testing

Strategies and settlement are pure functions, so the tests are fast, framework-free and — in a machine-coding round — visible proof the code works. Cover the remainder case, the validation failures and settlement conservation.

class SplitterTest {
    @Test
    void equalSplitDistributesRemainderCents() {
        var shares = new EqualSplit().split(10000,
            List.of(Participant.plain("a"), Participant.plain("b"), Participant.plain("c")));
        assertThat(shares.values().stream().mapToLong(Long::longValue).sum()).isEqualTo(10000);
        assertThat(shares).containsEntry("a", 3334L).containsEntry("b", 3333L);
    }

    @Test
    void settlementClearsEveryBalance() {
        var payments = Splitter.settleUp(Map.of("a", 10500L, "b", -3000L, "c", -7500L));
        assertThat(payments).containsExactly(new Payment("c", "a", 7500), new Payment("b", "a", 3000));
    }
}

Add a property-style test: for random expense lists, settleUp(balances()) must always sum transferred cents to the total debt and leave every net balance at zero when applied.

Bugs you will hit

• double amounts. 10000.0 / 3 rounds, totals stop matching, and the balance sheet is off by a cent that no one can find. Cents as long from the first line of code.
• Percent splits that do not total 100. Validate before splitting, or the rounding of each percentage independently makes the sum drift; the output sum check then fails confusingly late.
• Storing balances instead of expenses. The first settlement "settles" a balance to zero and history is gone forever; a later refund has nothing to net against. Events in, projections out.
• HashMap shares. Output order changes between runs and the demo looks broken. LinkedHashMap keeps insertion order at zero cost.
• Mutating a Map entry while iterating. Adjusting balances in a for-each over the same map throws ConcurrentModificationException; collect updates, then merge.

Interview angle

• Why strategy plus registry instead of a switch? The evaluator's favourite move is "now support shares/split-by-weight" two minutes before time. A new class plus one registry line is a 30-second change that touches no existing code — the open/closed principle as a survival tactic, not a slide.
• How do you split 100 between three people exactly? Floor division plus remainder distribution to the first participants. Follow-up: is that fair? The alternative — giving one person the extra cent — is exactly what banks do with interest rounding; state the rule and be consistent.
• Why compute balances instead of storing them? An event log is the source of truth; balances are a cheap fold over it. This also answers "how would you persist this": append the expense events, rebuild state by replay.
• Does greedy settlement minimize transfers? It minimizes nothing provably; it terminates with everyone at zero using at most n - 1 transfers. Minimum transfers is NP-hard (reduce it to a graph partition); saying this out loud is worth more than pretending.
• What is the time complexity of settlement? Each payment removes at least one party from a queue, so O(n log n) for the heap operations across at most n - 1 payments.