题目重点：Phone coding 题目要求按请求到达时间找被丢弃的时刻；本文明确包含端点、已丢弃请求是否计数和重复时间戳，并与全前缀参考对照。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版 timestamps 非递减且为整数秒；每秒指同一个整数时间戳，10 秒窗口为 [t−9,t]，即 t−10 的记录已过期。
- 所有到达请求都会计入两个规则的窗口，即使该请求被丢弃；若业务按‘已放行请求’计数，应改另一状态机。两个规则任一超限只记录该请求时间一次。
- 返回丢弃请求的时间列表，可重复时间值；若原题要求 request ID，应返回索引而非时间。
解题路线
- 顺序扫描时间戳；当前秒重复计数 sameSecondCount，一旦时间戳变化重置。
- 用 deque 保留最近 10 秒所有到达时间，入当前时间前清理≤t−10 的旧值，再追加当前请求。
- 若 sameSecondCount>3 或 deque 长度>20，则把 t 追加 dropped。不能因两个条件都超限而追加两次，也不要在拒绝后省略其到达记录，除非题目另定义。
- 用完整输入前缀在每步重新计数同秒和 (t−10,t] 中到达请求，随机 10,000 组独立对照；重点测同秒第 4 次、10 秒边界、两限制同触发。
手动走一遍
t=5 连续四个请求，前三个未触发 3/s，第四个时间 5 被输出一次。若在 t=0…9 各有两次请求，第 21 个在 t=9 到达，将触发 20/10s；到 t=10 时 t=0 已不在窗口。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Report arrival times dropped by 3-per-second and 20-per-ten-second rules."""
from collections import deque
def dropped_request_times(timestamps: list[int]) -> list[int]:
recent_ten_seconds = deque()
last_time = None
same_second_count = 0
dropped = []
for timestamp in timestamps:
if last_time is not None and timestamp < last_time:
raise ValueError("timestamps must be nondecreasing")
if timestamp != last_time:
same_second_count = 0
last_time = timestamp
same_second_count += 1
while recent_ten_seconds and recent_ten_seconds[0] <= timestamp - 10:
recent_ten_seconds.popleft()
recent_ten_seconds.append(timestamp) # every arrival counts, even when dropped
if same_second_count > 3 or len(recent_ten_seconds) > 20:
dropped.append(timestamp)
return dropped
复杂度
N 个请求各入队一次、最多出队一次，O(N) 时间；若 10 秒窗口内可有 W 条到达，队列 O(W) 空间，加输出最多 O(N)。即便窗口受限规则存在，丢弃项仍留队列，W 可超过 20。
易错点与追问
容易失分的边界
- 把 10 秒窗口当作 [t−10,t]，多算第 11 个整秒。
- 只记录第一次超额，同秒后续丢弃时刻漏掉。
- 两个限制同时触发就把同一请求输出两次。
- 删掉已丢弃请求后再计数，和训练口径不同。
- 从常见题库擅自加入 60 秒限额，题目只公开两个条件。
继续深挖
- 若输入乱序，如何按 event time 排序且保持原 request ID 输出？
- 若丢弃请求不计入后续 quota，状态如何改？
- 分布式实时限流如何把检查与计数做成原子操作？
- 若额外有每分钟限额，怎样扩展而不重复判定同一请求？
