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

题目描述

实现一个 trending tracker。接收操作流：inc(key, delta) 把某个键的计数增加 delta，并支持查询当前计数最高的前 K 个键。相同计数时要有确定性的排序规则，保证结果可复现。

解题思路

用哈希表维护每个键的实时计数，inc 是 O(1)。查询时用大小为 K 的堆筛出前 K 名，或直接用 nlargest。若追求流式 O(log K)，可以在每次 inc 后把 (计数, key) 压入堆并惰性剔除过期堆顶，查询时重建。

import heapq
from collections import Counter

class TrendingTracker:
    def __init__(self, k):
        self.k = k
        self.cnt = Counter()

    def inc(self, key, delta):
        self.cnt[key] += delta

    def topk(self):
        return heapq.nlargest(self.k, self.cnt.keys(), key=lambda x: (self.cnt[x], x))

复杂度与易错点

inc 为 O(1)，topk 为 O(n log k)。排序键要提前定死——计数降序、键升序（或按题意），否则并列项顺序不稳定。若要求流式，注意堆里残留的过期 (计数, key) 要在出堆时与哈希表核对后丢弃。

FAQ

为什么 topk 的排序键要把 key 也带上？

并列计数时只按计数排序会得到不稳定顺序。加上 key 作为次级键，并列项的输出才可复现。

参考来源

• LeetCode 355 — Design Twitter
• LeetCode 692 — Top K Frequent Words

联系 VOPathway

如果你希望把这套方法用于自己的 OA 或 VO 准备，可以把目标岗位、当前阶段、面试时间和主要难点发给 VOPathway，我们会据此安排针对性的练习与复盘。

• 微信：Coding0201
• 邮箱：[email protected]
• Telegram：@OAVOProxy
• WhatsApp：+86 178 6396 8105

可提供 OA辅助、OA辅导、VO辅助与 VO辅导。文章用于训练参考，不代表相关公司的官方流程；实际安排请以候选人收到的通知为准。