海量数据处理面试题
如果你想在校招中顺利拿到更好的offer，阿秀建议你多看看前人的经验 ，比如准备 、简历 、实习 、上岸经历 、校招总结 、阿里、字节、腾讯、美团等一二线大厂真实面经 、也欢迎来一起参加秋招打卡活动 等；如果你是计算机小白，学习/转行/校招路上感到迷茫或者需要帮助，可以点此联系阿秀；免费分享阿秀个人学习计算机以来的收集到的好资源，点此白嫖；如果你需要《阿秀的学习笔记》网站中求职相关知识点的PDF版本的话，可以点此下载
# 6、如何查询最热门的查询串？
# 题目描述
搜索引擎会通过日志文件把用户每次检索使用的所有查询串都记录下来，每个查询串的长度不超过 255 字节。
假设目前有 1000w 个记录（这些查询串的重复度比较高，虽然总数是 1000w，但如果除去重复后，则不超过 300w 个）。请统计最热门的 10 个查询串，要求使用的内存不能超过 1G。（一个查询串的重复度越高，说明查询它的用户越多，也就越热门。）
# 解答思路
每个查询串最长为 255B，1000w 个串需要占用 约 2.55G 内存，因此，我们无法将所有字符串全部读入到内存中处理。
# 方法一：分治法
分治法依然是一个非常实用的方法。
划分为多个小文件，保证单个小文件中的字符串能被直接加载到内存中处理，然后求出每个文件中出现次数最多的 10 个字符串；最后通过一个小顶堆统计出所有文件中出现最多的 10 个字符串。
方法可行，但不是最好，下面介绍其他方法。
# 方法二：HashMap 法
虽然字符串总数比较多，但去重后不超过 300w，因此，可以考虑把所有字符串及出现次数保存在一个 HashMap 中，所占用的空间为 300w*(255+4)≈777M（其中，4 表示整数占用的 4 个字节）。由此可见，1G 的内存空间完全够用。
思路如下：
首先，遍历字符串，若不在 map 中，直接存入 map，value 记为 1；若在 map 中，则把对应的 value 加 1，这一步时间复杂度 O(N) 。
接着遍历 map，构建一个 10 个元素的小顶堆，若遍历到的字符串的出现次数大于堆顶字符串的出现次数，则进行替换，并将堆调整为小顶堆。
遍历结束后，堆中 10 个字符串就是出现次数最多的字符串。这一步时间复杂度 O(Nlog10) 。
# 方法三：前缀树法
方法二使用了 HashMap 来统计次数，当这些字符串有大量相同前缀时，可以考虑使用前缀树来统计字符串出现的次数，树的结点保存字符串出现次数，0 表示没有出现。
思路如下：
在遍历字符串时，在前缀树中查找，如果找到，则把结点中保存的字符串次数加 1，否则为这个字符串构建新结点，构建完成后把叶子结点中字符串的出现次数置为 1。
最后依然使用小顶堆来对字符串的出现次数进行排序。
# 方法总结
前缀树经常被用来统计字符串的出现次数。它的另外一个大的用途是字符串查找，判断是否有重复的字符串等。
# 7、如何统计不同电话号码的个数？
# 题目描述
已知某个文件内包含一些电话号码，每个号码为 8 位数字，统计不同号码的个数。
# 解答思路
这道题本质还是求解数据重复的问题，对于这类问题，一般首先考虑位图法。
对于本题，8 位电话号码可以表示的号码个数为 108 个，即 1 亿个。我们每个号码用一个 bit 来表示，则总共需要 1 亿个 bit，内存占用约 12M。
思路如下：
申请一个位图数组，长度为 1 亿，初始化为 0。然后遍历所有电话号码，把号码对应的位图中的位置置为 1。遍历完成后，如果 bit 为 1，则表示这个电话号码在文件中存在，否则不存在。bit 值为 1 的数量即为 不同电话号码的个数。
# 方法总结
求解数据重复问题，记得考虑位图法。
# 8、 如何从 5 亿个数中找出中位数？
# 题目描述
从 5 亿个数中找出中位数。数据排序后，位置在最中间的数就是中位数。当样本数为奇数时，中位数为 第 (N+1)/2 个数；当样本数为偶数时，中位数为 第 N/2 个数与第 1+N/2 个数的均值。
# 解答思路
如果这道题没有内存大小限制，则可以把所有数读到内存中排序后找出中位数。但是最好的排序算法的时间复杂度都为 O(NlogN) 。这里使用其他方法。
# 方法一：双堆法
维护两个堆，一个大顶堆，一个小顶堆。大顶堆中最大的数小于等于小顶堆中最小的数；保证这两个堆中的元素个数的差不超过 1。
若数据总数为偶数，当这两个堆建好之后，中位数就是这两个堆顶元素的平均值。当数据总数为奇数时，根据两个堆的大小，中位数一定在数据多的堆的堆顶。
class MedianFinder {
private PriorityQueue<Integer> maxHeap;
private PriorityQueue<Integer> minHeap;
/** initialize your data structure here. */
public MedianFinder() {
maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
minHeap = new PriorityQueue<>(Integer::compareTo);
}
public void addNum(int num) {
if (maxHeap.isEmpty() || maxHeap.peek() > num) {
maxHeap.offer(num);
} else {
minHeap.offer(num);
}
int size1 = maxHeap.size();
int size2 = minHeap.size();
if (size1 - size2 > 1) {
minHeap.offer(maxHeap.poll());
} else if (size2 - size1 > 1) {
maxHeap.offer(minHeap.poll());
}
}
public double findMedian() {
int size1 = maxHeap.size();
int size2 = minHeap.size();
return size1 == size2
? (maxHeap.peek() + minHeap.peek()) * 1.0 / 2
: (size1 > size2 ? maxHeap.peek() : minHeap.peek());
}
}Copy to clipboardErrorCopied
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
见 LeetCode No.295：https://leetcode.com/problems/find-median-from-data-stream/
以上这种方法，需要把所有数据都加载到内存中。当数据量很大时，就不能这样了，因此，这种方法适用于数据量较小的情况。5 亿个数，每个数字占用 4B，总共需要 2G 内存。如果可用内存不足 2G，就不能使用这种方法了，下面介绍另一种方法。
# 方法二：分治法
分治法的思想是把一个大的问题逐渐转换为规模较小的问题来求解。
对于这道题，顺序读取这 5 亿个数字，对于读取到的数字 num，如果它对应的二进制中最高位为 1，则把这个数字写到 f1 中，否则写入 f0 中。通过这一步，可以把这 5 亿个数划分为两部分，而且 f0 中的数都大于 f1 中的数（最高位是符号位）。
划分之后，可以非常容易地知道中位数是在 f0 还是 f1 中。假设 f1 中有 1 亿个数，那么中位数一定在 f0 中，且是在 f0 中，从小到大排列的第 1.5 亿个数与它后面的一个数的平均值。
提示，5 亿数的中位数是第 2.5 亿与右边相邻一个数求平均值。若 f1 有一亿个数，那么中位数就是 f0 中从第 1.5 亿个数开始的两个数求得的平均值。
对于 f0 可以用次高位的二进制继续将文件一分为二，如此划分下去，直到划分后的文件可以被加载到内存中，把数据加载到内存中以后直接排序，找出中位数。
注意，当数据总数为偶数，如果划分后两个文件中的数据有相同个数，那么中位数就是数据较小的文件中的最大值与数据较大的文件中的最小值的平均值。
# 方法总结
分治法，真不错！
# 9、如何按照 query 的频度排序？
# 题目描述
有 10 个文件，每个文件大小为 1G，每个文件的每一行存放的都是用户的 query，每个文件的 query 都可能重复。要求按照 query 的频度排序。
# 解答思路
如果 query 的重复度比较大，可以考虑一次性把所有 query 读入内存中处理；如果 query 的重复率不高，那么可用内存不足以容纳所有的 query，这时候就需要采用分治法或其他的方法来解决。
# 方法一：HashMap 法
如果 query 重复率高，说明不同 query 总数比较小，可以考虑把所有的 query 都加载到内存中的 HashMap 中。接着就可以按照 query 出现的次数进行排序。
# 方法二：分治法
分治法需要根据数据量大小以及可用内存的大小来确定问题划分的规模。对于这道题，可以顺序遍历 10 个文件中的 query，通过 Hash 函数 hash(query) % 10 把这些 query 划分到 10 个小文件中。之后对每个小文件使用 HashMap 统计 query 出现次数，根据次数排序并写入到另外一个单独文件中。
接着对所有文件按照 query 的次数进行排序，这里可以使用归并排序（由于无法把所有 query 都读入内存，因此需要使用外排序）。
# 方法总结
内存若够，直接读入进行排序；
内存不够，先划分为小文件，小文件排好序后，整理使用外排序进行归并。
# 10、如何找出排名前 500 的数？
# 题目描述
有 20 个数组，每个数组有 500 个元素，并且有序排列。如何在这 20*500 个数中找出前 500 的数？
# 解答思路
对于 TopK 问题，最常用的方法是使用堆排序。对本题而言，假设数组降序排列，可以采用以下方法：
首先建立大顶堆，堆的大小为数组的个数，即为 20，把每个数组最大的值存到堆中。
接着删除堆顶元素，保存到另一个大小为 500 的数组中，然后向大顶堆插入删除的元素所在数组的下一个元素。
重复上面的步骤，直到删除完第 500 个元素，也即找出了最大的前 500 个数。
为了在堆中取出一个数据后，能知道它是从哪个数组中取出的，从而可以从这个数组中取下一个值，可以把数组的指针存放到堆中，对这个指针提供比较大小的方法。
import lombok.Data;
import java.util.Arrays;
import java.util.PriorityQueue;
/**
* @author https://github.com/yanglbme
*/
@Data
public class DataWithSource implements Comparable<DataWithSource> {
/**
* 数值
*/
private int value;
/**
* 记录数值来源的数组
*/
private int source;
/**
* 记录数值在数组中的索引
*/
private int index;
public DataWithSource(int value, int source, int index) {
this.value = value;
this.source = source;
this.index = index;
}
/**
*
* 由于 PriorityQueue 使用小顶堆来实现，这里通过修改
* 两个整数的比较逻辑来让 PriorityQueue 变成大顶堆
*/
@Override
public int compareTo(DataWithSource o) {
return Integer.compare(o.getValue(), this.value);
}
}
class Test {
public static int[] getTop(int[][] data) {
int rowSize = data.length;
int columnSize = data[0].length;
// 创建一个columnSize大小的数组，存放结果
int[] result = new int[columnSize];
PriorityQueue<DataWithSource> maxHeap = new PriorityQueue<>();
for (int i = 0; i < rowSize; ++i) {
// 将每个数组的最大一个元素放入堆中
DataWithSource d = new DataWithSource(data[i][0], i, 0);
maxHeap.add(d);
}
int num = 0;
while (num < columnSize) {
// 删除堆顶元素
DataWithSource d = maxHeap.poll();
result[num++] = d.getValue();
if (num >= columnSize) {
break;
}
d.setValue(data[d.getSource()][d.getIndex() + 1]);
d.setIndex(d.getIndex() + 1);
maxHeap.add(d);
}
return result;
}
public static void main(String[] args) {
int[][] data = {
{29, 17, 14, 2, 1},
{19, 17, 16, 15, 6},
{30, 25, 20, 14, 5},
};
int[] top = getTop(data);
System.out.println(Arrays.toString(top)); // [30, 29, 25, 20, 19]
}
}Copy to clipboardErrorCopied
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
# 方法总结
求 TopK，不妨考虑一下堆排序？
# 参考资料
← 海量数据处理01-05 系统设计01-03 →