大量数据面试题目

判读40亿数字中是否有某个数字
使用的bitmap算法。大体思路是：一个字节（Byte） 在计算机中占8位（bit）,每个位（bit）可以表示一个数字，1表示含有，0表示不含有。1个32位系统的int类型可以存储2的32次方个bit位,大约是42亿多点。这样40亿需要 40/8=5亿字节，1M =1024KB*1024=1042576Byte，故大概需要512M左右大小即可。空间复杂度是O(n)+O(1);

海量数据排序
100亿个数字排序，100亿个 int 型数字放在文件里面大概有 37.2GB，内存一次装不下了，需要拆分成小的文件一个一个来处理，最终在合并成一个排好序的大文件。

实现思路
1.把这个37GB的大文件直接平均分成1000份
2.拆分完了之后，得到一些几十MB的小文件，那么就可以放进内存里排序了，可以用快速排序，归并排序，堆排序等等
3.1000个小文件内部排好序之后，进行k路归并排序。首先遍历1000个文件，每个文件里面取第一个数字，组成 (数字, 文件号) 这样的组合加入到堆里（假设是从小到大排序，用小顶堆），遍历完后堆里有1000个 (数字，文件号) 这样的元素
然后不断从堆顶拿元素出来，每拿出一个元素，把它的文件号读取出来，然后去对应的文件里，加一个元素进入堆，直到那个文件被读取完。拿出来的元素当然追加到最终结果