Maintain top N payers
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
Implement topNPayers(n) that returns the n accounts with the highest cumulative outgoing payment amounts as strings formatted "{accountId}:{totalOutgoing}". Rank by the sum of amounts from debit operations (e.g., pay, executed scheduled payments). Support online updates as new debits occur. Explain your data structures (e.g., a size-N min-heap or an ordered map), tie-breaking rules, how to handle accounts with equal totals, and the time/space complexity per update and query.
Quick Answer: This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Maintain top N payers states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
You are building the reporting layer of a bank system. Each debit operation (a `pay` or an executed scheduled payment) records an outgoing amount from an account. Implement `topNPayers(payments, n)` that returns the `n` accounts with the highest cumulative outgoing amounts.
Each element of `payments` is a pair `[accountId, amount]` describing one debit (the same account may appear many times). Return a list of strings formatted as `"{accountId}:{totalOutgoing}"`, ordered by total outgoing amount descending. When two accounts have the same total, the account with the lexicographically smaller `accountId` comes first.
If `n` is larger than the number of distinct accounts, return all of them. If `n` is 0 or there are no payments, return an empty list.
Example: `payments = [["a",100],["b",50],["a",25],["c",75]]`, `n = 2` -> `["a:125", "c:75"]` (a totals 125, c totals 75, b totals 50).
Note on data structures: an interviewer expects you to discuss maintaining totals in a hash map and answering the query with either a full sort (O(A log A) per query) or a size-N min-heap (O(A log N)); for online updates a heap or ordered map keyed by total keeps each update near O(log N).
Constraints
- 0 <= len(payments) <= 10^5
- 0 <= n <= number of distinct accounts (n may exceed it; return all)
- amount is a non-negative integer
- accountId is a non-empty string
- Ties are broken by lexicographically smaller accountId
Examples
Input: ([['a', 100], ['b', 50], ['a', 25], ['c', 75]], 2)
Expected Output: ['a:125', 'c:75']
Explanation: Totals: a=125, c=75, b=50. Top 2 are a then c.
Input: ([['x', 30], ['y', 30], ['z', 10]], 2)
Expected Output: ['x:30', 'y:30']
Explanation: x and y tie at 30; the smaller accountId 'x' is listed first, then 'y'. z (10) is excluded.
Hints
- Aggregate first: walk the payments once and accumulate each account's total in a hash map. The same account can appear in many debits.
- To rank, sort the map entries by total descending; for equal totals fall back to ascending accountId so the order is deterministic.
- For an online / streaming version, maintain a size-N min-heap (or an ordered map keyed by total) so each update is O(log N) instead of re-sorting everything.
- Watch the edge cases: n = 0 and empty payments both return an empty list, and n larger than the distinct-account count returns every account.