问题一：
输入：给定一个文件，里面最多含有n个不重复的正整数（也就是说可能含有少于n个不重复正整数），且其中每个数都小于等于n，n=10^7。
输出：得到按从小到大升序排列的包含所有输入的整数的列表。
条件：最多有大约1MB的内存空间可用，但磁盘空间足够。且要求运行时间在5分钟以下，10秒为最佳结果。
10^7 = 1000,0000 = 10,000,000
一个数据=1B，那么大约为10M
你可能会想到把磁盘文件进行归并排序，但题目要求你只有1MB的内存空间可用，所以，归并排序这个方法不行。
由于要求的可用内存为1MB，那么每次可以在内存中对250K的数据进行排序，然后将有序的数写入硬盘。
那么10M的数据需要循环40次，最终产生40个有序的文件。
个人理解：
１． 按个数１０００个，文件内遍历每个数字做ｍｏｄ/1000操作，把数据分散到１０００个文件中。每个小文件大约４０ＫＢ大小。
２． １０００个小文件，分别导入内存做快排或者任何nlogn排序
３． 内存中创建
//自定义从小到大排序
std::priority_queue < int, vector<int>, greater<int> > pq_int;
每次分别从１０００个文件中读取一个数值（这个数值是每个文件中最小的一个），ｐｕｓｈ到优先级队列内，写入队列后，优先级队列会自动排序，内部机制是堆排序，然后打印队列内１０００个数值，即为结果（相当于归并排序）
接着，继续从１０００个小文件内继续读取后面的数值，写入优先级队列，排序输出。
４． 基本思想 拆分大文件，各个击破小文件，归并处理结果。
将每个文件最开始的数读入(由于有序，所以为该文件最小数)，存放在一个大小为40的first_data数组中；
选择first_data数组中最小的数min_data，及其对应的文件索引index；
将first_data数组中最小的数写入文件result，然后更新数组first_data(根据index读取该文件下一个数代替min_data)；
判断是否所有数据都读取完毕，否则返回2。
第一步、Memory Sort。
第二步、Merge Sort。
问题二：给定a、b两个文件，各存放50亿个url，每个url各占用64字节，内存限制是4G，如何找出a、b文件共同的url？
50亿 = 5G * 64 Byte = 320G 两个文件总共640GB内存不可能内存中处理
思路一：此处引入布隆过滤布隆过滤器(Bloom Filter)详解
简单来说，bloom算法类似一个hash set，用来判断某个元素（key）是否在某个集合中。
和一般的hash set不同的是，这个算法无需存储key的值，对于每个key，只需要k个比特位，每个存储一个标志，用来判断key是否在集合中。
算法：
1. 首先需要k个hash函数，每个函数可以把key散列成为1个整数
2. 初始化时，需要一个长度为n比特的数组，每个比特位初始化为0
3. 某个key加入集合时，用k个hash函数计算出k个散列值，并把数组中对应的比特位置为1
4. 判断某个key是否在集合时，用k个hash函数计算出k个散列值，并查询数组中对应的比特位，如果所有的比特位都是1，认为在集合中。
优点：不需要存储key，节省空间
缺点：
1. 算法判断key在集合中时，有一定的概率key其实不在集合中
2. 无法删除
典型的应用场景：
场景一 前端页面缓存系统：先查询某个页面在本地是否存在，如果存在就直接返回，如果不存在，就从后端获取。但是当频繁从缓存系统查询一个页面时，缓存系统将会频繁请求后端，把压力导入后端。
这时只要增加一个bloom filter服务，后端插入一个key时，在这个服务中设置一次， 需要查询后端时，先判断key在后端是否存在，这样就能避免后端压力。
场景二 在日常生活中，包括在设计计算机软件时，我们经常要判断一个元素是否在一个集合中。比如在字处理软件中，需要检查一个英语单词是否拼写正确（也就是要判断 它是否在已知的字典中）；
场景三 在FBI，嫌疑人名字是否已经在嫌疑名单内；
场景四 网络爬虫系统，判断一个网址是否被访问过等等。最直接的方法就是将集合中全部的元素存在计算机中，遇到一个新 元素时，将它和集合中的元素直接比较即可。
当集合比较小时，问题不显著，但当集合巨大时，哈希表存储效率低的问题就显现出来 了。比如说，一个象 Yahoo,Hotmail 和 Gmai 那样的email提供商，过滤垃圾邮件 一个办法就是记录下那些发垃圾邮件的 email 地址。发送者不停地注册新地址，全世界少说也有几十亿个发垃圾邮件地址，将他们都存起来则需要大量存储空间。
如果用哈希表，每存储一亿 个 email 地址（成本太高）， 就需要 1.6GB 的内存（用哈希表实现的具体办法是将每一个 email 地址对应成一个八字节的信息指纹（详见：googlechinablog.com/2006/08/blog-post.html）， 然后将这些信息指纹存入哈希表，由于哈希表的存储效率一般只有 50%，因此一个 email 地址需要占用十六个字节。一亿个地址大约要 1.6GB， 即十六亿字节的内存）。因此存贮几十亿个邮件地址可能需要上百 GB 的内存。除非是超级计算机，一般服务器是无法存储的［2］
优点：布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数。另外, Hash 函数相互之间没有关系，方便由硬件并行实现。布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势。
缺点：布隆过滤器的缺点和优点一样明显。误算率（False Positive）是其中之一。随着存入的元素数量增加，误算率随之增加。但是如果元素数量太少，则使用散列表足矣。
采用Bloom filter，假设布隆过滤器的错误率为0.01，则位数组大小m约为输入元素个数n的13倍，此时需要的哈希函数k约为8个。元素个数：n = 5G
位数组大小：m = 5G * 13 = 65G = 650亿 即需要650亿个bit位才能达到错误率0.01
而我们拥有的内存可容纳bit位个数：4G * 8bit = 32G bit = 320亿，按此实现错误率大于0.01。
思路二：
分别扫描A，B两个文件，根据hash(url)%k(k为正整数，比如k = 1000，那么每个小文件只占用300M，内存完全可以放得下)将url划分到不同的k个文件中，比如a0，a1,....a999; b0，b1，...b999；
这样处理后相同的url肯定在对应的小文件中（a0 vs b0,a1 vs b1,...a999 vs b999）因为相同的url%1000的值肯定相同，不对应的小文件不可能有相同的url；
然后我们只要求出1000对小文件中相同的url即可。比如对于a0 vs b0，我们可以遍历a0，将其中的url存放到hash_map中，然后遍历b0，如果b0中的某个url在hash_map中，则说明此url在a和b中同时存在，保存下来即可。
问题三：
