Case study: LLD Splitwise

Splitwise is one of the ten problems in Tradeoff's machine-coding practice round (lesson 105). Friends share bills. One friend pays, and the app remembers who owes whom. Then the interviewer adds a new requirement, such as "show the fewest payments that settle everything".

The interviewer looks at four things. Do you handle money in a way that loses no rupee? Do you keep all debts in one place? Is each way of splitting a bill a small piece that you can add to? Can you explain how to reduce many debts to a few payments?

A weak answer keeps money as decimal numbers. It keeps "A owes B" and "B owes A" as two separate lines. It writes one long if chain for the split types. A strong answer uses whole rupees with a clear rule for the leftover. It joins the two debts of each pair of friends into one, in one function. It works out the plan for fewer payments from each person's total.

At SDE-1 level you should reach working code for the three split types. At SDE-2 level you should combine opposite debts, settle up, and add the new requirement with a small change. At SDE-3 level you should also say that the simple plan is not always the smallest, and why.

Think of friends on a trip with one notebook. Each page says who paid, how much, and for whom. At the end nobody wants to read every page. Someone writes one line for each friend: "owes 500" or "is owed 300". Then the friends pay each other in a few payments, and the notebook is clean.

An app does the same. A graph is a set of nodes joined by edges. In a debt graph, each friend is a node. Each debt is an edge: an arrow with the amount written on it. It goes from the friend who owes (the debtor) to the friend who is owed (the creditor). Two arrows between the same two friends, one each way, can be replaced by one arrow for the difference. This is netting. After netting, a pair has at most one arrow. So n friends have at most n x (n - 1) / 2 arrows. For 4 friends that is 6, and for 10 friends it is 45.

The net balance of a friend is what others owe this friend, minus what this friend owes others. A positive balance means "I am owed". Every debt adds to one balance and takes the same amount from another, so all net balances add up to 0.

We use this statement for the whole lesson. It is a shortened form of Tradeoff's practice problem.

1. A group of friends. Their names are unique and given at the start. A name that is not in the group is an error.
2. One friend pays an expense of some rupees (more than 0) for a list of friends. The list is not empty and has no name twice. The payer may or may not be in the list.
3. The split type is EQUAL, EXACT or PERCENT. Anything else is an error.
4. Money is whole rupees. EQUAL: each share is the amount divided by the number of friends, rounded down. The leftover rupees go one each to the first friends of the list, in list order.
5. EXACT: the values are the shares, and they must add up to the amount. PERCENT: the values are whole percents that add up to 100. A share is the amount times the percent divided by 100, rounded down. The leftover rupees go one each to the first friends of the list whose percent is above 0.
6. Every friend in the list owes the payer the share. The payer owes nothing to himself.
7. Settle up: a friend pays another friend cash. This reduces what the payer owes. If he pays more than he owes, the debt turns around.
8. The app answers four questions. How much does A owe B? What is the net balance of A? What are all the debts, as lines "A owes B 250"? Which of those lines have one given friend in them? The lines are sorted by the name of the one who owes, and then by the name of the one who is owed.
9. A bad call changes nothing and uses no expense number.

Step 1: nouns become classes

Lesson 109 showed how to find classes. Keep a noun as a class when it has its own data or rules.

For a history of expenses, add an Expense class.

Step 2: money in whole numbers

Lesson 68 said to store money as a whole number of the smallest unit. Here the unit is the rupee, and a real app would use paise (100 paise make 1 rupee). Division makes a problem. Rs 100 for 3 friends is 33.33 for each if you round to the paisa, and 3 x 33.33 = 99.99. One paisa is gone. With whole rupees, 100 // 3 is 33 (// divides and drops the fraction). 3 x 33 = 99, so 1 rupee is left over. The rule in points 4 and 5 gives that rupee to the first friends of the list. Then the shares always add up to the amount.

Write this rule once. Both EQUAL and PERCENT call it. A strategy (lesson 107) is one rule in its own small class with one method. Each split type is a strategy that returns one share for each friend.

from abc import ABC, abstractmethod

