Compute top-N outgoing spenders
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
Add a feature to report the top N accounts by total outgoing payments across both immediate pays and scheduled payments. Implement: List<String> topNSpenders(int n) that returns N strings each formatted as "{accountId}{amount}", where amount is the cumulative spent amount for that account. Support online updates after every payment with O(log N) update time by maintaining per-account totals and a size-N min-heap (or equivalent). Specify tie-breaking rules, query/update complexity, and how deletions/merges affect the ranking.
Quick Answer: This question evaluates a candidate's ability to design efficient aggregation and top-N ranking over transactional data, testing algorithm design, data structure knowledge, and complexity analysis within the Coding & Algorithms domain.
You are building the reporting feature for a bank system. Every payment a customer makes is an outgoing transfer of some amount from one account. You need to report the top N accounts ranked by their cumulative outgoing payment total.
Implement a function `topNSpenders(payments, n)` where:
- `payments` is a list of `[accountId, amount]` pairs, one per outgoing payment, applied in order. The same account may appear many times; its outgoing total is the sum of all its amounts.
- `n` is the number of top spenders to return.
Return a list of at most `n` strings. Each string is the concatenation `accountId + amount` (the account id immediately followed by that account's cumulative outgoing total, as a string), for the top spenders.
Ranking rules:
- Primary: descending by cumulative outgoing total.
- Tie-break: when two accounts have the same total, the account whose id is smaller in lexicographic (ascending string) order comes first.
Return the top `n` entries by this ordering. If fewer than `n` accounts have made payments, return all of them. If no payments were made, return an empty list.
Note on complexity: in an online system you would maintain per-account running totals in a hash map and a size-N min-heap keyed on total so each payment updates the ranking in O(log N). Here the function recomputes from the full payment list, but the same tie-breaking and ordering rules apply.
Example:
payments = [["acc1",100],["acc2",200],["acc1",50],["acc3",200]], n = 2
Totals: acc1=150, acc2=200, acc3=200. Ranked: acc2(200), acc3(200) [tie broken acc2<acc3], acc1(150). Top 2 -> ["acc2200", "acc3200"].
Constraints
- 0 <= number of payments
- 1 <= n
- amount is a non-negative integer
- accountId is a non-empty string
- If n exceeds the number of distinct accounts, return all accounts
- Ties on total are broken by ascending lexicographic accountId
Examples
Input: ([['acc1', 100], ['acc2', 200], ['acc1', 50], ['acc3', 200]], 2)
Expected Output: ['acc2200', 'acc3200']
Explanation: Totals: acc1=150, acc2=200, acc3=200. acc2 and acc3 tie at 200, broken by id (acc2<acc3). Top 2 are acc2 then acc3.
Input: ([['a', 10], ['b', 20], ['c', 30]], 5)
Expected Output: ['c30', 'b20', 'a10']
Explanation: n exceeds the account count, so all three are returned in descending total order.
Hints
- Accumulate each account's cumulative outgoing total in a hash map in a single pass over the payments.
- Sort accounts by (total descending, accountId ascending); a size-N min-heap keyed on total gives the same top-N in O(P log N) for the online case.
- Format each result by concatenating the account id directly with its total converted to a string, then take the first n entries.