Compute top-N outgoing spenders
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Take-home Project
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.
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.
Input: ([], 3)
Expected Output: []
Explanation: No payments were made, so there are no spenders to report.
Input: ([['x', 5]], 1)
Expected Output: ['x5']
Explanation: A single account with a single payment; its total is 5.
Input: ([['acc1', 100], ['acc2', 100], ['acc3', 100]], 2)
Expected Output: ['acc1100', 'acc2100']
Explanation: All three tie at 100; the tie-break picks the two lexicographically smallest ids, acc1 and acc2.
Input: ([['z', 0], ['y', 0]], 2)
Expected Output: ['y0', 'z0']
Explanation: Both accounts have a zero total; tie-broken by ascending id so y comes before z.
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.