面试真题：经典海量数据处理题最详解析（上）

本文正在参与【[ 面霸养成记 ] 】 征文活动，一起来聊聊校招的那些事吧，牛客周边和百元京东卡等你来领~

前言

大家好，我是鬼仔。之前鬼仔整理了有关智力题的系列面试题，感兴趣的同学们可以复习下：

• 面试真题：经典智力题最详汇总（上）
• 面试真题：经典智力题最详汇总（中）
• 面试真题：经典智力题最详汇总（下）

除了智力题，技术岗同学面试的时候常常会遇到另一种特殊题型：海量数据处理题。

为了帮助同学们在面试中拿下海量数据处理题，鬼仔特意准备了该系列，不仅分析解读经典面试真题，让同学们直面感受该类题型的难度，以及对应的解决方案，而且还会对该类题型进行总结升华，题目是无限的，但方法是有限的，以不变应万变，有形化无形，才能真正拿下海量数据处理题！大家记得关注鬼仔哦，这样才能第一时间收到更新信息～

此时我们常用的方法就是Hash映射、分而治之，将大数据切分为多块小数据，逐个击破，这其实也是Map Reduce的思想。除了空间复杂度的优化，我们还可以通过巧妙的数据结构和算法来优化时间复杂度，比如HashMap、BitMap、前缀树等数据结构和堆排序、topk等算法。

公众号：码农鬼仔，专注分享算法知识｜面试技巧｜职场感悟｜内推信息。

一、海量日志数据，提取出某日访问百度次数最多的IP。

假设内存无穷大，我们可以用常规的HashMap(ip，value)来统计ip出现的频率，统计完后利用排序算法得到次数最多的IP，这里的排序算法一般是堆排序或快速排序。

但考虑实际情况，我们的内存是有限的，所以无法将海量日志数据一次性塞进内存里，那应该如何处理呢？很简单，分而治之！即将这些IP数据通过Hash映射算法划分为多个小文件，比如模1000，把整个大文件映射为1000个小文件，再找出每个小文件中出现频率最大的IP，最后在这1000个最大的IP中，找出那个频率最大的IP，即为所求（是不是很像Map Reduce的思想？）。

这里鬼仔再多说一句：Hash取模是一种等价映射算法，不会存在同一个元素分散到不同小文件中的情况，这保证了我们分别在小文件统计IP出现频率的正确性。我们对IP进行模1000的时候，相同的IP在Hash取模后，只可能落在同一个小文件中，不可能被分散的。因为如果两个IP相等，那么经过Hash(IP)之后的哈希值是相同的，将此哈希值取模（如模1000），必定仍然相等。

总结一下，该类题型的解决方法分三步走：

1. 分而治之、hash映射；
2. HashMap（或前缀树）统计频率；
3. 应用排序算法（堆排序或快速排序）。

如果将题目改为：海量日志数据，提取出某日访问百度次数最多的前N个IP。牛油们知道怎么处理吗？把答案写在评论区吧～

二、搜索引擎会通过日志文件把用户每次检索使用的所有查询串都记录下来，每个查询长度不超过 255 字节。假设目前有一千万个记录（这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门），请你统计最热门的10个查询串，要求使用的内存不能超过1G。

我们首先分析题意：一千万个记录，除去重复后，实际上只有300万个不同的记录，每个记录假定为最大长度255Byte，则最多占用内存为：3M*1K/4=0.75G<1G，完全可以将所以查询记录存放在内存中进行处理。相较于第一道题目，这题还更简单了，直接HashMap（或前缀树）+堆排序即可。

具体做法如下：

1. 遍历一遍左右的Query串，利用HashMap（或前缀树）统计频率，时间复杂度为O(N)，N=1000万；
2. 建立并维护一个大小为10的最小堆，然后遍历300万Query的频率，分别和根元素（最小值）进行对比，最后找到Top K，时间复杂度为N‘logK，N‘=300万，K=10。

三、有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。

经过前两道题的训练，第三道题相信大家已经游刃有余了，这类题型都有相同的特点：文件size很大，内存有限，解决方法还是经典三步走：分而治之 + hash统计 + 堆/快速排序。

具体做法如下：

1. 分而治之、hash映射：遍历一遍文件，对于每个词x，取hash(x)并模5000，这样可以将文件里的所有词分别存到5000个小文件中，如果哈希函数设计得合理的话，每个文件大概是200k左右。就算其中有些文件超过了1M大小，还可以按照同样的方法继续往下分，直到分解得到的小文件的大小都不超过1M；
2. HashMap（或前缀树）统计频率：对于每个小文件，利用HashMap（或前缀树）统计词频；
3. 堆排序：构建最小堆，堆的大小为100，找到频率最高的100个词。

四、给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？

每个url是64字节，50亿*64=5G×64=320G，内存限制为4G，所以不能直接放入内存中。怎么办？分而治之！

具体做法如下：

1. 遍历文件a中的url，对url进行hash(url)%1000，将50亿的url分到1000个文件中存储（a0，a1，a2.......），每个文件大约300多M，对文件b进行同样的操作，因为hash函数相同，所以相同的url必然会落到对应的文件中，比如文件a中的url1与文件b中的url2相同，那么它们经过hash(url)%1000也是相同的。即url1落入第n个文件中，url2也会落入到第n个文件中。
2. 遍历a0中的url，存入HashSet中，同时遍历b0中的url，查看是否在HashSet中存在，如果存在则保存到单独的文件中。然后以此遍历剩余的小文件即可。

小结

除了上述的这些题型，海量数据处理题还有其他类型，鬼仔过两天会继续更新该系列，相信同学们跟着鬼仔学完这个系列，以后面试中再也不会怕遇到海量数据处理题了！

希望大家能够给鬼仔点个收藏+关注，你的支持是鬼仔更新的动力！后面鬼仔会持续分享面试经验 & 算法相关的专业知识，点关注、不迷路～