阿秀的学习笔记

海量数据处理面试题

这是六则或许对你有些许帮助的信息:

⭐️1、阿秀与朋友合作开发了一个编程资源网站，目前已经收录了很多不错的学习资源和黑科技（附带下载地址），如过你想要寻求合适的编程资源，欢迎体验以及推荐自己认为不错的资源，众人拾柴火焰高，我为人人，人人为我🔥！

2、👉23年5月份阿秀从字节跳动离职跳槽到某外企期间，为方便自己找工作，增加上岸几率，我自己从0开发了一个互联网中大厂面试真题解析网站，包括两个前端和一个后端。能够定向查看某些公司的某些岗位面试真题，比如我想查一下行业为互联网，公司为字节跳动，考察岗位为后端，考察时间为最近一年之类的面试题有哪些？

网站地址：InterviewGuide大厂面试真题解析网站。点此可以查看该网站的视频介绍：B站视频讲解 如果可以的话求个B站三连，感谢！

3、😊 分享一个学弟发给我的20T网盘资源合集，点此白嫖，主要是各类高清影视、电视剧、音乐、副业、纪录片、英语四六级考试、考研考公等资源。

4、😍免费分享阿秀个人学习计算机以来收集到的免费学习资源，点此白嫖；也记录一下自己以前买过的不错的计算机书籍、网络专栏和垃圾付费专栏；也记录一下自己以前买过的不错的计算机书籍、网络专栏和垃圾付费专栏

5、🚀如果你想在校招中顺利拿到更好的offer，阿秀建议你多看看前人踩过的坑和留下的经验，事实上你现在遇到的大多数问题你的学长学姐师兄师姐基本都已经遇到过了。

6、🔥 欢迎准备计算机校招的小伙伴加入我的学习圈子，一个人踽踽独行不如一群人报团取暖，圈子里沉淀了很多过去21/22/23届学长学姐的经验和总结，好好跟着走下去的，最后基本都可以拿到不错的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个星期的时间，如何检验出哪个瓶子有毒药？

# 解答思路：

这个问题可以通过二进制编码来解决。具体方法如下：

1. **为每个瓶子编号**：将1000个瓶子从1到1000编号。

2. **将瓶子编号转换为二进制**：因为你有10只小白鼠，所以可以用10位二进制数来表示每个瓶子的编号。例如，瓶子1的二进制表示为`0000000001`，瓶子1000的二进制表示为`1111101000`。

3. **分配小白鼠喝水**：
   - 用每个瓶子的二进制表示法的每一位（0或1）来决定哪只小白鼠要喝那瓶水。例如，如果某个瓶子的二进制表示中的第一位是1，就让第一只小白鼠喝这瓶水，如果第二位是1，就让第二只小白鼠喝，以此类推。
   - 对每个瓶子按照它的二进制表示给对应的小白鼠喝水。例如，瓶子1000的二进制是`1111101000`，所以第1到第5只小白鼠和第7只小白鼠要喝瓶子1000的水。

4. **等待一周后观察小白鼠的死亡情况**：
   - 一周后，观察哪些小白鼠死了。根据死亡的小白鼠，我们可以形成一个新的10位二进制数。
   - 例如，如果第1、2、5只小白鼠死了，而其他小白鼠存活，那么这个二进制数为`00000001101`，将这个二进制数转换为十进制，就可以得出有毒的瓶子的编号。

通过这种方式，最多可以检测1024个瓶子（因为2^10 = 1024），但因为题目中只有1000个瓶子，所以足够用了。最终，通过观察死亡的小白鼠，你就可以精确确定哪一瓶是毒药。

← 海量数据处理06-10 →