Skip to content

Latest commit

 

History

History
executable file
·
65 lines (30 loc) · 4.72 KB

只用2GB内存从20亿,40亿,80亿个整数中找到出现次数最多的数.md

File metadata and controls

executable file
·
65 lines (30 loc) · 4.72 KB

这几天小秋去面试了,不过最近小秋学习了不少和位算法相关文章,对于算法题还是有点信心的,,,,于是,发现了如下对话。

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 亿次了。

这里说明下,文件还是 21 个就够了,因为 21 个文件就可以把每个文件的数值种类控制在 2亿种了,也就是说,哈希表存放的记录还是不会超过 2 亿中。

80亿级别

面试官:反应挺快哈,那我如果把 40 亿增加到 80 亿呢?

小秋:(我靠,这变本加厉啊).........我知道了,我可以一边遍历一遍判断啊,如果我在统计的过程中,发现某个 key 出现的次数超过了 40 亿次,那么,就不可能再有另外一个 key 出现的次数比它多了,那我直接把这个 key 返回就搞定了。

面试官:行,此次面试到此结束,回去等通知吧。

总结

今天这篇文章主要讲了大数据处理相关的一些问题,后面可能还会给大家找一些类似,但处理方式不同的题勒.

学习更多算法 + 计算机基础知识,欢迎关注我的微信公众号,每天准时推送技术干货

在这里插入图片描述