面经策

现在有一天内的大量日志，每条日志记录了用户 id, 登陆时间,登出时间 {userid, login_time, logout_time}, 时间单位是秒。怎么求出一天内的最大在线人数？以及维持最大在线人数的最长持续时间？ ​

  • 标签：后端、场景题

🏛 业务架构师 ​

一天内所有用户的登录/登出日志求最大在线人数及持续时长——这是经典的扫描线（差分）问题，我先给算法，再按数据量级讲工程落地，最后点出业务用途。

算法：事件拆分 + 前缀和

每条日志拆成两个事件：(login_time, +1)、(logout_time, -1)，全部事件按时间排序后累加：

排序: (10:00,+1) (10:05,+1) (10:30,-1) (11:00,+1) ...
前缀和: 1 → 2 → 1 → 2 ... 
最大前缀和 = 最大同时在线人数
  • 求最大值：一次扫描取 max
  • 求最大值的持续时长：记录最大值出现的区间——进入最大值的时刻到跌落的时刻之差；若多个相同峰值取最长（扫描时维护"当前峰值区间长度"）
  • 边界约定要和业务对齐：登出瞬间算不算在线、同秒多事件排序（+1 在前还是 -1 在前）——口径差一秒，结果可能差一个量级的用户数

工程分档

  • 百万条日志：单机排序几秒搞定，Spark/Hive 一条 SQL（UNION ALL + 窗口函数）出结果，别犹豫
  • 实时需求（作战大屏实时在线数）：Flink 按 key（或全局）维护当前在线数，实时输出峰值——亿级事件的正规解
  • 内存优化：事件只存（时间戳, ±1），可用紧凑结构；超大规模按时间分片并行

业务视角（差异点）

最大同时在线（PCU）是容量规划的核心输入：连接数、消息推送、会话存储都按 PCU 的倍数规划——算错就是大促当晚容量事故。而"峰值持续时长"决定扩容策略：尖峰 1 分钟可以靠弹性秒级扩容扛，平台期 1 小时就必须真实容量。数据任务的口径（去不去重、多端怎么算）要和运营对齐——"在线人数"和"在线设备数"在汇报时差 30% 是常见的尴尬。

🏗 系统架构师 ​

这是经典的扫描线（差分）问题，我按正确性思路讲，再给在线人数的持续区间解法。

思路：把"人"转成"事件" 每个用户的 [login_time, logout_time] 拆成两个事件：login 时刻 +1、logout 时刻 -1（若 login 当秒在线、logout 当秒离线；按业务定义决定 logout 是 -1 在下一秒，先声明假设）。把 2N 个事件按时间排序（同一时刻先减后加或先加后减，按边界定义），扫描累加：

java
events.sort(by time, then by type);
int cur = 0, max = 0;
for (Event e : events) {
    cur += e.delta;          // login:+1  logout:-1
    max = Math.max(max, cur);
}

复杂度 O(N log N)，N 是日志条数（一天千万级单机秒级跑完）。

最大在线人数的"最长持续时间"：扫描时记录最大值出现的区间——遍历中 cur == max 的连续时间段。做法：维护 maxStartTime，每当 cur 刷新最大值记起点；每当 cur 从 max 掉下来，结算一段区间 [起点, 当前时刻)，更新最长区间。注意峰值 plateau（多次达到同一最大值）要拼接相邻段。

海量数据的分布式解法：

  • 日志 TB 级时，事件生成与按时间分片排序交给 MapReduce/Flink：map 阶段输出 (time, ±1)，按小时/分钟分桶排序归并；每个分桶内先算局部事件，reduce 阶段做前缀和拼接（携带上一分桶的结束计数），全局求 max
  • 若只要在线人数的近似监控（不精确峰值区间），可用每分钟采样计数：按分钟聚合 active 用户（bitmap），扫描分钟序列求峰值——工程上更常用，精度 1 分钟

边界细节（面试加分）：跨天的 login/logout 如何归到当天；同秒 login/logout 是否算在线；logout 缺失（掉线无登出）怎么用心跳时间补——真实数据清洗往往比算法本身工作量大。

💻 全栈开发专家 ​

这是经典的扫描线（差分）问题：每条记录拆成两个事件，排序后一遍扫完。

核心算法

  • 每条 {userid, login_time, logout_time} 拆成 (login_time, +1) 和 (logout_time, -1) 两个事件。
  • 所有事件按时间升序排序；同秒时 +1 排在 -1 前面，避免在线人数出现负数。
  • 扫描时维护 cur：遇到 +1 加一、-1 减一；cur > max 时更新 max 并记录峰值起点；cur == max 的区段取最长者即"最大在线人数的持续时间"。
java
long[][] ev = new long[2 * n][]; // {time, delta}
Arrays.sort(ev, (a, b) -> a[0] != b[0]
        ? Long.compare(a[0], b[0]) : Long.compare(b[1], a[1])); // +1 优先
int cur = 0, max = 0; long segStart = 0, best = 0;
for (long[] e : ev) {
    cur += e[1];
    if (cur > max) { max = cur; segStart = e[0]; best = 0; }
    else if (cur == max) { best = Math.max(best, e[0] - segStart); }
}

亿级优化：按秒开桶

一天只有 86400 秒，不排序，直接开长度 86401 的 int[] diff：diff[login]++、diff[logout]--，然后求前缀和扫一遍，O(N) 完事，一亿条数据单机毫秒级，多天就加日期维度分桶。

坑

  • 区间开闭要和面试官对齐：logout 当秒算不算在线、同秒登出又登录怎么排，直接影响结果。
  • 前缀和扫描时注意"峰值出现在两个事件之间的区段"，持续时间 = 下一个事件时间 − 峰值起点时间，别把端点重复计算。