大数据培训算法面试题分享

​

 01 如何从海量数据中找出最高频词

题目描述：

有一个 GB 大小的文件，文件里面每一行是一个英文单词，每个单词的大小不超过 16 个字节，内存限制是 1MB。请设计一个算法思路，返回单词词频数最高的 100 个单词（Top100）。

题目解析：

题目中文件的大小为 1GB，由于内存大小的限制，我们无法直接将这个大文件的所有单词一次性读入内存中。因此我们需要采用分治法，将一个大文件分割成若干个小文件，并且每个小文件的大小不超过 1MB，从而能将每个小文件分别加载到内存中进行处理。然后使用 HashMap 分别统计出每个小文件的单词词频数，并获取每个小文件词频最高的 100 个单词。最后使用小顶堆统计出所有单词中出现词频最高的 100 个单词。

实现方式：分治法

步骤 1

首先遍历这个大文件，对文件中遍历到的每个单词 word，执行 n=hash(word)%5000 操作，然后将结果为 n 的单词存放到第 fn 个文件中。整个大文件遍历结束之后，我们可以得到 5000 个小文件，每个小文件的大小为 200KB 左右。如果有的小文件的大小仍然超过 1MB，则采用同样的方式继续进行分解，直到每个小文件的大小都小于 1MB 为止。文件分割过程如图 1-1 所示。

步骤 2

分别统计每个小文件中出现单词词频数最高的 100 个单词，最简单的实现方式是使用 HashMap 来实现，其中 key 为单词，value 为该单词出现的词频数。具体做法是：遍历文件中的所有单词，对于遍历到的单词 word，如果 word 在 map 中不存在，那么就执行 map.put(word,1)，将该词频设置为 1；如果 word 在 map 中存在，那么就执行 map.put(word,map.get(word)+1)，将该单词词频数加 1。遍历完成之后，可以很容易找出每个文件出现频率最高的 100 个单词_大数据培训。

步骤 3

因为步骤 2 已经找出了每个文件出现频率最高的 100 个单词，接下来我们可以通过维护一个小顶堆来找出所有单词中出现频率最高的 100 个单词。具体做法是：依次遍历每个小文件，构建一个小顶堆，堆大小为 100。如果遍历到的单词出现的次数大于堆顶单词出现的次数，那么就用新单词替换堆顶的单词，然后重新调整为小顶堆。当遍历完所有文件后，小顶堆中的单词就是出现频率最高的 100 个单词。小顶堆构建过程如图 1-1 所示。

点击并拖拽以移动

​编辑

方法总结：

针对限定内存，求解海量数据的 TopN 问题，可以采取以下几个步骤。

1.分而治之，利用哈希取余，将大文件分割为小文件。

2.使用 HashMap 统计每个单词的词频。

3.求解词频最大的 TopN，使用小顶堆；求解词频最小的 TopN，使用大顶堆。

02 如何找出访问百度最多的 IP 地址

题目描述：

现在有一个 1 亿条记录的超大文件，里面包含着某一天海量用户访问日志，但已有内存存放不下该文件，现要求从这个超大文件中统计出某天访问百度次数最多的那个 IP 地址。

题目解析：

因为题目中只关心访问百度最多的 IP 地址，所以需要对原始文件进行遍历，将这一天访问百度的 IP 的相关记录输出到一个单独的大文件中。由于内存大小的限制，我们无法将这个大文件一次性加载到内存中，所以需要采用分治法将大文件分割为若干个小文件，直到内存可以装下每个小文件为止。然后使用 HashMap 分别统计出每个小文件中的每个 IP 地址出现的次数，并找出每个小文件中出现次数最多的 IP 地址。最后比较所有小文件中出现次数最多的 IP，从而最终统计出这个超大文件中访问百度最多的 IP 地址。

实现方式：分治法

步骤 1

