Practice/Netflix/Netflix internal bank (usual DS&A no tricks)

Netflix internal bank (usual DS&A no tricks)

CodingOptional

Problem

You're building an internal transaction settlement system for a company. Employees can make transactions with each other throughout a billing period, and at the end of the period, you need to calculate the minimum number of settlement transactions required to clear all debts.

Given a list of transactions where each transaction is represented as [debtor, creditor, amount] (meaning the debtor owes the creditor that amount), calculate the minimal set of transactions needed to settle all debts between users.

Requirements

1. Calculate the net balance for each user (total owed minus total owing)
2. Generate a minimal set of settlement transactions that clears all debts
3. Return the result as a list of transactions in the format [debtor, creditor, amount]
4. The order of transactions in the output doesn't matter
5. If no settlements are needed, return an empty list

Constraints

• 0 ≤ number of transactions ≤ 1000
• 1 ≤ amount ≤ 10^6
• User names are non-empty strings containing only lowercase letters and numbers
• All amounts are positive integers
• The total amount owed equals the total amount to be received across all users
• Time complexity should be O(n) for calculating balances, where n is the number of transactions
• Space complexity should be O(u) where u is the number of unique users

Examples

Example 1:

` Input: [["alice", "bob", 50], ["bob", "charlie", 30], ["charlie", "alice", 20]] Output: [["alice", "bob", 30]] Explanation:

• Alice owes 50 total and is owed 20, net: -30
• Bob is owed 50 and owes 30, net: +20
• Charlie is owed 30 and owes 20, net: +10 After optimization: Alice pays Bob 30, Bob pays Charlie 10, Charlie already settled `

Example 2:

Input: [["alice", "bob", 100], ["bob", "alice", 100]] Output: [] Explanation: The debts cancel out perfectly, so no settlement is needed.

Example 3:

Input: [["user1", "user2", 30], ["user1", "user2", 20], ["user2", "user1", 15]] Output: [["user1", "user2", 35]] Explanation: Combine all transactions between user1 and user2: 30 + 20 - 15 = 35 net owed by user1