去年春招的时候很多师弟师妹跑来问我百度实习生的笔试该怎么准备。我翻出当年自己做过的题单发现那道附加题放在今天看依然是很有代表性的海量数据考题给你一个包含大量整数的数据文件假设有10亿个整数内存只有几百MB要求找出其中最大的1000个数。题目看似简单却能在“内存受限”这个条件下刷掉一大半人。这篇文章就把这道题从头到尾拆透包括我自己的解题过程和踩过的坑希望能帮到正在准备大厂实习面试的朋友。1. 题目还原与考点拆解1.1 题目原貌百度2015春季实习生招聘的这道附加题核心描述大致是这样的有一个二进制文件里面按顺序存储了10亿个32位整数也就是大概4GB的数据量。现在给你一台内存只有512MB的机器要求用尽可能快的方式输出其中最大的1000个数。需要注意的是这道题在当时并不是独立出现的而是作为整套笔试题的附加部分。和前面的基础算法题不同附加题往往没有标准答案面试官更看重你的思考过程。也正因为如此它其实是一个非常好的“压力测试”题目你只有在有限的内存条件和时间限制下拿出一个可行且高效的方案才能让面试官眼前一亮。为什么我说这道题有代表性因为它同时考察了三个层面的能力第一对基础数据结构的掌握比如堆、分治这些概念第二对真实硬件环境的理解也就是内存、磁盘IO的取舍第三对工程化方案的敏感度能不能从“做题家”思维切换到“解决实际问题”的思维。这三个层面恰恰是大厂招聘实习生时最看重的素质。1.2 面试官真正想考察的点很多第一次看到这道题的同学第一反应是“直接排序不就行了”。在内存充足的前提下对10亿个数排序然后取前1000个当然是可以的。但问题就在这里题目明确限制了内存只有512MB而10亿个整数占4GB根本不可能一次性载入内存。就算你强行用虚拟内存频繁的缺页中断也会让程序慢到无法接受。所以这道题的第一个隐含考点就是你能不能意识到“单机全量排序不可行”。意识到这个之后你需要继续拆解问题并不需要全局有序只需要前1000个最大数。这个“只需要”三个字就是你优化空间的突破口。此外这道题还考察了沟通能力。面试官在听你讲方案的时候会故意设置一些模糊地带比如“如果数据量再翻10倍怎么办”“如果前1000个里面允许误差呢”。这些问题没有标准答案但你的应对方式会直接反映你对问题本质的理解深度。我在面试别人的时候最怕听到的就是应聘者背答案一旦追问几句就开始支支吾吾。真正的理解应该是面对追问时能够不断迭代自己的方案。2. 海量数据Top K的4种解法对比2.1 排序法最直观也最容易挂先说说最直觉的解法也就是全量排序。把4GB数据全部读入内存用快速排序或者归并排序整体排序然后取前1000个。这个方案的代码量确实很小大概十几行就能写完。但问题在于4GB的数据在512MB内存的机器上根本放不下。那如果退一步用外部排序呢外部排序的思路是把大文件切分成多个可以载入内存的小块分别排序后写入磁盘再通过多路归并的方式得到全局有序的结果。这个方案从理论上讲是可行的时间复杂度大约是O(n log n)但它有一个致命的问题——太慢了。以10亿条数据为例即使你用看起来很高效的多路归并磁盘IO的时间也会达到分钟级别这在笔试场景下是不可接受的。更重要的是排序法做了大量“无用功”。我们需要的只是前1000个最大值而排序会把剩下的9亿9千多万个元素的顺序也全部排好。这就好比你要在一个万人体育馆里找出最高的10个人理论上只需要把每个人量一下身高、打个标记而不需要让全体观众按身高排成一条长队。所以排序这个方案虽然正确但绝非最优。2.2 局部淘汰法朴素但清晰如果面试官让你在“排序法”和“更优解法”之间做一个过渡你最容易想到的思路就是局部淘汰法。具体做法是先读入前1000个数放到一个数组里然后遍历剩下的所有数。每遍历一个数就和当前数组里的最小值比较如果它比最小值大就替换掉最小值然后重新找出数组里的最小值。这个方案的优点是空间占用只有1000个整数也就是4KB完全无视内存限制。但它的缺点是时间复杂度偏高每处理一个新数都要在长度为1000的数组里线性扫描一遍找最小值整体复杂度是O(n×k)其中n是10亿k是1000。你可以算一下10亿乘以1000等于1万亿次比较这个时间足以让程序跑到天荒地老。局部淘汰法给我们的启发是它证明了用一个“固定大小的候选集合”来解决问题是可行的。接下来的问题就是如何高效地维护这个候选集合里的最小值这就自然而然引出了堆这个数据结构。2.3 最小堆解法面试的“标准答案”最小堆解法是这道题最经典、也最被面试官认可的答案。思路很简单维护一个容量为1000的最小堆也就是根节点永远是最小元素的完全二叉树。遍历10亿个数的时候对每个数执行“如果它比堆顶元素大就替换堆顶并调整堆”的操作。这样做的效果是遍历结束后留在堆里的1000个元素就是整个数据集中最大的1000个。因为堆顶是这个集合里的最小值任何比它更大的数都已经把它挤出去了。整个过程的建堆和维护复杂度是O(n log k)这里的k是1000log k大约是10。也就是说10亿个数只需要大概100亿次基本操作在C/C优化过的代码里是可以接受的。而且这个方案的空间占用依然只有O(k)也就是几百KB到几MB完全无视题目中的内存限制。更妙的是这个过程可以流式处理数据可以一个一个从磁盘读进来不需要一次性载入内存。我当年在笔试中写的就是这个方案面试官追问了几轮之后也认可了这是单机条件下的最优解。2.4 分治与哈希分流真正的大数据方案如果面试官继续加码说“现在数据量是100亿分布在一百台机器上你怎么算”这时候就要用到分治和哈希分流的思想了。最常用的方式是按数据的某种哈希规则把原始数据均匀切分到多台机器上每台机器在自己的分片数据上运行最小堆算法得出该分片的Top 1000。然后再把所有机器的Top 1000汇总到一台机器上再做一次Top 1000得到全局结果。这个方案的巧妙之处在于它利用了哈希的均匀性把一个大问题拆解成多个互不相交的小问题。每个小问题都可以用前面提到的单机解法解决最后合并的结果也是精确的。需要注意的是哈希函数的选择非常关键如果分布不均匀某台机器可能分到很多数据另一台却很闲最后总耗时取决于最慢的那台机器。分治和哈希分流的思想本质上和MapReduce是一致的。所以如果你能在面试中主动提到“这个方案可以很自然地扩展到MapReduce框架”会给面试官留下不错的好印象——说明你不是只会刷题而是真正理解大数据处理的基本范式。3. 最小堆解法详解与代码实现3.1 为什么最小堆而不是最大堆这是我在面试实习生时最喜欢追问的一个问题。很多同学能说出“用堆维护Top 1000”但当我问“为什么是堆顶为最小值的最小堆而不是堆顶为最大值的最大堆”时就答不上来了。原因其实很直接对于一个容量为k的堆堆顶就是当前这k个数的最小值。如果我们构建的是最大堆堆顶是最大值那新来的数无论多大只要不是比最大值大就无法通过堆顶比较决定它是否进入候选集合。这样一来新数必须和堆里的k个数逐一比较堆的效率就体现不出来了。从另一个角度理解最小堆像一个“淘汰机制”它总是把候选集合里最弱的一个暴露在根部任何一个新来的强者都可以直接挤掉它然后再通过调整恢复堆结构。这种“比堆顶大就替换”的策略保证了每次比较都只需要O(log k)的时间就能完成堆调整。而最大堆则像一个“守门员”它把最强的一个放在门口新来的挑战者反而要经过仔细检验才能挤进队伍。3.2 手写最小堆的完整实现下面这个例子是当年我在笔试中写的C版本。为了便于阅读我稍微做了些注释说明。核心逻辑分为两部分建堆遍历和堆调整。其中堆调整采用的是“下沉”方式从根节点开始与左右子节点中较小者交换直到满足最小堆性质。#include iostream #include fstream #include vector #include queue using namespace std; // 手写最小堆的调整过程root是当前需要下沉的节点下标 void siftDown(vectorlong long heap, int root, int len) { int child root * 2 1; while (child len) { // 在左右孩子中选出较小值对应的下标 if (child 1 len heap[child 1] heap[child]) { child 1; } // 如果当前节点已经比孩子小说明堆结构合理 if (heap[root] heap[child]) { break; } swap(heap[root], heap[child]); root child; child root * 2 1; } } int main() { const int K 1000; vectorlong long heap; heap.reserve(K); // 用模拟数据代替真实文件方便演示 // 实际场景中可以从文件流式读取10亿个整数 for (long long i 0; i 10000; i) { long long val (i * 131 7) % 1000000; // 模拟一个随机数 if (heap.size() K) { // 堆未满直接插入并向上调整 heap.push_back(val); push_heap(heap.begin(), heap.end(), greaterlong long()); } else { // 堆已满如果当前值比堆顶大就替换堆顶并下沉 if (val heap[0]) { heap[0] val; siftDown(heap, 0, K); } } } // 输出结果因为是最小堆需要把所有元素弹出才是降序 sort(heap.begin(), heap.end(), greaterlong long()); for (int num : heap) { cout num ; } cout endl; return 0; }这里有一个容易被忽略的细节C标准库中的push_heap默认构建的是最大堆如果你要构建最小堆需要传入greaterlong long()。但make_heap或者priority_queue的默认行为也是最大堆。为了避免混淆我在代码里选择了自己实现siftDown函数这样面试官看到的是我对堆原理的完整理解而不是对STL的简单调用。如果你对STL比较熟悉用priority_queuelong long, vectorlong long, greaterlong long会更简洁。但笔试时最好还是手写一遍原因有两个第一手写堆能体现数据结构功底第二有些公司的在线编译器可能对STL的支持有差异手写代码的移植性更好。3.3 复杂度分析与数据量估算现在来算一笔账。假设整数是32位也就是4字节。如果文件里存了10亿个数那么文件大小大约是4GB。我们的最小堆只需要维护1000个元素每个元素占4字节如果用long long就是8字节加上堆结构调整的临时空间总内存占用也就几十KB到几MB级别跟512MB的限制比起来可以忽略不计。时间方面堆顶替换和下沉操作的时间复杂度是O(log k)这里的k1000log2(1000)约等于10。最坏情况下10亿个数里每一个都比堆顶大每一轮都需要做10次左右的比较和交换总操作数大约在100亿级别。你可能觉得100亿听起来很多但实际上CPU每秒可以执行几十亿次简单操作加上C编译器的优化单机跑完这个流程也就是几十秒到一两分钟的事。如果你使用priority_queue它的底层实现也是堆复杂度完全一致。但有一点要注意priority_queue的push和pop是分开的如果你要替换堆顶需要先pop再push这会产生不必要的堆调整。相比之下直接改写根节点再下沉效率会更高。这类微小的优化在笔试中未必能拉开差距但在工程的高性能场景下是实打实的。4. 从附加题到真实业务Top K的工程化落地4.1 搜索引擎里的Top K你可能会觉得这种题目是不是只存在于笔试中真到了公司里根本用不上恰恰相反Top K问题在搜索引擎里几乎是“家常便饭”。比如用户在搜索框中输入“北京美食”后搜索引擎需要从海量的网页索引中快速找出与这个查询相关性最高的前10个网页。这个过程的本质就是Top K只不过分数不是整数而是相关性评分。在实际系统中相关性评分往往由多个因素加权计算包括词频、网页权重、用户地理位置、点击历史等。这些分数的计算可以在倒排索引遍历阶段完成然后把计算好的分数送入一个容量为10的堆结构中始终保持堆里是当前最优的10个结果。这样做的目的和笔试是一样的避免对所有候选结果做全量排序因为一次搜索可能召回几十万甚至上百万个候选结果全量排序的延迟完全不可接受。我之前在一家搜索相关的公司实习时有一次需要优化搜索接口的耗时。排查发现排名模块为了简便直接调用了std::sort对召回结果排序而召回量经常达到几十万量级。后来我把它改成了优先队列维护Top 50耗时直接降了一个数量级。这件小事让我意识到笔试中的那道附加题本质上就是在为这类场景做准备。4.2 用户行为日志中的高频词统计另一个典型的业务场景是统计用户行为日志里的高频词。比如产品经理想知道最近一天用户搜索的关键词Top 100用来做运营活动。这时候数据来源是海量日志可能一天的日志就有几百GB。由于单个关键词出现的次数是有限的可以先用哈希表做词频统计然后对词频执行Top K操作。在某些分布式中台框架比如MapReduce里思路会变成Map阶段读取日志输出关键词和计数1Reduce阶段对同一个关键词的计数相加得到总词频最后再用一个单独的作业做Top K。这个流程的逻辑框架和我在第2.4节里讲的分治与哈希分流方案如出一辙。所以你可以把这道附加题理解为一个大数据的微缩模型核心思路不变只是数据规模从“单机10亿个整数”放大到了“集群上的几百GB日志”。4.3 分布式场景下的两层Top K如果数据量大到单机无法处理就需要引入分布式架构。常见的做法是两层Top K第一层每台机器读取一部分数据用最小堆求出本机的Top K第二层把每台机器的Top K结果汇总到一台合并机上再次用最小堆求出全局Top K。这样做的数学依据是全局最大值一定会在某个分片的Top K里所以收集所有分片的Top K结果不会丢失全局最优解。这里有一个容易踩的坑如果你的目标是Top 1000但每台机器只返回Top 1000在极端情况下两台机器可能把某个并不属于全局Top 1000的元素都返回了。这是允许的因为合并阶段会再做一次完整的排序或堆选择最终只保留前1000个。但如果每台机器返回的数量小于目标值比如只返回Top 100那在分片不均匀的情况下就可能漏掉真正的全局Top 1000。所以“每台机器返回Top KK等于或大于目标值”是一个安全法则。在真实业界常提到的“两层 Top K”思想和 MapReduce 的作业流程很像你可以把它说成一个简化版的归并思路。如果面试官继续追问数据倾斜怎么办你可以回答增加一个哈希预分区步骤让相同的关键字尽量落在同一台机器上避免某个关键词在每台机器都出现导致的过度计数。这些细节在面试中会是非常加分的表现。5. 常见问题与解题误区5.1 内存估算容易踩的坑很多人在计算内存时只考虑了存储数据本身的空间。但如果你用vectorlong long存10亿个数每个long long在64位系统上占8字节总空间就变成了80GB比4GB还要大得多。所以在真实的笔试环境里如果要处理10亿个数应该用int或int32_t除非数值范围确实超过32位。堆结构本身的内存也不能忽略。虽然理论上只需要1000个元素但STL的vector扩容会预留capacity这个容量一般比size稍大。幸运的是堆的大小只有1000即使capacity翻倍到2000也才8KB不会对整体内存有任何压力。真正需要谨慎的是读取文件时的缓冲区有些人喜欢一次性读入一大块数据到内存里这在数据量大的时候可能会让内存瞬间飙升。流式读取每次只处理一小块才是最安全的。如果你在写代码的时候使用了递归算法来解决某个子问题比如某些分治方案还需要留意递归栈的深度。10亿级别的数据如果处理不当递归层数可能非常深导致栈溢出。虽然最小堆方案本身没有递归但一旦你扩展思路到分治就一定要把栈深度考虑进去。5.2 时间复杂度分析容易错的点对于最小堆方案很多人会简单地说“复杂度是O(n log k)”然后就不再继续了。但如果面试官追问“为什么不是O(n log n)”你至少要能答出因为k远小于nlog k是一个常数级别的因子。具体来说n10亿k1000log k≈10所以整体复杂度相当于O(10n)接近线性。如果写成O(n log n)在实际运行中会慢几百倍。另一个容易出错的点是忘记考虑建堆的复杂度。前1000个元素插入堆时如果每个元素都调用一次push_heap单次复杂度是O(log p)其中p是当前堆的大小累计复杂度是O(k log k)。幸好k很小这个开销可以忽略不计。如果你一次性对1000个元素调用make_heap整体复杂度是O(k)也就是线性建堆。两种方式都可行但如果你想展示更扎实的功底可以说出“线性建堆”这个知识点。时间估算的时候也不要只算CPU的时间。真实场景里最大的瓶颈其实是磁盘IO。从4GB的文件里读取10亿个数即使以每秒1GB的读取速度也要4秒钟。如果这台机器磁盘性能一般读取耗时会远高于计算耗时。所以在方案设计中减少磁盘随机读写、尽量顺序读往往比优化堆调整更重要。5.3 边界条件与异常处理我在面试别人的时候发现不少同学代码写得很流畅但一问边界条件就哑了。比如如果文件里的整数数量本身就不到1000个呢这时候堆永远填不满最后输出的就是全部数据。代码中需要判断堆是否已满避免在堆未满时执行“替换堆顶”的逻辑。再比如如果数据里面有重复值怎么办最小堆的处理方式对重复值是天然正确的。假设所有值都是同一个数那么堆里的元素都相等堆顶替换条件“val heap[0]”永远不会为真最后输出的堆里装的就是这个数本身。这个输出在数学上是正确的但如果你希望输出“不同的Top K”那就需要额外引入去重逻辑比如用哈希集合或者先对所有值做一次哈希去重。这个问题在面试现场很容易被问到提前想好回答思路会让你显得更有经验。还有文件读取异常的问题。如果文件指针走到了末尾或者文件损坏导致数据不完整代码要能优雅退出而不是直接崩溃。在实际生产代码里这类异常处理往往占了很大篇幅但在笔试中你只需要在关键位置加上判断即可。过度沉迷于异常处理反而会让代码变得冗长在有限时间内得不偿失。6. 这道题背后百度在选什么样的人6.1 从题目风格看公司技术文化百度作为国内搜索引擎的代表公司日常业务处理的数据量非常庞大。这道附加题的设计其实反映了百度对工程师的核心要求之一在海量数据面前不能慌不能蛮干而是要把问题进行合理的抽象和简化。你可以不会背红黑树的实现细节但你必须对数据规模有敏锐的直觉知道什么时候该用堆什么时候该用哈希。从另一个角度讲这题也透露出百度希望实习生具备“工程落地”意识。你不仅仅要给出理论上的最优算法还要考虑磁盘IO、内存限制、代码稳定性这些真实因素。这和学校里的算法课很不一样算法课上的输入规模通常是几千到几万而真实业务里动辄百万、千万甚至上亿。如果你能从笔试阶段就开始建立这种规模意识对以后的工作会有很大帮助。6.2 判断候选人潜力的核心标准我看到过很多候选人在讲这道题的时候会提到“我用过Hadoop”“我做过大数据项目”。但真正的加分项不在于你用过什么框架而在于你能不能清楚地说出背后的原理。比如为什么MapReduce适合处理这类问题因为Map阶段天然做了分片和并行Reduce阶段做了合并这正好对应了分治和Top K合并的流程。如果你能说清楚这一层说明你不是只会调用API而是理解了分布式计算的本质。另外一个容易被忽略的点是态度。附加题之所以叫附加题通常意味着有一定难度面试官不期待你百分之百答对。你愿意主动思考、大胆给出方案并在追问中不断修正自己这种积极解决问题的状态往往比正确答案更打动面试官。我在面试中更喜欢看到候选人犯一个错误后能快速反应、自我修正的过程这比全程顺利更真实。6.3 对你备战校招的几点建议如果你现在正在准备实习招聘我建议你除了刷题也多花点时间做“数据规模估算”的训练。比如看到任何一个系统试着估算一下它的日活和每天产生的数据量然后想一想如果让你处理这些数据内存够不够要不要分片用什么样的数据结构最合适这种习惯会慢慢培养起你“下意识考虑扩展性”的思维方式。最后我个人踩过几次坑之后最深的体会是笔试中最重要的不是写得多花哨而是“稳”。把最小堆方案写得清晰、完整把复杂度算明白对边界条件有清晰的交代就已经能超过绝大多数候选人了。在那个基础上如果能主动讨论分治扩展和分布式场景那就是可以给面试官留下“这人有潜力”印象的加分项。这道附加题虽然简单朴素但它的价值绝不止于一场笔试。 海量数据Top K问题解析：内存受限下的最小堆解法
去年春招的时候很多师弟师妹跑来问我百度实习生的笔试该怎么准备。我翻出当年自己做过的题单发现那道附加题放在今天看依然是很有代表性的海量数据考题给你一个包含大量整数的数据文件假设有10亿个整数内存只有几百MB要求找出其中最大的1000个数。题目看似简单却能在“内存受限”这个条件下刷掉一大半人。这篇文章就把这道题从头到尾拆透包括我自己的解题过程和踩过的坑希望能帮到正在准备大厂实习面试的朋友。1. 题目还原与考点拆解1.1 题目原貌百度2015春季实习生招聘的这道附加题核心描述大致是这样的有一个二进制文件里面按顺序存储了10亿个32位整数也就是大概4GB的数据量。现在给你一台内存只有512MB的机器要求用尽可能快的方式输出其中最大的1000个数。需要注意的是这道题在当时并不是独立出现的而是作为整套笔试题的附加部分。和前面的基础算法题不同附加题往往没有标准答案面试官更看重你的思考过程。也正因为如此它其实是一个非常好的“压力测试”题目你只有在有限的内存条件和时间限制下拿出一个可行且高效的方案才能让面试官眼前一亮。为什么我说这道题有代表性因为它同时考察了三个层面的能力第一对基础数据结构的掌握比如堆、分治这些概念第二对真实硬件环境的理解也就是内存、磁盘IO的取舍第三对工程化方案的敏感度能不能从“做题家”思维切换到“解决实际问题”的思维。这三个层面恰恰是大厂招聘实习生时最看重的素质。1.2 面试官真正想考察的点很多第一次看到这道题的同学第一反应是“直接排序不就行了”。在内存充足的前提下对10亿个数排序然后取前1000个当然是可以的。但问题就在这里题目明确限制了内存只有512MB而10亿个整数占4GB根本不可能一次性载入内存。就算你强行用虚拟内存频繁的缺页中断也会让程序慢到无法接受。所以这道题的第一个隐含考点就是你能不能意识到“单机全量排序不可行”。意识到这个之后你需要继续拆解问题并不需要全局有序只需要前1000个最大数。这个“只需要”三个字就是你优化空间的突破口。此外这道题还考察了沟通能力。面试官在听你讲方案的时候会故意设置一些模糊地带比如“如果数据量再翻10倍怎么办”“如果前1000个里面允许误差呢”。这些问题没有标准答案但你的应对方式会直接反映你对问题本质的理解深度。我在面试别人的时候最怕听到的就是应聘者背答案一旦追问几句就开始支支吾吾。真正的理解应该是面对追问时能够不断迭代自己的方案。2. 海量数据Top K的4种解法对比2.1 排序法最直观也最容易挂先说说最直觉的解法也就是全量排序。把4GB数据全部读入内存用快速排序或者归并排序整体排序然后取前1000个。这个方案的代码量确实很小大概十几行就能写完。但问题在于4GB的数据在512MB内存的机器上根本放不下。那如果退一步用外部排序呢外部排序的思路是把大文件切分成多个可以载入内存的小块分别排序后写入磁盘再通过多路归并的方式得到全局有序的结果。这个方案从理论上讲是可行的时间复杂度大约是O(n log n)但它有一个致命的问题——太慢了。以10亿条数据为例即使你用看起来很高效的多路归并磁盘IO的时间也会达到分钟级别这在笔试场景下是不可接受的。更重要的是排序法做了大量“无用功”。我们需要的只是前1000个最大值而排序会把剩下的9亿9千多万个元素的顺序也全部排好。这就好比你要在一个万人体育馆里找出最高的10个人理论上只需要把每个人量一下身高、打个标记而不需要让全体观众按身高排成一条长队。所以排序这个方案虽然正确但绝非最优。2.2 局部淘汰法朴素但清晰如果面试官让你在“排序法”和“更优解法”之间做一个过渡你最容易想到的思路就是局部淘汰法。具体做法是先读入前1000个数放到一个数组里然后遍历剩下的所有数。每遍历一个数就和当前数组里的最小值比较如果它比最小值大就替换掉最小值然后重新找出数组里的最小值。这个方案的优点是空间占用只有1000个整数也就是4KB完全无视内存限制。但它的缺点是时间复杂度偏高每处理一个新数都要在长度为1000的数组里线性扫描一遍找最小值整体复杂度是O(n×k)其中n是10亿k是1000。你可以算一下10亿乘以1000等于1万亿次比较这个时间足以让程序跑到天荒地老。局部淘汰法给我们的启发是它证明了用一个“固定大小的候选集合”来解决问题是可行的。接下来的问题就是如何高效地维护这个候选集合里的最小值这就自然而然引出了堆这个数据结构。2.3 最小堆解法面试的“标准答案”最小堆解法是这道题最经典、也最被面试官认可的答案。思路很简单维护一个容量为1000的最小堆也就是根节点永远是最小元素的完全二叉树。遍历10亿个数的时候对每个数执行“如果它比堆顶元素大就替换堆顶并调整堆”的操作。这样做的效果是遍历结束后留在堆里的1000个元素就是整个数据集中最大的1000个。因为堆顶是这个集合里的最小值任何比它更大的数都已经把它挤出去了。整个过程的建堆和维护复杂度是O(n log k)这里的k是1000log k大约是10。也就是说10亿个数只需要大概100亿次基本操作在C/C优化过的代码里是可以接受的。而且这个方案的空间占用依然只有O(k)也就是几百KB到几MB完全无视题目中的内存限制。更妙的是这个过程可以流式处理数据可以一个一个从磁盘读进来不需要一次性载入内存。我当年在笔试中写的就是这个方案面试官追问了几轮之后也认可了这是单机条件下的最优解。2.4 分治与哈希分流真正的大数据方案如果面试官继续加码说“现在数据量是100亿分布在一百台机器上你怎么算”这时候就要用到分治和哈希分流的思想了。最常用的方式是按数据的某种哈希规则把原始数据均匀切分到多台机器上每台机器在自己的分片数据上运行最小堆算法得出该分片的Top 1000。然后再把所有机器的Top 1000汇总到一台机器上再做一次Top 1000得到全局结果。这个方案的巧妙之处在于它利用了哈希的均匀性把一个大问题拆解成多个互不相交的小问题。每个小问题都可以用前面提到的单机解法解决最后合并的结果也是精确的。需要注意的是哈希函数的选择非常关键如果分布不均匀某台机器可能分到很多数据另一台却很闲最后总耗时取决于最慢的那台机器。分治和哈希分流的思想本质上和MapReduce是一致的。所以如果你能在面试中主动提到“这个方案可以很自然地扩展到MapReduce框架”会给面试官留下不错的好印象——说明你不是只会刷题而是真正理解大数据处理的基本范式。3. 最小堆解法详解与代码实现3.1 为什么最小堆而不是最大堆这是我在面试实习生时最喜欢追问的一个问题。很多同学能说出“用堆维护Top 1000”但当我问“为什么是堆顶为最小值的最小堆而不是堆顶为最大值的最大堆”时就答不上来了。原因其实很直接对于一个容量为k的堆堆顶就是当前这k个数的最小值。如果我们构建的是最大堆堆顶是最大值那新来的数无论多大只要不是比最大值大就无法通过堆顶比较决定它是否进入候选集合。这样一来新数必须和堆里的k个数逐一比较堆的效率就体现不出来了。从另一个角度理解最小堆像一个“淘汰机制”它总是把候选集合里最弱的一个暴露在根部任何一个新来的强者都可以直接挤掉它然后再通过调整恢复堆结构。这种“比堆顶大就替换”的策略保证了每次比较都只需要O(log k)的时间就能完成堆调整。而最大堆则像一个“守门员”它把最强的一个放在门口新来的挑战者反而要经过仔细检验才能挤进队伍。3.2 手写最小堆的完整实现下面这个例子是当年我在笔试中写的C版本。为了便于阅读我稍微做了些注释说明。核心逻辑分为两部分建堆遍历和堆调整。其中堆调整采用的是“下沉”方式从根节点开始与左右子节点中较小者交换直到满足最小堆性质。#include iostream #include fstream #include vector #include queue using namespace std; // 手写最小堆的调整过程root是当前需要下沉的节点下标 void siftDown(vectorlong long heap, int root, int len) { int child root * 2 1; while (child len) { // 在左右孩子中选出较小值对应的下标 if (child 1 len heap[child 1] heap[child]) { child 1; } // 如果当前节点已经比孩子小说明堆结构合理 if (heap[root] heap[child]) { break; } swap(heap[root], heap[child]); root child; child root * 2 1; } } int main() { const int K 1000; vectorlong long heap; heap.reserve(K); // 用模拟数据代替真实文件方便演示 // 实际场景中可以从文件流式读取10亿个整数 for (long long i 0; i 10000; i) { long long val (i * 131 7) % 1000000; // 模拟一个随机数 if (heap.size() K) { // 堆未满直接插入并向上调整 heap.push_back(val); push_heap(heap.begin(), heap.end(), greaterlong long()); } else { // 堆已满如果当前值比堆顶大就替换堆顶并下沉 if (val heap[0]) { heap[0] val; siftDown(heap, 0, K); } } } // 输出结果因为是最小堆需要把所有元素弹出才是降序 sort(heap.begin(), heap.end(), greaterlong long()); for (int num : heap) { cout num ; } cout endl; return 0; }这里有一个容易被忽略的细节C标准库中的push_heap默认构建的是最大堆如果你要构建最小堆需要传入greaterlong long()。但make_heap或者priority_queue的默认行为也是最大堆。为了避免混淆我在代码里选择了自己实现siftDown函数这样面试官看到的是我对堆原理的完整理解而不是对STL的简单调用。如果你对STL比较熟悉用priority_queuelong long, vectorlong long, greaterlong long会更简洁。但笔试时最好还是手写一遍原因有两个第一手写堆能体现数据结构功底第二有些公司的在线编译器可能对STL的支持有差异手写代码的移植性更好。3.3 复杂度分析与数据量估算现在来算一笔账。假设整数是32位也就是4字节。如果文件里存了10亿个数那么文件大小大约是4GB。我们的最小堆只需要维护1000个元素每个元素占4字节如果用long long就是8字节加上堆结构调整的临时空间总内存占用也就几十KB到几MB级别跟512MB的限制比起来可以忽略不计。时间方面堆顶替换和下沉操作的时间复杂度是O(log k)这里的k1000log2(1000)约等于10。最坏情况下10亿个数里每一个都比堆顶大每一轮都需要做10次左右的比较和交换总操作数大约在100亿级别。你可能觉得100亿听起来很多但实际上CPU每秒可以执行几十亿次简单操作加上C编译器的优化单机跑完这个流程也就是几十秒到一两分钟的事。如果你使用priority_queue它的底层实现也是堆复杂度完全一致。但有一点要注意priority_queue的push和pop是分开的如果你要替换堆顶需要先pop再push这会产生不必要的堆调整。相比之下直接改写根节点再下沉效率会更高。这类微小的优化在笔试中未必能拉开差距但在工程的高性能场景下是实打实的。4. 从附加题到真实业务Top K的工程化落地4.1 搜索引擎里的Top K你可能会觉得这种题目是不是只存在于笔试中真到了公司里根本用不上恰恰相反Top K问题在搜索引擎里几乎是“家常便饭”。比如用户在搜索框中输入“北京美食”后搜索引擎需要从海量的网页索引中快速找出与这个查询相关性最高的前10个网页。这个过程的本质就是Top K只不过分数不是整数而是相关性评分。在实际系统中相关性评分往往由多个因素加权计算包括词频、网页权重、用户地理位置、点击历史等。这些分数的计算可以在倒排索引遍历阶段完成然后把计算好的分数送入一个容量为10的堆结构中始终保持堆里是当前最优的10个结果。这样做的目的和笔试是一样的避免对所有候选结果做全量排序因为一次搜索可能召回几十万甚至上百万个候选结果全量排序的延迟完全不可接受。我之前在一家搜索相关的公司实习时有一次需要优化搜索接口的耗时。排查发现排名模块为了简便直接调用了std::sort对召回结果排序而召回量经常达到几十万量级。后来我把它改成了优先队列维护Top 50耗时直接降了一个数量级。这件小事让我意识到笔试中的那道附加题本质上就是在为这类场景做准备。4.2 用户行为日志中的高频词统计另一个典型的业务场景是统计用户行为日志里的高频词。比如产品经理想知道最近一天用户搜索的关键词Top 100用来做运营活动。这时候数据来源是海量日志可能一天的日志就有几百GB。由于单个关键词出现的次数是有限的可以先用哈希表做词频统计然后对词频执行Top K操作。在某些分布式中台框架比如MapReduce里思路会变成Map阶段读取日志输出关键词和计数1Reduce阶段对同一个关键词的计数相加得到总词频最后再用一个单独的作业做Top K。这个流程的逻辑框架和我在第2.4节里讲的分治与哈希分流方案如出一辙。所以你可以把这道附加题理解为一个大数据的微缩模型核心思路不变只是数据规模从“单机10亿个整数”放大到了“集群上的几百GB日志”。4.3 分布式场景下的两层Top K如果数据量大到单机无法处理就需要引入分布式架构。常见的做法是两层Top K第一层每台机器读取一部分数据用最小堆求出本机的Top K第二层把每台机器的Top K结果汇总到一台合并机上再次用最小堆求出全局Top K。这样做的数学依据是全局最大值一定会在某个分片的Top K里所以收集所有分片的Top K结果不会丢失全局最优解。这里有一个容易踩的坑如果你的目标是Top 1000但每台机器只返回Top 1000在极端情况下两台机器可能把某个并不属于全局Top 1000的元素都返回了。这是允许的因为合并阶段会再做一次完整的排序或堆选择最终只保留前1000个。但如果每台机器返回的数量小于目标值比如只返回Top 100那在分片不均匀的情况下就可能漏掉真正的全局Top 1000。所以“每台机器返回Top KK等于或大于目标值”是一个安全法则。在真实业界常提到的“两层 Top K”思想和 MapReduce 的作业流程很像你可以把它说成一个简化版的归并思路。如果面试官继续追问数据倾斜怎么办你可以回答增加一个哈希预分区步骤让相同的关键字尽量落在同一台机器上避免某个关键词在每台机器都出现导致的过度计数。这些细节在面试中会是非常加分的表现。5. 常见问题与解题误区5.1 内存估算容易踩的坑很多人在计算内存时只考虑了存储数据本身的空间。但如果你用vectorlong long存10亿个数每个long long在64位系统上占8字节总空间就变成了80GB比4GB还要大得多。所以在真实的笔试环境里如果要处理10亿个数应该用int或int32_t除非数值范围确实超过32位。堆结构本身的内存也不能忽略。虽然理论上只需要1000个元素但STL的vector扩容会预留capacity这个容量一般比size稍大。幸运的是堆的大小只有1000即使capacity翻倍到2000也才8KB不会对整体内存有任何压力。真正需要谨慎的是读取文件时的缓冲区有些人喜欢一次性读入一大块数据到内存里这在数据量大的时候可能会让内存瞬间飙升。流式读取每次只处理一小块才是最安全的。如果你在写代码的时候使用了递归算法来解决某个子问题比如某些分治方案还需要留意递归栈的深度。10亿级别的数据如果处理不当递归层数可能非常深导致栈溢出。虽然最小堆方案本身没有递归但一旦你扩展思路到分治就一定要把栈深度考虑进去。5.2 时间复杂度分析容易错的点对于最小堆方案很多人会简单地说“复杂度是O(n log k)”然后就不再继续了。但如果面试官追问“为什么不是O(n log n)”你至少要能答出因为k远小于nlog k是一个常数级别的因子。具体来说n10亿k1000log k≈10所以整体复杂度相当于O(10n)接近线性。如果写成O(n log n)在实际运行中会慢几百倍。另一个容易出错的点是忘记考虑建堆的复杂度。前1000个元素插入堆时如果每个元素都调用一次push_heap单次复杂度是O(log p)其中p是当前堆的大小累计复杂度是O(k log k)。幸好k很小这个开销可以忽略不计。如果你一次性对1000个元素调用make_heap整体复杂度是O(k)也就是线性建堆。两种方式都可行但如果你想展示更扎实的功底可以说出“线性建堆”这个知识点。时间估算的时候也不要只算CPU的时间。真实场景里最大的瓶颈其实是磁盘IO。从4GB的文件里读取10亿个数即使以每秒1GB的读取速度也要4秒钟。如果这台机器磁盘性能一般读取耗时会远高于计算耗时。所以在方案设计中减少磁盘随机读写、尽量顺序读往往比优化堆调整更重要。5.3 边界条件与异常处理我在面试别人的时候发现不少同学代码写得很流畅但一问边界条件就哑了。比如如果文件里的整数数量本身就不到1000个呢这时候堆永远填不满最后输出的就是全部数据。代码中需要判断堆是否已满避免在堆未满时执行“替换堆顶”的逻辑。再比如如果数据里面有重复值怎么办最小堆的处理方式对重复值是天然正确的。假设所有值都是同一个数那么堆里的元素都相等堆顶替换条件“val heap[0]”永远不会为真最后输出的堆里装的就是这个数本身。这个输出在数学上是正确的但如果你希望输出“不同的Top K”那就需要额外引入去重逻辑比如用哈希集合或者先对所有值做一次哈希去重。这个问题在面试现场很容易被问到提前想好回答思路会让你显得更有经验。还有文件读取异常的问题。如果文件指针走到了末尾或者文件损坏导致数据不完整代码要能优雅退出而不是直接崩溃。在实际生产代码里这类异常处理往往占了很大篇幅但在笔试中你只需要在关键位置加上判断即可。过度沉迷于异常处理反而会让代码变得冗长在有限时间内得不偿失。6. 这道题背后百度在选什么样的人6.1 从题目风格看公司技术文化百度作为国内搜索引擎的代表公司日常业务处理的数据量非常庞大。这道附加题的设计其实反映了百度对工程师的核心要求之一在海量数据面前不能慌不能蛮干而是要把问题进行合理的抽象和简化。你可以不会背红黑树的实现细节但你必须对数据规模有敏锐的直觉知道什么时候该用堆什么时候该用哈希。从另一个角度讲这题也透露出百度希望实习生具备“工程落地”意识。你不仅仅要给出理论上的最优算法还要考虑磁盘IO、内存限制、代码稳定性这些真实因素。这和学校里的算法课很不一样算法课上的输入规模通常是几千到几万而真实业务里动辄百万、千万甚至上亿。如果你能从笔试阶段就开始建立这种规模意识对以后的工作会有很大帮助。6.2 判断候选人潜力的核心标准我看到过很多候选人在讲这道题的时候会提到“我用过Hadoop”“我做过大数据项目”。但真正的加分项不在于你用过什么框架而在于你能不能清楚地说出背后的原理。比如为什么MapReduce适合处理这类问题因为Map阶段天然做了分片和并行Reduce阶段做了合并这正好对应了分治和Top K合并的流程。如果你能说清楚这一层说明你不是只会调用API而是理解了分布式计算的本质。另外一个容易被忽略的点是态度。附加题之所以叫附加题通常意味着有一定难度面试官不期待你百分之百答对。你愿意主动思考、大胆给出方案并在追问中不断修正自己这种积极解决问题的状态往往比正确答案更打动面试官。我在面试中更喜欢看到候选人犯一个错误后能快速反应、自我修正的过程这比全程顺利更真实。6.3 对你备战校招的几点建议如果你现在正在准备实习招聘我建议你除了刷题也多花点时间做“数据规模估算”的训练。比如看到任何一个系统试着估算一下它的日活和每天产生的数据量然后想一想如果让你处理这些数据内存够不够要不要分片用什么样的数据结构最合适这种习惯会慢慢培养起你“下意识考虑扩展性”的思维方式。最后我个人踩过几次坑之后最深的体会是笔试中最重要的不是写得多花哨而是“稳”。把最小堆方案写得清晰、完整把复杂度算明白对边界条件有清晰的交代就已经能超过绝大多数候选人了。在那个基础上如果能主动讨论分治扩展和分布式场景那就是可以给面试官留下“这人有潜力”印象的加分项。这道附加题虽然简单朴素但它的价值绝不止于一场笔试。