文档教程知识库【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/forthespada/InterviewGuide点击查看免费下载导读本篇整理自 InterviewGuide 仓库中阿秀总结的海量数据处理面试题系列第 6–10 题覆盖了互联网大厂面试中最高频的四类场景化问题统计最热门的查询串TopK、统计不同电话号码的个数判重、从 5 亿个数中找出中位数、按 query 频度排序以及从多路有序数组找出前 500 大的数。读完本篇你将掌握内存装不下时的通用解题三板斧——分而治之 哈希取余、HashMap 统计频数、大小顶堆求 TopN并能把位图法、前缀树、双堆法与仓库内的 LeetCode 题解一一对应起来做到面试手撕不慌。本系列前 5 题从大量 URL 中找相同、找高频词、找最多访问 IP、找不重复整数、判断数是否存在等见同目录的 07-01-massive_data.md本篇承接其解题思想继续深入。一、如何查询最热门的查询串题目描述搜索引擎会通过日志文件把用户每次检索使用的所有查询串都记录下来每个查询串的长度不超过255 字节。假设目前有1000w 个记录这些查询串的重复度比较高虽然总数是 1000w但如果除去重复后则不超过 300w 个。请统计最热门的10 个查询串要求使用的内存不能超过1G。一个查询串的重复度越高说明查询它的用户越多也就越热门。内存估算为什么不能一次性读入每个查询串最长为 255B1000w 个串需要占用约2.55G内存1000w × 255B ≈ 2.55G 1G因此我们无法将所有字符串全部读入到内存中处理。针对数据总量大、去重后规模小、要求 TopN这一类问题有三种经典思路。方法一分治法分治法依然是海量数据处理里非常实用的通用方法把大文件划分为多个小文件保证单个小文件中的字符串能被直接加载到内存中处理求出每个文件中出现次数最多的 10 个字符串最后通过一个小顶堆统计出所有文件中出现最多的 10 个字符串。方法可行但不是最好下面两种方法在本题背景下更优。方法二HashMap 法虽然字符串总数比较多但去重后不超过 300w因此可以考虑把所有字符串及出现次数保存在一个 HashMap 中300w × (255 4) ≈ 777M其中 4 表示整数出现次数占用的 4 个字节。由此可见1G 的内存空间完全够用。思路如下第一步遍历字符串若不在 map 中直接存入 mapvalue 记为 1若在 map 中则把对应的 value 加 1。这一步时间复杂度为O(N)第二步遍历 map构建一个10 个元素的小顶堆。若遍历到的字符串的出现次数大于堆顶字符串的出现次数则进行替换并将堆调整为小顶堆第三步遍历结束后堆中 10 个字符串就是出现次数最多的字符串。这一步时间复杂度为O(Nlog10)。方法三前缀树法方法二使用了 HashMap 来统计次数当这些字符串有大量相同前缀时可以考虑使用**前缀树Trie**来统计字符串出现的次数树的结点保存字符串出现次数0 表示没有出现。思路如下在遍历字符串时在前缀树中查找如果找到则把结点中保存的字符串次数加 1否则为这个字符串构建新结点构建完成后把叶子结点中字符串的出现次数置为 1最后依然使用小顶堆来对字符串的出现次数进行排序。方法总结前缀树经常被用来统计字符串的出现次数它的另外一个大的用途是字符串查找、判断是否有重复的字符串等。当数据集中存在大量共享前缀时前缀树相比 HashMap 还能进一步降低存储成本、提高查询效率这一思路与本系列第 1 题如何从大量 URL 中找出相同的 URL中提到的字典树方案一脉相承详见 07-01-massive_data.md。二、如何统计不同电话号码的个数题目描述已知某个文件内包含一些电话号码每个号码为8 位数字统计不同号码的个数。解答思路位图法这道题本质还是求解数据重复的问题对于这类问题一般首先考虑位图法位图的基本原理与本系列第 4 题在 2.5 亿个整数中找出不重复的整数一致可对照阅读 07-01-massive_data.md。对于本题8 位电话号码可以表示的号码个数为10^8个即1 亿个。我们每个号码用一个 bit 来表示则总共需要 1 亿个 bit内存占用约10^8 bit 12.5MB ≈ 12M思路如下申请一个位图数组长度为 1 亿初始化为 0遍历所有电话号码把号码对应的位图中的位置置为 1遍历完成后如果 bit 为 1则表示这个电话号码在文件中存在否则不存在bit 值为 1 的数量即为不同电话号码的个数。方法总结求解数据重复问题记得考虑位图法。位图以 bit 为存储单位能把一个整数是否出现/出现几次的信息压缩到极致非常适合判重、快速查找与排序类场景。本系列第 4、5 题找不重复整数、判断一个数是否存在也都是位图法的典型应用。三、如何从 5 亿个数中找出中位数题目描述从5 亿个数中找出中位数。数据排序后位置在最中间的数就是中位数当样本数为奇数时中位数为第(N1)/2个数当样本数为偶数时中位数为第N/2个数与第1N/2个数的均值。思路分析如果这道题没有内存大小限制则可以把所有数读到内存中排序后找出中位数。但是最好的排序算法的时间复杂度都为O(NlogN)这里使用其他方法。方法一双堆法维护两个堆一个大顶堆、一个小顶堆。大顶堆中最大的数小于等于小顶堆中最小的数保证这两个堆中的元素个数的差不超过 1。判定规则若数据总数为偶数当这两个堆建好之后中位数就是这两个堆顶元素的平均值当数据总数为奇数时根据两个堆的大小中位数一定在数据多的堆的堆顶。原文档给出了完整的 Java 实现对应 LeetCode 第 295 题数据流的中位数class MedianFinder { private PriorityQueueInteger maxHeap; private PriorityQueueInteger 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()); } }该方法对应 LeetCode No.295 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 可以用次高位的二进制继续将文件一分为二如此划分下去直到划分后的文件可以被加载到内存中把数据加载到内存中以后直接排序找出中位数。注意当数据总数为偶数如果划分后两个文件中的数据有相同个数那么中位数就是数据较小的文件中的最大值与数据较大的文件中的最小值的平均值。方法总结分治法把内存放不下的大问题逐步切割成内存放得下的小问题每次切割只保留与中位数相关的一半数据信息损失可控非常适合超大文件求中位数、求分位数等场景。四、如何按照 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 都读入内存因此需要使用外排序。方法总结内存若够直接读入进行排序内存不够先划分为小文件小文件排好序后整理使用外排序进行归并。五、如何找出排名前 500 的数题目描述有20 个数组每个数组有500 个元素并且有序排列。如何在这20 × 500个数中找出前 500的数解答思路堆排序对于 TopK 问题最常用的方法是使用堆排序。对本题而言假设数组降序排列可以采用以下方法首先建立大顶堆堆的大小为数组的个数即为20把每个数组最大的值存到堆中接着删除堆顶元素保存到另一个大小为 500 的数组中然后向大顶堆插入删除的元素所在数组的下一个元素重复上面的步骤直到删除完第 500 个元素也即找出了最大的前 500 个数。为了在堆中取出一个数据后能知道它是从哪个数组中取出的从而可以从这个数组中取下一个值可以把数组的指针存放到堆中对这个指针提供比较大小的方法。原文档给出的完整 Java 实现如下核心是DataWithSource记录数值 来源数组 数组内索引并通过改写compareTo让默认小顶堆的PriorityQueue变成大顶堆import lombok.Data; import java.util.Arrays; import java.util.PriorityQueue; public class DataWithSource implements ComparableDataWithSource { /** * 数值 */ 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]; PriorityQueueDataWithSource 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] } }从示例main可以看到3 个降序数组{29,17,14,2,1}、{19,17,16,15,6}、{30,25,20,14,5}运行后输出[30, 29, 25, 20, 19]即正确取出了前 5 大的数。该思路本质上是多路归并 堆堆中始终只保留每个数组当前的最大候选值堆大小 数组个数每次弹出全局最大后从同源数组补位从而把时间复杂度控制在O(Nlogk)量级N 为总元素数k 为数组个数。六、源码佐证堆与 TopK 在 InterviewGuide 算法题库中的落地本篇五道题反复用到两个底层数据结构——堆小顶堆/大顶堆与位图/哈希。InterviewGuide 的算法题库为它们提供了大量可直接刷的配套题解1. 堆排序基础实现02-07-十大排序.md 给出了堆排序的 C 实现包含三个核心函数heapify对第 i 个结点取根、左、右的最大值并下沉调整建堆与调整的基础操作heapify_build从树的倒数第二层第一个结点开始自底向上建大根堆heapify_sort建好大根堆后每次交换最后一个结点和根节点最大值再对交换后的根节点继续heapify此时堆的最后一位已是最大值n 变为 n-1。这与本篇第 5 题先建堆、反复取堆顶的思路完全一致先掌握裸堆排序再理解多路堆归并会容易很多。另外在 02-algorithm-basic.md 中堆排序被列为非稳定排序时间复杂度O(nlogn)这是面试中常被追问的知识点。2. 求前 k 大用最小堆的口诀在 LeetCode 题解中的印证347.前K个高频元素.md 中有一句醒目的提示与本篇第 1、2、5 题的方法论完全同源求前 k 大用小根堆求前 k 小用大根堆。面试的时候如果说反了会挂其题解正是unordered_map统计频数 priority_queue维护大小为 k 的小根堆堆满后弹出堆顶与本题HashMap 统计 10 元素小顶堆的流程一一对应priority_queuepairint, int, vectorpairint, int, compare freq; for (auto a : hash) { freq.push(a); if (freq.size() k) freq.pop(); }类似的还有215.数组中的第K个最大元素.md用大小为 k 的小顶堆priority_queueint, vectorint, greaterint一趟求出第 k 大元素是 TopK 问题最直接的落地692.前K个高频单词.md在频数相同的情况下再按字典序比较展示了如何通过自定义比较器扩展堆的排序规则本题DataWithSource的compareTo正是同一技巧。3. 分治 哈希取余的通用套路本篇第 1、4 题使用的hash(x) % N拆小文件套路与本系列第 1、2、3 题07-01-massive_data.md中的分而治之进行哈希取余完全一致是海量数据处理面试题出现频率最高的通用解法建议作为第一反应优先考虑。七、五题方法论总览题目核心考点首选思路复杂度/内存要点查询最热门查询串Top10TopK 字符串统计HashMap 统计 小顶堆前缀树优化共享前缀去重后 300w × 259B ≈ 777M 1G统计不同电话号码个数判重位图法10^8 bit ≈ 12M5 亿个数找中位数中位数双堆法内存够 / 分治法内存不够双堆法需 2G 内存分治法按符号位逐位切割按 query 频度排序外排序HashMap 法重复率高/ 分治 外排序归并内存够直接排不够拆小文件后归并20 个有序数组找前 500多路归并 TopK大小为 20 的大顶堆 同源补位每次 O(log20)总 O(Nlogk)面试记忆要点数据总量大、内存装不下 →分而治之哈希取余拆小文件拆完后统计频数 →HashMap / 前缀树求最大的 TopN 用小顶堆求最小的 TopN 用大顶堆判重、判断存在 →位图法多路有序数据取前 N →大小为路数的大顶堆 同源补位多路归并大文件整体排序 →小文件各自排好后用外排序归并。掌握以上六条再配合仓库算法题库中的 堆排序实现、347 前 K 个高频元素、215 第 K 个最大元素 与 692 前 K 个高频单词 反复练习海量数据处理这一类场景题基本可以做到举一反三、稳定拿下。赞分享文档教程知识库【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/forthespada/InterviewGuide点击查看免费下载相关推荐海量数据 TopK 问题常用套路详解堆排序、类快排、Bitmap、Hash、字典树与混合查询advanced-java 大数据实战海量数据 TopK 问题常用套路详解堆排序、类快排、Bitmap、Hash、字典树与混合查询advanced java 大数据实战 本文是 advance文档教程知识库后端接上 REA 之后逆向引擎还需要几个REA 对比 Hopper / Ghidra / IDA 选型指南接上 REA 之后逆向引擎还需要几个REA 对比 Hopper / Ghidra / IDA 选型指南 Agent 没有鼠标从一个离线搜索功能说起 假设你逆向工程MCP 服务AI 技能从比特币到以太坊OpenZeppelin精选资源带你全面了解区块链技术从比特币到以太坊OpenZeppelin精选资源带你全面了解区块链技术 想要从零开始学习区块链技术吗OpenZeppelin团队精心整理的这份 区块链学习资上一篇终结内存泄漏System Informer实战调试指南下一篇深读 DSH Desktop 的设计定位为什么 DeepSeek Harness 需要一个桌面端以及插件化边界的价值创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考