Settle Group Expenses with Transfers
Company: Pinterest
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given a list of group expense transactions from a trip.
Each transaction contains:
- `payer`: the person who paid the full amount.
- `amount`: the total amount paid, represented as an integer number of cents.
- `payees`: the people who shared this expense equally. The payer may also appear in this list, meaning they paid for their own share as well.
For each transaction, the `amount` is split equally among all `payees`. Compute a list of direct transfers that settles all balances, so that every person's final net balance becomes zero.
Return any valid list of transfers. Each transfer should specify:
- `from`: the person who pays money.
- `to`: the person who receives money.
- `amount`: the amount transferred.
The order of transfers does not matter. You may assume each transaction amount is evenly divisible by the number of payees.
Example:
```python
transactions = [
{
"payer": "Alice",
"amount": 4000,
"payees": ["Bob", "Alice", "Charlie", "Daisy"]
},
{
"payer": "Charlie",
"amount": 2000,
"payees": ["Alice", "Charlie"]
}
]
```
One valid output is:
```python
[
{"from": "Bob", "to": "Alice", "amount": 1000},
{"from": "Daisy", "to": "Alice", "amount": 1000}
]
```
Explanation:
- Alice should receive a net total of `2000`.
- Bob owes `1000`.
- Daisy owes `1000`.
- Charlie is already settled.
Quick Answer: This question evaluates the ability to compute and reconcile per-person financial balances from transactional data and to translate net liabilities into direct transfers, exercising skills in numeric bookkeeping and data aggregation.
You are given a list of group expense transactions from a trip. Each transaction has a payer, an integer amount in cents, and a list of payees who shared that expense equally. The payer may or may not be included in the payees list. For each transaction, the payer initially paid the full amount, and each payee is responsible for an equal share of that amount. Compute direct money transfers that settle everyone so that each person's final net balance becomes zero. Return any valid settlement list. For deterministic testing, the reference solution processes people in lexicographic order.
Constraints
- 0 <= len(transactions) <= 100000
- 1 <= total number of payee entries across all transactions <= 200000, unless transactions is empty
- Each transaction has at least one payee
- Within a transaction, payees are unique
- 0 <= amount <= 1000000000000
- For every transaction, amount is evenly divisible by len(payees)
- Person names are non-empty strings
Examples
Input: ([{'payer': 'Alice', 'amount': 4000, 'payees': ['Bob', 'Alice', 'Charlie', 'Daisy']}, {'payer': 'Charlie', 'amount': 2000, 'payees': ['Alice', 'Charlie']}],)
Expected Output: [{'from': 'Bob', 'to': 'Alice', 'amount': 1000}, {'from': 'Daisy', 'to': 'Alice', 'amount': 1000}]
Explanation: Alice is owed 2000 total. Bob and Daisy each owe 1000. Charlie's balance is already zero.
Input: ([] ,)
Expected Output: []
Explanation: There are no transactions, so no transfers are needed.
Hints
- Track each person's net balance: add the full amount to the payer, then subtract one equal share from every payee.
- After computing balances, separate people who owe money from people who should receive money, then greedily match them.