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:
from heapq import heappush, heappop
# Compute net balances
balance = {}
for payer, payee, amount in transactions:
balance[payer] = balance.get(payer, 0) - amount
balance[payee] = balance.get(payee, 0) + amount
# Build max-heaps using (negative amount, name) to simulate max behavior
creditors = [] # entries: (-credit, name) where credit > 0
debtors = [] # entries: (-owed, name) where owed > 0 (owed = -balance)
for name, amt in balance.items():
if amt > 0:
heappush(creditors, (-amt, name))
elif amt < 0:
heappush(debtors, (amt, name)) # amt is negative; smaller is more owed
result = []
while creditors and debtors:
# Largest debtor: pop most negative (smallest) amt
d_amt, d_name = heappop(debtors)
owed = -d_amt # positive
# Largest creditor: pop most positive
c_neg, c_name = heappop(creditors)
credit = -c_neg # positive
pay = owed if owed < credit else credit
result.append([d_name, c_name, pay])
owed -= pay
credit -= pay
if owed > 0:
heappush(debtors, (-owed * -1, d_name)) # push as negative again
if credit > 0:
heappush(creditors, (-credit, c_name))
return result