bigo 3面 c++

2020/09/04 19：48更新了场景题思路

--------------------------------------------------------------

准时到场

自我介绍

写题：

1. 二叉搜索树，输出第三大的结点。右根左遍历

2. 说思路，二叉树a，b，判断a是不是b的子树。判断先序遍历b的结点是不是a的根节点，如果是的话就判断相等。怎么优化？ KMP算法?

场景题：

1. 十亿用户的上线下线时间数据，生成统计每个时刻在线用户的数量。

2. 用户名片系统，有用户id和其他信息，要求的功能为查找，增加，删除，查找频次较多，怎么设计？

3. 十亿用户给100万主播投票，每人只能投一次，实时显示得票数top100的主播。

思路：

1. 十亿用户的上线下线时间数据，生成统计每个时刻在线用户的数量。[过程中面试官有提示！]

假设第i个用户的上下线时间为[Si, Ei] ,单位为s，即第i个用户在第Si秒上线，在第Ei秒时下线。一天有24*60*60 = 86,400s，输出的数组长度out为86400，out[i] 表示第i秒在线的用户数量。

再维护两个同等长度的数组，一个是online, 一个是offline， online[i]表示在第i秒上线的人数, offline[i]表示再第i秒下线的人数。 out, online, offline数组全部初始化为0。

十亿用户的数据是无序的。依次遍历数据[Si, Ei], online[Si]++; offline[Ei]++;

遍历之后，状态转移方程为 out[i] = out[i-1] + online[i] - offline[i]] ; 第i秒在线的人数等于第i-1秒在线的人数 + 在第i秒上线的人数 - 在第i秒下线的人数；

时间复杂度 O(N)

空间复杂度O(N)

2. 用户名片系统，有用户id和其他信息（还是十亿个用户），要求的功能为查找，增加，删除，查找频次较多，怎么设计？

这题答得不好，第一反映是用红黑树来存储，因为查找比较多嘛。后来想想用户数量是十亿个，不能同时放到放到内存里，用红黑树不大行。

回答的是用链表来存储信息，具体来说是用跳表存储，这样的话查找删除增加的复杂度也可以是O(logN),并且相对红黑树来说更容易实现。

面试官：这种方法有什么缺点? 占用额外的空间比较多，除了数据本身占用的空间之外，还要额外的空间来存储跳表相关的信息。

面试官：如果服务器宕机了怎么办？(持久化问题) 在磁盘上保留一个数据的备份。具体的说，这十亿数据肯定不能都放到内存中的，大部分都是在磁盘里的，所以要对数据分段，读入和换出内存的时候以段为单位进行操作，类似于操作系统，可以使用lru，lfu页面淘汰算法决定哪个段要被淘汰。操作的时候，先判断数据在不在内存中，如果不在的话对数据段进行换入换出操作，把要操作的段换入到内存中。如果对内存中的数据进行了修改，也要同步地修改磁盘地数据。可以使用一个队列，把每次修改地信息压到队列里面，然后开个线程专门用来执行周期性地回写操作，这样就能保证磁盘地数据也是较新的数据。

3. 十亿用户给100万主播投票，每人只能投一次，实时显示得票数top100的主播

第一次回答的还是用链表。。。自己都笑了，跟链表过不去了这是。后来面试官强调说只实时显示得票数前100的主播，意思就是没必要对所有的数据进行排序。

那就维护一个size=100的小顶堆，主播的得票数有更新的时候，就去跟堆顶的得票数比一比，如果比它大，就把弹出堆顶元素，把当前主播压入堆。

面试官：怎么保证每个人只能投票一次。这种大量数据，每个数据的状态比较简单的情景最好用位图表示，申请一块连续的十亿位的空间，每个用户的id对应一个位，该位为0表示当前用户未投票，否则就表示已经投过票了。

一个人的力量总是有限的，上面的思路是我能想到的局部最优解，希望能抛砖引玉，大家一块探讨，会有更合适的方法！

智力题：

给N个人做测试，每次提取n个样本的血清，做一次测试就知道这n个人里面有没有人患病，如果有人患病，必须对这n个人每个人都做一次测试。

问n为多少时，做测试的数量最少。我的思路[假设一个人患病的概率为p，可以推导出做测试的数量 C= f(p, n), 当p一定时，C=f(n), 求函数f(n)的最小值即可。听说是智力题，第一反应竟然是用脑筋急转弯的思路来做。。]

反问：

工作用什么语言比较多？ c++

如果录用了，是去哪个部门？去二面面试官的部门。

多久会有通知过与不过? 不知道，等hr通知。