Splitwise Machine Coding | Dataford Interview Questions

Your question is Splitwise Machine Coding. Start with the requirements on the right.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Build the settlement engine for a Splitwise-like group used by Swiggy employees. Given participants and recorded expenses, calculate each person's net balance and return a set of money transfers that settles the group using the minimum possible number of transactions.

A positive balance means the participant should receive money. A negative balance means the participant owes money. Every expense amount and share is an integer number of paise.

Formal Specification

Implement settle_debts(participants, expenses).

participants is a list of unique participant names.
expenses is a list of dictionaries with keys payer, amount, and shares.
shares maps every participant who owes part of that expense to an integer share. Shares for an expense sum to its amount.
Return a list of dictionaries with keys from, to, and amount.
Every returned transfer must have a positive amount.
The result must settle all balances and use the minimum number of transfers.

Because finding the globally minimum number of settlements is combinatorial, use exact backtracking for the input limits below.

Constraints

1 <= len(participants) <= 10
0 <= len(expenses) <= 50
Expense amounts and shares are non-negative integers measured in paise
Each expense's shares sum to its amount
Every participant appears in every expense's shares map

Function Signature

def settle_debts(participants, expenses):