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
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.