How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Stripe.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Stripe during technical interviews.

How to settle multi-person debts in minimum transactions

Company: Stripe

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Problem 1: Minimize multi-person debt settlement Given a group of people with multiple loan records, find the minimum number of transactions to settle all debts so everyone's balance is zero. Core idea: First compute each person's net balance, and only focus on those whose net amount is non-zero. Then use backtracking or greedy matching to cancel positive and negative amounts against each other. For example, if someone owes 50 and another is owed 50, a single transaction settles both — minimizing the total number of transactions. Follow-up: If the debt relationships are very complex, involving hundreds of people, can your algorithm still maintain efficiency? Problem 2: Cheapest flights within K stops Given a list of flights with prices, find the lowest-cost path from source to destination within K stops. Approach: This is a classic graph shortest-path problem. You can solve it with dynamic programming where dp[i][k] represents the minimum fare to reach node i within k steps. Alternatively, use a modified Dijkstra's algorithm with a priority queue that also tracks the current number of stops, ensuring you don't exceed K stops while finding the lowest price. Follow-up: If the airline network is very large, or you need to support real-time price updates, how would you optimize?

Quick Answer: This question evaluates algorithm design and combinatorial optimization skills, focusing on reasoning about net balances, transaction minimization, and efficient search in multi-party debt settlement within the Coding & Algorithms domain.

Part 1: Minimum Transactions to Settle Multi-Person Debts

Given a list of money transfer records transactions where each record [from, to, amount] means from paid amount to to, compute the minimum number of additional settlement transactions needed so that every person's final net balance becomes 0. You may choose any settlement participants and amounts; the settlement transactions do not need to follow the original transaction graph. People whose net balance is already 0 do not need to participate.

Constraints

0 <= len(transactions) <= 50
transactions[i] has exactly 3 integers: [from, to, amount]
from and to are non-negative integer person IDs
from != to
amount > 0
Let K be the number of people with non-zero final balance. K <= 12
All intermediate sums fit in a signed 64-bit integer

Examples

Input: ([],)

Expected Output: 0

Explanation: There are no transactions and no one has a non-zero balance.

Input: ([[0, 1, 10]],)

Expected Output: 1

Explanation: One settlement transaction can reverse the imbalance between person 0 and person 1.

Input: ([[0, 1, 10], [2, 0, 5]],)

Expected Output: 2

Explanation: After netting, person 1 has +10 while persons 0 and 2 each have -5, requiring two settlement transactions.

Input: ([[0, 1, 10], [1, 0, 1], [1, 2, 5], [2, 0, 5]],)

Expected Output: 1

Explanation: Only persons 0 and 1 remain imbalanced, so a single settlement transaction is enough.

Input: ([[0, 1, 5], [2, 3, 7]],)

Expected Output: 2

Explanation: There are two independent exact-canceling pairs, so two settlement transactions are optimal.

Hints

First compress all original transactions into one net balance per person; the original edges no longer matter.
Use backtracking on the first unsettled balance and try pairing it only with opposite-signed balances. Skipping duplicate balance values and stopping after exact cancellation are useful pruning strategies.

Part 2: Scalable Greedy Debt Settlement Plan

This problem turns the scalability follow-up into an implementation task. Exact minimum debt settlement can be exponential in the number of non-zero balances, so for large debt networks you must build a deterministic greedy settlement plan efficiently. Given transactions where [from, to, amount] means from paid amount to to, compute each person's net balance as inflow minus outflow. A person with positive net balance must pay that amount during settlement, and a person with negative net balance must receive that amount. Repeatedly match the positive-balance person with the largest remaining amount to the negative-balance person with the largest remaining need. Break ties by smaller person ID. Return the settlement transactions generated by this rule. The returned plan must balance everyone, but it is not required to use the theoretical minimum number of transactions.

Constraints

0 <= len(transactions) <= 200000
transactions[i] has exactly 3 integers: [from, to, amount]
from and to are non-negative integer person IDs
from != to
amount > 0
The number of distinct people can be in the hundreds of thousands
Amounts and final balances fit in a signed 64-bit integer
You must follow the deterministic greedy rule; exact minimum transaction count is not required

Examples

Input: ([],)

Expected Output: []

Explanation: No balances exist, so the settlement plan is empty.

Input: ([[0, 1, 10]],)

Expected Output: [[1, 0, 10]]

Explanation: Person 1 has positive net balance 10 and pays person 0, who has negative net balance -10.

Input: ([[0, 1, 10], [2, 0, 5]],)

Expected Output: [[1, 0, 5], [1, 2, 5]]

Explanation: Person 1 pays the two receivers with need 5 each. Receiver ID 0 is chosen before receiver ID 2 due to tie-breaking.

Input: ([[0, 1, 7], [1, 0, 7]],)

Expected Output: []

Explanation: The two original transfers cancel out exactly, so no settlement transactions are needed.

Input: ([[0, 2, 5], [1, 3, 5]],)

Expected Output: [[2, 0, 5], [3, 1, 5]]

Explanation: Both payers and receivers are tied by amount, so smaller IDs are matched first.

Hints

After computing net balances, people with zero balance can be discarded immediately.
Use two heaps: one for the largest positive balances and one for the largest absolute negative balances. Each greedy match fully settles at least one participant.

Quick Overview

This question evaluates algorithm design and combinatorial optimization skills, focusing on reasoning about net balances, transaction minimization, and efficient search in multi-party debt settlement within the Coding & Algorithms domain.