摘要：这几天小秋去面试了，不过最近小秋学习了不少和位算法相关文章，例如面试现场如何判断一个数是否在亿个整数中算法技巧位运算装逼指南对于算法题还是有点信心的，，，，于是，发现了如下对话。
这几天小秋去面试了，不过最近小秋学习了不少和位算法相关文章，例如
【面试现场】如何判断一个数是否在40亿个整数中？
【算法技巧】位运算装逼指南
对于算法题还是有点信心的，，，，于是，发现了如下对话。
20亿级别面试官：如果我给你 2GB 的内存，并且给你 20 亿个 int 型整数，让你来找出次数出现最多的数，你会怎么做？
小秋：（嗯？怎么感觉和之前的那道判断一个数是否出现在这 40 亿个整数中有点一样？可是，如果还是采用 bitmap 算法的话，好像无法统计一个数出现的次数，只能判断一个数是否存在），我可以采用哈希表来统计，把这个数作为 key，把这个数出现的次数作为 value，之后我再遍历哈希表哪个数出现最多的次数最多就可以了。
面试官：你可以算下你这个方法需要花费多少内存吗？
小秋：key 和 value 都是 int 型整数，一个 int 型占用 4B 的内存，所以哈希表的一条记录需要占用 8B，最坏的情况下，这 20 亿个数都是不同的数，大概会占用 16GB 的内存。
面试官:你的分析是对的，然而我给你的只有 2GB 内存。
小秋：（感觉这道题有点相似，不过不知为啥，没啥思路，这下凉凉），目前没有更好的方法。
面试官：按照你那个方法的话，最多只能记录大概 2 亿多条不同的记录，2 亿多条不同的记录，大概是 1.6GB 的内存。
小秋：（嗯？面试官说这话是在提示我？）我有点思路了，我可以把这 20 亿个数存放在不同的文件，然后再来筛选。
面试题：可以具体说说吗？
小秋：刚才你说，我的那个方法，最多只能记录大概 2 亿多条的不同记录，那么我可以把这 20 亿个数映射到不同的文件中去，例如，数值在 0 至 2亿之间的存放在文件1中，数值在2亿至4亿之间的存放在文件2中....，由于 int 型整数大概有 42 亿个不同的数，所以我可以把他们映射到 21 个文件中去，如图
显然，相同的数一定会在同一个文件中，我们这个时候就可以用我的那个方法，统计每个文件中出现次数最多的数，然后再从这些数中再次选出最多的数，就可以了。
面试官：嗯，这个方法确实不错，不过，如果我给的这 20 亿个数数值比较集中的话，例如都处于 1~20000000 之间，那么你都会把他们全部映射到同一个文件中，你有优化思路吗？
小秋：那我可以先把每个数先做哈希函数映射，根据哈希函数得到的哈希值，再把他们存放到对应的文件中，如果哈希函数设计到好的话，那么这些数就会分布的比较平均。（关于哈希函数的设计，我就不说了，我这只是提供一种思路）
40亿级别面试官：那如果我把 20 亿个数加到 40 亿个数呢？
小秋：（这还不简单，映射到42个文件呗）那我可以加大文件的数量啊。
面试官：那如果我给的这 40 亿个数中数值都是一样的，那么你的哈希表中，某个 key 的 value 存放的数值就会是 40 亿，然而 int 的最大数值是 21 亿左右，那么就会出现溢出，你该怎么办？
小秋：（那我把 int 改为 long 不就得了，虽然会占用更多的内存，那我可以把文件分多几份呗，不过，这应该不是面试官想要的答案），我可以把 value 初始值赋值为 负21亿，这样，如果 value 的数值是 21 亿的话，就代表某个 key 出现了 42 亿次了。
80亿级别这里说明下，文件还是 21 个就够了，因为 21 个文件就可以把每个文件的数值种类控制在 2亿种了，也就是说，哈希表存放的记录还是不会超过 2 亿中。
面试官：反应挺快哈，那我如果把 40 亿增加到 80 亿呢？
小秋：（我靠，这变本加厉啊）.........我知道了，我可以一边遍历一遍判断啊，如果我在统计的过程中，发现某个 key 出现的次数超过了 40 亿次，那么，就不可能再有另外一个 key 出现的次数比它多了，那我直接把这个 key 返回就搞定了。
面试官：行，此次面试到此结束，回去等通知吧。
总结今天这篇文章主要讲了大数据处理相关的一些问题，后面可能还会给大家找一些类似，但处理方式不同的题勒，大家如果觉得不错，不妨：
1、点赞，让更多的人也能看到这篇内容（收藏不点赞，都是耍流氓 -_-）
2、关注我，让我们成为长期关系
3、关注公众号「苦逼的码农」，主要写算法、计算机基础之类的文章，里面已有100多篇原创文章，我也分享了很多视频、书籍的资源，以及开发工具，欢迎各位的关注，第一时间阅读我的文章。。
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/7872.html
摘要：答案使用，申请一个长度为类型的，每个位置只表示或，该数组占用空间约。遍历亿个数，当前数为，落在区间，对应。 过滤100亿黑名单 题目 假设有100亿个URL的黑名单，每个URL最多占用64B，设计一个过滤系统，判断某条URL是否在黑名单里。 要求 不高于万分之一的判断失误率；额外内存不超过30GB 答案 100亿个64B的URL需要640GB的内存，显然直接存哈希表不合理。考虑布隆过滤...
摘要：面试，是跳槽后第一个需要面对的问题而且不同公司面试的着重点不同但是却有一个共同点基础是必考的。对自动灾难恢复有要求的表。 貌似这一点适应的行业最广，但是我可以很肯定的说：当你从事Java一年后，重新找工作时，才会真实的感受到这句话。 工作第一年，往往是什么都充满新鲜感，什么都学习，冲劲十足的一年；WEB行业知识更新特别快，今天一个框架的新版本，明天又是另一个新框架，有时往往根据项目的需...
摘要：面试，是跳槽后第一个需要面对的问题而且不同公司面试的着重点不同但是却有一个共同点基础是必考的。对自动灾难恢复有要求的表。 貌似这一点适应的行业最广，但是我可以很肯定的说：当你从事Java一年后，重新找工作时，才会真实的感受到这句话。 工作第一年，往往是什么都充满新鲜感，什么都学习，冲劲十足的一年；WEB行业知识更新特别快，今天一个框架的新版本，明天又是另一个新框架，有时往往根据项目的需...
阅读 1638·2023-04-26 01:02
阅读 4682·2021-11-24 09:39
阅读 1765·2019-08-30 15:44
阅读 2798·2019-08-30 11:10
阅读 1766·2019-08-30 10:49
阅读 960·2019-08-29 17:06
阅读 580·2019-08-29 16:15
阅读 880·2019-08-29 15:17
