← Remitly Interview Insights

Remitly·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Apr 2026

Summary

Remitly coding round, pretty much a classic debt-settlement problem. If you've seen LC 465 before you'll recognize it immediately, but there's enough implementation detail to trip you up if you're not careful.

Questions Asked (1)

Q1

Given a set of financial transactions or net account balances, compute the minimum number of transfers needed to settle all debts between accounts.

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

I'd seen this problem before in a slightly different form and jumped straight to the greedy approach.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, reduce the problem to net balances per account, then use a greedy algorithm that repeatedly matches the largest creditor with the largest debtor. Discuss the optimality of this approach and its time complexity, and consider trade-offs with alternative methods like subset-sum or flow-based solutions.

Pro tip: Mention that the greedy approach minimizes the number of transfers in practice but is not always optimal; however, finding the true minimum is NP-hard, so interviewers often expect the greedy solution with a clear explanation of its limitations.

1. Clarify the problem and inputs

Ask whether transactions are given as a list or net balances, and confirm that the goal is to minimize the number of transfers, not the amount transferred.

2. Compute net balances

Aggregate all transactions to compute each person's net balance (positive for creditors, negative for debtors).

3. Apply greedy matching

Repeatedly match the largest creditor with the largest debtor, settling the smaller amount and updating balances until all are zero.

4. Analyze complexity and optimality

State that the greedy approach runs in O(n log n) with sorting, and discuss that it yields at most n-1 transfers but may not be optimal in all cases.

5. Discuss trade-offs and alternatives

Mention that the exact minimum is NP-hard (related to subset sum), and briefly describe alternative approaches like backtracking or min-cost flow for small inputs.

Key Points to Mention

  • Net balance calculation: sum of credits minus debits per account.
  • Greedy algorithm: sort balances and match largest creditor with largest debtor.
  • Time complexity: O(n log n) due to sorting, with O(n) additional space.
  • Optimality: greedy minimizes transfers in many practical cases but not always; exact solution is NP-hard.
  • Alternative approaches: backtracking for small n, or min-cost flow for weighted transfers.
  • Edge cases: zero balances, single account, all balances zero.

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