面试题：字节跳动面试题，用户在线波峰计算

题目

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

示例的日志可能长这个样子：

<pre class="EnlighterJSRAW" data-enlighter-group="" data-enlighter-highlight="" data-enlighter-language="generic" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-theme="" data-enlighter-title="">uid        登录时间         登出时间
uid1       00:00:01        00:00:10
uid2       00:00:02        00:00:05
uid3       00:00:03        00:00:05

题目来自https://blog.cocktail1024.top/archives/149.html?hmsr=toutiao.io&utm_medium=toutiao.io&utm_source=toutiao.io，原文也有一些解答。我尝试用自己的方法做了一下这道题，发现跟题主最后的方法其实是一样的。

面试时的算法题通常不一定要求最优解，这个跟信息学刷题是不太一样的，有时候一条命令就能搞定的事情就没必要写代码去算了。比如从日志里找qps的峰值，其实就是一条命令：

<pre class="EnlighterJSRAW" data-enlighter-group="" data-enlighter-highlight="" data-enlighter-language="generic" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-theme="" data-enlighter-title="">cat 1.log|awk '{print $1}'|sort|uniq -c|sort -n

这么一条命令，又是sort，又是uniq，效率肯定高不了，但是对于一半的日志，也都是1分钟之内就能出结果，要是写代码实现，恐怕没有半小时完成不了，而且还不一定正确。所以用合适的方法去解决问题，也是面试的时候需要变现的一个素质。

对于这道题，我能想到的最好的办法是用一个1秒的滑动窗口来扫描日志，扫描的过程中动态的更新窗口内的在线人数，扫描完一遍日志，结果自然就出来了。在此之前需要把日志改造成线性的，如下所示：

<pre class="EnlighterJSRAW" data-enlighter-group="" data-enlighter-highlight="" data-enlighter-language="generic" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-theme="" data-enlighter-title="">uid     action      时间     
uid1    登入     00:00:01    
uid2    登入     00:00:02
uid3    登入     00:00:03    
uid2    登出     00:00:05 
uid3    登出     00:00:05
uid1    登出     00:00:10

当日志改造成单一的操作之后，我们就能很简单的记录滑动窗口内的在线人数。实际上，原文的解答也是与此类似。不过，日志的改造过程其实是相对耗费时间的，这块有可能是这道题的关键所在，最直接的办法就是跟插入排序一样，把所有的登出操作插入到合适的位置。

刚要结束的时候，突然又想起一个方法，也许更合适，日志不用拆分，处理每条日志的时候，首先是处理登入，直接把峰值加1，如果超过历史峰值则更新历史峰值，接下来处理这条日志的登出，可以开一个86400大小的数组，记录每一秒的登出数，这样在处理到这个登出时间点时，就减去相应的在线人数。

我们来看一下代码（假定日志的登入登出时间都是时间戳）：

<pre class="EnlighterJSRAW" data-enlighter-group="" data-enlighter-highlight="" data-enlighter-language="cpp" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-theme="" data-enlighter-title="">int logout[86400];
int max_online = 0;
int current_online = 0;

for(int i=0; i<LOG_SIZE; i++) {
    current_online -= logout[logs[i].login_time]
    if(++current_online > max_online) {
        max_online = current_online;
    }

    logout[logs[i].logout_time]++;
}

目测这段代码是有效果的，细节就不说了，比如登入时间不连续的时候，减去登出时间的人数这块，其实要考虑一个范围，这个只要记录上一条日志的登入时间即可。