Skip to main content

面经

David Liu12/12/25About 5 min

面经

内存有限，怎么对 100 亿数据进行排序（大数据小内存排序问题）
内存有限，如何在 20 亿个整数中找到出现次数最多的数
内存有限，如何在 40 亿个非负整数中找到所有未出现的数
内存有限，如何在 100 亿数据中找到中位数
内存有限，如何在 2 亿个整数中找出不连续的最小数
百万文件如何找到相似度最高的文件
40 亿个 QQ 号，限制 1G 内存，如何去重？

大文件排序

外排序

大文件找众数

摩尔投票法

两个大文件求交集

假设文件为 a，b

  1. 直接遍历法。一般人第一时间都是想遍历吧。读取每一行 a，在 b 中遍历，这样时间复杂度为 O（n^2），显然一般人都不能接受这个时间复杂度。

  2. 哈希 + 分片的思想。先把 a 文件 hash，在遍历 b 文件，去判断是否存在。

    时间复杂度降低为 O（n） ，但是空间复杂度上来了，以空间换时间。

    1. 将文件 A 中的 hash(url)%100，生成 100 个小文件。
    2. 文件 B 中也 hash(url)%100，生成 100 个小文件。
    3. 然后将 A 子文件 001 和 B 子文件 001 求交集，放入一个结果文件即可。

  3. 布隆过滤器。但是布隆过滤器是有可能出现错误的，当时应该问问他是否可以出现小的错误？

对于大文件的话，一般都是使用分治思想，将文件分割成多个小文件来处理。

题目背景

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

主体思路

分治+hash

实现步骤

遍历文件 A，对每个 url 使用 hash(url) % 1000，根据所得的取值将 url 存储到 1000 个小文件中（a1,a2,…,a1000）（根据内存大小设定 hash 函数）
遍历文件 B，使用同样的 hash 函数将 B 中的 url 存储到 1000 个小文件中（b1,b2,…,b1000）（这样相同的 url 就会被映射到下标相同的小文件中）
读取文件 a1，建立 hash 表，再读取文件 b1，遍历其中的 url，若 url 在 hash 表中出现，说明为两文件共有，存入结果中。

如何在大量的数据中判断一个数是否存在？

题目描述

给定 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 表示不存在。

方法总结

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

求两个超大文件中 URLs 的交集，并且内存中不足以放下所有的 URLs

所谓海量数据处理，其实就是基于海量数据的存储、删除、搜索等操作。所谓海量，就是数据量太大，所以导致要么无法在短时间内迅速处理，要么无法一次性装入内存。

那应该如何解决呢？针对时间，我们可以采用更加精妙而迅速的数据结构和算法，比如 BloomFilter、Hash、堆、Bitmap 等；针对空间，无非就是：大而化小，分而治之。在这里我们先不一一展开。

根据上面的讨论，在海量数据处理类的问题中，我们总结了以下考点：

算法方面：

  • 外排序算法（External Sorting）
  • Map Reduce
  • 非精确算法
  • 概率算法
  • 哈希函数（Hash Function）

数据结构方面：

  • 哈希表（Hash Table）
  • 堆（Heap）
  • 布隆过滤器（BloomFilter）
  • 位图（Bitmap）

40 亿个 QQ 号，限制 1G 内存，如何去重？

对于 Java 来说，可以使用 int 类型表示 QQ 号（Java 并未设计无符号整型，只有几个无符号整型的静态方法)。

40 亿个 QQ 号如果直接存储的话，大约需要内存：4*4000000000/1024/1024/1024≈15G。实际开发过程中，所需的内存肯定会更多。

1KB=1024B,1MB=1024KB,1GB=1024MB

很显然，这种方式是不现实的。

对于这种大数据量去重的场景，我们可以考虑使用位图(Bitmap)。位图可以在不占用太多内存的前提下，解决海量数据的存在性问题，进而实现去重。

Bitmap 是一种用于存储二进制数据的数据结构。简单来说，Bitmap 就是使用二进制位来表示某个元素是否存在的数组。每一位只有两种状态，可以方便地用 0 和 1 来表示存在与不存在。

使用 Bitmap 的话，一个数字只需要占用 1 个 bit。

我们知道 QQ 号是 4 字节无符号整数，共 326t,也就是说，QQ 号的取值范围是：[0,232-1]。232-1 的值是 4294967295，是一个 10 位的整数，大约是 43 亿。

这样的话，大约需要 512MB 内存就可以表示所有的 QQ 号了，计算过程：4294967295/8/1024/1024≈512MB。

假设我们要把 QQ 号 1384593330 放入 Bitmap,我们只需要将 1384593330 位置的数组元素设置为 1 即可。当我们要判断对应的 QQ 号是否已经存在于 Bitmap 中时，只需要查看对应位置的数组元素是否为 1 即可。

Redis 就支持 Bitmap,实际项目中我们可以基于 Redis 来做。

David's Blog
Copyright © 2025 David Liu