Expense Splitter

Flatmates share bills: balances in paise, equal and exact splits, and a short settle-up plan.

Medium90 minutesJava · class ExpenseSplitter

the brief

What you are building

Rahul, Priya and Amit share a flat in Bengaluru. Rent, Wi-Fi, electricity and groceries are paid by whoever is at the shop or online first.

At the end of the month, nobody remembers who owes whom. They want an app like Splitwise: record every bill, show each person's balance, and suggest a short list of payments that settles everything.

You will build its core. Money is the one thing that must be exactly right.

must have

Requirements

All amounts are paise (int; ₹1 = 100 paise). Never double.
addEqualExpense(paidBy, amount, people): split equally among people. Each share is amount / n; the first amount % n people in the list pay 1 paisa more, so the shares add up to the bill exactly.
The payer may or may not be in people (Rahul can pay a bill only for Priya and Amit).
addExactExpense(paidBy, people, shares): people[i] owes shares[i]; the bill is the sum of the shares.
balance(person): what others owe this person (positive) or what this person owes (negative). 0 for someone never seen.
settleUp() returns a payment plan and changes nothing: repeat — the person who owes the most pays the person owed the most, min of the two amounts. Ties go to the name that comes first alphabetically.
Each payment is written as "<debtor> pays <creditor> <paise>", e.g. "amit pays rahul 40000".

the contract

The Java API: class ExpenseSplitter

public ExpenseSplitter(): No people, no bills.
public void addEqualExpense(String paidBy, int amount, String[] people): An equal split.
public void addExactExpense(String paidBy, String[] people, int[] shares): An exact split.
public long balance(String person): Net paise: + is owed, − owes.
public List<String> settleUp(): The greedy plan; at most n − 1 payments.

1 ≤ amount, each share ≤ 10⁷ paise (₹1 lakh)
1 ≤ people in one bill ≤ 20, no name twice in one bill
up to 2,000 bills and 100 people
balances can pass Integer.MAX_VALUE: use long

example session

call	returns	why
`new ExpenseSplitter()`	`—`
`addEqualExpense("rahul", 90000, new String[] {"rahul", "priya", "amit"})`	`—`	30000 each; rahul is owed 60000
`addExactExpense("priya", new String[] {"rahul", "amit"}, new int[] {20000, 10000})`	`—`	priya paid 30000 for the other two
`balance("rahul")`	`40000`	+90000 − 30000 − 20000
`balance("priya")`	`0`	−30000 + 30000
`settleUp()`	`["amit pays rahul 40000"]`
`addEqualExpense("amit", 100, new String[] {"rahul", "priya", "amit"})`	`—`	100 / 3 = 33 rest 1: rahul 34, priya 33, amit 33
`balance("amit")`	`-39933`	−40000 + 100 − 33
`settleUp()`	`["amit pays rahul 39933", "priya pays rahul 33"]`	the biggest debt is paid first

Your 90 minutes

10 minclarify — Paise or rupees? Who gets the leftover paisa? Can the payer be outside the split? Does settleUp change the balances?
10 mindesign — One balance per person is enough — you do not need who-owes-whom pairs. Splits are strategies: equal, exact, later percent.
35 mincore code — Both add methods and balance. Run the first half of the example. Then settleUp with two heaps.
25 minedge cases — Payer pays only for themself, payer outside the split, leftover paise, debts that cancel to 0, totals past the int range.
10 minpolish — Be ready to say why the greedy plan is short but not always the shortest possible.

Practise under real pressure: a 90-minute clock with the phases above. It keeps running if you reload the page.

your turn

Build it here

Write the whole class in the editor. Run replays the example session; Submit adds the hidden tests (edge cases and large random sessions). Stuck for 20 minutes? Open one hint at a time.

Build ExpenseSplitter in the browser

Design: implement every operation. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

The reference, the data-structure reasoning and the rubric are hidden so you can build it first. Even a half-working attempt teaches you more than reading a perfect answer.

Opening all three hints also shows it.

reference

Which data structures, and why

HashMap<String, Long> of net balances

All that matters for settling is each person's net amount, not the history of who paid for whom.

O(people in the bill) per expense; O(1) per balance.

two PriorityQueues (creditors, debtors)

Always gives the biggest amount on each side for the greedy step.

O(n log n) for the whole plan, with at most n − 1 payments.

interface Split

Equal and exact are two ways to cut a bill into shares. Percent or by-shares splits become new classes; recording stays the same.

O(people) per bill.

long paise

Integers are exact. 0.1 + 0.2 in double is 0.30000000000000004.

No rounding errors, ever.

traps

Common mistakes

Using double for money. Rounding errors pile up, and a balance of -0.0000001 breaks the settle loop.
Splitting ₹1 three ways as 33 + 33 + 33 and losing 1 paisa. The shares must add up to the bill.
Storing a matrix of who owes whom. It is not wrong, but the net balance is simpler and settles the same.
Changing the balances inside settleUp, so calling it twice gives a different answer.
int balances: 300 bills of ₹1 lakh is 3 × 10⁹ paise, past Integer.MAX_VALUE.

what they ask next

Follow-ups and extensions

Is the greedy plan the minimum number of payments?

Not always. Finding the true minimum is NP-hard in general: it means splitting people into as many zero-sum groups as possible (LeetCode 465 is this problem). The greedy plan is short (at most n − 1 payments) and fast — good enough for a flat's monthly bills, and easy to explain.

Add a percent split (40% / 35% / 25%).

A new Split class: share = amount × percent / 100 with integer maths, and the leftover paise go to the first people, as in the equal split. Nothing else changes.

Show the history: who paid what and when.

Keep a list of Expense records (payer, amount, shares, time) next to the balances. Balances stay O(1) to read; history is for display and audit.

Groups: the flat and the office lunch group are separate.

Make Group own its balances. A Map<String, Group> holds them; a person can be in many groups.

revise