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 hard difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Affirm.

What role is this question designed for?

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

Compute Balances and Minimize Settlements

Company: Affirm

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

You are building a daily ledger service. A transaction record has three fields: `timestamp`, `user_id`, and `delta_amount`. `delta_amount` can be positive or negative and represents how that user's balance changes during the day. All amounts are integers. 1. Given a list of transaction records for a single day, compute each user's end-of-day net balance, assuming every user's starting balance is 0. 2. Using the resulting balances, generate a settlement plan with the minimum possible number of transfers so that every user's final balance becomes 0. A user with a negative balance must pay money, and a user with a positive balance must receive money. Each settlement transfer should be represented as `(from_user, to_user, amount)`. Notes: - Users whose balance is 0 do not need to appear in the settlement plan. - You may assume the sum of all balances is 0. - For the exact-minimum settlement part, assume the number of users with non-zero balance is small enough to permit an exponential-search solution if needed.

Quick Answer: This question evaluates transactional data aggregation and net-balance computation skills alongside combinatorial optimization for minimizing settlement transfers, testing competencies in data structures, numeric aggregation, and algorithmic reasoning.

End-of-Day Net Balances

You are building a daily ledger service. Each transaction record has three fields: `timestamp`, `user_id`, and `delta_amount`. `delta_amount` is an integer (positive or negative) representing how that user's balance changes during the day. Every user's starting balance is 0. Given a list of transaction records for a single day, compute each user's end-of-day **net** balance (the sum of all their `delta_amount` values). Return a mapping from `user_id` to net balance. Users whose final net balance is 0 should be **omitted** from the result (they are settled and need no entry). Input: a list of records, where each record is `[timestamp, user_id, delta_amount]`. Output: a dict mapping each user with a non-zero balance to that balance.

Constraints

delta_amount is an integer and may be negative, positive, or zero.
A user may appear in many records; sum all their deltas.
Omit any user whose final net balance equals 0.
The input list may be empty (return an empty mapping).

Examples

Input: ([[1, 'alice', 100], [2, 'bob', -50], [3, 'alice', -30], [4, 'carol', 20]],)

Expected Output: {'alice': 70, 'bob': -50, 'carol': 20}

Explanation: alice nets 100-30=70, bob -50, carol 20. All non-zero, all kept.

Input: ([],)

Expected Output: {}

Explanation: No transactions means no balances.

Input: ([[1, 'alice', 50], [2, 'alice', -50]],)

Expected Output: {}

Explanation: alice nets to 0, so she is omitted, leaving an empty result.

Input: ([[1, 'x', -10], [2, 'y', 10]],)

Expected Output: {'x': -10, 'y': 10}

Explanation: x owes 10 (debtor), y is owed 10 (creditor); total balance is 0.

Input: ([[1, 'a', 5], [1, 'a', 5], [2, 'a', -3], [3, 'b', -7]],)

Expected Output: {'a': 7, 'b': -7}

Explanation: Multiple records for 'a' (including a same-timestamp duplicate) sum to 5+5-3=7; 'b' is -7.

Hints

A single hash map keyed by user_id is enough — accumulate delta_amount per user in one pass.
timestamp is not needed for the net balance; you only sum the deltas.
After accumulating, filter out users whose balance is exactly 0 so settled users don't appear.

Minimum-Transfer Settlement Plan

Continuing the ledger service: you are given the users' net balances (the output of part 1) as a mapping from `user_id` to balance. Positive balances are **creditors** (must receive money); negative balances are **debtors** (must pay money). The sum of all balances is 0. Produce a settlement that brings everyone to 0 using the **minimum possible number of transfers**, where each transfer moves money from one debtor to one creditor. Return that minimum **number of transfers**. This is the Optimal Account Balancing problem: greedily pairing the largest creditor with the largest debtor does NOT always give the minimum. The optimum requires finding subsets of users whose balances cancel exactly. The prompt permits an exponential-search solution because the number of users with non-zero balance is small. Key insight: if the non-zero accounts can be partitioned into `G` disjoint groups that each sum to 0, a group of `k` accounts settles in `k - 1` transfers. With `n` non-zero accounts, total transfers = `sum(k_g - 1) = n - G`, so minimizing transfers means **maximizing** the number of zero-sum groups. Input: a dict mapping user_id to a (possibly zero) balance. Output: an integer, the minimum number of transfers.

Constraints

The number of users with non-zero balance is small (an exponential-time solution is acceptable).
The sum of all balances is exactly 0.
Users with a balance of 0 are ignored and do not appear in any transfer.
Greedy largest-creditor/largest-debtor pairing is NOT guaranteed optimal; subsets that cancel exactly must be found.

Examples

Input: ({},)

Expected Output: 0

Explanation: No non-zero balances means no transfers are needed.

Input: ({'a': 10, 'b': -10},)

Expected Output: 1

Explanation: b pays a 10 in a single transfer.

Input: ({'a': 5, 'b': 5, 'c': -10},)

Expected Output: 2

Explanation: c must pay both a and b; no zero-sum proper subgroup exists, so 3 accounts settle in 3-1=2 transfers.

Input: ({'a': 4, 'b': -1, 'c': -3},)

Expected Output: 2

Explanation: The classic case: {4,-1,-3} has no two-element zero-sum subset, so it settles in 3-1=2 transfers, not 1.

Input: ({'a': 1, 'b': 1, 'c': -2, 'd': 3, 'e': -3},)

Expected Output: 3

Explanation: Partition into {a,b,c} (sums to 0, 2 transfers) and {d,e} (1 transfer) = 2 groups; 5-2=3.

Input: ({'a': -100, 'b': 50, 'c': 50},)

Expected Output: 2

Explanation: a pays both b and c; no zero-sum subgroup, so 3-1=2 transfers.

Input: ({'w': 5, 'x': -5, 'y': 6, 'z': -6},)

Expected Output: 2

Explanation: Two independent zero-sum pairs {w,x} and {y,z}; 2 groups, 4-2=2 transfers.

Input: ({'a': 3, 'b': 2, 'c': -5, 'd': 4, 'e': -4, 'f': 1, 'g': -1},)

Expected Output: 4

Explanation: Three zero-sum groups {a,b,c}, {d,e}, {f,g}; 7-3=4 transfers.

Hints

The minimum number of transfers for a set whose total is 0 and that cannot be split into smaller zero-sum subsets is (count - 1).
So minimize total transfers by MAXIMIZING the number of disjoint subsets that each sum to exactly 0; the answer is n - (max number of such subsets).
Use bitmask DP over the non-zero accounts: precompute each subset's sum, then for each zero-sum mask, anchor on its lowest set bit and try every zero-sum sub-group containing that bit.

Quick Overview

This question evaluates transactional data aggregation and net-balance computation skills alongside combinatorial optimization for minimizing settlement transfers, testing competencies in data structures, numeric aggregation, and algorithmic reasoning.