Uber 过期 Counter：单元素计数与窗口总数

题意与假设

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

• 每个 put 产生一个独立事件，即使元素相同也分别计数；所有操作时间非递减。
• 训练约定：事件在 t_insert+window 时过期，所以时刻 now 的有效条件是 t_insert+window>now。题目只给跨越过期点的示例，未规定等于边界时的行为。
• 代码将 now 作为显式参数便于复现；原题 put(element) 等无时间参数，可由统一的单调时钟适配器注入 now。

解题路线

1. 按插入时间将 (timestamp, element) 放入全局 deque；另用哈希表维护各元素的未过期数量和一个 total。
2. 每次 put 或查询前，从 deque 头部连续弹出已过期事件，并同步减去元素计数与 total；时间非递减保证过期事件只在队首。
3. put 清理后追加事件并增两个计数；get_count 查哈希表，get_total_count 直接读 total。

手动走一遍

window=10，t=1 放 a、t=3 放 a、t=5 放 b；t=6 时 a=2、total=3。t=12 时 t=1 的 a 已过期，另外两次仍有效，故 a=1、total=2，与题目一致。

Python 参考实现

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

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

"""Exact counts for events in a fixed time-to-live window."""

from collections import defaultdict, deque


class ExpiringCounter:
    def __init__(self, window: int):
        if window <= 0:
            raise ValueError("window must be positive")
        self.window = window
        self.events: deque[tuple[int, str]] = deque()
        self.counts: dict[str, int] = defaultdict(int)
        self.total = 0
        self.last_time: int | None = None

    def _expire(self, now: int) -> None:
        if self.last_time is not None and now < self.last_time:
            raise ValueError("timestamps must be nondecreasing")
        self.last_time = now
        while self.events and self.events[0][0] + self.window <= now:
            _, element = self.events.popleft()
            self.counts[element] -= 1
            if self.counts[element] == 0:
                del self.counts[element]
            self.total -= 1

    def put(self, element: str, now: int) -> None:
        self._expire(now)
        self.events.append((now, element))
        self.counts[element] += 1
        self.total += 1

    def get_count(self, element: str, now: int) -> int:
        self._expire(now)
        return self.counts.get(element, 0)

    def get_total_count(self, now: int) -> int:
        self._expire(now)
        return self.total

复杂度

每个事件入队和出队最多各一次，m 个操作的摊还总时间 O(m)；单次清理可能弹出 O(m) 个事件，不能声称最坏 O(1)。空间 O(W+D)，W 为当前有效事件数、D 为不同有效元素数。

易错点与追问

容易失分的边界

• 只在 put 时过期会使纯查询阶段返回旧计数；所有读操作也必须先清理。
• 用最近一次 put 覆盖同名元素会漏掉同一元素的多个独立事件。
• 若传入乱序事件时间，全局队首可能不是最早到期事件；需拒绝乱序或改用按到期时间排序的结构。

继续深挖

• 如果查询必须保证最坏 O(log W)，可按到期时间用最小堆清理，但单次仍可能批量弹出多个过期事件；严格延迟界需要后台清理或分摊预算。
• 并发版须原子更新 deque、counts 与 total，并确保使用同一时钟口径；跨机器部署需明确事件时间与处理时间及迟到数据策略。