使用2-bitmap。00表示为出现,01表示出现1次,10表示出现2次或多次,11无意义。
叫板面试官:请不要再问我海量数据题!
面试官:老鸟
一个大文件,包含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的大文件,其中有一个数字是不重复的,其余都是重复的,怎么找出来。
应聘者:小鹅
面试官:老鸟
好了,你还有啥问题吗?
应聘者:小鹅
弱弱地问下,我能把面经发网上吗?
面试官:老鸟
把咱俩开头那几段对话掐掉的话,可以
应聘者:小鹅
那可不一定
面试官:老鸟
……你要发哪,我盯着点,别乱写
应聘者:小鹅
那你扫描这个二维码关注我吧!