海量数据处理面试题

如果你想在校招中顺利拿到更好的offer,阿秀建议你多看看前人的经验 ,比如准备简历实习上岸经历校招总结阿里、字节、腾讯、美团等一二线大厂真实面经也欢迎来一起参加秋招打卡活动 等;如果你是计算机小白,学习/转行/校招路上感到迷茫或者需要帮助,可以点此联系阿秀;免费分享阿秀个人学习计算机以来的收集到的好资源,点此白嫖;如果你需要《阿秀的学习笔记》网站中求职相关知识点的PDF版本的话,可以点此下载

其实互联网招聘中,经常会被问到关于海量数据处理的问题,阿秀这里也为大家总结了一些经典的海量数据处理面试题!

# 1、如何从大量的 URL 中找出相同的 URL?

  • 题目描述

    给定 a、b 两个文件,各存放 50 亿个 URL,每个 URL 各占 64B,内存限制是 4G。请找出 a、b 两个文件共同的 URL。

    # 解答思路

    # 1. 分治策略

    每个 URL 占 64B,那么 50 亿个 URL 占用的空间大小约为 320GB。

    5, 000, 000, 000 _ 64B ≈ 5GB _ 64 = 320GB

    由于内存大小只有 4G,因此,我们不可能一次性把所有 URL 加载到内存中处理。对于这种类型的题目,一般采用分治策略,即:把一个文件中的 URL 按照某个特征划分为多个小文件,使得每个小文件大小不超过 4G,这样就可以把这个小文件读到内存中进行处理了。

    思路如下

    首先遍历文件 a,对遍历到的 URL 求 hash(URL) % 1000 ,根据计算结果把遍历到的 URL 存储到 a0, a1, a2, ..., a999,这样每个大小约为 300MB。使用同样的方法遍历文件 b,把文件 b 中的 URL 分别存储到文件 b0, b1, b2, ..., b999 中。这样处理过后,所有可能相同的 URL 都在对应的小文件中,即 a0 对应 b0, ..., a999 对应 b999,不对应的小文件不可能有相同的 URL。那么接下来,我们只需要求出这 1000 对小文件中相同的 URL 就好了。

    接着遍历 ai( i∈[0,999] ),把 URL 存储到一个 HashSet 集合中。然后遍历 bi 中每个 URL,看在 HashSet 集合中是否存在,若存在,说明这就是共同的 URL,可以把这个 URL 保存到一个单独的文件中。

    # 2. 前缀树

    一般而言,URL 的长度差距不会不大,而且前面几个字符,绝大部分相同。这种情况下,非常适合使用字典树(trie tree) 这种数据结构来进行存储,降低存储成本的同时,提高查询效率。

    # 方法总结

    # 分治策略

    1. 分而治之,进行哈希取余;
    2. 对每个子文件进行 HashSet 统计。

    # 前缀树

    1. 利用字符串的公共前缀来降低存储成本,提高查询效率。

# 2、如何从大量数据中找出高频词?

# 题目描述

有一个 1GB 大小的文件,文件里每一行是一个词,每个词的大小不超过 16B,内存大小限制是 1MB,要求返回频数最高的 100 个词(Top 100)。

# 解答思路

由于内存限制,我们依然无法直接将大文件的所有词一次读到内存中。因此,同样可以采用分治策略,把一个大文件分解成多个小文件,保证每个文件的大小小于 1MB,进而直接将单个小文件读取到内存中进行处理。

思路如下

首先遍历大文件,对遍历到的每个词 x,执行 hash(x) % 5000 ,将结果为 i 的词存放到文件 ai 中。遍历结束后,我们可以得到 5000 个小文件。每个小文件的大小为 200KB 左右。如果有的小文件大小仍然超过 1MB,则采用同样的方式继续进行分解。

接着统计每个小文件中出现频数最高的 100 个词。最简单的方式是使用 HashMap 来实现。其中 key 为词,value 为该词出现的频率。具体方法是:对于遍历到的词 x,如果在 map 中不存在,则执行 map.put(x, 1) ;若存在,则执行 map.put(x, map.get(x)+1) ,将该词频数加 1。

上面我们统计了每个小文件单词出现的频数。接下来,我们可以通过维护一个小顶堆来找出所有词中出现频数最高的 100 个。具体方法是:依次遍历每个小文件,构建一个小顶堆,堆大小为 100。如果遍历到的词的出现次数大于堆顶词的出现次数,则用新词替换堆顶的词,然后重新调整为小顶堆,遍历结束后,小顶堆上的词就是出现频数最高的 100 个词。

# 方法总结

  1. 分而治之,进行哈希取余;
  2. 使用 HashMap 统计频数;
  3. 求解最大的 TopN 个,用小顶堆;求解最小的 TopN 个,用大顶堆

# 3、如何找出某一天访问百度网站最多的 IP?

