数据人必会的面试场景题【字节、美团、阿里等大厂】

内存限制 1 GB,如何快速判断一个数是否存在于 40 亿整数中?

这不简单吗?

直接把40亿个整数加载到内存中,然后判断遍历整个列表,看是否存在该整数

此种方式需要占用的内存空间:40 * 100000000 * 4 / 1024 / 1024 / 1024 约等于 15GB,远大于内存限制,并且查询的时间复杂度是O(N)

那么再想想有没有其他办法呢?

再次理解题目,题目要求的是判断一个整数是否存在,而不是求一个整数出现了几次的问题,所以我们根本不用关心这个整数是啥,只用判断是否存在即可

一个整数存不存在完全可以用一个二进制位来表示,比如1代表存在,0代表不存在(BitMap)

那么我们如何在内存中维护整数和二进制位之间的关系呢?

可以用数组来存储,数组的索引表示整数,数组存放的值表示是否存在,如下图所示

此时需要占用的内存空间:2^32 / 8 / 1024 / 1024 / 1024 约等于 512MB,符合内存限制的要求,并且查询的时间复杂度为O(1)

#数据人的面试交流地##大数据开发#
全部评论

相关推荐

update:4 月 15 号收到 oc,hr很友善,有点愧疚,已经签约了其他家了。浪费字节面试官和 hr资源了😭==============================3 月 4 日投递国际电商后端开发3 月 5日约面到 3 月 12 号3 月 12日 一面,1.5h,八股,项目,手撕。和面试官对手撕部分探讨了很久,不同的实现方式,还有一个情景题,也是讲了很多,不然估计 1h 结束的。3 月 13 日约二面,约的是 20 号3 月 20 号面试官有事情,改约 25 号3 月 23 号二阳发烧,改约 4 月 3 号4 月 3 号二面,常规八股+项目拷打+手撕4 月 7 号约三面4 月 8 号三面,第一次体验到三面,腾讯是二面就到 hr 了,感觉问的和二面差不多。手撕 3 道,难度是 2 中(dp,归并), 1简单(单词反转)吧。4 月 8 号约 hr 面4 月 10 号 hr面,说这周左右 oc,但到 12 号周五还没动静。总体面起来的话,感觉操作系统八股相对少一些。redis,mysql 会多一些。挺喜欢一面的面试官,互相讨论做法,很有耐心,面试体验很棒。点赞字节的面试流程,每次面试都有专门hr 小姐姐来联系,请假好沟通,二面那个是我请病假,结果小姐姐也刚好在医院看病,让她同事帮我操作的,xs😂想点踩一下美团,二阳请假申请推迟一周,约好新的面试时间后,结果中间被释放简历,还不发邮件提醒,到面试那天白等面试官,打电话才知道情况,体验很糟糕。
点赞 评论 收藏
转发
8 18 评论
分享
牛客网
牛客企业服务