百度大数据笔试卷复盘：TopK、MapReduce与系统设计要点解析

每年春招秋招的时候都有不少准备面大数据岗的同学翻出各类大厂真题来刷。这之中百度2015年的大数据云计算研发笔试卷虽然是十年前的老题但在我看来吃透它的价值一点不比刷那些新题小。原因很简单那几年恰好是大数据技术栈从Hadoop一家独大走向Spark、Storm百花齐放的关键转折期大厂的出题思路非常集中地落在“懂原理、能编码、会设计”三个维度上题型也足够典型。这篇文章就带你把这份卷子从头到尾复盘一遍顺带聊聊当年我们是怎么被它“教做人”的。百度这套笔试卷基本锁定的是Hadoop生态相关岗位覆盖算法、Java基础、HDFS/MapReduce原理、SQL能力、系统设计五个块面。无论你现在是准备校招还是想系统补一补大数据基础这份卷子的考点都值得逐个过一遍。下面直接按题型和考察逻辑拆开讲。1. 岗位考察逻辑从一份试卷反推大厂要什么人1.1 大数据岗位的能力模型不管招聘JD上怎么包装2015年前后百度大数据云计算研发岗要的人底层能力模型是很清晰的。我把它拆成三块来看第一块是计算机基础。数据结构、算法、操作系统、网络这部分和通用后端岗的考察没有本质区别。原因很简单大数据研发本质上是分布式系统研发Java虚拟机怎么管理内存、网络通信怎么走的、进程和线程怎么协同这些底层认知决定了你在面对集群规模增长时是“能调优”还是“只能重启”。百度的卷子在这一块从来不会含糊选择题和简答题都有覆盖。第二块是分布式与大数据组件原理。这一点是核心分水岭。当年很多候选人能熟练跑HiveQL、能提交Spark任务但对HDFS的副本放置策略、MapReduce的Shuffle细节讲不清楚。而大厂恰恰最看重这部分——因为生产环境里你遇到的绝大多数问题比如数据倾斜、小文件过多、Reduce端OOM都需要用原理去反推解决方案光会调API解决不了问题。第三块是代码与工程设计能力。笔试中手写代码是必须的而且数据结构和算法题所占分值通常最高。大数据场景下的算法题又很有特点刷过LeetCode常规题还不够得有海量数据处理的思维比如Top K、去重、排序这几种经典问题用什么数据结构、多大内存能装下、时间复杂度如何都要能在短时间内给出合理方案。1.2 试卷结构与时间分配我记忆里这套卷子大致可以分成客观题和主观题两大部分。客观题以单选和多选为主覆盖Java语法、集合类、并发编程、TCP/IP协议、Linux基础命令等主观题包括手写算法、MapReduce原理简答、SQL查询编写以及一道开放性系统设计题。整套卷子的时间一般是120分钟左右但实际上在考场里能把所有题都完整答完的人非常少。主要原因是主观题的书写量很大尤其是手写代码题一行行写下来非常耗时。我当年就吃过这个亏前面选择题纠结太久到后面系统设计题只能草草写几百字收场现在回过头看时间分配是有明确策略的客观题控制在40分钟以内算法题留50分钟原理和SQL题25分钟最后设计题至少留20分钟。2. 基础功底的考察算法与Java核心2.1 手写Top K大数据场景最核心的算法这份卷子的算法题里最有代表性的一道是给定一个包含几十亿整数的文件每一行一个数内存只有2GB如何找出其中最大的100个数。这道题考察的就是经典的Top K问题。在当时的技术语境下标准解法是维护一个大小为K的最小堆。遍历所有数据的过程中如果堆还满着就直接插入如果当前数比堆顶即当前最小的那个候选数大就替换堆顶并做一次堆化。这样一趟扫描下来时间复杂度是O(n log K)空间复杂度只有O(K)。public class TopK { public static int[] findTopK(int[] nums, int k) { // Java PriorityQueue默认是小顶堆正好符合需求 QueueInteger minHeap new PriorityQueue(k); for (int num : nums) { if (minHeap.size() k) { minHeap.offer(num); } else if (num minHeap.peek()) { minHeap.poll(); minHeap.offer(num); } } int[] result new int[k]; for (int i k - 1; i 0; i--) { result[i] minHeap.poll(); } return result; } }注意这里K是100所以堆是完全能放进内存的。但如果是找出Top十亿这种极端情况堆方案就不行了得换成外排序或者更复杂的分布式方案。我当时在卷子上批注了一句如果数据量极大、K也很大可以分段排序后做多路归并每段排序后取前K个最后归并时继续剪枝。这道题其实还有一类变种数据不是静态文件而是无限流式到达要求随时能快速返回当前已经见过的数据中Top K是什么。这种场景下堆结构依然是正解因为它天然支持动态插入和弹出不需要事先把所有数据都存下来。2.2 Java集合与并发HashMap和线程池笔试选择题里有个高频考点HashMap在多线程环境下会有什么问题。2015年那会儿JDK 8还没完全普及很多线上环境还是JDK 7HashMap在并发扩容时可能形成环形链表导致下一次查询时CPU飙到100%这个经典的线上事故在面试题里反复出现。标准答法是多线程环境下使用ConcurrentHashMap它在JDK 7里采用Segment分段锁设计JDK 8后改成了CAS加synchronized锁桶头节点读操作基本无锁性能提升明显。另一个高频考题是线程池参数。比如一个线程池核心线程数是5最大线程数是10队列容量是100当第200个任务同时提交过来时会发生什么。这个题考察ThreadPoolExecutor的执行逻辑先尝试让核心线程执行核心线程满后任务进队列队列满了才创建新线程直到最大线程数再满就执行拒绝策略。很多人的误区是把“最大线程数”当成“并发上限”实际上队列容量这个中间缓冲层才是最容易忽略的环节。我当年在这类题上吃过亏后来养成一个习惯看集合类和并发源码时不只是记结论而是亲手模拟一遍极端情况比如单线程反复put触发扩容、多线程同时put看丢数据效果。纸上得来终觉浅这句话在并发编程学习上尤其成立。2.3 操作系统与网络基础卷子里还出现了不少操作系统和网络基础题。比如进程和线程的本质区别是什么TCP三次握手为什么不能是两次select、poll、epoll的区别是什么。这些题现在看很基础但对大数据岗位来说它们直接关联到日常调优比如你写MapReduce时调整map数量本质上就是在调整进程和线程的调度模型你排查HDFS写慢的问题很多时候瓶颈就出在TCP窗口和网络缓冲区上。3. 大数据专项Hadoop生态原理拆解3.1 HDFS写入流程与副本机制客观题和简答题里几乎必考HDFS的写入流程。百度的卷子问得更细一些会要求描述“客户端写一个文件到HDFSNameNode和DataNode分别做了什么”。完整的流程我来捋一遍。客户端先调用DistributedFileSystem的create方法远程调用NameNode的RPC接口NameNode检查权限和路径是否合法然后在文件系统元数据中注册这个新文件条目返回一个FSDataOutputStream。客户端开始写第一个block时NameNode根据机架感知策略返回一个DataNode列表这个列表决定了副本放置的位置。副本放置策略是另一个必考点。默认副本数是3第一个副本放在客户端所在节点上如果客户端不在集群内就随机选一个节点第二个副本放在与第一个副本不同机架的某个节点上第三个副本放在与第二个副本同机架、但也尽量与第一个副本不同节点的位置。这样设计是为了平衡容错和写入性能跨机架副本保证单机架故障数据不丢同时两个副本在同一机架又减少了跨机架流量。写入时客户端逐个向DataNode传输packetDataNode之间用pipeline方式接力写入每写一个packet就返回一个ack。客户端等所有副本都确认收到后才继续写下一个packet。最后一个block写完后客户端调用close彻底关闭流NameNode在元数据里把文件状态标记为已完成。3.2 MapReduce Shuffle全流程叙述Shuffle是MapReduce的核心也是百度这张卷子的重头戏。题目一般是“描述MapReduce中Shuffle阶段的具体流程包括Map端和Reduce端分别发生了什么”。Map端的第一步是分区。每个map输出键值对会先经过Partitioner默认实现是根据key的哈希值对Reducer数量取模决定这条数据进入哪个分区。紧接着输出并不是直接写磁盘而是先写到一个环形内存缓冲区缓冲区默认大小是100MB当写入量达到阈值比例80%时后台线程开始对缓冲区做排序并溢写到本地磁盘的spill文件。排序过程可以指定只按key排序也可以配合二次排序按value排序。溢写过程中如果配置了Combiner相当于Map端的局部Reducer会在写spill文件之前对分区内的数据做一次合并从而减少写到磁盘的数据量。多个spill文件最后还会被合并成一个有序的大文件同时生成对应的索引文件标明每个分区在文件中的偏移量方便Reduce端拉取。Reduce端则分三个阶段拉取、合并、归并。每个Reducer启动若干Fetcher线程从Map端已完成的节点上拉取属于自己分区的数据。拉取来的数据先放在内存中内存不够时也溢写到磁盘。所有数据到齐后Reducer做最终的归并排序把相同key的所有value聚在一起然后传给reduce函数处理。这个全流程我建议每个大数据岗的人都手画一遍画出缓冲区、spill文件、索引文件、Fetcher线程的位置画完你对整个任务性能调优的敏感度会提升一个档次。3.3 数据倾斜的原因与应对简答题里有一道关于数据倾斜的单词统计案例中如果某一个词出现频率极高会导致什么后果如何缓解。这道题的经典场景就是WordCount里一个超高频单词把所有数据都分到了同一个Reduce导致其他Reduce很快跑完、这个Reduce卡住几个小时。后果层面要答到几点单个Reduce处理数据量极大内存压力大可能OOM整个Job的完成时间被这个最长尾的Task拖住集群资源利用率严重不均衡。应对方案有几个层次。最粗粒度的是设置参数让一个key对应多个Reduce任务比如自定义Partitioner对当前key做打散。更精准的方案是加一层局部聚合在Map端先用Combiner把相同单词的计数累加一次这样即使有一个超高频词经过Combiner之后流量也大幅降低那个Reduce收到的只是聚合后的少数记录而不是原始每条记录。如果倾斜实在无法解决还可以考虑把倾斜key单独抽出来处理和其它正常key分开跑最后再合并结果。4. 实操场景题海量数据处理与SQL4.1 海量日志统计的完整方案设计卷子的大题里有一道综合性设计题给定若干台Web服务器每天产生的访问日志每行包含时间、用户IP、访问URL、停留时长等字段日志总量在TB级别要求统计出每天访问量前100的URL并说明方案能支撑的水平扩展方式。拿到这种题千万不能直接写一个SQL或者一段代码就完事。正确姿势是把它拆解成计算链路和存储链路两部分。计算链路方面我的思路是两层MapReduce或两层Spark作业。第一层做“URL维度按天聚合”Map阶段把日志行解析成(日期_URL, 1)的键值对Combine和Reduce阶段做累加得到当天每个URL的总访问量。第二层做“按天求Top100”每个Mapper读取第一层输出的当天数据用自己的本地小顶堆维护当前看到的前100个再把堆中数据输出到一个Reducer里做全局TopK排序最终得到全站前100的URL列表。存储链路方面第一层聚合结果落地成按天分区的Hive表后续查询只扫描当天分区成本很低。第二层Top100结果可以落到MySQL或者Redis里供前端报表调用。整套链路有一层中间结果缓冲即使某个环节出了问题也可以从中间结果恢复不用重跑原始日志。水平扩展性要从日志采集端就开始设计接入Kafka做削峰填谷消费端根据URL的哈希值做分区保证相同URL进入同一个处理单元的同一时刻只有一个实例在写避免并发写冲突。整个链路里没有单点瓶颈后流量翻倍时只需要横向加机器。4.2 分组TopN的SQL实现SQL题也基本围绕TopN展开。比如有一张用户访问日志表user_visit字段包括user_id、url、visit_time要求统计每个用户最近访问的3个URL。Hive中标准写法是使用ROW_NUMBER()窗口函数按用户分组、按访问时间倒序排然后过滤排名小于等于3的记录SELECT user_id, url, visit_time FROM ( SELECT user_id, url, visit_time, ROW_NUMBER() OVER (PARTITION BY user_id ORDER BY visit_time DESC) AS rn FROM user_visit ) t WHERE rn 3;这道题除了验证窗口函数会不会用还考察一个隐性知识点如果表数据量极大直接开窗排序会在Reduce端产生非常大的数据倾斜因为每个user_id的全部数据都要跑到同一个Reducer里做排序。生产环境里更稳妥的办法是先按user_id哈希分桶在桶内做好预排序再开窗同时配合Map端聚合把每个用户可能输出的URL数尽量压缩。当时卷子上还有一道简单的JOIN题考察的是Hive中MapJoin与普通Join的区别小表足够小时通过MapJoin把表加载到每个Mapper内存中避免Reduce端Shuffle这也是面试大数据岗位必须掌握的SQL优化点。4.3 系统设计百万级URL去重设计题里还有一道典型的“URL去重”有一个不断产生URL的爬虫系统需要实时判断一个URL是否已经抓取过URL总量预计在亿级如何处理。最想看到的标准答案是布隆过滤器。布隆过滤器的核心是一个位数组和若干哈希函数判断“不存在”是绝对准确的判断“存在”则可能有误判。对于URL去重场景我们可以容忍极少量的“已存在”误判因为最多就是少抓一次影响可控。public class BloomFilter { private BitSet bits; private int bitSize; private int[] seeds; public BloomFilter(int expectedSize, double fpp) { // bit数组大小估算公式bitSize -n * ln(fpp) / (ln2)^2 this.bitSize (int) (-expectedSize * Math.log(fpp) / (Math.pow(Math.log(2), 2))); this.bits new BitSet(bitSize); // 哈希函数数量k (bitSize / n) * ln2 int hashCount Math.max(1, (int) ((bitSize / expectedSize) * Math.log(2))); this.seeds new int[hashCount]; for (int i 0; i hashCount; i) { seeds[i] i * 31 17; } } public void add(String url) { for (int seed : seeds) { int pos hash(url, seed) % bitSize; bits.set(pos); } } public boolean contains(String url) { for (int seed : seeds) { int pos hash(url, seed) % bitSize; if (!bits.get(pos)) { return false; } } return true; } private int hash(String url, int seed) { int h 0; for (char c : url.toCharArray()) { h h * seed c; } return h; } }设计时要注意几个参数预估URL总量为1亿期望误判率设为1%根据公式需要的位数组大小大约为95.8MB哈希函数个数约为7个。整套过滤器可以完全被容纳在单机内存里外层再叠一层Redis存储已抓取URL的明文用于最终精确校验既能抗住高并发查询又保证了最终准确性。我在答卷上还多提了一点BloomFilter的位数组如果后期容量不够要支持渐进式扩容避免一次性重建引发的全量停顿。这是生产环境真正会踩的坑。5. 笔试题复盘与避坑指南5.1 考场时间分配与答题策略这套卷子最大的坑是题量偏大、分值分布不透明很多人在选择题上恋战最后大题草草收尾。我复盘后的建议是先把所有题快速通读一遍标出哪些是看一眼就有思路的哪些是需要现场推导的优先把有把握的分拿满。手写算法题时不要追求一步到位写出最优解法。先把暴力解或最直接的思路写上标注复杂度再在空余处补充优化思路。阅卷老师往往更看重你的推导过程和代码规范而不是只看最终答案。我在卷子上就吃过这个亏TopK那道题直接写了最终版本的实现但因为缺少推导说明得分反而不如旁边那位写了“先用全排序再说明为什么不可行最后给出堆方案”的同学。SQL题写完后建议自己默读一遍检查GROUP BY字段和SELECT字段是否对齐窗口函数PARTITION BY是否正确。这类题出错通常不在语法而在思路比如忘了加去重或者排名条件写错边界。5.2 大数据岗位备考的核心建议这么多年过来我对准备大数据研发岗笔试的建议可以浓缩成三条。第一条把原理题“讲给自己听”。HDFS写流程、MapReduce Shuffle、ZooKeeper选主流程这些经典原理不要只看博客。合上电脑用自己的话把完整的流程讲一遍如果中间有卡顿那卡顿处就是你的知识盲区。这个方法比反复看十篇博文都管用。第二条算法题要练“海量数据版”。LeetCode刷得好不代表笔试能过大数据的算法题往往不是单纯的逻辑题而是带有资源限制条件比如内存不够、数据分布在多机。训练时每道题多问自己一句如果数据量扩大1万倍这个方案还成立吗。养成这个习惯后面对系统设计题就不会慌张。第三条SQL窗口函数和Hive调优必须过关。2015年那会儿窗口函数还算是进阶题现在已经是基础题了。ROW_NUMBER、RANK、DENSE_RANK之间的区别PARTITION BY与GROUP BY的语义差异MapJoin、Sort Merge Join各适合什么场景这些都要形成肌肉记忆。这份百度2015年的笔试卷单论难度在当年大厂里算是中规中矩但它把大数据研发岗的核心知识面覆盖得很完整。把这张卷子吃透再去面其他厂的大数据岗你会发现很多题目只是换了层皮内核都是通的。平时复习的时候也可以按这个思路整理自己的“知识树”基础算法、Java底层、分布式原理、SQL调优、系统设计每个分支扎扎实实过一遍上考场时心里就有底了。