面试题:字节跳动面试题,用户在线波峰计算。
前几天面试了字节跳动,记录下面试遇到的算法题
题目
输入: 用户日志(time, user_id, login | logout)
输出:同时在线人数的峰值,精确到秒
一开始,想了一分钟左右,想到了一个比较简单粗暴的方式。
使用位图的思想,将一天 分成 86400 秒,每秒单独统计,最后遍历一遍,找最大的值所对应的秒数
总的来说简单粗暴,也是比较容易想到的方式。只是由于按照每秒来统计了,所以写入到这个位图的效率是很低的。如果用户一天都在线, 那么就要写86400 次,明显是很慢的。
面试官一看这么粗暴,问了句,有没有优化的方案?
按照套路来,要么动态规划把历史记录一下,要么二分一下。动态规划明显不适用,二分的思想好像是可行的。
先将一天分成24小时,按照上面的方法统计一遍,找到峰值的小时,然后从这小时里面按照分钟统计一遍,找到峰值的分钟,再将分钟分成60秒,再统计一遍
理论上,每个用户跨越的时间越长,这样统计起来应该是会比第一种方式优秀很多。
但是面试官的问题来了,如果有多个峰值怎么办,最坏情况下每秒都是峰值,这种方式会比第一种方式慢得多
那就得继续想呗,想了几分钟,面试官看我想不出来就放弃了,我的心也凉了下,感觉没戏了
面试结束之后,继续想了下这个问题有没有更好的解法
毕竟同一个坑不能栽进去两次对不对。
可能是最优解的解法来了
跳开之前的统计所有秒数的想法,这个问题的解法就简单多了
我们先来想一下什么时候会有峰值,肯定是在线人数最多的时候。那么某个时间点在线的人数怎么算呢,很明显是 所有在这个时间点之前登入的 - 在这个时间点之前所有登出的。
那么算法也很简单,
- 定义三个变量,其中一个记录当前在线人数(
currentVal
),一个最大值(maxVal
),最后一个记录其对应的秒数的数组(seconds
)。 - 将日志分成 登录,登出 两种状态,并且根据时间进行正向排序
- 遍历
步骤2
得到的日志,如果是登录则currentVal + 1
并且跟maxVal
对比,如果比maxVal
大,则将maxVal
设置为currentVal
,seconds
设置为 当前秒数, 如果maxVal == currentVal
, 则seconds
增加当前秒数。如果是登出,则currentVal - 1
(不过更完美点应该判断下当前是不是maxVal
, 如果是则将上一次峰值的秒数,到当前秒数的区间写入到seconds
) - 遍历完成之后得到的
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]