2020年5月

前几天面试了字节跳动,记录下面试遇到的算法题

题目

输入: 用户日志(time, user_id, login | logout)
输出:同时在线人数的峰值,精确到秒

一开始,想了一分钟左右,想到了一个比较简单粗暴的方式。

使用位图的思想,将一天 分成 86400 秒,每秒单独统计,最后遍历一遍,找最大的值所对应的秒数

总的来说简单粗暴,也是比较容易想到的方式。只是由于按照每秒来统计了,所以写入到这个位图的效率是很低的。如果用户一天都在线, 那么就要写86400 次,明显是很慢的。

面试官一看这么粗暴,问了句,有没有优化的方案?

按照套路来,要么动态规划把历史记录一下,要么二分一下。动态规划明显不适用,二分的思想好像是可行的。

先将一天分成24小时,按照上面的方法统计一遍,找到峰值的小时,然后从这小时里面按照分钟统计一遍,找到峰值的分钟,再将分钟分成60秒,再统计一遍

理论上,每个用户跨越的时间越长,这样统计起来应该是会比第一种方式优秀很多。

但是面试官的问题来了,如果有多个峰值怎么办,最坏情况下每秒都是峰值,这种方式会比第一种方式慢得多

那就得继续想呗,想了几分钟,面试官看我想不出来就放弃了,我的心也凉了下,感觉没戏了

面试结束之后,继续想了下这个问题有没有更好的解法

毕竟同一个坑不能栽进去两次对不对。

可能是最优解的解法来了

跳开之前的统计所有秒数的想法,这个问题的解法就简单多了

我们先来想一下什么时候会有峰值,肯定是在线人数最多的时候。那么某个时间点在线的人数怎么算呢,很明显是 所有在这个时间点之前登入的 - 在这个时间点之前所有登出的。

那么算法也很简单,

  1. 定义三个变量,其中一个记录当前在线人数(currentVal),一个最大值(maxVal),最后一个记录其对应的秒数的数组(seconds)。
  2. 将日志分成 登录,登出 两种状态,并且根据时间进行正向排序
  3. 遍历步骤2得到的日志,如果是登录则 currentVal + 1 并且跟 maxVal 对比,如果比 maxVal 大,则将 maxVal 设置为 currentVal, seconds 设置为 当前秒数, 如果 maxVal == currentVal, 则 seconds 增加当前秒数。如果是登出,则 currentVal - 1 (不过更完美点应该判断下当前是不是maxVal, 如果是则将上一次峰值的秒数,到当前秒数的区间写入到 seconds
  4. 遍历完成之后得到的 maxVal 就是 峰值, seconds 就是对应的秒数列表

比如说,日志长这样

uid        登录时间         登出时间
uid1       00:00:01        00:00:10
uid2       00:00:02        00:00:05
uid3       00:00:03        00:00:05

步骤2中,将其变成

uid     action      时间     
uid1    登入     00:00:01    
uid2    登入     00:00:02
uid3    登入     00:00:03    
uid2    登出     00:00:05  // 到这里的时候需要 将上一次峰值到当前值(00:00:03 到 00:00:04 )写入到 seconds
uid3    登出     00:00:05
uid1    登出     00:00:10

步骤三

`currentVal` -> 1   -> 2   -> 3   -> 2   -> 1   -> 0
`maxVal`     -> 1   -> 2   -> 3   -> 3   -> 3   -> 3
`seconds`    -> [1] -> [2] -> [3] -> [3,4] -> [3,4] -> [3,4] 

最后,好像虽然做不出来,面试还是过了,感谢面试官抬一手。 如果有更好的解法,或者这个解法有问题,也方便留言。