题目重点：三段题目题意分别统计某 policy 的唯一 Pin、时间范围内的唯一 Pin、范围内逐 policy 的唯一 Pin，明确跨 policy 去重差异。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 每条记录是 (pinId,policy,date)，训练日期统一为 YYYY-MM-DD，因此可用字符串顺序比较；题目未公布日期格式和时区。
- 范围 [startDate,endDate] 两端包含，重复记录不重复计数；第二问跨所有 policy 只算每个 Pin 一次，第三问按 policy 分别去重；空结果返回 0 或空映射。
解题路线
- 第一问筛选目标 policy，将 pinId 放入集合；第三问在日期范围内维护 policy→pinId 集合。
- 第二问用单个跨 policy 集合，不能把第三问的各 policy 计数求和，因为同一 Pin 可能违反多个 policy。
- 单次查询先用线性扫描给正确基线；若日期范围查询很多，按日期排序记录并二分查找左右边界，再扫描命中的记录；更高 QPS 可按天预聚合集合，但跨日求唯一数仍需集合并集或近似 sketch。
- 生产数据要先标准化日期和时区、明确撤销事件语义，并对记录去重键做定义。
手动走一遍
记录 (7,spam,01-02)、(7,spam,01-02)、(7,safety,01-03)、(8,spam,01-03)。范围 01-02 至 01-03：第二问结果 2 个 Pin，第三问是 spam→2、safety→1，不能把 2+1 当第二问答案。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Simple exact violation queries; dates are normalized YYYY-MM-DD strings."""
def unique_pin_count_for_policy(records, policy: str) -> int:
return len({pin for pin, record_policy, _ in records if record_policy == policy})
def unique_pins_in_range(records, start_date: str, end_date: str) -> int:
if start_date > end_date:
raise ValueError("reversed date range")
return len({pin for pin, _, date in records if start_date <= date <= end_date})
def unique_pins_per_policy_in_range(records, start_date: str, end_date: str):
if start_date > end_date:
raise ValueError("reversed date range")
grouped = {}
for pin, policy, date in records:
if start_date <= date <= end_date:
grouped.setdefault(policy, set()).add(pin)
return {policy: len(pins) for policy, pins in sorted(grouped.items())}
复杂度
展示版每问扫描 N 条记录，时间 O(N)，去重集合最坏 O(U)，U 为范围内不同 Pin 数；多次范围查询可按日期排序 O(N log N) 预处理，单次二分 O(log N)+扫描范围命中 M 条。
易错点与追问
容易失分的边界
- 对 policy 的记录条数计数而非 unique pinId。
- 把逐 policy 的唯一数相加作为全局唯一数。
- 未定义日期格式就直接按字符串比较。
- 过早用每日计数相加回答跨日去重。
继续深挖
- 记录迟到或 policy 被撤销时如何更新范围查询？
- 每天千万条记录、查询很多时，索引和近似计数怎么取舍？
- 同一 Pin 同日多次违反同一 policy，记录层的去重键应是什么？
