叫板面试官：请不要再问我海量数据题
source link: https://mp.weixin.qq.com/s/TFQPdDDVlUA35BQHS3JjeQ
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
点击上方“蓝字”关注我们
面试官：老鸟
一个大文件，包含5亿个整数，求中位数
应聘者：小鹅
这题不难啊。
排序，找出中间行的数字即可
面试官：老鸟
请审题，是一个大文件。不能装进内存里
应聘者：小鹅
5亿个int也就2GB，什么机器内存这么小？
面试官：老鸟
是2G么？你怎么算的这么快？
应聘者：小鹅
很简单，面试的时候，快速口算内存占用有技巧。我先问一句，你学过英语吗？
面试官：老鸟
废话，当然学过
应聘者：小鹅
和中文数字习惯不同。英文数字在朗读和表示的时候是三位一组的。1,000,000,000 从右向左看，每个逗号前一位分别为千、百万、十亿。忽略GB、MB、KB、B之间的进位是1024，简化理解成1000。那么1GB也就是10亿B。假设你机器上一个int是4字节的，也就是4B，那么5亿个int，也就是 5亿*4B=20亿B=2GB。听明白了。
面试官：老鸟
奥。知道了，我刚从网上找的题目太旧了。哎，不对，跑偏了。那给你100亿个int的文件。共40GB，而且明确告诉你，内存就是装不下。
应聘者：小鹅
仍然是：
排序，找出中间行的即可
面试官：老鸟
不是的，同学，我不是告诉你，装不进内存了么？
应聘者：小鹅
我是说：
sort -n data|awk "NR==5000000000"
面试官：老鸟
？
应聘者：小鹅
Linux的sort、awk以及其他命令处理大文件时，都不是把文件全部加载到内存的，这些命令的实现逻辑是可以换出数据到磁盘，后续自动处理的。
面试官：老鸟
哦。还能这样，妙啊。
应聘者：小鹅
那我考你一个：
100亿个int的大文件，其中有一个数字是不重复的，其余都重复，怎么找出来。
面试官：老鸟
sort -n a|uniq -c|sort -n|head -1
这简单啊。先按照数字排序，然后uniq -c进行聚合，会产生两列，第一列是数字出现次数，第二列是原来的数字。再排一次序，默认就把出现次数为1的那行放首行了。然后head -1就看到了。
应聘者：小鹅
不错嘛，活学活用。
通常情况下， Linux命令 都能搞定了。 不过你要是真的数据更更更大，你上MapReduce，Spark啊。
所以你还有什么要问的吗？
面试官：老鸟
没了。
不对，我才是面试官啊。
咱们继续刚才的问题吧。不用Linux命令，100亿个int的大文件找中位数，你怎么办。
应聘者：小鹅
分桶法（类似鸽巢原理）：
1.int数字范围确定，划分成50个区间， 遍历一遍大文件， 按照数字大小拆分到50个小文件中，每个文件存储1000W个数(每个文件40M)。
2. 遍历一遍小文件，统计每个文件中的数字个数。可以计算出中位数在哪个文件中，以及其中排第几的是中位数。
3. 内存中加载那个文件，直接排序，可以找到中位数。
如果你觉得文件还是可能较大，那么可以再用bitmap来表示数字节省空间
面试官：老鸟
那大文件排序。
不准用sort，请老实作答。
应聘者：小鹅
多路归并排序
归并排序又叫外部排序，顾名思义，细节我就不说了。
面试官：老鸟
大文件取top K。请老实作答。
应聘者：小鹅
堆排序。 求Top K大的数据用小根堆， 求Top K小的数据用大根堆。
面试官：老鸟
好吧，最后用你给我出的题考你一下：
100亿个int的大文件，其中有一个数字是不重复的，其余都是重复的，怎么找出来。
应聘者：小鹅
使用2-bitmap。00表示为出现，01表示出现1次，10表示出现2次或多次，11无意义。
面试官：老鸟
好了，你还有啥问题吗？
应聘者：小鹅
弱弱地问下，我能把面经发网上吗？
面试官：老鸟
把咱俩开头那几段对话掐掉的话，可以
应聘者：小鹅
那可不一定
面试官：老鸟
……你要发哪，我盯着点，别乱写
应聘者：小鹅
那你扫描这个二维码关注我吧！
扫码关注更多精彩
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK