Trending Tracker: Top-K Retrieval
You are building a trending tracker.
You receive a stream of operations:
apply("inc", key, delta)— increase the key’s score by deltaapply("dec", key, delta)— decrease the key’s score by delta
The topk() operation should return up to k keys sorted by:
- Highest score first
- Lexicographically smaller key on ties
Constraints:
- Scores must not go below 0
- Keys with score 0 should not appear in results
- Up to 200,000 updates
topk()may be called many times — aim for efficiency
This problem asks you to maintain a live trending leaderboard with incremental score updates and efficient top-k queries. A common solution is to keep the current score of each key in a hash map, and maintain an ordered structure that ranks entries by descending score and then ascending lexicographical order. Updates must clamp scores at zero, and keys with zero score should be removed from the result set. Because there can be up to 200,000 updates and many repeated topk() calls, the key challenge is making both updates and queries efficient.
END
