给定一个用户行为日志（如用户ID、行为类型、时间戳），如何高效计算每个用户在最近7天内的活跃次数（即登录次数），并找出活跃用户Top 10？请说明数据结构选择、算法流程及优化措施。
Tencent软件开发-移动客户端开发方向难度：中等
答案
1) 【一句话结论】
采用哈希表记录用户登录次数，结合时间戳队列维护7天滑动窗口，过滤登录行为后动态更新，最终按活跃次数降序输出Top 10用户。
2) 【原理/概念讲解】
老师会解释：这个问题本质是动态维护一个固定长度（7天）的时间窗口，并统计窗口内特定行为（登录）的次数。核心思路是结合时间窗口的滑动特性和哈希表的高效查询能力。具体来说：
- 时间窗口：滑动窗口，以当前系统时间为基准，窗口长度为7天。新日志到来时，判断其时间是否在窗口内（即当前时间 - 日志时间 ≤ 7天），若在则纳入统计，否则忽略。
- 哈希表：存储用户ID到“活跃次数”的映射，用于快速查询和更新用户登录次数，时间复杂度为O(1)。
- 时间戳队列（双端队列）：维护窗口的时间边界，采用FIFO（先进先出）机制，存储窗口内所有登录记录（用户ID+时间戳）。当队列长度超过7天（即窗口内记录数超过7天）时，移除队头（最早的时间戳），并同步更新哈希表（减少该用户活跃次数，因为记录已出窗口）。
类比：滑动窗口像移动的“时间篮子”，只保留最近7天的登录记录；哈希表是篮子里的“用户标签”，快速标记谁在篮子里（即是否在7天内登录过）；队列是篮子的“时间边界”，通过FIFO控制篮子的大小，确保篮子里的数据不超过7天。
3) 【对比与适用场景】
| 数据结构组合 | 定义 | 特性 | 使用场景 | 注意点 |
|---|---|---|---|---|
| 普通列表 + 哈希表 | 列表存储时间戳，哈希表存储用户状态 | 时间戳遍历需O(n)，哈希表O(1) | 小数据量，简单场景 | 移除旧时间戳需遍历列表，效率低 |
| 哈希表 + 双端队列（时间戳队列） | 哈希表存储用户活跃次数，队列存储（用户ID，时间戳） | 队列O(1)入队/出队，哈希表O(1) | 大规模日志，高效维护时间窗口 | 需确保队列与哈希表同步，移除旧时间戳时同步更新用户状态 |
4) 【示例】
假设用户行为日志（时间戳为毫秒级，当前系统时间1702895200）：
[
{"user_id": "u1", "action_type": "login", "timestamp": 1702895200},
{"user_id": "u2", "action_type": "click", "timestamp": 1702895200},
{"user_id": "u1", "action_type": "login", "timestamp": 1702902400},
{"user_id": "u3", "action_type": "login", "timestamp": 1702903000},
{"user_id": "u1", "action_type": "login", "timestamp": 1702909200},
{"user_id": "u2", "action_type": "login", "timestamp": 1702910800},
{"user_id": "u4", "action_type": "login", "timestamp": 1702916400},
{"user_id": "u1", "action_type": "login", "timestamp": 1702922600},
{"user_id": "u5", "action_type": "login", "timestamp": 1702928200},
{"user_id": "u2", "action_type": "login", "timestamp": 1702934800},
{"user_id": "u3", "action_type": "login", "timestamp": 1702935400},
{"user_id": "u1", "action_type": "login", "timestamp": 1702941000},
{"user_id": "u6", "action_type": "login", "timestamp": 1702941600},
{"user_id": "u2", "action_type": "login", "timestamp": 1702947600},
{"user_id": "u1", "action_type": "login", "timestamp": 1702954200},
{"user_id": "u3", "action_type": "login", "timestamp": 1702954800},
{"user_id": "u7", "action_type": "login", "timestamp": 1702961000},
{"user_id": "u1", "action_type": "login", "timestamp": 1702967600},
{"user_id": "u2", "action_type": "login", "timestamp": 1702974200},
{"user_id": "u4", "action_type": "login", "timestamp": 1702980800},
{"user_id": "u5", "action_type": "login", "timestamp": 1702987400},
{"user_id": "u1", "action_type": "login", "timestamp": 1702994000},
{"user_id": "u3", "action_type": "login", "timestamp": 1703000600},
{"user_id": "u6", "action_type": "login", "timestamp": 1703002200},
{"user_id": "u2", "action_type": "login", "timestamp": 1703008800},
{"user_id": "u1", "action_type": "login", "timestamp": 1703015400},
{"user_id": "u4", "action_type": "login", "timestamp": 1703022000},
{"user_id": "u7", "action_type": "login", "timestamp": 1703028600},
{"user_id": "u5", "action_type": "login", "timestamp": 1703035200},
{"user_id": "u1", "action_type": "login", "timestamp": 1703041800},
{"user_id": "u2", "action_type": "login", "timestamp": 1703042400},
{"user_id": "u3", "action_type": "login", "timestamp": 1703049000},
{"user_id": "u8", "action_type": "login", "timestamp": 1703055600}
]
处理流程伪代码：
- 过滤：仅保留
action_type="login"的日志。 - 初始化：当前时间
curTime=1702895200，窗口长度7天=604800秒，队列q为空，哈希表userCount为空。 - 遍历过滤日志：
a. 计算时间差：diff=curTime - log.timestamp。若diff≤604800，则：- 将
(log.user_id, log.timestamp)入队（队列按时间顺序排列）。 - 更新哈希表：若用户已存在则
userCount[user_id] +=1，否则初始化为1。
b. 检查队列长度，若超过7天（队列长度 > 7天内的记录数），则移除队头元素（最早的时间戳），并同步更新哈希表：若该用户在哈希表中，则userCount[user_id] -=1（因为记录已出窗口）。
- 将
- 统计：哈希表中每个用户的值即为7天内登录次数。
- 排序：按活跃次数降序排序，取Top 10。
5) 【面试口播版答案】
好的，面试官，这个问题要高效统计最近7天登录次数并Top10。首先，只统计“登录”行为，因为活跃次数特指登录。然后，用哈希表记录用户活跃次数，用时间戳队列（存储用户ID和时间戳）维护7天滑动窗口。处理每条日志时，判断时间是否在窗口内（当前时间-日志时间≤7天），在的话更新哈希表（累加次数），并将（用户ID，时间戳）入队；队列长度超过7天就移除队头元素（最早的时间戳），同步更新哈希表（减少该用户活跃次数，因为记录已出窗口）。最后统计哈希表，按活跃次数降序取Top10。哈希表和队列操作都是O(1)，适合大规模日志。
6) 【追问清单】
- 问：时间戳精度如何处理？答：统一为毫秒级，确保时间差计算准确，避免秒级误差导致窗口错位。
- 问：大规模日志怎么优化？答：用流处理框架（如Flink），分片并行计算，每个分片维护本地队列和哈希表，最后合并Top10结果。
- 问：并发下如何保证数据一致？答：使用分布式锁（如Zookeeper）或数据库事务，确保同一用户行为不被重复处理或丢失。
- 问：相同活跃次数如何排序？答：按用户ID升序或最后登录时间降序，保证结果唯一。
- 问：如果日志中存在重复用户ID的登录记录，如何去重？答：哈希表自动去重，因为更新时只累加次数，不会重复计数。
7) 【常见坑/雷区】
- 忽略行为类型过滤：直接统计所有行为，导致结果错误（活跃次数特指登录）。
- 时间窗口维护错误：未正确移除旧时间戳，导致统计结果包含过期数据。
- 队列与哈希表同步：移除旧时间戳时未同步更新用户活跃次数，导致数据不准确。
- 排序逻辑错误：未按活跃次数降序排序，或未处理相同次数的排序规则。
- 并发导致不一致：多线程环境下队列与哈希表操作未同步，导致数据不一致。