← Microsoft Interview Insights

Microsoft·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Apr 2026

Summary

Microsoft SWE interview with a graph/greedy problem about settling debts among friends with minimum transactions. Short on details but the problem itself is a classic that's trickier than it looks.

Questions Asked (1)

Q1

Given a list of transactions between a group of friends, find the minimum number of transactions needed to settle all debts.

Algorithms & Data Structures
Author's notes

The example they gave makes it seem easy: Alice pays Bob $5, Bob pays Bill $5, so just have Alice pay Bill directly.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a graph where each person is a node and transactions are edges, then compute each person's net balance. The goal is to minimize the number of transactions to settle all debts, which can be approached by repeatedly matching the largest creditor with the largest debtor, or using a backtracking/DP approach for optimality. Explain the trade-offs between greedy and optimal solutions.

Pro tip: Mention that the problem is NP-hard in general (minimum transactions is equivalent to the minimum number of edges to make all balances zero, which is related to the subset-sum problem), so for large inputs a greedy approach is often used, but for small inputs an exact algorithm like backtracking with memoization can be used. This shows awareness of complexity and practical constraints.

1. Clarify the problem

Ask clarifying questions: Are transactions directed? Can we assume the net balances sum to zero? Is the goal to minimize the number of transactions or the total amount transferred? Confirm that we only care about the net amount each person owes or is owed.

2. Compute net balances

For each person, calculate their net balance by summing all amounts they paid and received. This reduces the problem to settling these net balances with the fewest transactions.

3. Choose an algorithm

Discuss options: a greedy approach (match largest creditor with largest debtor) which is simple but not always optimal, or an exact approach using backtracking/DP (e.g., recursively settle the first non-zero balance by trying all opposite-sign balances) which guarantees minimum transactions but may be exponential.

4. Analyze complexity and trade-offs

Explain that the exact problem is NP-hard (can be reduced from subset sum), so for large N, greedy is practical. For small N (e.g., N ≤ 10), backtracking with memoization is feasible. Mention that the greedy approach often yields near-optimal results.

5. Implement and test

Write code for the chosen approach, handle edge cases (all balances zero, one person owes everyone), and test with examples. If time permits, discuss optimizations like pruning in backtracking or using a priority queue for greedy.

Key Points to Mention

  • Net balance calculation: reduce transactions to net amounts each person owes or is owed.
  • Graph representation: people as nodes, transactions as edges, but net balances simplify to a list of positive and negative values.
  • Greedy algorithm: repeatedly settle the largest debt with the largest credit; not always optimal but efficient (O(N log N) with sorting).
  • Exact algorithm: backtracking/DP to minimize transactions, exponential time but optimal; can use memoization on the multiset of balances.
  • NP-hardness: the problem is NP-hard (related to subset sum), so no polynomial-time exact solution unless P=NP.
  • Edge cases: zero balances, single person, all balances cancel out, large number of friends.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.