# 题目描述

现有海量日志数据保存在一个超大文件中,该文件无法直接读入内存,要求从中提取某天访问百度次数最多的那个 IP。

# 解答思路

这道题只关心某一天访问百度最多的 IP,因此,可以首先对文件进行一次遍历,把这一天访问百度 IP 的相关信息记录到一个单独的大文件中。接下来采用的方法与上一题一样,大致就是先对 IP 进行哈希映射,接着使用 HashMap 统计重复 IP 的次数,最后计算出重复次数最多的 IP。

注:这里只需要找出出现次数最多的 IP,可以不必使用堆,直接用一个变量 max 即可。

# 方法总结

  1. 分而治之,进行哈希取余;

  2. 使用 HashMap 统计频数;

  3. 求解最大的 TopN 个,用小顶堆;求解最小的 TopN 个,用大顶堆

# 4、如何在大量的数据中找出不重复的整数?

# 题目描述

在 2.5 亿个整数中找出不重复的整数。注意:内存不足以容纳这 2.5 亿个整数。

# 解答思路

# 方法一:分治法

与前面的题目方法类似,先将 2.5 亿个数划分到多个小文件,用 HashSet/HashMap 找出每个小文件中不重复的整数,再合并每个子结果,即为最终结果。

# 方法二:位图法

位图,就是用一个或多个 bit 来标记某个元素对应的值,而键就是该元素。采用位作为单位来存储数据,可以大大节省存储空间。

位图通过使用位数组来表示某些元素是否存在。它可以用于快速查找,判重,排序等。不是很清楚?我先举个小例子。

假设我们要对 [0,7] 中的 5 个元素 (6, 4, 2, 1, 5) 进行排序,可以采用位图法。0~7 范围总共有 8 个数,只需要 8bit,即 1 个字节。首先将每个位都置 0:

0 0 0 0 0 0 0 0Copy to clipboardErrorCopied
1

然后遍历 5 个元素,首先遇到 6,那么将下标为 6 的位的 0 置为 1;接着遇到 4,把下标为 4 的位 的 0 置为 1:

0 0 0 0 1 0 1 0Copy to clipboardErrorCopied
1

依次遍历,结束后,位数组是这样的:

0 1 1 0 1 1 1 0Copy to clipboardErrorCopied
1

每个为 1 的位,它的下标都表示了一个数:

for i in range(8):
    if bits[i] == 1:
        print(i)Copy to clipboardErrorCopied
1
2
3

这样我们其实就已经实现了排序。

对于整数相关的算法的求解,位图法是一种非常实用的算法。假设 int 整数占用 4B,即 32bit,那么我们可以表示的整数的个数为 $2^32$。

那么对于这道题,我们用 2 个 bit 来表示各个数字的状态:

  • 00 表示这个数字没出现过;
  • 01 表示这个数字出现过一次(即为题目所找的不重复整数);
  • 10 表示这个数字出现了多次。

那么这 $2^32$ 个整数,总共所需内存为 $2^32$*2b=1GB。因此,当可用内存超过 1GB 时,可以采用位图法。假设内存满足位图法需求,进行下面的操作:

遍历 2.5 亿个整数,查看位图中对应的位,如果是 00,则变为 01,如果是 01 则变为 10,如果是 10 则保持不变。遍历结束后,查看位图,把对应位是 01 的整数输出即可。

当然,本题中特别说明:内存不足以容纳这 2.5 亿个整数,2.5 亿个整数的内存大小为:2.5e8/1024/1024/1024 * 4=3.72GB, 如果内存大于 1GB,是可以通过位图法解决的。

# 方法总结

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

# 5、如何在大量的数据中判断一个数是否存在?

# 题目描述

给定 40 亿个不重复的没排过序的 unsigned int 型整数,然后再给定一个数,如何快速判断这个数是否在这 40 亿个整数当中?

# 解答思路

# 方法一:分治法

依然可以用分治法解决,方法与前面类似,就不再次赘述了。

# 方法二:位图法

由于 unsigned int 数字的范围是 [0, 1 << 32),我们用 1<<32=4,294,967,296 个 bit 来表示每个数字。初始位均为 0,那么总共需要内存:4,294,967,296b≈512M。

我们读取这 40 亿个整数,将对应的 bit 设置为 1。接着读取要查询的数,查看相应位是否为 1,如果为 1 表示存在,如果为 0 表示不存在。

# 方法总结

判断数字是否存在、判断数字是否重复的问题,位图法是一种非常高效的方法。6、毒药毒白鼠,找出哪个瓶子中是毒药

有1000个一模一样的瓶子,其中有999瓶是普通的水,有1瓶是毒药。任何喝下毒药的生命都会在一星期之后死亡。现在你只有10只小白鼠和1个星期的时间,如何检验出哪个瓶子有毒药?