首先遍历超大原始日志文件，将包含百度 url 地址的相关信息记录输出到一个单独的大文件中，那么这个新生成的大文件只包含访问百度的相关信息记录。文件过滤如图 1-1 所示。

点击并拖拽以移动

​编辑

步骤 2

然后遍历新生成的大文件，对文件中遍历到的每个 IP 执行 n=hash(IP)%1000 操作，将结果为 n 的日志记录放到第 fn 个文件中。整个大文件遍历结束后，我们可以得到 1000 个小文件。那么相同的 IP 会存储到同一个文件中，分割后的每个小文件的大小为大文件的 1/1000。如果分割后的文件中仍然有部分文件无法装载到内存中，可以对该文件进行分割直至内存可以装下为止。文件分割过程如图 1-1 所示。

点击并拖拽以移动

​编辑

步骤 3

接着统计每个小文件中出现次数最多的 IP，最简单的方法是通过 HashMap 来实现，其中 key 为 IP 地址，value 为该 IP 地址出现的次数。具体做法是：遍历每个小文件中的所有记录，对于遍历到的 IP，如果 IP 地址在 map 中不存在，那么就执行 map.put(IP,1)，将该 IP 出现次数设置为 1；如果 IP 地址在 map 中存在，那么就执行 map.put(IP,map.get(IP)+1)，将该 IP 出现的次数加 1。然后再遍历 HashMap，可以很容易分别统计出每个文件中访问百度次数做多的 IP_大数据视频。

点击并拖拽以移动

​编辑

步骤 4

最后比较所有小文件中访问百度次数最多的 IP，便可以统计出整个超大文件中某日访问百度次数最多的 IP 地址。结果汇总过程如图 1-1 所示

点击并拖拽以移动

​编辑

方法总结：

针对限定内存，求解海量数据的最大值问题，可以采取以下几个步骤。

1.分而治之，利用哈希取余，将大文件分割为小文件。

2.使用 HashMap 统计每个 IP 出现的次数。

3.求解 IP 出现次数的最大值，遍历 HashMap 即可。

03 如何从 2.5 亿个整数中找出不重复的整数

题目描述：

在 2.5 亿个整数文件中找出不重复的整数。

备注：现有内存无法容纳 2.5 亿个整数。

题目解析：

题目中已经说明现有内存无法容纳 2.5 亿个整数，所以我们无法一次性将所有数据加载到内存中进行处理。

实现方式 1：分治法

由于无法直接将 2.5 亿个整数一次性加载到内存处理，所以我们需要采用分治法，将一个大文件分割成若干个小文件，从而能将每个小文件分别加载到内存中进行处理，然后使用 HashMap 分别统计出每个小文件中每个整数出现的次数，最后遍历 HashMap 输出 value 值为 1 的整数即可。

步骤 1

首先遍历这个大文件，对文件中遍历到的每个整数 digit 执行 hash(digit)%1000 操作，将结果为 n 的整数存放到第 fn 个文件中。整个大文件遍历结束之后，我们就可以将 2.5 亿个整数划分到 1000 个小文件中。那么相同的整数会存储到同一个文件中，分割后的每个小文件的大小为大文件的 1/1000。如果有的小文件仍然无法加载到内存中，则可以采用同样的方式继续进分解，直到每个小文件都可以加载到内存中为止。文件分割过程如图 1-1 所示。

点击并拖拽以移动

​编辑

步骤 2

然后在每个小文件中找出不重复的整数，最简单的方法是通过 HashMap 来实现，其中 key 为整数，value 为该整数出现的次数。具体做法是：遍历每个小文件中的所有记录，对于遍历到的整数 digit，如果 digit 在 map 中不存在，那么就执行 map.put(digit,1)，将 digit 出现次数设置为 1；如果 digit 在 map 中存在，那么就执行 map.put(digit,map.get(digit)+1)，将 digit 出现的次数加 1。整数出现次数统计逻辑如图 1-1 所示。

