Nvidia Log Parser Top N：计数、并列排序与坏行策略

题意与假设

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

• 训练日志为逐行文本，每条有效行恰有一个空白分隔的 `item=VALUE` 字段，VALUE 非空且不含空白。题目未明确语法，不能把此格式说成原题规定。
• 有零个或多个 item 字段的行计为坏行并跳过，额外返回坏行数量；N 为非负整数，N=0 返回空榜单。
• 同频率按 item 字典序升序输出，保证测试可复现。若面试官指定首次出现顺序或其他 tie-break，应替换排序键。

解题路线

1. 逐行解析并验证 item 字段数量；对每条有效行用哈希计数器加一，坏行单独累计。不要在解析阶段就维护排序后的完整列表。
2. 计数结束后按键 (-count,item) 选最小的 N 项；这等价于次数降序、名称升序。N 小于不同 item 数量时用固定大小堆选取，避免全部排序。
3. 先在面试中问日志是否有转义、引号、JSON 和多 item；若为结构化日志，应使用正式解析器，不应用训练版正则猜测字段边界。

手动走一遍

日志 `item=gpu`、`item=cpu`、`item=gpu`、`item=cpu`、`item=disk`，取 Top 2，得到 [(cpu,2),(gpu,2)]；同频按字典序。若再有一行缺 item，结果不变但坏行数加一。

Python 参考实现

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

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

"""Training log grammar: exactly one whitespace-delimited item=VALUE field."""

from collections import Counter
from heapq import nsmallest
import re


ITEM_FIELD = re.compile(r"(?:^|\s)item=([^\s]+)")


def top_items(lines, n):
    if n < 0:
        raise ValueError("n must be nonnegative")
    counts = Counter()
    malformed = 0
    for line in lines:
        matches = ITEM_FIELD.findall(line)
        if len(matches) != 1:
            malformed += 1
            continue
        counts[matches[0]] += 1
    ranked = nsmallest(n, counts.items(), key=lambda pair: (-pair[1], pair[0]))
    return ranked, malformed

复杂度

L 为全部字符数，K 为不同 item 数，N 为榜单大小：解析与计数预期 O(L)；N≥1 时选 Top N 为 O(K log min(N,K))，N=0 时跳过选择。空间 O(K+min(N,K))。输出全量时也可直接排序 O(K log K)。哈希与比较成本还受 item 字符串长度影响。

易错点与追问

容易失分的边界

• 把每行计一次却不按 item 聚合，重复 item 无法进入正确排名。
• 在更新每个计数时就对所有 item 全排序，导致不必要的重复排序成本。
• 没有约定并列规则，同一数据多次运行可能以不同顺序返回。
• 未经确认就把训练正则推广到 JSON、带引号字段或多行日志，会错误截断 item。

继续深挖

• 流式无限日志要决定时间窗、迟到数据与 item 高基数策略；全局 Top N 不能无限期持有全部不同 item。
• 多分片聚合先合并各 item 的精确计数，再选全局 Top N；只合并每片的 Top N 在部分场景可能漏掉全局热门 item。
• 若只需近似热门项，可讨论 heavy hitters 摘要与误差界，但应先确认精度和内存预算。