IP频率Top10及并列分组：第十名与十个频次层不同

题意与假设

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

• 输入已解析规范化IP字符串，每条header计一次；同一IP的不同文本表示应上游归一。
• 默认top K地址但纳入截止频次全部并列；distinct_levels=True取K个不同频次层。实际要求需先澄清。

解题路线

1. 先Counter全部IP次数，再按频次把IP分组，组内排序，频次降序输出。默认累计IP数达K后停止，因此最后一组可能使结果超过K。
2. 取不同频次层直接数输出组数，不等于按IP个数cutoff。若要求exact K则还要定义组内tie截断，不应既承诺全tie又保证K个。
3. 内存不够时按IP hash外部partition，分区内部精确聚合；全局合并本地counts后的TopK边界，不能只留每partition10个而丢所有cutoff tie成员。要返回全部并列可能结果本身很大。

手动走一遍

K2，A5/B3/C3：默认输出(5,[A]),(3,[B,C])共3地址。若最高频次所有100万IP都并列，K10也可能返回100万，内存和分页需明确。

Python 参考实现

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

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

from collections import Counter

def top_groups(addresses,k=10,distinct_levels=False):
    if k<0:raise ValueError("nonnegative k")
    if k==0:return []
    counts=Counter(addresses);groups={}
    for ip,count in counts.items():groups.setdefault(count,[]).append(ip)
    result=[];used=0
    for count in sorted(groups,reverse=True):
        group=sorted(groups[count]);result.append((count,group));used+=len(group)
        if (len(result)>=k if distinct_levels else used>=k):break
    return result

复杂度

N记录/U不同IP，计频O(N)期望；示例排序O(UlogU)保守、空间O(U)。外排/分区增加磁盘I/O，最终tie输出Ω(T)。

易错点与追问

容易失分的边界

• IP header哪字段src/dst未给时不能偷偷选双方。
• 将approximate heavy-hitters当精确全部tie会漏阈值边界。

继续深挖

• IPv6规范化与IPv4映射地址应怎样统一身份？
• 外部聚合如何处理极热点IP且保持精确计数？