点击并拖拽以移动

​编辑

步骤 3

最后针对每个小文件，遍历 HashMap 输出 value 为 1 的所有整数，就可以找出这 2.5 亿个整数中所有的不重复的数。这里不用再对每个小文件输出的整数进行重复筛重，因为每个整数经过 hash 函数处理后，相同的整数只会被划分到同一个小文件中，不同的文件中不会出现重复的整数。

实现方式 2：位图法

对于整数相关的算法的求解，位图法是一种非常实用的算法。假设整数占用 4B，即 32bit，那么可以表示的整数的个数为 2^32。那么对于本题目来说，我们只需要查找不重复的数，而无需关心具体整数出现的次数，所以可以分别使用 2 个 bit 来表示各个数字的状态：00 表示这个数字没有出现过；01 表示这个数字出现过一次；10 表示这个数字出现过多次。那么这 2^32 个整数，总共需要的内存为 2^32*2b=1GB。因此，当可用内存超过 1GB 时，可以采用位图法求解该题目。

步骤 1

首先需要开辟一个用 2Bitmap 法标志的 2^32 个整数的桶数组，并初始化标记位为 00，其存储的数据量远远大于 2.5 亿个整数。开辟并初始化位图如图 1-1 所示。

点击并拖拽以移动

​编辑

步骤 2

然后遍历 2.5 亿个整数，并查看每个整数在位图中对应的位，如果位值为 00，则修改为 01，如果位值为 01，则修改为 10，如果位值为 10 则保持不变。遍历数据并修改位图状态如图 1-1 所示。

点击并拖拽以移动

​编辑

步骤 3

最后当所有数据都遍历完成之后，可以再遍历一遍位图，把对应位值是 01 的整数输出，即可统计出 2.5 亿个整数中所有不重复的数。

方法总结：

判断整数是否重复的问题，位图法是一种非常高效的方法，当然前提是：内存要满足位图法所需要的存储空间。

04 判断一个数在 40 亿数据中是否存在

题目描述：

给定 40 亿个不重复的没有排序过的整数，然后再给定一个整数，如何快速判断这个整数是否包含在这 40 亿个整数当中。备注：现有内存不足以容纳这 40 亿个整数。

题目解析：

题目中已经说明现有内存无法容纳 40 亿个整数，所以我们无法一次性将所有数据加载到内存中进行处理，那么最容易想到的方法还是分治法。

实现方式 1：分治法

根据实际内存大小情况，确定一个 hash 函数，比如 hash(digit)%1000，通过这个 hash 函数将 40 亿个整数划分到若干个小文件（f1，f2，f3，...，f1000），从而确保每个小文件都能加载到内存中进行处理。然后再对待找出的整数使用相同的 hash 函数求出 hash 值，假设计算出的这个 hash 值为 n，如果这个整数存在的话，那么它一定存在 fn 文件中。接着将 fn 文件中所有的整数都保存到 HashSet 中，最后判断待查找的整数是否存在。由于详细步骤与前面分治法类似，这里就不再赘述了。

实现方式 2：位图法

假设整数占用 4B，即 32bit，那么可以表示的整数的个数为 2^32。那么对于本题目来说，我们只需要判断整数是否存在，而无需关心整数出现的次数，所以可以使用 1 个 bit 来标记整数是否存在：0 表示这个整数不存在；1 表示这个整数存在。那么这 2^32 个整数，总共需要的内存为 2^32*2b=1GB。因此，当可用内存超过 1GB 时，可以采用位图法求解该题目。

步骤 1

首先需要开辟一个用 1Bitmap 法标志的 2^32 个整数的桶数组，并初始化标记位为 0，其存储的数据量大于 40 亿个整数。开辟并初始化位图如图 1-1 所示。

点击并拖拽以移动

​编辑

步骤 2

然后遍历 40 亿个整数，将对应的位值设置为 1。遍历数据并修改位图状态如图 1-1 所示。