def spread_leftover(amount, shares, eligible):
    leftover = amount - sum(shares)
    for i in range(len(shares)):
        if leftover == 0:
            break
        if eligible[i]:
            shares[i] += 1
            leftover -= 1
    return shares

class SplitRule(ABC):
    @abstractmethod
    def shares(self, amount, users, values):
        """Return one share for each user. The shares add up to amount."""

class EqualSplit(SplitRule):
    def shares(self, amount, users, values):
        n = len(users)
        return spread_leftover(amount, [amount // n] * n, [True] * n)

class ExactSplit(SplitRule):
    def shares(self, amount, users, values):
        if len(values) != len(users) or min(values) < 0 or sum(values) != amount:
            raise ValueError("the exact amounts must add up to the expense")
        return list(values)

class PercentSplit(SplitRule):
    def shares(self, amount, users, values):
        if len(values) != len(users) or min(values) < 0 or sum(values) != 100:
            raise ValueError("the percents must add up to 100")
        shares = [amount * p // 100 for p in values]
        return spread_leftover(amount, shares, [p > 0 for p in values])

Step 3: one place for the debts

The DebtBook holds a dictionary. The key is a pair, (debtor, creditor), and the value is the amount, always above 0. All netting happens in one method, add_debt. It works out the net: what the debtor already owes the creditor, minus what the creditor already owes the debtor, plus the new amount. A positive net is one arrow. A negative net is an arrow the other way. Zero removes both arrows.

Settle up needs no special case. When the payer pays cash to the receiver, the receiver now owes the payer that amount. That is one more call of add_debt in the other direction.

class DebtBook:
    def __init__(self):
        self.debts = {}       # (debtor, creditor) -> rupees, always above 0

    def amount(self, debtor, creditor):
        return self.debts.get((debtor, creditor), 0)

    def add_debt(self, debtor, creditor, amount):
        if debtor == creditor or amount == 0:
            return
        net = self.amount(debtor, creditor) - self.amount(creditor, debtor) + amount
        self.debts.pop((debtor, creditor), None)
        self.debts.pop((creditor, debtor), None)
        if net > 0:
            self.debts[(debtor, creditor)] = net
        elif net < 0:
            self.debts[(creditor, debtor)] = -net

    # more methods of DebtBook
    def net_balance(self, user):
        owed_to_user = sum(a for (d, c), a in self.debts.items() if c == user)
        user_owes = sum(a for (d, c), a in self.debts.items() if d == user)
        return owed_to_user - user_owes

    def lines(self, user=None):
        return [f"{d} owes {c} {a}" for (d, c), a in sorted(self.debts.items())
                if user in (None, d, c)]

A pair sorts by its first item and then by its second item, so sorted gives the order of point 8. The check debtor == creditor is why the payer never owes himself.

Step 4: the main class

A dictionary picks the strategy by name (lesson 108). add_expense checks everything first, then changes the book. So a bad call changes nothing, and the expense number grows only for a good call.

class ExpenseManager:
    RULES = {"EQUAL": EqualSplit(), "EXACT": ExactSplit(), "PERCENT": PercentSplit()}

    def __init__(self, users):
        self.users = set(users)
        self.book = DebtBook()
        self.count = 0

    def know(self, *names):
        for name in names:
            if name not in self.users:
                raise ValueError(f"unknown user {name}")

    # more methods of ExpenseManager
    def add_expense(self, paid_by, amount, split_type, users, values):
        self.know(paid_by, *users)
        if amount <= 0 or not users or len(set(users)) != len(users):
            raise ValueError("bad expense")
        rule = self.RULES.get(split_type)
        if rule is None:
            raise ValueError("unknown split type")
        shares = rule.shares(amount, users, values)   # may raise: nothing changed yet
        for user, share in zip(users, shares):
            self.book.add_debt(user, paid_by, share)
        self.count += 1
        return self.count

    def settle_up(self, payer, receiver, amount):
        self.know(payer, receiver)
        if amount <= 0 or payer == receiver:
            raise ValueError("bad payment")
        self.book.add_debt(receiver, payer, amount)

    # more methods of ExpenseManager
    def amount_owed(self, debtor, creditor):
        self.know(debtor, creditor)
        return self.book.amount(debtor, creditor)

    def net_balance(self, user):
        self.know(user)
        return self.book.net_balance(user)

    def owes(self):
        return self.book.lines()

    def owes_of(self, user):
        self.know(user)
        return self.book.lines(user)

In a round, calls arrive one after another. In a real app, two friends may add an expense at the same moment. add_debt reads and then writes, which is a check followed by a change (lesson 110). One lock around add_expense and settle_up fixes it. On many servers, the database must do it (lesson 22).

Fewer payments: work from the net balances

Now the new requirement. The arrows may form chains. Asha owes Bala Rs 100, and Bala owes Chitra Rs 100. Bala only passes the money on. The balances are Asha -100, Bala 0 and Chitra +100. One payment, Asha to Chitra, settles all.

The plan forgets the arrows and works from the balances only:

1. Take the creditor with the biggest positive balance and the debtor with the biggest negative balance. If two are tied, take the name that comes first.
2. The debtor pays the creditor the smaller of the two amounts. That is one payment.
3. Reduce both balances by that amount. Repeat until all balances are 0.

This is a greedy plan: at each step it takes the best-looking choice and never goes back. Each payment sets at least one friend to 0. The balances add up to 0, so when only two friends are left, one payment clears both. So k friends with a balance other than 0 need at most k - 1 payments.

The plan is a new small class. ExpenseManager gets one new line in __init__, self.simplifier = GreedySimplifier(), and two new methods. Preview changes nothing. Apply replaces all arrows by the payments.

class GreedySimplifier:
    def plan(self, balances):
        balances = dict(balances)
        payments = []
        while True:
            creditors = [u for u, b in balances.items() if b > 0]
            debtors = [u for u, b in balances.items() if b < 0]
            if not creditors:
                return payments
            creditor = min(creditors, key=lambda u: (-balances[u], u))
            debtor = min(debtors, key=lambda u: (balances[u], u))
            pay = min(balances[creditor], -balances[debtor])
            payments.append((debtor, creditor, pay))
            balances[creditor] -= pay
            balances[debtor] += pay

    # two new methods of ExpenseManager
    def preview_simplified(self):
        balances = {u: self.book.net_balance(u) for u in self.users}
        plan = sorted(self.simplifier.plan(balances))
        return [f"{d} owes {c} {a}" for d, c, a in plan]

    def apply_simplified(self):
        balances = {u: self.book.net_balance(u) for u in self.users}
        self.book = DebtBook()
        plan = self.simplifier.plan(balances)
        for debtor, creditor, pay in plan:
            self.book.add_debt(debtor, creditor, pay)
        return len(plan)

1. The chain (the predict box). Asha owes 200, so her balance is -200. Bala is owed 200 and owes 200, so 200 - 200 = 0. Chitra is also 200 - 200 = 0. Dev is owed 200, so his balance is +200. The sum is -200 + 0 + 0 + 200 = 0. One payment settles all: Asha pays Dev Rs 200. Without the plan, there are three payments.

2. A trip. Assumption: four friends, Asha, Bala, Chitra and Dev. All numbers are made up to teach with.

In E3, 905 x 50 // 100 = 452 and 905 x 30 // 100 = 271 and 905 x 20 // 100 = 181. These sum to 904, so 1 rupee is left over. Asha is first in the list, so she gets it.

After E4, owes() returns 6 lines, one for each pair that is not zero:

1. Bala owes Asha 1500
2. Bala owes Dev 667
3. Chitra owes Asha 1047
4. Chitra owes Bala 153
5. Chitra owes Dev 1229
6. Dev owes Asha 500

The net balances are:

• Asha: 1,500 + 1,047 + 500 = 3,047.
• Bala: 153 - 1,500 - 667 = -2,014.
• Chitra: -(1,047 + 153 + 1,229) = -2,429.
• Dev: (667 + 1,229) - 500 = 1,396.

The sum is 3,047 - 2,014 - 2,429 + 1,396 = 0.

3. Settle up. Chitra owes Asha Rs 1,047. If Chitra pays Asha Rs 1,047, the line disappears. If she pays Rs 1,100, then 1,047 - 1,100 = -53, so the debt turns around: "Asha owes Chitra 53".

4. The new requirement: fewer payments. The creditors are Asha (3,047) and Dev (1,396). The debtors are Chitra (-2,429) and Bala (-2,014).

1. The biggest creditor is Asha and the biggest debtor is Chitra. Chitra pays Asha min(3,047, 2,429) = 2,429. Asha is left with 618.
2. The biggest creditor is now Dev (1,396) and the biggest debtor is Bala (-2,014). Bala pays Dev 1,396. Bala is left with -618.
3. Bala pays Asha 618. All balances are 0.

So preview_simplified() returns three lines: "Bala owes Asha 618", "Bala owes Dev 1396" and "Chitra owes Asha 2429". The 6 lines became 3 payments, and 3 is the limit of 4 - 1. apply_simplified() returns 3, and every net balance stays the same.

5. Not always the smallest. Take five friends with the balances Asha +9, Bala +8, Chitra -3, Dev -6 and Esha -8. The greedy plan makes four payments. Esha pays Asha 8, and Asha is left with 1. Dev pays Bala 6, and Bala is left with 2. Chitra pays Bala 2, and Chitra is left with -1. Chitra pays Asha 1. But three payments are enough. Asha +9, Chitra -3 and Dev -6 add up to 0, so two payments clear these three friends. Bala +8 and Esha -8 need one payment. Total 2 + 1 = 3. The payments split the friends into groups, and each group clears itself. A group of s friends needs at least s - 1 payments. A group whose balances add up to 0 can do it in exactly s - 1. So the fewest payments equal the number of friends with a balance other than 0, minus the largest number of such groups. Here that is 5 - 2 = 3. The known way to find the largest number of groups is to try subsets of friends (see Sources). For n friends there are 2 to the power of n subsets: 1,024 for 10 friends, and 1,048,576 for 20 friends.

• One debt book with netting solves the question "how much does A owe B" with one lookup and one line in owes(). It costs a scan of all arrows for net_balance. I would keep a running total for each friend if the app asks for balances often.
• A strategy for each split type solves adding a new type: one new class and one dictionary entry. It costs more classes. I would use one if when there is a single split type.
• The greedy plan solves fewer payments in a few lines, and it needs at most k - 1 of them. It costs two things. It may not be the smallest, and a friend may pay someone he never shared a bill with. I would check all subsets for a small group, if the interviewer asks for the true minimum.
• Whole rupees solve lost money. They cost a leftover rule that you must state and test. I would use paise in a real app.

"I can keep money as a decimal number and round at the end." Rounding each share loses money: 3 x 33.33 = 99.99, not 100. A float cannot store most decimal fractions exactly, so in Python 0.1 + 0.1 + 0.1 is not equal to 0.3. Use whole numbers, and give the leftover out by a rule.

"I can keep 'A owes B 100' and 'B owes A 30' as two lines." Then amount_owed must add and subtract at every read. Also owes() shows two lines for one pair. Net the pair in one place, so the book never holds both arrows. The answer is then the one line "A owes B 70".

"The simplify plan always gives the fewest payments." It gives at most k - 1 payments, but not always the smallest number. In example 5 the greedy plan used 4 payments and 3 were enough. Finding the true smallest number is a hard problem: no fast method that always finds it is known (see Sources).

1. What is a net balance? What do all net balances add up to, and why?
2. (a) Rs 701 is split EQUAL among Asha, Bala, Chitra and Dev, in this order. What is each share? (b) Rs 101 is split PERCENT among Asha 40, Bala 35 and Chitra 25. What is each share?
3. The interviewer says: "Add a split by shares. Asha has 2 shares, Bala has 1 and Chitra has 1." Which code do you write and which code stays the same? What are the shares for Rs 1,000?