Splitwise
Design Splitwise: users, groups, expenses split equally, by exact amounts or by percentage (Strategy), balances in integer cents, and debt simplification.
On this page
- The problem: shared expenses that never add up
- 1. Clarify the requirements
- 2. Entities and the class design
- 3. Money: integer cents, and where the leftover cent goes
- 4. The code
- 5. Simplifying debts
- 6. Concurrency: two phones, one group
- 7. Extensions the interviewer will ask for
- When not to over-design
- In the interview
- Quiz
The problem: shared expenses that never add up
Four friends on a trip pay for dinner, a taxi, a hotel and groceries, each split differently. Splitwise is an app that records who paid what and tells everyone who owes whom. It is a popular machine-coding question because it mixes three things interviewers like: a clean Strategy for the split types, money arithmetic that must be exact, and a small algorithm (simplifying debts).
The usual first attempt:
class Splitwise {
Map<String, Map<String, Double>> owes = new HashMap<>(); // owes[a][b] = what a owes b
void addExpense(String payer, double amount, List<String> people, String type, List<Double> values) {
for (int i = 0; i < people.size(); i++) {
double share;
if (type.equals("EQUAL")) share = amount / people.size();
else if (type.equals("EXACT")) share = values.get(i);
else share = amount * values.get(i) / 100; // PERCENT
owes.computeIfAbsent(people.get(i), k -> new HashMap<>()).merge(payer, share, Double::sum);
}
}
}
What is wrong:
- Money as
double. 100 / 3 is 33.333333333333336. Three shares add up to 100.00000000000001, and after a few hundred expenses balances show "you owe 0.0000001". - No validation. Exact amounts that don't add up to the total, or percentages that add up to 90, are silently accepted, and money appears from nowhere.
- The split type is a string with an
ifchain; a new type ("by shares", "by nights stayed") edits this method. - A person owes themselves their own share, and the pairwise map grows into a tangle of debts that nobody can settle in fewer than a dozen transfers.
1. Clarify the requirements
The interviewer says "Design Splitwise." Write 5 questions and the requirements you would agree on.
Compare with our answer
Questions worth asking: Which split types: equal, exact, percentage, shares? Groups, or also expenses between two friends? One currency or many? Do we need "simplify debts"? Can expenses be edited or deleted? Do we record settle-up payments? Is it a library, or an app with many users at once?
A strong answer mentions: the split types and their validation rules · groups with members · balances per person · settle-up payments · money representation and rounding · debt simplification · out of scope: multiple currencies, notifications, receipts.
The agreed list:
| Requirement | Detail |
|---|---|
| Users and groups | A group has members; expenses belong to a group |
| Expense | Paid by one member, for an amount, split among some members |
| Split types | Equal; exact amounts (must add up to the total); percentage (must add up to 100%) |
| Balances | Each member's net position: positive = is owed, negative = owes |
| Settle up | Record a payment from one member to another |
| Simplify | Suggest a small set of transfers that clears every balance |
| Money | Exact: no rounding drift, no cent lost or created |
Out of scope: multiple currencies, editing history, notifications and the user interface. Each appears as an extension below.
2. Entities and the class design
Nouns: user, group, expense, payer, share, split type, balance, payment, transfer. Payer is a field of an expense. Share is a number per person, stored in the expense. Balance is a number per person in the group. Split type is behaviour that varies, so it becomes an interface.
Group, Expense, and the SplitStrategy family
| Class / type | Kind | Responsibility |
|---|---|---|
User | value object | Id and name; equality by value |
SplitStrategy | interface | split(amountCents, people) → a share per person that adds up to the amount exactly; validates its own inputs |
EqualSplit, ExactSplit, PercentSplit | strategies | The three split rules |
Expense | value object | Description, payer, amount, the computed shares. Immutable once recorded |
Transfer | value object | "A pays B this much": the output of simplification |
Group | class | Members, expenses, net balances; adds expenses and payments; simplifies debts |
Why these choices:
- Strategy for the split. Each split type has its own inputs and its own validation, and new ones arrive ("by shares": 2 shares for a couple, 1 for a single person). Each is a class with one method;
Grouponly callssplit. See the Strategy pattern. - Shares are computed once and stored in the expense. If balances ever need recomputing (after a bug fix, or an edit), the expenses are the source of truth.
- Net balance per person, not a pairwise "A owes B" matrix. For simplification only the net matters, and it is n numbers instead of n².
3. Money: integer cents, and where the leftover cent goes
Floating-point numbers are binary fractions, so most decimal amounts (0.10, 33.33) cannot be stored exactly; 0.1 + 0.2 is 0.30000000000000004. Two exact representations:
| Representation | How | Good at | Watch out for |
|---|---|---|---|
Integer minor units (cents) in a long / int | 100.00 is 10000 | Fast, simple, exact; easy to store in a database BIGINT | Currencies differ: JPY has 0 decimal places, KWD has 3, so store the currency with the amount |
Decimal type: Java BigDecimal, Python decimal.Decimal | new BigDecimal("100.00") | Exact decimal fractions; handy for rates and percentages | Division needs an explicit scale and rounding mode; new BigDecimal(0.1) (from a double) is inexact; slower |
This page uses integer cents. The remaining question is what happens when an amount does not divide evenly.
Splitting 100.00 three ways with integer cents
Each strategy gives everyone the rounded-down share and then hands out the leftover cents one at a time, so the shares always add up to the exact amount. Who gets the extra cent is a product rule: the first people in the list (as here), the payer, or a random person. Pick one, make it deterministic, and say it out loud.
4. The code
The complete model: three split strategies with validation, a group with net balances, settle-up payments, greedy simplification, and a demo that replays the trip, rejects a bad split, settles everything, and then adds 4,000 expenses from four threads.
import java.util.*;
import java.util.concurrent.*;
record User(String id, String name) {}
/** How an expense is divided. Every strategy returns shares in cents that add up to the amount exactly. */
interface SplitStrategy {
Map<User, Long> split(long amountCents, List<User> people);
}
final class EqualSplit implements SplitStrategy {
public Map<User, Long> split(long amount, List<User> people) {
long base = amount / people.size(), extra = amount % people.size();
Map<User, Long> out = new LinkedHashMap<>();
for (int i = 0; i < people.size(); i++) out.put(people.get(i), base + (i < extra ? 1 : 0)); // leftover cents go to the first few
return out;
}
}
final class ExactSplit implements SplitStrategy {
private final List<Long> amounts;
ExactSplit(Long... amounts) { this.amounts = List.of(amounts); }
public Map<User, Long> split(long amount, List<User> people) {
if (amounts.size() != people.size()) throw new IllegalArgumentException("one amount per person");
if (amounts.stream().mapToLong(Long::longValue).sum() != amount)
throw new IllegalArgumentException("exact amounts must add up to " + amount);
Map<User, Long> out = new LinkedHashMap<>();
for (int i = 0; i < people.size(); i++) out.put(people.get(i), amounts.get(i));
return out;
}
}
/** Percentages in basis points: 4000 = 40.00%. Integers, so 33.33% is exact. */
final class PercentSplit implements SplitStrategy {
private final List<Integer> basisPoints;
PercentSplit(Integer... basisPoints) { this.basisPoints = List.of(basisPoints); }
public Map<User, Long> split(long amount, List<User> people) {
if (basisPoints.size() != people.size()) throw new IllegalArgumentException("one percentage per person");
if (basisPoints.stream().mapToInt(Integer::intValue).sum() != 10_000)
throw new IllegalArgumentException("percentages must add up to 100%");
Map<User, Long> out = new LinkedHashMap<>();
long given = 0;
for (int i = 0; i < people.size(); i++) {
long share = amount * basisPoints.get(i) / 10_000; // rounds down
out.put(people.get(i), share); given += share;
}
for (int i = 0; given < amount; i++, given++) // hand out the rounding cents one by one
out.merge(people.get(i % people.size()), 1L, Long::sum);
return out;
}
}
record Expense(String id, String description, User paidBy, long amountCents, Map<User, Long> shares) {}
record Transfer(User from, User to, long cents) {
public String toString() { return from.name() + " pays " + to.name() + " " + Money.fmt(cents); }
}
final class Money {
static String fmt(long cents) { return String.format("%s%d.%02d", cents < 0 ? "-" : "", Math.abs(cents) / 100, Math.abs(cents) % 100); }
}
final class Group {
final String name;
private final Set<User> members = new LinkedHashSet<>();
private final List<Expense> expenses = new ArrayList<>();
private final Map<User, Long> net = new LinkedHashMap<>(); // + is owed money, - owes money
private int seq;
Group(String name, User... users) { this.name = name; for (User u : users) addMember(u); }
synchronized void addMember(User u) { members.add(u); net.putIfAbsent(u, 0L); }
synchronized Expense addExpense(String desc, User paidBy, long amountCents, List<User> people, SplitStrategy how) {
if (amountCents <= 0) throw new IllegalArgumentException("amount must be positive");
if (!members.contains(paidBy) || !members.containsAll(people)) throw new IllegalArgumentException("not a group member");
Map<User, Long> shares = how.split(amountCents, people); // validate before changing anything
Expense e = new Expense("E" + (++seq), desc, paidBy, amountCents, Collections.unmodifiableMap(new LinkedHashMap<>(shares)));
expenses.add(e);
net.merge(paidBy, amountCents, Long::sum);
shares.forEach((u, s) -> net.merge(u, -s, Long::sum));
return e;
}
/** A real payment between two members ("settle up"). */
synchronized void recordPayment(User from, User to, long cents) {
net.merge(from, cents, Long::sum);
net.merge(to, -cents, Long::sum);
}
synchronized Map<User, Long> balances() { return new LinkedHashMap<>(net); }
/** Greedy: the biggest debtor pays the biggest creditor. At most n - 1 transfers. */
synchronized List<Transfer> simplify() {
Comparator<Map.Entry<User, Long>> byAmount = (a, b) -> Long.compare(Math.abs(b.getValue()), Math.abs(a.getValue()));
PriorityQueue<Map.Entry<User, Long>> owed = new PriorityQueue<>(byAmount), owes = new PriorityQueue<>(byAmount);
for (Map.Entry<User, Long> e : net.entrySet()) {
if (e.getValue() > 0) owed.add(new AbstractMap.SimpleEntry<>(e));
else if (e.getValue() < 0) owes.add(new AbstractMap.SimpleEntry<>(e));
}
List<Transfer> out = new ArrayList<>();
while (!owed.isEmpty() && !owes.isEmpty()) {
var c = owed.poll(); var d = owes.poll();
long x = Math.min(c.getValue(), -d.getValue());
out.add(new Transfer(d.getKey(), c.getKey(), x));
if (c.getValue() - x > 0) { c.setValue(c.getValue() - x); owed.add(c); }
if (d.getValue() + x < 0) { d.setValue(d.getValue() + x); owes.add(d); }
}
return out;
}
}
public class SplitwiseDemo {
public static void main(String[] args) throws Exception {
User alice = new User("u1", "alice"), bob = new User("u2", "bob"), carol = new User("u3", "carol"), dan = new User("u4", "dan");
Group trip = new Group("Goa trip", alice, bob, carol, dan);
Expense dinner = trip.addExpense("dinner", alice, 10_000, List.of(alice, bob, carol), new EqualSplit());
System.out.println("dinner shares: " + fmt(dinner.shares()));
trip.addExpense("taxi", bob, 6_000, List.of(alice, bob, dan), new ExactSplit(1_000L, 2_000L, 3_000L));
trip.addExpense("hotel", carol, 20_000, List.of(alice, bob, carol, dan), new PercentSplit(4000, 3000, 2000, 1000));
trip.addExpense("groceries", dan, 9_000, List.of(alice, bob, carol, dan), new EqualSplit());
try { trip.addExpense("bad", bob, 5_000, List.of(alice, bob), new ExactSplit(1_000L, 2_000L)); }
catch (IllegalArgumentException e) { System.out.println("rejected: " + e.getMessage()); }
Map<User, Long> b = trip.balances();
System.out.println("balances: " + fmt(b) + " (sum " + b.values().stream().mapToLong(Long::longValue).sum() + ")");
List<Transfer> plan = trip.simplify();
plan.forEach(t -> System.out.println(" " + t));
for (Transfer t : plan) trip.recordPayment(t.from(), t.to(), t.cents());
System.out.println("after settling: " + fmt(trip.balances()));
// Concurrency: 4 threads add 1,000 expenses each; the balances must still sum to zero
Group g = new Group("flat", alice, bob, carol);
ExecutorService pool = Executors.newFixedThreadPool(4);
List<Future<?>> fs = new ArrayList<>();
for (int t = 0; t < 4; t++) fs.add(pool.submit(() -> {
for (int i = 0; i < 1_000; i++) g.addExpense("x", bob, 1_001, List.of(alice, bob, carol), new EqualSplit());
}));
for (Future<?> f : fs) f.get();
pool.shutdown();
long sum = g.balances().values().stream().mapToLong(Long::longValue).sum();
System.out.println("4,000 concurrent expenses: bob is owed " + Money.fmt(g.balances().get(bob)) + ", sum " + sum);
}
static String fmt(Map<User, Long> m) {
StringJoiner j = new StringJoiner(", ");
m.forEach((u, c) -> j.add(u.name() + " " + Money.fmt(c)));
return j.toString();
}
}import heapq
import itertools
import threading
from abc import ABC, abstractmethod
from concurrent.futures import ThreadPoolExecutor
from dataclasses import dataclass
@dataclass(frozen=True)
class User:
id: str
name: str
def fmt(cents: int) -> str:
sign = "-" if cents < 0 else ""
return f"{sign}{abs(cents) // 100}.{abs(cents) % 100:02d}"
class SplitStrategy(ABC):
"""How an expense is divided. Shares are in cents and add up to the amount exactly."""
@abstractmethod
def split(self, amount: int, people: list) -> dict: ...
class EqualSplit(SplitStrategy):
def split(self, amount, people):
base, extra = divmod(amount, len(people))
# leftover cents go to the first few people
return {u: base + (1 if i < extra else 0) for i, u in enumerate(people)}
class ExactSplit(SplitStrategy):
def __init__(self, *amounts: int):
self.amounts = amounts
def split(self, amount, people):
if len(self.amounts) != len(people):
raise ValueError("one amount per person")
if sum(self.amounts) != amount:
raise ValueError(f"exact amounts must add up to {amount}")
return dict(zip(people, self.amounts))
class PercentSplit(SplitStrategy):
"""Percentages in basis points: 4000 = 40.00%. Integers, so 33.33% is exact."""
def __init__(self, *basis_points: int):
self.bp = basis_points
def split(self, amount, people):
if len(self.bp) != len(people):
raise ValueError("one percentage per person")
if sum(self.bp) != 10_000:
raise ValueError("percentages must add up to 100%")
out = {u: amount * p // 10_000 for u, p in zip(people, self.bp)} # rounds down
for i in range(amount - sum(out.values())): # hand out the rounding cents
out[people[i % len(people)]] += 1
return out
@dataclass(frozen=True)
class Expense:
id: str
description: str
paid_by: User
amount: int
shares: dict
@dataclass(frozen=True)
class Transfer:
frm: User
to: User
cents: int
def __str__(self):
return f"{self.frm.name} pays {self.to.name} {fmt(self.cents)}"
class Group:
def __init__(self, name: str, *users: User):
self.name = name
self._members: dict = {} # insertion-ordered set
self._expenses: list = []
self._net: dict = {} # + is owed money, - owes money
self._seq = itertools.count(1)
self._lock = threading.Lock()
for u in users:
self.add_member(u)
def add_member(self, u: User) -> None:
with self._lock:
self._members[u] = True
self._net.setdefault(u, 0)
def add_expense(self, desc: str, paid_by: User, amount: int, people: list,
how: SplitStrategy) -> Expense:
if amount <= 0:
raise ValueError("amount must be positive")
with self._lock:
if paid_by not in self._members or any(p not in self._members for p in people):
raise ValueError("not a group member")
shares = how.split(amount, people) # validate before changing anything
e = Expense(f"E{next(self._seq)}", desc, paid_by, amount, dict(shares))
self._expenses.append(e)
self._net[paid_by] += amount
for u, s in shares.items():
self._net[u] -= s
return e
def record_payment(self, frm: User, to: User, cents: int) -> None:
"""A real payment between two members ("settle up")."""
with self._lock:
self._net[frm] += cents
self._net[to] -= cents
def balances(self) -> dict:
with self._lock:
return dict(self._net)
def simplify(self) -> list:
"""Greedy: the biggest debtor pays the biggest creditor. At most n - 1 transfers."""
with self._lock:
order = {u: i for i, u in enumerate(self._net)} # tie-break: member order
owed = [(-c, order[u], u) for u, c in self._net.items() if c > 0]
owes = [(c, order[u], u) for u, c in self._net.items() if c < 0]
heapq.heapify(owed)
heapq.heapify(owes)
out = []
while owed and owes:
c_amt, ci, c = heapq.heappop(owed) # c_amt is minus what c is owed
d_amt, di, d = heapq.heappop(owes) # d_amt is minus what d owes
x = min(-c_amt, -d_amt)
out.append(Transfer(d, c, x))
if -c_amt - x > 0:
heapq.heappush(owed, (c_amt + x, ci, c))
if -d_amt - x > 0:
heapq.heappush(owes, (d_amt + x, di, d))
return out
def show(m: dict) -> str:
return ", ".join(f"{u.name} {fmt(c)}" for u, c in m.items())
if __name__ == "__main__":
alice, bob, carol, dan = (User(f"u{i}", n) for i, n in
enumerate(["alice", "bob", "carol", "dan"], 1))
trip = Group("Goa trip", alice, bob, carol, dan)
dinner = trip.add_expense("dinner", alice, 10_000, [alice, bob, carol], EqualSplit())
print("dinner shares:", show(dinner.shares))
trip.add_expense("taxi", bob, 6_000, [alice, bob, dan], ExactSplit(1_000, 2_000, 3_000))
trip.add_expense("hotel", carol, 20_000, [alice, bob, carol, dan],
PercentSplit(4000, 3000, 2000, 1000))
trip.add_expense("groceries", dan, 9_000, [alice, bob, carol, dan], EqualSplit())
try:
trip.add_expense("bad", bob, 5_000, [alice, bob], ExactSplit(1_000, 2_000))
except ValueError as e:
print("rejected:", e)
b = trip.balances()
print(f"balances: {show(b)} (sum {sum(b.values())})")
plan = trip.simplify()
for t in plan:
print(" ", t)
for t in plan:
trip.record_payment(t.frm, t.to, t.cents)
print("after settling:", show(trip.balances()))
g = Group("flat", alice, bob, carol)
def add_many(_):
for _ in range(1_000):
g.add_expense("x", bob, 1_001, [alice, bob, carol], EqualSplit())
with ThreadPoolExecutor(max_workers=4) as pool:
list(pool.map(add_many, range(4)))
bal = g.balances()
print(f"4,000 concurrent expenses: bob is owed {fmt(bal[bob])}, sum {sum(bal.values())}")Running either version prints:
dinner shares: alice 33.34, bob 33.33, carol 33.33
rejected: exact amounts must add up to 5000
balances: alice -45.84, bob -75.83, carol 104.17, dan 17.50 (sum 0)
bob pays carol 75.83
alice pays carol 28.34
alice pays dan 17.50
after settling: alice 0.00, bob 0.00, carol 0.00, dan 0.00
4,000 concurrent expenses: bob is owed 26680.00, sum 0
Check one balance by hand. Alice paid 100.00 for dinner. Her shares are 33.34 (dinner) + 10.00 (taxi) + 80.00 (40% of the hotel) + 22.50 (a quarter of the groceries) = 145.84. Net: 100.00 − 145.84 = −45.84, she owes 45.84. The sum of all balances is zero, which is the invariant to test after every operation: money is only moved, never created.
Note how the payer's own share is handled. Alice paid 100.00 and her share is 33.34; adding +100.00 and −33.34 to her balance leaves +66.66, which is what the others owe her for dinner. No special case for "a person owes themselves" is needed.
5. Simplifying debts
Without simplification, every expense creates debts between the payer and each participant. Four people quickly need six transfers.
From six debts to three transfers
The greedy algorithm in the code:
- Split the members into creditors (balance > 0) and debtors (balance < 0), each in a priority queue by size.
- Take the largest creditor and the largest debtor. The debtor pays
min(credit, debt). - Whoever is not fully settled goes back into their queue. Repeat until both are empty.
Each round settles at least one person, so it produces at most n − 1 transfers for n people with a non-zero balance, in O(n log n) time.
Is the greedy answer the minimum?
Not always. The true minimum is n − k, where k is the largest number of separate subgroups whose balances each sum to zero (each such subgroup can settle internally with size − 1 transfers). Example: balances +5, +4, +2, −5, −6. The minimum is 3 transfers: the +5 and −5 settle each other, and the −6 pays the +4 and the +2. Greedy starts with the largest pair (+5 and −6), which breaks the perfect +5/−5 match, and needs 4. Finding the largest zero-sum partition is NP-hard (it contains the subset-sum problem), so real apps use the greedy method or a search for small groups. In the interview: describe greedy, state the n − 1 bound, and mention that exact minimisation is NP-hard.
6. Concurrency: two phones, one group
Several members add expenses from their phones at the same moment.
| Race | What goes wrong | Fix |
|---|---|---|
| Two expenses update the same balance | Read-modify-write on net[bob]: one update is lost, and the balances no longer sum to zero | All changes to a group happen under one lock per group (synchronized, with self._lock); in a database, one transaction per expense |
| Half-applied expense | Payer credited, then a share fails validation: balances are off by the amount | Validate and compute all shares before changing anything, then apply in one critical section or transaction |
| Simplify while an expense is added | The suggested transfers are computed from a mix of old and new balances | Copy the balances under the lock, then compute from the snapshot |
| Double submit (a retry after a timeout) | The same dinner is recorded twice | The client sends an idempotency key (a unique id per expense); the server ignores a key it has already seen |
The demo's 4,000 concurrent expenses end with a sum of exactly 0. The lock is per group, so different groups never wait for each other.
7. Extensions the interviewer will ask for
- Split by shares (2 shares for a couple, 1 for a single): a new
ShareSplitstrategy using the same remainder trick. Nothing else changes. - Edit or delete an expense: apply the old shares in reverse, then the new ones; keep the old version for history.
- Multiple currencies: store
(amount, currency); keep balances per currency and only convert when settling, at a rate recorded with the conversion. Never add amounts in different currencies. - Expenses between two friends with no group: model it as a two-person group, so the code path is the same.
- Notifications ("alice added dinner"): the group publishes events and notifiers subscribe (Observer).
- Pairwise view ("you owe bob 23.33"): derive it from the expenses on demand, or keep a pairwise map next to the net balances.
When not to over-design
- Only equal splits: an
EqualSplitfunction is enough; add the interface when the second type appears. - A one-off trip calculator: no persistence, no locks, no idempotency. A list of expenses and a function that computes balances will do.
- No simplification needed: skip the heaps; showing net balances may be all users want.
In the interview
This percentage split passes the interviewer's test (40/30/20/10 of 200.00) but fails in production. Find two bugs and fix them.
public Map<User, Long> split(long amount, List<User> people) {
Map<User, Long> out = new LinkedHashMap<>();
for (int i = 0; i < people.size(); i++)
out.put(people.get(i), Math.round(amount * percents.get(i) / 100.0));
return out;
}Compare with our answer
The bugs: (1) no check that the percentages add up to 100, so 40 + 30 + 20 shares out only 90% and the payer silently absorbs the rest. (2) Each share is rounded on its own, so the total can be off by a cent or more: 10 cents split 33.33/33.33/33.34% gives 3 + 3 + 3 = 9. (3) Percentages as double cannot express 33.33% exactly; basis points (integers) can.
public Map<User, Long> split(long amount, List<User> people) {
if (basisPoints.size() != people.size()) throw new IllegalArgumentException("one percentage per person");
if (basisPoints.stream().mapToInt(Integer::intValue).sum() != 10_000)
throw new IllegalArgumentException("percentages must add up to 100%");
Map<User, Long> out = new LinkedHashMap<>();
long given = 0;
for (int i = 0; i < people.size(); i++) {
long share = amount * basisPoints.get(i) / 10_000; // round down
out.put(people.get(i), share); given += share;
}
for (int i = 0; given < amount; i++, given++) // leftover cents, one each
out.merge(people.get(i % people.size()), 1L, Long::sum);
return out;
}def split(self, amount, people):
if len(self.bp) != len(people):
raise ValueError("one percentage per person")
if sum(self.bp) != 10_000:
raise ValueError("percentages must add up to 100%")
out = {u: amount * p // 10_000 for u, p in zip(people, self.bp)} # round down
for i in range(amount - sum(out.values())): # leftover cents, one each
out[people[i % len(people)]] += 1
return outA strong answer mentions: validating that percentages sum to 100 · rounding down and distributing the remainder · shares that sum exactly to the amount · integer basis points instead of floating-point percentages · a test with an amount that does not divide evenly.
The trip is in Thailand. Some expenses are in THB, some in EUR, and members want to see what they owe in their home currency. How does the design change, and what must you not do?
Compare with our answer
A strong answer mentions:
- Every amount becomes a
Money(amountMinorUnits, currency)value object; the minor-unit scale comes from the currency (THB 2, JPY 0). - Balances are kept per currency (
Map<Currency, Map<User, Long>>); EUR and THB are never added together. - Conversion happens only when displaying or settling, using a rate fetched at that moment and stored with the settlement, so history stays reproducible.
- Simplification runs per currency, or after converting everything at one recorded rate if the group agrees.
- Split strategies do not change: they still split an integer amount; the currency travels alongside.
- Classes:
User,Group(members, expenses, net balances),Expense(payer, amount, shares),Transfer,SplitStrategywithEqualSplit,ExactSplit,PercentSplit. - Strategy: each split validates its inputs (exact sums to the total, percentages to 100%) and returns exact shares.
- Money: integer minor units (cents) or
BigDecimal/Decimal; neverdouble. Round down, then hand out leftover cents deterministically. - Balance: payer +amount, each participant −share. Invariant: balances sum to zero.
- Simplify: greedy max debtor → max creditor with two heaps; ≤ n − 1 transfers, O(n log n); exact minimum is NP-hard.
- Concurrency: one lock or transaction per group; validate before mutating; snapshot for simplify; idempotency key per expense.
- Durability: append-only ledger of expenses and payments; balances updated in the same transaction; reconciliation job.
- Extensions: share-based split, edits as reverse + re-add, per-currency balances, notifications (Observer).
1. A group splits a 100.00 bill equally among three people. The code computes each share as Math.round(10000 / 3.0) cents. What happens over many such bills?
10000 / 3.0 = 3333.33…, which rounds to 3333 for everyone: 9,999 cents in total. Round down and distribute the remainder explicitly, so the shares always add up to the amount.
2. Why is the split type modelled as a SplitStrategy interface instead of an enum and a switch in Group?
The strategy keeps each rule's data (percentages, amounts) and checks with the rule. Java enums can have fields, and neither choice affects thread safety; the point is that Group does not change for a "by shares" split.
3. Balances are alice −30, bob −20, carol +50. How many transfers does greedy simplification suggest?
Largest creditor carol (+50), largest debtor alice (−30): alice pays 30. Carol has +20 left, bob −20: bob pays 20. Two transfers for three people, matching the n − 1 bound.
4. An interviewer asks whether greedy simplification always gives the fewest possible transfers. What is the most accurate answer?
If the group splits into k subsets that each sum to zero, n − k transfers suffice, which can be fewer than greedy finds. Finding the best partition contains subset-sum, so exact minimisation is NP-hard; greedy is the practical answer.
5. Two members add expenses to the same group at the same moment. Afterwards the balances sum to 12.50 instead of zero. What is the most likely cause?
net[u] = net[u] + x from two threads is a lost-update race. Applying each expense under one lock (or one database transaction) per group fixes it. A long holds about 9.2 × 10^18 cents, so overflow is not the issue.
6. addExpense credits the payer, then calls the split strategy, which throws because the exact amounts don't add up. What is the state afterwards, and the fix?
Validate first, mutate second. In-memory changes are not rolled back by an exception; in a database the expense and balance updates belong in one transaction.
7. A mobile app retries "add expense" after a timeout, and the dinner now appears twice. What prevents this?
The retry is a second, valid-looking request; a lock only orders the two, it doesn't merge them. Matching on amount and description rejects genuine repeat purchases. An idempotency key identifies the operation itself.
Score 60% or more and the lesson is marked complete.