叫板面试官：请不要再问我海量数据题！

面试官：老鸟

一个大文件，包含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的大文件，其中有一个数字是不重复的，其余都是重复的，怎么找出来。

应聘者：小鹅

面试官：老鸟

好了，你还有啥问题吗？

应聘者：小鹅

面试官：老鸟

把咱俩开头那几段对话掐掉的话，可以

应聘者：小鹅

面试官：老鸟

……你要发哪，我盯着点，别乱写

应聘者：小鹅