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通知。
面试官很好，有不对或者打不出来的地方会提醒你。很nice的一次面试体验。面试之前搜了下牛客的面经，大概了解了三面的考察点，可能看我项目比较水又没实习，所以就直接写题了吧。
取之牛客，用之牛客，馈之牛客。
祝大家offer++ ；×
祝大家++offer; √
全部评论
(8) 回帖