Nvidia 三天日志题：每天错误数都超过阈值的用户

题意与假设

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

• 每条记录为 (user_id,error_count)，同一用户一天可出现多行，必须先求和；错误数为非负整数。
• “超过 10”是严格 >10；某天缺失即视为 0。恰好 10 不入选。
• 输出是满足条件的用户集合；如面试官要求排序，则在返回前额外排序。

解题路线

1. 扫描第一天，用哈希表累计每个用户的错误数，选出 >10 的候选集合。
2. 第二、三天只需为上一天候选用户累计次数，再与该天 >10 的用户求交；候选为空可提前返回。
3. 解释为什么可安全剪枝：用户若任意一天不达标，之后任何日志都无法让其满足“每天都达标”。

手动走一遍

第一天 U1 出现 2 次与 9 次两行，累计 11；U2 单行 20。第二天 U1=12、U2=10，于是候选仅剩 U1。第三天 U1=13，最终返回 {U1}。如果错误地按单行比较，第一天会漏掉 U1。

Python 参考实现

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

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

from collections import defaultdict


def users_over_threshold_each_day(daily_logs, threshold=10):
    """Each day is a sequence of (user_id, error_count) records."""
    if len(daily_logs) != 3:
        raise ValueError("expected exactly three days")
    if not isinstance(threshold, int) or threshold < 0:
        raise ValueError("threshold must be a nonnegative integer")
    candidates = None
    for records in daily_logs:
        totals = defaultdict(int)
        for user_id, count in records:
            if not isinstance(count, int) or count < 0:
                raise ValueError("error counts must be nonnegative integers")
            if candidates is None or user_id in candidates:
                totals[user_id] += count
        qualified = {user_id for user_id, count in totals.items() if count > threshold}
        candidates = qualified if candidates is None else candidates & qualified
        if not candidates:
            return set()
    return candidates

复杂度

设三天总记录数 M，哈希聚合总时间期望 O(M)，集合空间 O(U)，U 为首日不同用户数。后两天只累计候选用户，可降低实际内存与处理量，但仍需扫描输入记录。

易错点与追问

容易失分的边界

• 把每行计数与 10 直接比较，漏掉同日同用户的累加。
• 用 >=10 而不是 >10，把恰好 10 的用户误纳入。
• 把三天总错误数相加再比较，错误替代了每天都满足的交集条件。

继续深挖

• 日志分片时先按 (day,user_id) 聚合，再合并分片结果；不能在每个分片单独判 >10。
• 若日志是事件流而非已汇总记录，需定义时区、事件时间、迟到窗口和重复事件去重。
• 若有 D 天，可逐日过滤候选集合，空间仍由当前候选数与当日聚合键数决定。