‹ DS&A interview · Socratic
DSA · Hashing + top-k · #31

Top Users by Spending (bookings)

Module 34 · difficulty 3/5·⏱ 30:00starts on first keystroke

You are given a list of `bookings`, each an object `{ userId, amount }`. Group the bookings by user, total each user's spend, and return the `userId`s of the top `k` users by total spending, highest first. Break ties by `userId` in ascending (lexicographic) order, so the result is deterministic. (This is Agoda's own example Round-1 question — a travel-flavored group-and-rank.)

Examples
  • bookings = [{userId:"u1",amount:100},{userId:"u2",amount:50},{userId:"u1",amount:25}], k = 1 → ["u1"] — u1 spent 125, u2 spent 50
  • bookings = [...same...], k = 2 → ["u1","u2"]
  • bookings = [], k = 3 → []

Stuck? Reveal an animated walkthrough of the approach.

Constraints
  • · 0 <= bookings.length <= 10^5
  • · 0 <= amount <= 10^6
  • · 1 <= k <= number of distinct users (clamp if k is larger).
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.