Social Payment: Split Bills and Settle Debts Among a Group

Question

## Problem

A group of friends track shared expenses. Each transaction is `(payer, [participants], amount)`. After all transactions, compute the **minimum number of payments** needed to settle all balances (everyone ends at net 0).

```python
def min_transfers(transactions: list[tuple[str, list[str], float]]) -> int:
    pass
```

## Example

```
Input:
transactions = [
    ("Alice", ["Alice", "Bob", "Carol"], 90),   # Alice paid $90 for 3 people
    ("Bob",   ["Bob", "Carol"], 40),             # Bob paid $40 for 2 people
    ("Carol", ["Alice", "Bob", "Carol"], 60),   # Carol paid $60 for 3 people
]

Net balances:
  Alice: paid 90, owes (90/3 + 60/3) = 50  -> net +40
  Bob:   paid 40, owes (90/3 + 40/2 + 60/3) = 90 -> net -50
  Carol: paid 60, owes (90/3 + 40/2 + 60/3) = 90 -> net -30

Output: 2
# Bob -> Alice $40, Bob -> Carol $10, Carol -> Alice 0 ... optimally 2 transfers
```

## Follow-ups

1. Why is minimizing transfers NP-hard in general? What structure allows greedy to work?
2. How would you handle multi-currency transactions?
3. Design a REST API for this service: what endpoints, data model, and consistency guarantees do you need?

Social Payment: Split Bills and Settle Debts Among a Group

Question Details

Full Details

Topics

More from Robinhood