1. 给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？
解析：100G的文件给我们的感觉是太大，我们的电脑内存一般都为4G左右所以不可能一次性把这么多的信息都加载到内存，所以就要进行切分成100份。IP地址是字符串太长，我们可以把它转化为整型%100，这样取模后的值都落在0-99的区间里，所取模后值相同的IP地址都被分配到同一个文件，这时我们就可以采用哈希表统计出每个文件中最多的那个IP地址，最后比较得到100个IP中最大的那个IP就可以了 。
2. 与上题条件相同，如何找到top K的IP？
解析：看到求TOP K个IP就要立马反应到使用堆排序，这里的堆排序应该注意的是要建一个最小堆。堆的设计对于处理top K问题十分方便。首先设置一个大小为K的堆（如果求最大top K,那么用最小堆，如果求最小top K,那么用最大堆），然后扫描数组。并将数组的每个元素与堆的根比较，符合条件的就插入堆中，同时调整堆使之符合堆的特性，扫描完成后，堆中保留的元素就是最终的结果。
3. 给定100亿个整数，设计算法找到只出现一次的整数
解析：整数分为有符号和无符号两种，有符号数的取值为-2147483648~2147483648 是从-21亿到+21亿， 无符号数的范围为0~4294967296是从0到42亿，然而给了我们100亿个整数，要找出只出现一次的整数，所以我们还是要用到哈希表的思想，但我们最好不要定义一个整型数组，因为 42亿 * 4B 约为16G，这么大的数组我们再进行切分的话就太麻烦了，这里我们可以使用BitMap,用一个位来表示一个数存不存在，不存在表示为0，出现一次表示为1，出现一次以上用另一个位表示。这样就可以将数组的大小减为原来的16分之一。还遇到一个问题，就是到底怎么定义这个数组，正数好定义，负数的话我们可以用32位全1（-1）和它取异或取到和正数相同的位置，我们此时定义一个二维数组，一半表示正数一半表示负数，都位于同一行。此时我们使用1G的空间就可以解决这个问题了。
4. 只有500M或者更少的空间的话怎么做？
解析：同样采用切分的思想，不过我觉得这里我们直接可以按数的范围直接切分。要是有500M 内存的话，我们就切一次就可以了，此时如果我们有50%的几率一次就找到这个只出现一次的数，效率可能更高。
5. 给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？
解析：hash分桶，使用bitmap或再次hash。
6. 1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数
解析：这个问题和以上唯一不同这道题是找不超过两次的整数，方法一样。
7. 给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集分别给出精确算法和近似算法!
解析：求两个文件的交集，这种算法我们肯定要用到比较，如果我们把两个文件都均分为100份，拿一个文件里的一份分别与另一个文件里的100份分别比较一次的话效率 就太低了，我们可以借用第1道面试题的思维对它们进行取模，这样我们只要比较取模的为同一值的两个文件比较就可以了，如果相同则标记。使用的是相同的hash函数，相同的会下标一致。
8. 如何扩展BloomFilter使得它支持删除元素的操作？
解析：BloomFilter并不支持删除元素的操作，因为很可能产生哈希冲突（就是由不同的哈希函数算出的位置指向同一个位），这样改变一个位很可能会影响到其他元素的判断。这里我们可以按照和智能指针sharedptr的思想即“引用计数”来解决，我们添加一个count计数器，每当我们在这个位上表示一个元素时就让它count++，每删除一个涉及到这个位表示的元素时就让它count--,这样只当count为0时我们再对这一位置清0，这样就完成了删除的操作。
9. 如何扩展BloomFilter使得它支持计数操作？
解析：这道题思想和上一道题一样。
10. 给上千个文件，每个文件大小为1K—100M。给n个词，设计算法对每个词找到所有包含它的文件，你只有100K内存
解析：我们可以使用布隆过滤器来判断一个文件是否包含这n个单词生成n个布隆过滤器放到外存，我们事先定义好一个包含这n个单词信息的文件info，每当我们在一个文件找到一个对应的单词就将这个文件的信息写入info对应单词的位置。我们只有100K内存，这100K内存我们一部分用来存放布隆过滤器一部分可以存放文件，因为文件最小都为100K，所以我们可以尝试把它切分为50K的小文件，每个文件标志好所属的大文件，这样我们每次读入一个布隆过滤器和一个小文件，如果这个文件有对应的单词则在info中标记所属大文件的信息，如果没有则读入下一个布隆过滤器，把所有布隆过滤器都使用后，再读下一个文件重复上述步骤直至把所有文件都遍历完。
11. 有一个词典，包含N个英文单词，现在任意给一个字符串，设计算法找出包含这个字符串的所有英文单词
解析：
1，使用 strstr（）进行字符串匹配；
2，字典树；
3，倒排索引；
给输入字符串，利⽤用字母建立倒排索引，索引中存储该字母 出现在哪个单词以及在单词中位置；查询时，利用倒排找到所有的单词，并求交集并且位置要连续。
总结
对于此类大数据问题我们一般都是采用哈希切分即模上一个数组的长度将数据分配到一个合理的位置，同时将一个大文件切分为小文件，这样特别方便将其与其他数进行比较例如对IP地址取整后进行哈希切分，或者对内部元素进行操作。使用BloomFilter可以进行判断元素在集合的存在与否。
网友评论