后端岗位面试题更新 2026-08-05

在给定的QQ登录记录中,需要快速找出在任意5分钟窗口内登录次数达到两次及以上的QQ号。请说明你会选择哪种数据结构来实现这一需求,并阐述其原因与具体实现思路。

后端开发性能优化系统设计技术原理

考察说明

考查候选人对时间窗口计数问题的理解,以及选择合适数据结构进行高效处理的能力。

回答思路

  1. 【回答框架 1】核心需求是按用户统计在5分钟滑动窗口内的登录次数,并筛选出次数≥2的用户。可选用哈希表(如字典)将QQ号映射到其登录时间戳列表,利用有序结构(如数组或链表)保存时间。
  2. 【回答框架 2】处理每条登录记录时,先取出该QQ号的时间戳列表,删除所有早于当前时间5分钟的历史时间戳(即窗口外的记录),然后将当前时间戳追加。若列表长度达到2,则说明该QQ号在窗口内重复登录,可输出或标记。
  3. 【回答框架 3】哈希表提供O(1)平均查找与插入复杂度,列表维护时间有序,每次操作只需检查窗口边缘,整体时间复杂度为O(n),空间复杂度为O(m),其中n为记录数,m为不同QQ号数量。
  4. 【回答框架 4】若需支持更高并发或实时流处理,可考虑使用滑动窗口日志或使用Redis的ZSET(有序集合)以时间戳为score存储,但基础数据结构为哈希表加时间戳列表已足够。
  5. 【回答框架 5】实际实现中需注意时间单位统一,并确定窗口为闭区间或开区间,避免边界误判。
  6. 【关键点 1】选择哈希表(字典)以QQ号为键,值为按时间排序的戳记列表。
  7. 【关键点 2】窗口内删除过期时间戳,保证列表只包含最近5分钟的记录。
  8. 【关键点 3】列表长度≥2即判定为重复登录,时间复杂度O(n)。
  9. 【易错点 1】误将窗口固定为每分钟分隔,导致跨分钟边界重复登录未被识别,必须使用滑动窗口。
  10. 【易错点 2】忽略时间戳排序,导致删除或计数不准确。