Pinterest 广告 Impression 窗口 Top K：摄入、过期与并列顺序

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练版只实现可确定的共同核心：按广告 ID 统计曝光日志，支持批量 ingestImpressions 和最近 W 个时间单位内 Top K；不把 getCommonAds 的未公开交集语义编造成题面。
• 事件 timestamp 非递减，查询 now 也不得早于已处理时间；窗口定义为 (now−W, now]。同曝光次数按广告 ID 字典序升序；空批次允许。
• 未公开去重键，本训练版同 ad ID 的每条输入都计一次；实际日志若可能重试，应加 eventId 去重与过期策略。

解题路线

1. 时间有序时用 deque 存当前窗口事件、Counter 存广告计数。每次摄入后，弹出 timestamp≤now−W 的旧事件并递减计数，零计数删除。
2. 查询 Top K 前也推进窗口时钟并清理过期项，再按 (-count,adId) 排序取前 K。这个实现优先保证语义清楚；若 Top K 高频，再引入可删除有序结构或重建策略。
3. 所有入队事件最多出队一次，滑窗更新摊销 O(1) 每事件；固定 K 查询可以用 heap 降低排序成本，但实时更新和过期仍需维护。
4. 与保留完整历史的独立扫描模型在随机批次、空批次、边界 timestamp 和 k>不同广告数情形下逐次比较。

手动走一遍

W=10：t=1 广告 A 两次、B 一次；t=10 再给 B 一次。now=10 的窗口 (0,10] 中 A=2、B=2，按 ID 返回 A、B。now=11 时 t=1 已到边界被移出，只剩 B=1。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

"""Training interface for ingestion and Top K over a time ordered impression log."""

from collections import Counter, deque


class ImpressionWindow:
    def __init__(self, width: int):
        if width <= 0:
            raise ValueError("width must be positive")
        self.width = width
        self.events = deque()
        self.counts = Counter()
        self.last_time = None

    def ingest_impressions(self, impressions: list[tuple[int, str]]) -> None:
        for timestamp, ad_id in impressions:
            if self.last_time is not None and timestamp < self.last_time:
                raise ValueError("timestamps must be nondecreasing")
            self.last_time = timestamp
            self.events.append((timestamp, ad_id))
            self.counts[ad_id] += 1
            self._expire(timestamp)

    def top_k(self, k: int, now: int) -> list[tuple[str, int]]:
        if k < 0 or (self.last_time is not None and now < self.last_time):
            raise ValueError("invalid query")
        self.last_time = now
        self._expire(now)
        return sorted(self.counts.items(), key=lambda item: (-item[1], item[0]))[:k]

    def _expire(self, now: int) -> None:
        cutoff = now - self.width
        while self.events and self.events[0][0] <= cutoff:
            _, ad_id = self.events.popleft()
            self.counts[ad_id] -= 1
            if self.counts[ad_id] == 0:
                del self.counts[ad_id]

复杂度

N 条事件总摄入与过期 O(N) 摊销时间；单次查询若当前有 U 种广告，排序 O(U log U)，返回 K 项。内存 O(E+U)，E 为当前窗口内事件数。若日志乱序，deque 过期不再正确，需要 watermark 或按时间组织的状态。

易错点与追问

容易失分的边界

• 题目没有解释 common，就擅自定义为两份日志交集。
• 窗口边界用 < 与 ≤ 混淆，t=now−W 的事件不应留下。
• 只在摄入时过期，空闲后查询仍返回过期广告。
• Counter 零值不删除，Top K 可能出现无曝光广告。
• 声称查询 O(K) 而实际上对 U 个广告全排序。

继续深挖

• 如果 event time 乱序且允许 5 分钟迟到，怎样设 watermark 与修订输出？
• getCommonAds 若意指两个日志源共有广告，接口与输出如何重新定义？
• 海量广告且 Top K 每秒查询时怎样降低排序成本？
• 曝光日志重复投递如何按 eventId 做精确去重？