海量数据处理面试题
海量数据处理思路分析题
1.给一个超过100G大小的log file，log中存着ip地址，设计算法找到出现次数最多的ip地址?
解决方法：哈希切割topK。将100G的大文件分成1000份，根据同一个哈希函数HashFunc将ip映射到向对应的文件(每个文件的大小可以在内存中处理)中，相同的ip一定会被放在同一个文件中。然后处理每一个文件，找出出现次数最多的ip,每个文件中最大的value对应的key既为出现次数最多的ip。最后在比较1000个文件中的MAX,确定最终的出现次数最多的ip。如果需要找出topk，则需要以每个小文件中出现次数最多的ip建成一个最小堆，从而确定topK
注意：
为什么要分成1000份，而不是100份呢？因为如果分成100份，哈希切割不均匀，有的文件很小，但是有的文件依然很大，依旧放不到内存去处理它们。
2.给定100亿整数，设计算法找到只出现一次的整数？
100亿整数需要多少内存呢？
一个整数4个字节，100亿个整数400亿个字节，1G是10^9个字节，那么400亿个字节就是大约40G的内存，我们根本没有这么大的内存，所以只能另想办法了。
解决方法一：
- 1.将100亿个整数切分成100份，每份大约500MB
- 2.将每一份加载到内存中放在一个哈希表中，通过哈希表找出只出现一次的数
- 3.将100份中所有只出现一次的数合并在一起
解决方法二：借助位图解决。在前边的位图实现中，只有两个状态0(不存在)、1（存在）。要解决找出只出现一次的数字，我们可以增加状态，用两个比特位作为哈希映射的地址，我们可以让00(不存在)、01(只出现一次)、11(出现两次)、10(出现两次以上)。
3. 给两个文件，分别有100亿整数，我们只有1G内存，如何找到两个文件的交集？
解决方法一：
- 1.将其中的一个文件切分成100份
- 2.将每一份加载到内存中
- 3.用第二个文件中的数据到每一份中去查找
时间复杂度O(100n*n),既O(n^2)
解决方法二：哈希切割。
- 1.两个文件用相同的哈希函数映射到各自的编号文件中
- 2.如果两个数相同，他们一定会在编号相同的两个文件
- 3.对编号相同的两个文件求交集(可以放在内存中)
时间复杂度O(n)
解决方法三：位图
- 1.将一个文件中的整数映射到位图中。
- 2.用第二个文件中的数到位图中查找
- 3.存在，则是交集，不存在，不是交集里的数
时间复杂度O(n)
4.1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数？
解决方法：借助位图解决。要解决找出只出现次数不超过2次的数字，我们可以增加位图状态，用两个比特位作为哈希映射的地址，我们可以让00(不存在)、01(只出现一次)、11(出现两次)、10(出现两次以上)。
- 建两个文件，设置一个值key,大于这个key的数进入第一个文件；小于key值的数进入第二个文件（设置的key尽量使得这两个文件中数的数目差不多）
- 将第一个文件中的所有数的状态存到一个位图中
（第一个文件以位图存储大约需要9540多MB的内存），然后通过查找，找出文件一中出现次数不超过两次的所有整数 - 第二个文件和第一个文件方法一样
- 合并两个文件中所有找到的数
5.给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法？
精确算法：哈希切分。和第三题哈希切割的方法是一样的，只需要将HashFunc变为处理字符串的即可。(query查询)
近似算法：布隆过滤器。将一个文件的query放在布隆过滤器中，然后在用另一个文件中的query去查布隆过滤器中存不存在。布隆过滤器查找存在是不精确的。
6.如何扩展BloomFilter使得它支持删除元素的操作？
解决方法：因为一个布隆过滤器的key对应多个位，冲突的概率比较大，所以不支持删除，因为删除有可能影响到其他元素。如果要对其元素进行删除，就不得不对每一个位进行引用计数。将BloomFilter中的每一位扩展为一个计数器，记录有多少个hash函数映射到这一位；删除的时候，只有当引用计数变为0时，才真正将该位置为0否则减1即可。
7.如何扩展BloomFilter使得它支持引用计数操作？
解决方法：将BloomFilter中的每一位扩展为一个计数器，每个输入元素都要把对应位置加1，从而支持计数操作。但是有一个问题，1个比特位只能是两个状态0和1，我们只能把位图扩大成1字节或者更多，1个字节仅仅能存放计数256，但代价依旧是浪费内存。