Startup OA 面试真题解析：Trending Tracker Top-K Retrieval

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 delta
• apply("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

这道题考察的是一个支持动态增减分数并高效查询前 K 名的趋势榜系统。核心做法通常是用哈希表维护每个 key 的当前分数，再配合有序结构（例如按分数降序、key 字典序升序排序的平衡树、堆或自定义双层结构）来快速拿到 topk() 结果。更新时要注意分数不能小于 0，且分数变为 0 的 key 不应出现在结果中；由于更新次数可达 20 万且 topk() 可能被频繁调用，因此需要尽量避免每次查询都全量排序。