如何快速定位五分钟内重复登录两次的 QQ 号？

日期：2026-07-12
标签：#面试 #八股 #后端 #时间窗口 #数据结构 #场景题

一句话答案

日志按时间有序时，用 HashMap 保存每个 QQ 最近一次登录时间，新登录与上次差值不超过 300 秒即命中，时间复杂度 O(n)、状态 O(活跃用户数)。

面试口语版

如果登录事件按时间顺序到达，维护 Map<qq,lastLoginTime>。每来一条先查上次时间，若当前时间减上次时间小于等于 300 秒，就记录该 QQ；然后更新最近时间。若只关心当前五分钟活跃用户并希望控制内存，可再用时间轮/最小堆或队列淘汰过期 Map 项。分布式流处理中按 QQ KeyBy，维护带 TTL 的 ValueState；事件乱序则使用事件时间和 Watermark，不能只依赖处理时间。

伪代码

Map<Long, Long> last = new HashMap<>();
for (Login e : eventsInTimeOrder) {
    Long prev = last.put(e.qq(), e.time());
    if (prev != null && e.time() - prev <= 300) {
        report(e.qq());
    }
}

关键细节

明确“重复登录”是任意两次还是不同设备/地区。
只保存最近一次足以判断相邻登录间隔是否小于窗口。
乱序数据可能把 lastTime 回退，应按事件时间处理。
输出 QQ 去重可再维护结果 Set 或幂等落库。

面试官追问

为什么只保存最近一次登录时间就够？
数据乱序怎么办？
QQ 数量巨大如何控制内存？

面试官追问参考答案

1. 为什么只保存最近一次登录时间就够？

按时间有序时，若当前登录与任何历史登录在五分钟内，那么与它最近的前一次登录间隔一定也不超过五分钟。因此无需保存完整列表。

2. 数据乱序怎么办？

离线数据先按时间排序；实时流按 QQ 分区并使用事件时间、Watermark 和允许迟到，状态中可保存窗口内有序时间集合。过晚事件进入补偿流重新判断。

3. QQ 数量巨大如何控制内存？

状态设置五分钟 TTL，并用时间轮/过期队列删除长时间未登录用户；分布式系统按 QQ 哈希分区到多个节点，状态可落 RocksDB。只保留当前窗口相关用户。

学习清单

掌握 HashMap 最近状态与 TTL。
能处理流式乱序和分区状态。