首先让我们明确一下内存之间的换算：
1> 1Byte=8bit
2>1KB=1024Byte=1024*8 bit
3>1MB=1024KB=1024*1024Byte=1024*1024*8bit
4>1G=1024MB=1024*1024KB=1024*1024*1024Byte(大约一亿个字节)=1024*1024*1024*8bit
1）给一个超过100G大小的log file,log中存在着IP地址，设计算法找到出现次数最多的IP地址？
解答：100G大小的文件，加载到内存中是放不下的，所以为们要进行哈希切分，通过散列函数，相同的IP将映射到同一个文件中，然后统计出文件中出现次数最多的IP的次数，再将所有文件中统计出的IP的次数进行比较，找到出现次数最多的IP.（特殊情况，一个文件中IP出现的次数特别多，仍然加载不到内存中，我们再将这个进行切分，统计出IP的次数）
2）与上题条件一样，如何找到top K的IP？
解答：首先我们有每个文件中IP出现的次数，取K个出现的次数，建立小堆，其余的数依次跟小堆的第一个数进行比较，比小堆的第一个数大就将他们交换，调整小堆，直到后续所有数都比较完，找到其中出现次数最多的前K个，每个文件的前K个找到之后，汇总这些文件，继续建立小堆，找到最多的前K个IP
3）给定100亿个整数，设计算法找到只出现一次的整数。
解答：100亿个整数，大约存储下来要40G的空间，这是不现实的，我们可以这样做：
1>将100亿个整数分成100份，这样就只需要400M的内存，将每个数加载到哈希表中，就可以知道那个数据只出现了一次。
2>100亿个整数其实也都在是42亿9千万数字之中，利用位图的扩展，用2个位表示数字出现的次数，00表示没有出现过，01表示出现过一次，10表示出现过多次，这样内存需要1G（负数当做无符号数处理）
3>整数有32位，按照第一位是0或者是1将所有书分为2组，接着看第二位是0还是1，将数据分为4组，以此类推，直到比较完32个位之后，在所有的文件中看那个文件只有一个数。
4）给两个文件，分别有100亿个整数，我们只有1G内存，如何找两个文件的交集？
解答：
1>将一个文件切分成100份，分别加载到内存中，用另外一个文件中的数据与其进行比较，时间复杂度为O(N*N)
2>利用哈希切分,对其中一个文件中的数据实行散列函数，这样相同的数字会进入同一个文件，并对这些文件进行编号，同样的对另外一个文件使用相同的散列函数，同时也对产生的文件进行编号，这样下来我们只需要比较相同编号的文件即可，时间复杂度为O（N）
3>将一个文件中的内容全部映射到位图中去，在用另一个文件中的数据去位图中寻找，需要500M空间
5）1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数。
解答：位图的扩展，同题3）
6）给两个文件，分别有100亿个query,我们只有1G内存，如何找到两个文件的交集？分别给出精确算法和近似算法。
解答：
精确算法：
利用哈希切分，如题4）方法二，要将query转换成整型
近似算法：
利用BloomFilter，将文件一的内容映射到位图的对应位中，用文件二的内容去位图中查找
7）如何扩展BloomFilter使得它支持计数的操作？如何扩展BloomFilter使得它支持删除元素的操作？
解答：删除操作要用到引用计数，不用一个位表示一个数据，而是用一个size_t表示一个数据。
8）1个文件有100亿个整数，1G内存，设计算法找到第一个没有出现的整数。
解答：位图解决，将所有数字映射到位图中的每一位，从第一位开始遍历位图，第一个为0的位置所对应的数字，就是没有出现过的，用了500M内存
9）给上千个文件，每个文件大小为1K-100M，给n个词，设计算法对每个词找到所有包含他的文件，你只有100k内存。
解答：用布隆过滤器来解决，有上千个文件就要有上千个布隆过滤器，将文件的内容映射到布隆过滤器中，从n个词中拿出一个，与布隆过滤器中的内容比较，如果此单词存在，就返回此布隆过滤器所对应的文件，否则继续对比下一个文件，直到所有单词都被查找完之后结束。
10）有一个词典，包含N个英文单词，现在任意给一个字符串，设计算法找出包含这个字符串的所有英文单词。
解答：我们对于这种问题可以用字典树来进行解决。字典树又称：单词查找树，这种树形结构是哈希树的一种变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来节约存储空间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。
首先要把这N个单词建立一颗字典树，再用给定的单词去这棵树中进行查找，找到就记录想用的英语单词，没有找到的话那么这棵树中就不包含这个单词。在这颗树比较深的情况下，就会比较浪费内存，可以用哈希表把这棵树n层以后的数据存放到哈希表中去，这样就会节省内存空间。