Bill Splitting - Compute Minimum Transactions to Settle Shared Expenses. LeakCode

Question Details

Round 1 Coding

Problem

A group of friends shared expenses during a trip. Given a list of payments (who paid, how much, for whom), compute the minimum number of transactions to settle all debts.

python
def min_transfers(transactions: list[tuple[str, str, float]]) -> list[tuple[str, str, float]]:
    # transactions[i] = (payer, beneficiary, amount)

**Returns**: list of (from, to, amount) settlement transfers
    # Minimize the number of transfers
    ...


**Example**:
transactions = [
    ("Alice", "Bob",   30),
    ("Alice", "Carol", 20),
    ("Bob",   "Carol", 10),
]
# Net balances: Alice=+50, Bob=-20, Carol=-30
# Settlement:
#   Bob   -> Alice: 20
#   Carol -> Alice: 30
min_transfers(transactions) -> [
    ("Bob",   "Alice", 20),
    ("Carol", "Alice", 30)
]

Follow-ups

Can you settle with fewer transactions by finding a chain (A owes B who owes C -> A pays C directly)?
What if amounts must be rounded to cents - how does that affect correctness?
Is the minimum-transfer problem NP-hard in the general case? When is a greedy approach optimal?
How would you handle a currency conversion requirement between friends in different countries?

Full Details

Round 1 Coding

Problem

A group of friends shared expenses during a trip. Given a list of payments (who paid, how much, for whom), compute the minimum number of transactions to settle all debts.

python
def min_transfers(transactions: list[tuple[str, str, float]]) -> list[tuple[str, str, float]]:
    # transactions[i] = (payer, beneficiary, amount)

**Returns**: list of (from, to, amount) settlement transfers
    # Minimize the number of transfers
    ...


**Example**:
transactions = [
    ("Alice", "Bob",   30),
    ("Alice", "Carol", 20),
    ("Bob",   "Carol", 10),
]
# Net balances: Alice=+50, Bob=-20, Carol=-30
# Settlement:
#   Bob   -> Alice: 20
#   Carol -> Alice: 30
min_transfers(transactions) -> [
    ("Bob",   "Alice", 20),
    ("Carol", "Alice", 30)
]

Follow-ups

Can you settle with fewer transactions by finding a chain (A owes B who owes C -> A pays C directly)?
What if amounts must be rounded to cents - how does that affect correctness?
Is the minimum-transfer problem NP-hard in the general case? When is a greedy approach optimal?
How would you handle a currency conversion requirement between friends in different countries?

Free preview. Unlock all questions →

Topics

Coding Onsite Phone

More from Pinterest

1p3a Pinterest Machine Learning Engineering Internship Online Test Overview 1p3a Pinterest Machine Learning Engineer Tech Phone Interview Experience 1p3a Pinterest Fulltime SDE Onsite Interview Experience and Coding Challenges Reddit Pinterest 2026 SWE Intern Phone Screen + Interview LeetCode Pinterest Coding 2024, Can't solve using AI either