拼多多2018校招的编程题在当时并不算特别难但很能代表电商类公司笔试的出题口味不跟你玩偏题怪题重点考察排序、模拟、贪心、字符串处理这些基本功加上一点对边界条件的敏锐度。这几年我带过不少学弟学妹做校招准备回头再看这套题反而觉得它对“校招笔试应该怎么准备”这件事特别有参考价值。这篇文章就挑几道典型题目从思路推导到代码实现再到踩坑点完整过一遍。1. 从“最大乘积”说起排序与负数的边界意识拼多多这套题里有一道非常经典的题给定一个无序数组包含正数、负数和0要求找出3个数使得乘积最大。我当时第一次见到这个题的时候第一反应是三层循环暴力枚举后来仔细一看题目给的数据范围瞬间就清醒了——绝对不可能让你用O(n^3)去解。1.1 “先排序再取三个数”的思路为什么是对的很多人拿到这道题稍微想一下就会得到一个结论先把数组排序然后最大乘积一定是这两种情况之一——最大的三个正数相乘两个最小的负数相乘再乘以最大的正数。因为负数乘负数为正两个绝对值最大的负数排序后最左边两个乘起来可能比三个正数的组合还要大。比如数组是[-100, -98, 1, 2, 3]最大乘积不是3×2×16而是(-100)×(-98)×329400。所以排序之后只用比较末尾三个数的乘积和开头两个数加末尾一个数的乘积取较大值即可。def maximum_product(nums): nums.sort() return max(nums[-1] * nums[-2] * nums[-3], nums[0] * nums[1] * nums[-1])时间复杂度O(n log n)空间复杂度O(1)。这个解法能在笔试中拿满分数代码短、思路清楚、不容易写错。1.2 不用排序怎么做到O(n)但这里有个问题如果题目要求时间复杂度是O(n)那排序就不行了。我当年就遇到过这个变种所以建议准备这道题的时候顺便把O(n)的解法也掌握一下面试延伸提问的时候用得上。思路其实也简单我们根本不需要全排序只需要扫描一遍数组维护最大的三个数和最小的两个数即可。def maximum_product_linear(nums): max1 max2 max3 float(-inf) min1 min2 float(inf) for num in nums: if num max1: max3 max2 max2 max1 max1 num elif num max2: max3 max2 max2 num elif num max3: max3 num if num min1: min2 min1 min1 num elif num min2: min2 num return max(max1 * max2 * max3, min1 * min2 * max1)写这个代码的时候最需要注意的是更新顺序。每次来了一个新数要从大到小逐级“挤”下去新数变成第一大原来的第一大变成第二大原来的第二大变成第三大。很多人第一次写会直接写成max1 num把原来的最大值覆盖掉那就错了。1.3 这道题真正容易踩的坑全是负数的情况比如[-5, -4, -3, -2, -1]排序后末尾三个数的乘积是(-2)×(-1)2再乘以一个负数等等三个负数相乘是负的。实际上这个例子中最大的乘积是(-3)×(-2)×(-1)-6但这不是我们想要的。再看[-1, -2, -3, -4, -5]这种情况最大的三个数相乘是(-3)×(-4)×(-5)-60但最大的正数乘积其实是(-1)×(-2)×(-3)-6。这两种解法公式依然成立因为公式本来就是取max它会把所有可能性都覆盖到。真正需要注意的是不要在代码里自己“优化”成只算正数或只算负数反而漏掉了全负数场景。数组中有0的情况0的存在会让乘积归零这时候max逻辑依然正确不用特殊处理。但如果你自作聪明去判断“如果包含0就返回0”反而可能在特殊场景下算错。不判断就是最好的判断。数值溢出Python不用考虑这个问题但如果你用C或Java写nums[i] * nums[j] * nums[k]可能超出int范围。校招笔试一般会提示用long long别忽视了。这道题给我最大的启发是排序并不总是最优解但在笔试中“用恰好满足时间复杂度的最简单方法”才是性价比最高的选择。2. “大整数相乘”竖式思维的代码化另一道很有代表性的题是“大整数相乘”。给定两个用字符串表示的非负整数返回它们相乘的结果字符串。两个数的长度可能达到上千位直接用int转换再相乘是不可能通过的。2.1 这道题到底在考什么这道题的核心不在于你会不会用大数库而在于你会不会把小学数学的“竖式乘法”翻译成代码。理解了这个本质实现起来就很顺。我们回忆一下手算乘法是怎么做的把两个数从低位到高位逐位相乘乘完之后把结果对齐然后逐列累加最后统一处理进位。代码里通常用一个长度为len(num1) len(num2)的数组来保存中间结果因为两个长度分别为m和n的数相乘结果长度最多是mn。举个具体例子计算123 × 451 2 3 × 4 5 --------------- 1 5 3×515位置在ij和ij1 1 0 2×510 0 5 1×505 1 2 3×412注意错位 0 8 2×408 0 4 1×404但我们不会这样做而是用一个数组把所有乘积累加在一起然后统一进位。2.2 数组模拟竖式的实现细节def multiply(num1: str, num2: str) - str: if num1 0 or num2 0: return 0 m, n len(num1), len(num2) res [0] * (m n) for i in range(m - 1, -1, -1): d1 ord(num1[i]) - ord(0) for j in range(n - 1, -1, -1): d2 ord(num2[j]) - ord(0) # 关键累加到对应位置 res[i j 1] d1 * d2 # 统一处理进位 carry 0 for k in range(m n - 1, -1, -1): total res[k] carry res[k] total % 10 carry total // 10 # 去掉前导0 start 0 while start m n - 1 and res[start] 0: start 1 return .join(str(x) for x in res[start:])2.3 实现时最容易被忽略的几个位置第一中间结果的存放位置。res[i j 1]这个下标很多人第一次会写成res[i j]导致结果整体错位一位。其实有个很简单的验证方法最高位相乘时i0, j0如果下标是ij那结果会落在第0位而m1, n1时res长度为2最低位应该落在第1位。所以i j 1才是对的。第二进位的处理方式。这里选择的是“先累加、再一次进位”而不是在每次内层循环里都做进位。先累加再统一进位的代码逻辑更简单也更容易证明正确性。如果每一步都进位代码容易乱还容易漏掉某些位的进位。第三前导零的清理。比如0 × 123内层循环确实会把所有位置都算成0但res数组可能全是0。上面代码先做了num1 0 or num2 0的特殊判断所以不会走到清理这步。但如果你去掉这个判断必须确保前导零清理逻辑能把所有0都去掉并保留最后一个0。2.4 关于“大整数”题型的延伸碰到这类题我建议你在准备时顺手掌握一个延伸技巧——任意进制大数乘法。做题时虽然用十进制但明白“每一位允许超过9最后统一进位”的原理后换成二进制、十六进制就是改个模数的事。很多面试官会在你写完十进制版本后追加一句“如果输入是十六进制字符串呢”这时候你的代码只需要把10全部改成16再改一下字符转换函数就行。3. “小熊吃糖”与贪心策略的优先级问题拼多多这套题里有一道我很喜欢的题它不像前两道那么“标准模板”而是带了一点场景包装有n只小熊每只小熊有一个战斗力值有m颗糖果每颗糖果有一个甜度值。小熊按战斗力从高到低依次挑选糖果每只小熊会选走当前可选的糖果中甜度最大的一颗。最后要求按小熊编号顺序输出每只小熊吃到的糖果甜度。这道题实质上是“贪心排序”的经典组合但场景包装之后很多人在第一步就乱了。3.1 先把题意翻译成数据结构这道题的关键在于你需要同时维护三个信息——小熊的编号、战斗力、最终吃到的糖。在代码里最自然的方式是定义一个列表每个元素是[战斗力, 编号, 初始顺序索引]按战斗力降序排序。糖果则只需要按甜度降序排列。为什么强调“编号”和“顺序索引”要分开记录因为题目要求最后按小熊编号输出而你排序之后顺序已经打乱了。如果不提前把编号存好后面根本没法恢复顺序。我在实际笔试中见过很多人的代码死在最后一步——结果算对了但输出顺序完全错乱。3.2 为什么“战斗力高优先”的贪心是正确的这部分值得多说两句。有些题你直接用贪心心里其实没底但这道题可以用一句话证明假设有两只小熊A和BA的战斗力高于B。如果让B先选B可能选走一颗A也能吃的糖从而降低A的收益而让A先选A只会选择它能吃的最甜的糖不会影响B的可行选择——因为A选完之后剩下的糖对B来说只是少了一颗可选项但B本来就不可能选到比A更优的糖战斗力低可选范围更小。换句话说战斗力的高低本身就定义了一种“优先级偏序”按照这个偏序依次做贪心选择不会破坏后续选择的可行性。这就是“交换论证”的一个最朴素版本。面试时能把这个逻辑讲清楚比单纯写出代码更容易拿高分。3.3 双指针实现与复杂度对比排序之后问题就变成了小熊按战斗力从高到低遍历糖果按甜度从高到低遍历用一个指针指向当前小熊能吃到的最甜糖果。这里最直接的做法是对每只小熊从头扫描糖果列表找到第一颗甜度不超过战斗力上限的糖然后标记为已吃。但这样做的复杂度是O(n*m)数据量大时会超时。优化思路是把糖果按甜度降序排序后用一个指针pos从前往后移动。因为小熊也是按战斗力降序排列的所以前一只小熊能吃的糖果后一只小熊不一定能吃但指针只需要继续向后移动不需要回头。这样就变成了一个双指针线性扫描复杂度只有O(n m)。def bear_and_candy(bears, candies): # bears: list of (power, id) # candies: list of sweetness candies.sort(reverseTrue) n len(candies) eaten [False] * n result {} bears_sorted sorted(bears, keylambda x: -x[0]) pos 0 for power, bear_id in bears_sorted: chosen None # 从pos开始尝试找当前小熊能吃的最大甜度 for k in range(pos, n): if not eaten[k] and candies[k] power: chosen candies[k] eaten[k] True break if chosen is None: chosen 0 result[bear_id] chosen # 按原编号输出 return [result[bear_id] for _, bear_id in bears]3.4 这题常见的两个失误一个是在排序时没按编号恢复原顺序结果输出全错另一个是忘了处理“小熊吃不到任何糖果”的情况这种熊应该输出0而不是报错或者不输出。这两个坑都很隐蔽但都很致命。我建议你写完之后先用一个极小的测试用例手动推演一遍比如两只熊三颗糖确认输出顺序和吃糖逻辑都正确再提交。笔试时这种“人肉debug”能救命的。4. 从拼多多真题看校招笔试的通用打法把这些题放到一起你会发现它们的共性其实很明显不考偏门算法不考高深的数据结构甚至不怎么会出动态规划。它们更看重的是你对基础算法的熟练程度以及在有限时间内写出正确代码的能力。4.1 电商公司出题偏好的底层逻辑电商公司的业务场景天然带着“排序”“匹配”“分配”这些关键词。商品要按价格排序库存要按优先级分配优惠券要匹配最优方案——这些场景翻译成算法题就是排序、贪心、双指针、模拟。所以拼多多2018年这套题本质上是在筛选“能快速把业务场景抽象成算法模型”的人。反过来这也给了你一个明确的准备方向如果你瞄准的是互联网公司的校招笔试尤其是电商、本地生活类公司排序和贪心永远值得你多花时间去刷。树、图、动态规划也重要但优先级可以往后排一点。4.2 数据范围是出题人留给你的提示我还想特别强调一个容易被忽略的东西——题目里的数据范围。这往往不是无关紧要的说明而是出题人在暗示你答案的时间复杂度。比如n≤10^5基本排除O(n^2)的暴力解n≤10^3O(n^2)大概率没问题n≤10^18那基本是在暗示你用数学公式而不是循环。养成先看数据范围再动笔的习惯可以帮你避免“辛辛苦苦写完暴力结果超时”的悲剧。4.3 校招笔试的实战建议以我自己的经验笔试题一般会有4道左右难度递增。最科学的策略是先把所有题都看一遍从最简单的开始做保证拿稳基础分遇到不会的题先跳过不要死磕。因为笔试的计分通常只看最终通过用例的多少一道题卡太久代价是后面简单题没时间做。还有一点就是多用Python自带的数据结构。Counter、defaultdict、heapq、bisect这些库能省很多事。比如“小熊吃糖”如果直接用heapq存糖果也可以实现快速取最大值只是还要额外维护“已吃”状态反而不如双指针直观。工具不是越高级越好而是越匹配场景越好。4.4 针对这套真题的一个小建议如果你决定拿这套题练手我建议你不只是把代码写对而是每道题都强制自己用两种方法各写一遍第一种是最符合直觉的解法哪怕复杂度没那么好第二种是优化后的解法。这样做的价值在于笔试现场你需要的是“能快速写对的优化解”而只有你亲手从暴力推到优化才能真正理解每种优化的代价和收益。比如“最大乘积”那道题你先写三层循环再写排序法最后写线性扫描法感受一下三种代码的复杂度和思维量差异以后再遇到“最大子序列乘积”之类的变体你心里就有底了。上次有个学弟跟我聊说他在笔试前刷了很多“难题”结果笔试碰到这些朴素但需要细节的题反而差点翻车。我觉得这个教训很有代表性校招笔试真正考的不是你会不会高深的算法而是你能不能把一道看似简单的题做得滴水不漏。拼多多2018这套题就是很好的试金石——如果你能不看题解独立把这套题里的排序、字符串、贪心都写得又对又快那应对大多数公司的校招笔试基本就有了一个不错的基础。