拼多多2020校招笔试的编程题在当年那批大厂笔试里算是一股清流。没有特别偏门的算法也不怎么考复杂的数据结构但每道题都带着浓厚的业务气息要么是订单流转要么是果园种植要么是营销玩法。正因如此很多人被题目绕进去以为要设计一个完整系统结果发现其实就是一道模拟或者动态规划。我带过的学生里有不少人参加过那场笔试事后复盘时观点非常一致基础算法吃透再培养一点“把业务场景翻译成算法模型”的能力拿高分的概率非常大。这篇内容围绕拼多多2020校招部分编程题展开重点拆解题型结构、解题思路和代码实现。我会把当时流传度比较高的几道题目重新整理按照从读题到AC的完整过程讲一遍同时把容易踩的坑标记出来。无论你是正在备战校招的应届生还是想查漏补缺的工作党只要目标是大厂笔试这些内容都能直接用上。1. 拼多多2020校招笔试整体考察什么1.1 题型分布与时间安排拼多多2020校招的在线笔试一般安排在90分钟左右编程大题数量在4到5道之间。我接触到的考生反馈里最常见的是4道编程题没有选择题和填空题全部在OJ环境里完成。题目难度采用梯度设计第一题通常是最基础的模拟或哈希表应用送分题第二题开始上强度可能会用到贪心或者动态规划第三题、第四题则偏向业务场景包装下的中等算法题偶尔会有一道偏数学期望的题目。时间分配上前两题建议控制在20分钟以内后两题每道留出25到30分钟。因为每道题都需要读题、思考、编码、调试尤其是第三道以后题目往往又长又绕读完没理清数据范围就动手写很容易浪费大量时间。我见过不少同学在第二题卡了40分钟最后第四题没时间写这是最可惜的。1.2 难度梯队与典型考点从考点分布看拼多多2020校招笔试几乎没有涉及线段树、后缀数组这类冷门数据结构重点集中在几类高频基础算法哈希表与模拟用于处理订单、库存、信息匹配类问题。排序与贪心用于区间选择、任务调度类问题。动态规划背包问题、字符串编辑距离、打家劫舍类问题。数学期望与概率掷骰子、抽卡类问题。滑动窗口和双指针数组子区间类问题。这类“业务场景 基础算法”的组合是拼多多笔试的最大特点。相比某些大厂上来就是硬核红黑树、单调栈拼多多更看重你能不能把一个具体的营销活动抽象成已知的算法模型。换句话说题目本身不难难的是你能不能识别出来它到底在考什么。1.3 业务场景题的通用解法框架面对拼多多这类业务包装型编程题我总结了一个非常实用的三步框架后面几道真题都会用到。第一步抽离“实体”。把题目里提到的用户、订单、商品、库存、坑位、骰子这些名词变成代码里的变量和数据结构。订单就是dict库存就是另一个dict坑位就是数组骰子面数就是整数n。第二步抽取“操作”。把业务动作转化成算法动作。检查订单能不能满足变成查哈希表相邻不能种树变成动态规划状态约束编辑字符串变成二维DP转移。第三步确定“约束”。看数据范围决定复杂度。n是1e5还是1e3决定能不能用O(n^2)的暴力还是必须优化到O(n log n)。这三个步骤走完一道看起来花里胡哨的题目就变成了一行核心算法关键词。剩下的事就是把这个关键词对应的模板代码写出来。2. 高频真题拆解解题思路是这样建立的2.1 订单匹配用哈希表把库存变成查询字典先看第一道典型题我叫它“订单匹配”。题目大意如下仓库里有多件商品每件商品有一个商品id和库存数量。现在收到n个订单每个订单包含若干种商品以及对应数量。如果一个订单里所有商品的需求量都不超过当前库存这个订单就可以被满足。求最终能满足的订单数量。约束方面商品id是一个整数订单总数和库存商品种类数都可能达到1e5级别每个订单包含的商品种类总和也可能很大。这道题就是典型的哈希表模拟。先读入所有库存以商品id为key库存数量为value存进一个字典。然后遍历每个订单对订单里的每种商品检查库存字典里有没有足够的数量。只要有一个商品不够就判定这个订单无法满足直接break。这里有个小坑同一件商品在库存输入里可能出现多行每次出现都是增加库存而不是覆盖。所以存字典时要写成stock[pid] stock.get(pid, 0) cnt不要直接赋值。订单内部也可能有重复商品id题目如果没说就不必合并但为了稳妥也可以用order.get(pid, 0) cnt合并不过不合并也不影响正确性因为后续会逐项判断。核心代码用Python写是这样的import sys def main(): data sys.stdin.buffer.read().split() if not data: return it iter(data) n int(next(it)) orders [] for _ in range(n): t int(next(it)) order {} for _ in range(t): pid int(next(it)) cnt int(next(it)) order[pid] cnt orders.append(order) k int(next(it)) stock {} for _ in range(k): pid int(next(it)) cnt int(next(it)) stock[pid] stock.get(pid, 0) cnt ans 0 for order in orders: ok True for pid, cnt in order.items(): if stock.get(pid, 0) cnt: ok False break if ok: ans 1 print(ans) if __name__ __main__: main()简单解释一下为什么用sys.stdin.buffer.read().split()而不是input().split()。在线笔试环境里输入数据可能非常大几千行是常事。input()每次读一行会有额外开销在Python里很容易导致超时。一次性把所有数据读进来再切分速度会快一个量级。这个习惯建议从刷题第一天就养成。2.2 果园种树相邻限制下的动态规划第二题是拼多多典型的业务包装题代码很短但思路需要转个弯。题目是这样一排有n个坑位每个坑位种上树之后能带来一个价值a_i但因为根系会互相影响不能同时在相邻的两个坑位种树。问在满足限制的前提下能得到的最大总价值是多少。看到“不能相邻选两个”这个条件就应该立刻联想到打家劫舍问题。动态规划的状态定义很简单dp[i]表示考虑前i个坑位时能获得的最大价值。对于第i个坑位有两种选择不种那么结果就是dp[i-1]如果种那么第i-1个坑位不能种所以结果是dp[i-2] a[i]。最终取这两种情况的最大值。初始状态要处理好。只有一个坑位时最大价值就是a[0]没有坑位时价值为0。我一般用两个滚动变量代替整个dp数组省空间。def max_value(a): n len(a) if n 0: return 0 if n 1: return a[0] prev2 0 # dp[i-2] prev1 a[0] # dp[i-1] for i in range(1, n): cur max(prev1, prev2 a[i]) prev2, prev1 prev1, cur return prev1这道题写起来不出十行但有几个细节值得注意。题目中的价值可能达到1e9所以结果要用64位整数保存Python的int没有溢出问题但如果你用C就必须用long long。另外数据范围如果n达到1e5空间复杂度O(n)也完全可以接受但滚动变量更优雅面试官看到也会觉得你基本功扎实。这道题还有一个变体是环形的也就是首尾坑位相邻只能用一次。处理方法是分两次DP一次不考虑第一个坑位一次不考虑最后一个坑位取最大值。拼多多2020年有没有出变体我不确定但把这种变形思路记下来遇到类似题目时就不慌了。2.3 编辑距离二维DP的经典模板字符串编辑距离属于笔试常青树拼多多那批题里也出现过。题目要求给定两个字符串s和t允许你进行三种操作插入一个字符、删除一个字符、替换一个字符。问把s变成t最少需要多少次操作。这道题的状态转移是很多人的第一个二维DP模板。定义dp[i][j]表示s的前i个字符变成t的前j个字符需要的最少操作次数。初始化很直接dp[i][0] i表示把s的前i个字符全部删除dp[0][j] j表示在空串里插入j个字符。转移的时候如果s[i-1] t[j-1]那么不需要额外操作dp[i][j] dp[i-1][j-1]。如果不相等可以从三种操作里挑一个最小的删除s的当前字符dp[i-1][j] 1在s里插入一个字符dp[i][j-1] 1替换s的当前字符dp[i-1][j-1] 1完整实现def min_distance(s, t): m, n len(s), len(t) dp [[0] * (n 1) for _ in range(m 1)] for i in range(m 1): dp[i][0] i for j in range(n 1): dp[0][j] j for i in range(1, m 1): for j in range(1, n 1): if s[i - 1] t[j - 1]: dp[i][j] dp[i - 1][j - 1] else: dp[i][j] min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) 1 return dp[m][n]如果字符串长度在1000以内二维数组完全没问题。但如果是5000以上二维数组可能占用25MB有点紧张可以用滚动数组优化成两行。不过优化时要注意dp[i][j-1]的值需要从当前行左边拿到不能覆盖太早处理起来比打家劫舍要小心一点。我第一次写滚动数组时就把左边的值覆盖了结果算出一堆错误。正确写法是用一个prev保存左上角的值。2.4 掷骰子最优停止的期望DP再来看一道偏数学期望的题。题目简化版是这样的有一个n面的骰子每面点数分别为1到n。现在你最多可以掷k次。每次掷完骰子你可以选择“收手”拿走当前这个点数作为最终得分也可以选择“继续”但会消耗一次机会。问在最优策略下你能得到的期望分数是多少。这道题的状态比较有意思。设dp[i]表示当前还能掷i次时你“准备掷骰子”的期望收益。那么当你掷出一个点数x之后你有两个选择拿x走人或者继续掷此时还能掷i-1次期望收益是dp[i-1]。所以你一定会选择max(x, dp[i-1])。因此转移方程是dp[i] (1/n) * sum(max(x, dp[i-1]) for x in range(1, n1))初始dp[0] 0也就是没有机会时收益为0。这个初始值非常关键它保证了只有一次机会时期望就是所有点数的平均值(n1)/2。直接按照这个方程写时间复杂度是O(nk)。k如果很大比如1e5n又很大就会超时。不过我们可以做一个简单优化当x dp时max(x, dp)恒等于dp当x dp时结果就是x。而x是连续的1到n所以可以用整数边界快速求和。def dice_expectation(n, k): dp 0.0 for _ in range(k): t int(dp) # 点数小于等于dp的个数 if t n: t n sum_part1 t * dp if t n: sum_part2 (t 1 n) * (n - t) // 2 else: sum_part2 0 dp (sum_part1 sum_part2) / n return dp比如输入n6, k2算出来是4.25。这个数字可以自己手算验证先算dp[1]3.5再算dp[2] (3.5×3 456)/6 4.25。如果题目要求保留小数直接print格式化即可。这道题考察的点很综合能把连续决策问题抽象出状态能写出递推还能在小数据范围内推算出样例。相比前面几道它更考验“建模”能力。拼多多这类公司尤其喜欢在笔试里加一道这种题用来筛掉只会背模板、不会分析问题的人。3. 从暴力到最优代码实现的完整演进3.1 数据范围决定算法先看约束再动手很多同学看到题目就直接开始写暴力写完才发现复杂度不对又推倒重来。这个习惯在笔试里非常致命。我建议拿到题目后第一件事不是写代码而是找数据范围。拼多多2020年这几道题数据范围设得很有讲究。以订单匹配为例如果总商品种类只有100那么三重循环都没问题。但实际给到1e5就必须用哈希表把查询从O(L)降到O(1)。果园种树也一样如果n只有20可以状态压缩暴力枚举但n给到1e5就只能用O(n)的DP。编辑距离的m和n如果都是1000O(mn)的二维DP没问题但如果都是5000就必须考虑滚动数组。所以我会在草稿纸上先把约束条件圈出来然后立刻给算法定复杂度。通常经验是n ≤ 20可以暴力枚举、状态压缩。n ≤ 5000O(n^2)可能可以但要看常数。n ≤ 1e5必须是O(n log n)或O(n)。n ≤ 1e9基本是数学题或贪心需要O(log n)或O(1)。3.2 读入优化笔试里的隐形送分项拼多多笔试用的是标准输入输出没有本地文件题目里给的样例只是用来验证思路的。真正跑分的时候输入可能非常大。Python选手如果使用input()逐行读很容易在读数据上花掉好几秒导致超时。我一直用的模板是import sys data sys.stdin.buffer.read().split() it iter(data)然后所有的整数都用int(next(it))读取。这样做的原理是sys.stdin.buffer直接读取二进制流比文本流更快read()一次性读取全部数据再通过split()按空白字符切分成列表避免了多次系统调用。对于几十万级别的数据速度差距可以缩小一个数量级。如果题目输入格式比较固定也可以使用sys.stdin.readline但如果是多行混合、字段数量不定的情况全量读取read().split()是最稳的。3.3 边界测试与调试技巧笔试里最尴尬的情况是样例通过了但提交后是0分。这时候大概率是边界条件没有覆盖到。我通常会养成一个习惯写完代码后先自己构造几组极端输入测试。对于订单匹配我会测库存为空但订单里有商品应该输出0。订单的商品数量正好等于库存应该算满足。库存里有重复商品id确保数量是累加的。对于果园种树我会测n1直接返回a[0]。n2返回max(a[0], a[1])。所有价值都为0输出0。价值为负数一般不会但如果有需要约定能否不种通常题目保证非负。编辑距离我会测两个空串0。一个空串一个非空串返回长度。完全相同0。只有替换操作的情况长度相同但字符不同。骰子期望我会测k0理论上应该是0但题目通常k≥1。n1输出1。k1输出平均数。把这些边界测完基本不会出现因为极端输入导致的翻车。调试时不要只盯着逻辑可以打印中间变量比如dp数组、库存字典和手算结果对比这样定位问题会快很多。4. 笔试中的常见问题与避坑指南4.1 输入输出格式导致的“血案”拼多多在线编译系统对输入输出格式非常严格多一个空格、少一个换行都可能导致误判。最常见的问题有两个。第一个是输出精度。对于浮点数题目如果要求保留六位小数就一定要用print({:.6f}.format(ans))不能直接print(ans)。C则需要printf(%.6f\n, ans)。有些同学会把样例里没保留的输出也交上去结果答案错误。第二个是换行符。很多题目要求“输出多少行就多少行”最后一组数据后面有没有换行无所谓但每组数据之间不能有多余空行。最好在写完代码后用题目给的样例跑一遍肉眼对比输出结果尤其是空格和空行。4.2 边界条件空串、单元素、极大值数组类题目最容易在边界上出错。比如果园种树如果n0代码里直接返回0不写这个判断后面访问a[0]就会报IndexError。再比如编辑距离当其中一个串长度为0时二维数组的初始化代码刚好能覆盖但如果你用递归写法可能会栈溢出。还有一种情况是极大值。题目说价值可能到1e9如果使用C的int结果可能超过2^31-1必须用long long。Python自然无压力但如果你用C请一定仔细读题中给的数据范围。我整理了一个笔试速查表可以对照着检查自己的代码问题类型常见原因解决办法样例通过但提交0分边界条件没覆盖构造空输入、单元素、最大输入测试超时复杂度太高或输入太慢换成O(n log n)算法读入改用read().split()答案错误但逻辑看起来没问题字典键值覆盖了或类型错误检查重复key检查int和float混用输出格式不对多空行、少换行、小数位不对用题目样例严格比对用格式化输出4.3 样例通过但提交0分的原因后面我带学生复盘时发现十个“样例通过”的人里至少有四五个是因为同一个坑读入时没有处理同一个key出现多次的情况。比如订单匹配里库存输入可能写成3 1 10 2 20 1 5这里商品1出现了两次总库存应该是15而不是10。如果你存字典时直接stock[pid] cnt第二次就会把第一次覆盖最终结果错误。用stock[pid] stock.get(pid, 0) cnt就不会有这个问题。编辑距离还有一个隐藏坑题目的字符串可能会包含空格。如果使用sys.stdin.buffer.read().split()空格会被当作分隔符切掉字符串就读取不完整。遇到这种情况应该改用readline()按行读取。所以在读题时一定要看字符串是否可能包含空格这是一个非常细节但致命的问题。拼多多原题里字符串通常只包含小写字母但稳妥起见遇到字符串时我都会单独处理。5. 校招备战复盘怎么刷题才有效5.1 以拼多多为代表的“业务型笔试题”训练法如果你已经刷了几百道LeetCode但参加笔试还是觉得题目陌生很可能是缺少“业务翻译”训练。常规平台上的题目都是裸的数据结构和算法比如“给定一个数组求最大子序和”。但拼多多的题目不会这么直白它会说“多多果园的树要隔一颗种一颗怎么选价值最大”或者“一堆订单要匹配库存怎么判断能否发货”。训练方法很简单刷题时多问自己一个问题——“如果这是一道商业题它会出现在什么业务场景里” 比如看到最长递增子序列可以联想成“按时间顺序选择优惠券”看到区间合并可以联想成“多个配送员的时间段合并”。这样在真正笔试时看到一大段业务描述就不会慌因为你知道它底下包着的一定是某个基础算法。5.2 刷题优先级与推荐题单以拼多多2020校招笔试为参照我建议按照下面的优先级准备第一梯队哈希表、数组模拟、字符串基础操作。这些是送分题必须全对。可以在LeetCode上刷“Two Sum”“Isomorphic Strings”“Valid Anagram”等基础题。第二梯队动态规划入门。打家劫舍、背包问题、编辑距离、最长公共子序列这些是笔试中高频考察点。建议每种题型做至少5道直到能默写出模板。第三梯队贪心与排序。区间调度、任务安排、最大收益类题目容易和业务场景结合需要掌握排序后如何决策。第四梯队数学期望与概率。这类题不算特别多但一旦出现就是区分度。建议把“掷骰子期望”“抽卡概率”“随机变量期望”这类经典题弄明白。LeetCode题目标签可以直接搜“Dynamic Programming”“Greedy”“Hash Table”按难度从Easy到Medium刷。不用刻意刷Hard拼多多笔试的压轴题难度最多也就是Medium偏上。5.3 从笔试到面试算法思维如何延续笔试只是校招的第一关拼多多面试时同样会问算法而且更注重推导过程。我当时一个很深的感受是笔试中可以靠刷题堆题感但面试时必须能讲清楚“为什么用这个方法”“有没有更优解”“能不能优化空间”。所以在准备笔试时不要只满足于AC。每道题完成之后问自己三个问题第一个问题这个状态定义是怎么想到的要想清楚是经验还是推导。 第二个问题如果数据扩大10倍这个解法还成立吗 第三个问题能不能把空间复杂度降到O(1)或者把二阶DP转成一阶把这三个问题想明白你就不是在这里做题而是在建立算法思维。这种思维从笔试一直延续到面试甚至到实际工作中的代码设计才是刷题真正有价值的地方。我在实际带人的过程中发现很多同学刚刷题时一道Easy都要看题解但坚持用这种“翻译复盘”的方式训练两个月后再做拼多多这类业务包装型题目基本都能稳定解出三到四题。最后再分享一个亲测有效的小技巧正式笔试前自己准备一个固定的代码模板包含最快的读入方式、常用的包导入、浮点数格式化输出。不要小看这几行代码它能让你在开局时比别人快出一两分钟而且能减少紧张带来的低级错误。祝你在下一次笔试里顺利AC。