Design Algorithm to Minimize Payments in Expense-Sharing App
Company: Pinterest
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
##### Scenario
Expense-sharing app needs to settle debts among friends after a trip.
##### Question
Given a list of transactions (payer, payee, amount), design an algorithm that produces the minimum set of payments required to settle every person’s balance.
##### Hints
Compute each person’s net balance, then greedily match positives with negatives using a heap or two-pointer sweep.
Quick Answer: This question evaluates algorithm design and optimization skills, focusing on modeling multi-party transactions and minimizing the number of settlement operations.
You are given a list of transactions, each as [payer, payee, amount], where amount is a positive integer (e.g., cents). Compute a settlement that clears every person's net balance using the minimum number of payments. First compute each person's net balance (negative = owes, positive = is owed). Then repeatedly make a payment from the person who owes the most to the person who is owed the most; transfer the smaller of the two amounts and update balances. If multiple debtors (or creditors) tie on amount, pick the lexicographically smallest name. Return the list of payments as [payer, payee, amount] in the order produced by this process.
Constraints
- 1 <= len(transactions) <= 200000
- Each transaction is [payer, payee, amount] with payer and payee as non-empty ASCII names (length 1..32)
- 1 <= amount <= 10^9 (integers)
- Number of distinct people P <= 200000
- Total of all amounts fits in 64-bit signed integer
- Output must follow the specified greedy rule; ties broken by lexicographically smallest names
Solution
def settle_expenses(transactions: list) -> list:
# Compute net balances
balance = {}
for payer, payee, amount in transactions:
balance[payer] = balance.get(payer, 0) - amount
balance[payee] = balance.get(payee, 0) + amount
# Separate into debtors (owe > 0) and creditors (owed > 0)
debtors = [] # [name, amount_owed]
creditors = [] # [name, amount_owed_to]
for name, amt in balance.items():
if amt < 0:
debtors.append([name, -amt])
elif amt > 0:
creditors.append([name, amt])
# Sort by amount descending, then name ascending (lexicographically smallest on ties)
debtors.sort(key=lambda x: (-x[1], x[0]))
creditors.sort(key=lambda x: (-x[1], x[0]))
res = []
i = j = 0
while i < len(debtors) and j < len(creditors):
d_name, d_amt = debtors[i]
c_name, c_amt = creditors[j]
pay = d_amt if d_amt < c_amt else c_amt
res.append([d_name, c_name, pay])
d_amt -= pay
c_amt -= pay
if d_amt == 0:
i += 1
else:
debtors[i][1] = d_amt
if c_amt == 0:
j += 1
else:
creditors[j][1] = c_amt
return res
Explanation
Compute each person's net balance. Use two max-heaps to always match the largest debtor with the largest creditor. Transfer the minimum of the two amounts, settle at least one party each step, and reinsert any remainder. Ties on equal amounts are resolved by heap tuple ordering using names, ensuring deterministic output. This greedy strategy yields the minimum number of payments.
Time complexity: O(T + P log P). Space complexity: O(P).
Hints
- Compute each person's net balance: decrement payer by amount, increment payee by amount.
- Maintain two max-heaps: one for creditors (positive balance) and one for debtors (absolute value of negative balance).
- At each step, pop the largest debtor and largest creditor, transfer the smaller amount, and push back any remainder.
- Break ties on equal amounts by lexicographically smallest names to ensure deterministic output.