首页 > bigo 3面 c++
头像
从天而降的招式
编辑于 2020-09-14 19:48
+ 关注

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通知。

面试官很好,有不对或者打不出来的地方会提醒你。很nice的一次面试体验。面试之前搜了下牛客的面经,大概了解了三面的考察点,可能看我项目比较水又没实习,所以就直接写题了吧。
取之牛客,用之牛客,馈之牛客。
祝大家offer++ ;×
祝大家++offer;   √

更多模拟面试

全部评论

(8) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