Machine coding · Wallets and payments
Expense sharing with debt simplification
- Listed in prep guides
- Strategy
- Ledger
- Bitmask DP
- 2 sources
Prep guides list it as a common prompt; no candidate write-up was found.
Design an expense-sharing app in the style of Splitwise, with users, groups and balances. People in a group add expenses that one person pays and several people share, and the app must always show who owes whom. Build it as an in-memory machine-coding task that is easy to extend with new ways of splitting.
Restated in our own words, not a quote from Groww or any page. The answer below is written for this site.
Clarify first
Pin the scope down before you name a single class.
Questions to ask first: which split types are needed (equal, exact amounts, percentages, shares), are amounts whole paise or decimals, must the payer be one of the people sharing, can a user be in several groups, do we record repayments between people, and should the app suggest a smaller set of payments that clears the group. Ask how a leftover paisa is handled when a total does not divide evenly.
Assumed scope: integer paise, one currency, equal, exact and percent splits chosen per expense, a payer who must be a group member, and repayments that are recorded as payments between two members and cannot exceed what is owed. Debt simplification is included as the main extension: the app can return the fewest payments that bring every balance in the group to zero. Out of scope: currencies, receipts, notifications, editing or deleting old expenses, authentication and persistence.
Entities and relationships
Who owns what, and who talks to whom.
- Group holds the member ids, a list of expenses and one
Ledger. It exposesaddExpense,settleandsimplify. A user is just an id in this version. - Expense is a record of the payer and the amount. The shares are not stored on it, because they are turned into ledger entries the moment they are validated.
- SplitStrategy is the interface with
split(amount, spec), which returns a map from user to share that adds up exactly to the amount.EqualSplittakes a list of users,ExactSplittakes user to amount, andPercentSplittakes user to percent. - Ledger keeps one number per ordered pair, so reverse debts cancel.
owes(a, b)reads it andnet()gives each person's total position, where a positive number means they are owed money. People at zero are left out. - Settlement functions
greedySettlementsandminimalSettlementstake net balances and return a list of payments from a debtor to a creditor.
The design
The class map, the main flow and the patterns that earn their place.
- The group asks the strategy for each person's share of the amount.
- Each non-payer's share is added to the ledger as a debt to the payer.
- When asked, the group reads each person's net position from the ledger and passes the balances to the simplifier, which returns the payments.
Open on the whiteboardAll 2 diagrams on one tidy board, with a step-by-step walkthrough.
Adding an expense validates that the amount is a positive integer, asks the strategy for the shares, checks that every share is a whole non-negative number of paise and that they add up exactly to the amount, checks that the payer and everyone in the shares belong to the group, and only then adds each non-payer's share to the ledger as a debt to the payer. The payer's own share is never recorded, because nobody owes themselves. The group does not trust the strategy, so a custom strategy, a name repeated in an equal split or a negative percentage is rejected before the ledger changes.
Strategy for splits. The three split types differ only in how they turn an amount and a spec into shares, so each is a class returning a map that sums exactly to the amount. This is the one place rounding lives. Equal split gives everyone the floor of the division and hands one extra paisa to the first few people. Percent split floors each share and gives leftover paise to the first people in order. Exact split passes the given shares through, and the group rejects them if they are negative, fractional or do not add up. A new split type, such as shares by weight, is one more class and no change to the group.
Ledger. It stores a single net debt per ordered pair. If B owes A 500 and later A owes B 150, the ledger holds that B owes A 350 and nothing in the other direction. A person's net position is what others owe them minus what they owe, and the sum of all net positions in a group is always zero, which is the invariant to assert in tests.
Simplification. Only net positions matter for clearing a group, so the problem becomes: given positive and negative balances that sum to zero, find the fewest payments from debtors to creditors. The greedy method repeatedly makes the largest debtor pay the largest creditor, and uses at most k minus 1 payments for k people with a non-zero balance, but it is not always the fewest. The true minimum is k minus the largest number of groups of people whose balances sum to zero, because a zero-sum group of size s needs s minus 1 payments and no fewer. Finding that partition is hard in general, so minimalSettlements uses a bitmask over subsets: for each subset it records the best count of zero-sum prefixes over all orderings, which costs about 2 to the power k times k steps. That is fine up to 16 people, and the group falls back to greedy beyond that.
Worked check. Balances in paise: A +500, B -300, C -200, D +400, E -400. Greedy pays E to A 400, B to D 300, C to D 100 and C to A 100, which is 4 payments. The partition {A, B, C} and {D, E} sums to zero in each part, so the minimum is 3: B to A 300, C to A 200, E to D 400.
Trade-off. The ledger is a cache of the expense history, quick to read but unable to answer which expense created a debt; the expense list is kept for audit and rebuilds. Writes to one group should be serialised, because an expense touches several pairs.
The code
Runnable JavaScript, with the checks it passes.
class EqualSplit {
split(amount, people) {
const base = Math.floor(amount / people.length);
const extra = amount - base * people.length;
return new Map(people.map((id, i) => [id, base + (i < extra ? 1 : 0)]));
}
}
class ExactSplit {
split(amount, shares) {
return new Map(Object.entries(shares));
}
}
class PercentSplit {
split(amount, percents) {
const ids = Object.keys(percents);
const sum = Object.values(percents).reduce((a, b) => a + b, 0);
if (sum !== 100) throw new Error("percentages add up to " + sum);
const shares = new Map(ids.map((id) => [id, Math.floor((amount * percents[id]) / 100)]));
let left = amount - [...shares.values()].reduce((a, b) => a + b, 0);
for (const id of ids) {
if (left === 0) break;
shares.set(id, shares.get(id) + 1);
left -= 1;
}
return shares;
}
}
class Ledger {
constructor() {
this.owed = new Map();
}
owes(from, to) {
return this.owed.get(from + ">" + to) || 0;
}
add(from, to, amount) {
const back = this.owes(to, from);
const net = amount - back;
this.owed.delete(to + ">" + from);
if (net > 0) this.owed.set(from + ">" + to, this.owes(from, to) + net);
else if (net < 0) this.owed.set(to + ">" + from, -net);
}
net() {
const net = new Map();
for (const [key, amount] of this.owed) {
const [from, to] = key.split(">");
net.set(from, (net.get(from) || 0) - amount);
net.set(to, (net.get(to) || 0) + amount);
}
for (const [id, value] of net) if (value === 0) net.delete(id);
return net;
}
}
function greedySettlements(net) {
const rest = [...net].filter(([, v]) => v !== 0).map(([id, v]) => ({ id, v }));
const moves = [];
for (;;) {
rest.sort((a, b) => b.v - a.v);
const give = rest[rest.length - 1];
const take = rest[0];
if (!give || give.v >= 0) return moves;
const amount = Math.min(take.v, -give.v);
moves.push({ from: give.id, to: take.id, amount });
take.v -= amount;
give.v += amount;
while (rest.length && rest[rest.length - 1].v === 0) rest.pop();
while (rest.length && rest[0].v === 0) rest.shift();
}
}
function minimalSettlements(net) {
const people = [...net].filter(([, v]) => v !== 0);
const n = people.length;
const sum = [0];
const best = [0];
const last = [0];
for (let mask = 1; mask < 1 << n; mask++) {
sum[mask] = sum[mask & (mask - 1)] + people[31 - Math.clz32(mask & -mask)][1];
best[mask] = -1;
for (let i = 0; i < n; i++) {
if (mask & (1 << i) && best[mask ^ (1 << i)] > best[mask]) {
best[mask] = best[mask ^ (1 << i)];
last[mask] = i;
}
}
if (sum[mask] === 0) best[mask] += 1;
}
const order = [];
for (let mask = (1 << n) - 1; mask; mask ^= 1 << last[mask]) order.push(last[mask]);
const moves = [];
let group = [];
for (const i of order.reverse()) {
group.push(people[i]);
if (group.reduce((total, [, v]) => total + v, 0) === 0) {
moves.push(...greedySettlements(new Map(group)));
group = [];
}
}
return moves;
}
class Group {
constructor(members) {
if (members.some((id) => id.includes(">"))) throw new Error("ids cannot contain >");
this.members = new Set(members);
this.ledger = new Ledger();
this.expenses = [];
}
addExpense(payer, amount, strategy, spec) {
if (!Number.isInteger(amount) || amount <= 0) throw new Error("amount must be positive paise");
const shares = strategy.split(amount, spec);
let total = 0;
for (const share of shares.values()) {
if (!Number.isInteger(share) || share < 0) throw new Error("shares must be whole paise");
total += share;
}
if (total !== amount) throw new Error("shares add up to " + total + " not " + amount);
for (const id of [payer, ...shares.keys()]) if (!this.members.has(id)) throw new Error(id + " is not in the group");
for (const [id, share] of shares) if (id !== payer) this.ledger.add(id, payer, share);
this.expenses.push({ payer, amount });
}
settle(from, to, amount) {
if (!Number.isInteger(amount) || amount <= 0 || amount > this.ledger.owes(from, to)) throw new Error("cannot settle " + amount);
this.ledger.add(to, from, amount);
}
simplify() {
const net = this.ledger.net();
return net.size > 16 ? greedySettlements(net) : minimalSettlements(net);
}
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Extend it
The change requests an interviewer throws next.
- How would you add a split by shares, such as two shares for an adult and one for a child?
- How would you support several currencies in one group, and when do you convert?
- How would you let a user delete or edit an old expense without breaking the balances of later ones?
- How would you keep the simplified payments stable so the suggestions do not change after every new expense?
- How would you handle a group with thousands of members, where the subset method is too slow?
Where candidates slip
The mistakes this problem punishes.
Using floating point money, so a three way split of 100.00 loses a paisa. Letting the shares add up to a different total than the amount. Recording the payer's own share as a debt. Keeping two directions per pair so that A owes B and B owes A at the same time. Settling with a greedy match and calling it minimal. Allowing a settlement larger than the debt, which silently reverses it. Accepting people who are not in the group. Forgetting that percentages must add up to exactly 100.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.