点击并拖拽以移动

​编辑

步骤 3

最后再读取要查询的整数，查看对应的位值是否为 1，如果位值为 1 表示存在，如果位值为 0 表示不存在。

方法总结：

判断数字是否存在、判断数字是否重复的问题，位图法是一种非常高效的方法。

05 如何找出 CSDN 网站最热门的搜索关键词

题目描述：

CSDN 网站搜索引擎会通过日志文件把用户每次搜索使用关键词都记录下来，每个查询关键词限定长度为 1~255 个字节。假设目前有 1000 万个搜索记录，现要求统计最热门的 10 个搜索关键词。备注：现有内存不超过 1GB。

题目解析：

从题目中给出的信息可知，每个搜索关键词最长为 255 个字节，1000 万个搜索记录需要占用约 10000000*255B≈2.55GB 内存，因此，我们无法将所有搜索记录全部读入内存中处理。

实现方式 1：分治法

分治法依然是一个非常实用的方法。首先将整个搜索记录文件分割为多个小文件，保证单个小文件中的搜索记录可以全部加载到内存中处理，然后统计出每个小文件中出现次数最多的 10 个搜索关键词，最后设计一个小顶堆统计出所有文件中出现最多的 10 个搜索关键词。在本题目中，分治法虽然可行，但不是最好的方法，因为需要 2 次遍历文件，分割文件的 Hash 函数被调用 1000 万次，所以性能不是很好，这里就不再赘述。

实现方式 2：HashMap 法

虽然题目中搜索关键词的总数比较多，但是一般关键词的重复度比较高，去重之后搜索关键词不超过 300 万个，因此可以考虑把所有搜索关键词及出现的次数保存到 HashMap 中，由于存储次数的整数一般占用 4 个字节，所以 HashMap 所需要占用的空间为 300 万*（255+4）≈800M，因此题目中限定的 1GB 内存完全够用。

步骤 1

首先遍历所有搜索关键词，如果关键词存在与 map 中，则 value 值累加 1；如果关键词不在 map 中，则 value 值设置为 1。关键词出现次数统计逻辑如图 1-1 所示。

点击并拖拽以移动

​编辑

步骤 2

然后遍历 map 集合，构建一个包含 10 个元素的小顶堆，如果遍历到的关键词出现的次数大于堆顶关键词出现的次数，则进行替换，并将堆调整为小顶堆。小顶堆构建过程如图 1-1 所示。

点击并拖拽以移动

​编辑

步骤 3

最后直接取出堆中的 10 个关键词就是出现次数最多的字符串。

实现方式 3：前缀树法

前缀树：又称为字典树、单词查找树，是一种哈希树的变种。典型应用是用于统计、排序和保存大量的字符串，所以经常被搜索引擎系统用于文本词频统计。

实现方式 2 使用了 HashMap 来统计关键词出现的次数，当这些关键词有大量相同的前缀时，可以考虑使用前缀树来统计搜索关键词出现的次数，树的结点可以保存关键词出现的次数。

步骤 1

首先遍历所有搜索关键词，针对每个关键词在前缀树中查找，如果能找到，则把结点中保存的关键词次数加 1，否则就为这个关键词构建新的结点，构建完成之后把叶子结点中关键词的出现次数设置为 1。当遍历完所有关键词之后，就可以知道每个关键词的出现次数了。前缀树的构建过程如图 1-1 所示。

点击并拖拽以移动

​编辑

备注：每个结点中的 P 表示所有字符添加到树的过程中，这个结点到达过几次，E 表示当前结点有多少个字符串是以它结尾。

步骤 2

然后遍历前缀树，就可以找出出现次数最多的关键词。

方法总结：

前缀树经常被用来统计字符串的出现次数，它的另外一个用途是字符串查找，判断是否有重复的字符串等。

文章来源于大数据研习社

​