How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Meta.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Meta during technical interviews.

Maintain top N payers | Meta Coding Question

Quick Overview

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.

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.

Input: ([], 3)

Expected Output: []

Explanation: No payments, so there are no accounts to rank.

Input: ([['solo', 500]], 5)

Expected Output: ['solo:500']

Explanation: Only one account exists; n=5 exceeds it so all accounts are returned.

Input: ([['a', 10], ['b', 20], ['c', 30]], 0)

Expected Output: []

Explanation: n=0 requests zero payers, so the result is empty.

Input: ([['b', 40], ['a', 40], ['c', 40]], 3)

Expected Output: ['a:40', 'b:40', 'c:40']

Explanation: Three-way tie at 40; all ordered by ascending accountId.

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.

Quick Overview