两日日志对象筛选：共同出现且客户至少两种

题意与假设

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

• 每条日志(timestamp,objID,clientID)，两文件已按正确时区分日。重复事件不增加不同客户数。
• 默认对象两日均出现且合并客户≥2；per_day=True代表每天各≥2。题目没有明确二者时先澄清。

解题路线

1. 每日日志按obj聚合client集合，对object键做交集，再按所选合同检查客户数。不要对整条日志交集，因为timestamp不同但obj可以相同。
2. 内存限制下把两文件外部排序为(obj,client)，按obj流式归并。每个obj只需保留最多两个不同client及两日出现标记，不必保存完整集合。
3. 外排成本由块数、内存和归并轮次决定；边读边对另一文件完整重扫会变二次I/O。若输入已经按obj排序，线性two-pointer归并即可。

手动走一遍

第一天objX只有A、第二天只有B：合并合同通过，每日合同不通过。同一天同客户重复100次仍只计一种客户；只出现在一天的对象不通过。

Python 参考实现

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

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

def eligible(day1,day2,per_day=False):
    # Records are (timestamp, object_id, client_id); files already represent days.
    def group(records):
        result={}
        for _,obj,client in records:result.setdefault(obj,set()).add(client)
        return result
    a,b=group(day1),group(day2)
    if per_day:
        return {obj for obj in a.keys()&b.keys() if len(a[obj])>=2 and len(b[obj])>=2}
    return {obj for obj in a.keys()&b.keys() if len(a[obj]|b[obj])>=2}

复杂度

集合版O(N1+N2)期望时间/O(U)不同obj-client空间；交集遍历较小obj键集。外排比较时间O(NlogN)、多轮顺序I/O，归并阶段O(N)。

易错点与追问

容易失分的边界

• 日边界按UTC还是业务时区不能默认为文件名。
• 只统计两天总记录数≥2会把同客户重复当成不同客户。

继续深挖

• 若日志乱序迟到，日结果何时可宣告最终？
• 怎样用分区哈希降低外排量并防热点对象撑爆单分区？