海量数据处理

1. 给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中

这里的数据要求40亿个不重复的无符号整数，使用位图用一个位来表示一个整数，将所有的数据映射到位图上，当进行查询时，只要位图的对应位置为1，则说明该数据在这40亿个数据中

2. 给定100亿个整数，设计算法找到只出现一次的整数？

方法1：使用特定的位图，每个映射的数有对应的两个bit位进行表示映射的状态

方法2：使用两个位图，同样的两个位图对应的映射的数的位置共同表示映射状态

注：没有映射00，一次映射01，一次以上映射10

3. 给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集

方法1：将文件1的整数全部映射到位图中，接着从文件2中读取数据，并在位图中查询该数据，如果数据存在，则说明该数据是交集之一

方法2：使用两个位图，对两个文件进行分别遍历文件读取数据映射到位图上，然后对位图进行遍历求交集，同一个位置都为1，那么则为交集

4. 1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数

方法1：使用特定的位图，每个映射的数有对应的两个bit位进行表示映射的状态

方法2：使用两个位图，同样的两个位图对应的映射的数的位置共同表示映射状态

注：没有映射00，一次映射01，两次映射10，三次以上映射11

5. 给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法

注：query一般为URL中的查询字符串或者SQL中的查询语句，假设每个query30个字节，那么100亿个query也得300G的内存才能装下

近似算法：使用布隆过滤器来进行处理，对一个文件将数据全部进行哈希映射，再对另一个文件中的数据进行查询，但是可能存在哈希冲突，导致造成误判，所以当一个数据不存在于布隆过滤器中，则它必定不存在，但是如果一个数据存在于布隆过滤器中，它也不一定存在

精确算法：如果要精确的进行查找，那就必须得将数据放入内存中，但是由于数据过大我们可以将数据存入到服务器中，先使用布隆过滤器进行处理，如果对应映射不存在，那么久一定不是交集，如果对应映射存在那么就到服务器中进行二次查询

平均切割： 平均切割不是一个很好的方法，但是它确实是我们很容易就能思考到的方法，我们将两个文件中的数据平均切分为M份(能放入内存)，分别存储到一个set中，然后以此将数据进行比较，这种方法就需要以此对所有的数据进行比对，效率会比较低

哈希切割： 创建多个临时文件，并进行标号，读取文件数据使用字符串哈希算法进行哈希映射，映射到对应的文件并将数据存进去，对两个文件的数据都采用这样的做法进行切分，由于我们使用的是同一种字符串哈希算法，所以相同的字符串必定会被映射到同一个编号下的文件中，所以我们只需要依次对编号相同的Ai和Bi文件中使用set寻找交集即可（如果有些文件切分之后依然过大，可以继续对其进行切分）

6. 给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？ 与上题条件相同，如何找到top K的IP？如何直接用Linux系统命令实现？

使用哈希切割的方式来解决文件分片的问题，相同的IP地址必定会被映射到同一个文件中，所以我们依次读取文件，使用Map进行次数统计即可之后再进行排序即可

Linux的命令：sort log_file | uniq -c | sort -nr | head -k

说明：首先使用sort log_file来将数据进行一个排序，使得相同的IP地址全部靠在一起。接着使用uniq - c进行去重，并将重复的次数显示在每列的旁边，通过这个次数来使用sort -nr进行降序排序，使得出现次数最的IP地址在前面，然后使用head -k 获取前k个IP地址即可

7. 100w个数中找出最大的100个数

由于100w个数据并不算多，可以存放进内存中，所以可以考虑以下解法

方法1：采用快排中的partition划分思想，即单趟划分后，枢轴s前面的数据都比他大，后面的数据都比他小，此时我们选取其中较大的那一部分，继续划分。当划分后前端的数据刚好等于100后划分结束，对前端数据进行排序即可得到结果。如果前端数据不足100，则从后端数据进行排序后取出不足的那部分补上，再进行排序即可。O(100w*100)

方法2：局部淘汰法，使用插入排序来完成，首先取出前100个数据进行排序，然后依次遍历后面的数据，如果数据大于最小值，则将最小值删除，然后按照插入排序的思路将数据插入进去O(100w*100)

方法3：局部淘汰法，使用一个大小为100的小堆来完成，维护一个小堆，当数据比堆顶也就是最小值大的时候，用新数据替换掉堆顶，然后调整堆的结构。遍历完所有数据后就可以得到前100的数据。O(100w*lg100)

8. 海量数据分布在100台电脑中，想个办法高效统计出这批数据的TOP10

对于每一个电脑，都构建一个大小为10的堆(选大的构建小堆，选小的构建大堆)，选出当前电脑的TOP10，接着将所有电脑的数据汇总起来，共1000个数据，继续用堆从其中选出TOP10

9. 给上千个文件，每个文件大小为 1K—100M。给 n 个词，设计算法对每个词找到所有包含它的文件，你只有 100K 内存

使用倒排索引来解决，即建立起单词——文件的映射，只需要遍历所有文章，如果文章中出现过查询词，则将文件号追加在对应词的倒排拉链中即可，如果100M的文件放不下内存中，就对数据进行切割后处理即可