拼多多的校招筆試題一直以來在互聯(lián)網圈子里都有點“傳說”色彩。2018年內推那批題難度和區(qū)分度都做得相當好既不像普通校招卷那樣隨便刷刷LeetCode熱題就能過也不像競賽題那樣脫離實際。它考的是很本質的算法功底、代碼實現(xiàn)能力和邊界條件的敏感度。這套題我反復刷過幾遍每次都有新收獲。這篇文章就結合我自己刷題時的踩坑經驗做一次完整的復盤和拆解。這套題適合誰看如果你是正在備戰(zhàn)大廠校招的研發(fā)崗同學建議逐題精做因為你很大概率在筆試中遇到同級別的題如果是工作兩三年的開發(fā)想系統(tǒng)回顧一下算法基本功這五道題也是很好的自測標尺。1. 整體解題思路與這套題的底層邏輯1.1 拼多多筆試的出題風格先說一個很核心的感受拼多多的筆試題不繞彎子就是直白地考你的基礎功底。不像一些公司喜歡出場景題、智力題、甚至閱讀理解題拼多多的題風是相當“硬核”的——大整數(shù)乘法、組合數(shù)學、貪心模擬、樹形結構。題目描述都不長但每一題的考察點都踩在算法和數(shù)據(jù)結構的關鍵位置上。從2018年內推這套題來看出題人的邏輯非常清晰基礎的數(shù)據(jù)結構要熟練尤其是模擬題要寫得又快又準基礎的算法思維要扎實不要一上來就想復雜的優(yōu)化有時候最簡單的思路反而是最優(yōu)解邊界條件處理能力是關鍵在筆試環(huán)境里沒有調試器一旦邊界出錯就是掛。1.2 五道題的類型拆解與能力覆蓋把五道題放在一起看其實就是一個完整的算法能力測試矩陣題目考察方向難度評級核心數(shù)據(jù)結構/算法大整數(shù)乘法高精度運算中低數(shù)組模擬、進位處理數(shù)三角形組合數(shù)學中GCD、去重邏輯最大乘積貪心/掃描中極值維護、負負得正小熊吃糖模擬題中高多維排序、貪心選擇選靚號狀態(tài)枚舉高枚舉、成本計算、字典序調整前兩題是基礎中的基礎屬于保障分中間兩題開始拉差距需要你真正理解貪心和模擬的精髓最后一題是壓軸題它考驗的是你在復雜度壓力下能否找到正確的枚舉狀態(tài)并處理字符串的字典序問題。1.3 為什么這套題值得反復刷我的觀點是刷算法題刷的不是題是解題的思維慣性。這套題里幾乎沒有偏題怪題每一道都是在訓練你面對一個“看著不難但寫起來容易出錯”的任務時如何理清思路、一次通過。這種能力在真實的開發(fā)工作里非常重要——你寫的每一段業(yè)務邏輯本質上都是一個需要處理各種邊界的“模擬題”。2. 高精度不犯錯的底層技巧大整數(shù)乘法詳解2.1 題目描述與本質分析這道題的原題是這樣的給定兩個非常大的正整數(shù)它們的長度可能達到幾千位甚至更多要求輸出它們的乘積。很多同學第一次看到這道題心里想的是“用Python不就直接乘嗎”或者“用Java的BigInteger啊”。這些思路沒有錯但注意筆試出這道題的目的恰恰是考察你在語言沒有大整數(shù)支持時的處理能力。在C里沒有內置的大整數(shù)類型在Java里雖然有BigInteger但如果你直接用某種程度上等于放棄了這道題考察的核心——高精度運算本身。在實際工作中高精度計算也經常出現(xiàn)在金融系統(tǒng)、加密算法、科學計算等場景里。2.2 豎式模擬法的完整推導高精度乘法的核心思想就是把我們在小學數(shù)學里學的豎式乘法用數(shù)組和循環(huán)來實現(xiàn)。假設第一個數(shù)的每一位是a[0]、a[1]、a[2]...從低位到高位存儲第二個數(shù)同理。那么結果數(shù)組的第ij位需要累加a[i] * b[j]的結果。這是關鍵推導def multiply(num1, num2): # 處理特殊情況 if num1 0 or num2 0: return 0 m, n len(num1), len(num2) # 兩個數(shù)相乘結果的位數(shù)不會超過mn位 result [0] * (m n) # 從低位到高位逐位相乘 for i in range(m - 1, -1, -1): for j in range(n - 1, -1, -1): mul (ord(num1[i]) - ord(0)) * (ord(num2[j]) - ord(0)) # 關鍵累加到對應位置 # ij1對應當前位的“個位”位置 p1, p2 i j, i j 1 total mul result[p2] result[p2] total % 10 result[p1] total // 10 # 去掉前導零 res .join(map(str, result)) return res.lstrip(0)2.3 為什么結果數(shù)組長度是mn這里有個數(shù)學小結論一個m位數(shù)和一個n位數(shù)相乘結果的位數(shù)要么是mn-1要么是mn。舉例來說99兩位數(shù)乘以99兩位數(shù)等于9801四位數(shù)是mn而10兩位數(shù)乘以10兩位數(shù)等于100三位數(shù)是mn-1。所以開mn長度的數(shù)組一定夠用最后去掉前導零就行。我當年寫這道題時犯過的一個低級錯誤是直接在result[p2]位置存放乘積結果而不是累加。這樣第一輪循環(huán)沒問題第二輪的時候就覆蓋掉了之前的結果。正確做法是先把mul和result[p2]當前的臨時值相加再拆分個位和進位。2.4 這道題的三個易錯點字符轉數(shù)字時一定要減去字符0而不是直接拿字符的ASCII碼去算。ASCII碼的48到57對應數(shù)字0到9直接取值會得到完全錯誤的結果。處理乘數(shù)為0的情況。很多實現(xiàn)里如果不特判0最后的結果會是一串0而不是一個0。雖然lstrip(0)能處理前導零但如果所有位都是0它會把整個字符串變成空串。這就是我前面代碼里先判斷乘數(shù)是否為0的原因。存儲順序的選擇。我習慣從低位到高位存儲這樣進位的時候是往高一位進位符合自然思維。但如果你從高位到低位存儲進位方向就反了會在取模和整除那里折騰很久。選一種你習慣的、不會搞混的順序一以貫之。注意高精度加法、乘法、減法在思路上一脈相承都是“每一位單獨運算然后處理進位/借位”。把大整數(shù)乘法的模板背熟遇到大數(shù)相關題目就能快速套用。3. 最大乘積與去重組合的思路對比3.1 最大乘積的貪心思維這道題的描述是給定一個整數(shù)數(shù)組長度至少為3從中選出三個數(shù)使得它們的乘積最大輸出這個最大乘積。注意數(shù)組里的整數(shù)可能是負數(shù)也可能是0。很多第一次看到這道題的同學第一反應是“排序然后取最后三個數(shù)相乘”。這個思路在全是正數(shù)的情況下沒問題但一旦出現(xiàn)負數(shù)和0就完全失效了。舉個例子數(shù)組是[-100, -98, 1, 2, 3]排序后最后三個數(shù)是1、2、3乘積是6。但正確答案應該是(-100)乘以(-98)乘以3等于29400因為兩個負數(shù)相乘得到很大的正數(shù)。所以要分情況討論最大乘積只有兩種可能最大的三個正數(shù)相乘或者都是負數(shù)時最大的三個數(shù)相乘比如-1、-2、-3的乘積是-6比-1、-2、-100的乘積-200要大最小的兩個數(shù)和最大的那個數(shù)相乘這個結論背后是一個很簡單的數(shù)學事實乘積要最大要么全取正數(shù)里最大的要么取兩個絕對值最大的負數(shù)來“變正”。寫代碼時一種做法是排序后比較nums[n-1] * nums[n-2] * nums[n-3]和nums[0] * nums[1] * nums[n-1]取較大值。def maximum_product(nums): nums.sort() n len(nums) return max(nums[0] * nums[1] * nums[-1], nums[-1] * nums[-2] * nums[-3])就這么幾行代碼但背后是清晰的貪心分類討論。我自己的體會是排序法簡單直接時間復雜度是O(nlogn)在筆試完全夠用。如果你追求極致性能可以用線性掃描維護三個最大值和兩個最小值時間復雜度降到O(n)但代碼量和出錯概率都會增加。3.2 數(shù)三角形的去重與共線檢測數(shù)三角形這道題描述是這樣的給定平面上若干個點問能組成多少個不同的三角形。這道題第一眼看去很容易想到暴力枚舉任取三個點判斷是否共線不共線就是三角形。但這里有兩個坑計算量。如果點是100個C(100,3)是161700種組合這個數(shù)量級暴力枚舉是能過的。但如果點是1000個呢C(1000,3)約等于1.6億暴力枚舉就非常吃力了。共線判斷的精度問題。如果用斜率判斷共線在浮點數(shù)計算時可能會遇到精度問題。三個點共線的本質是向量叉積為零。也就是說點A、B、C共線等價于(B.x - A.x)乘以(C.y - A.y)減去(B.y - A.y)乘以(C.x - A.x)等于0。用整數(shù)運算就能完全避開浮點誤差。def count_triangles(points): n len(points) count 0 for i in range(n): for j in range(i 1, n): for k in range(j 1, n): x1, y1 points[i] x2, y2 points[j] x3, y3 points[k] # 向量叉積為零則共線 cross (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1) if cross ! 0: count 1 return count3.3 大數(shù)量級時的優(yōu)化GCD去重如果點的數(shù)量達到幾千甚至上萬三重循環(huán)就廢了。這時候需要換一個思路枚舉每個點作為三角形的一個頂點然后計算它到其他所有點的向量按方向去重。這個思路的數(shù)學基礎是從點A出發(fā)如果有m個點與A的連線方向相同那么從這m個點中任選兩個與A組成的三角形是不成立的共線所以以A為頂點的不共線三點組合總數(shù)是C(n-1, 2)減去所有共線方向上的C(m, 2)。方向去重時需要把向量(x, y)化簡為最簡分數(shù)形式這里就用到了最大公約數(shù)GCD。比如(2, 4)和(1, 2)化簡后都是(1, 2)代表同一個方向。關鍵點在于向量要統(tǒng)一正負號標準比如規(guī)定x為負時整體取反x為0時規(guī)定y為正。否則(1, -2)和(-1, 2)會被當作兩個方向但實際上它們在同一條直線上。這個題的核心就是去重和共線檢測看起來是幾何題考的是組合數(shù)學和數(shù)論。想要精刷校招題庫的朋友這道題值得多花點時間。4. 小熊吃糖的模擬題優(yōu)化4.1 初看簡單的表象題目描述大致是有若干只小熊它們的戰(zhàn)斗力不同饑餓值也不同?，F(xiàn)在有若干顆糖每顆糖有對應的飽腹度。每只小熊按照戰(zhàn)斗力從高到低的順序依次選擇糖果——選擇目前剩余的、能讓它吃飽且不超過它饑餓值的最大一顆糖。如果吃完一顆糖后還是餓可以繼續(xù)選下一顆直到吃飽或糖果被選完。最后輸出每只小熊剩余饑餓值。這題第一眼看過去不就是模擬嘛排序就行了。但實際上手后會發(fā)現(xiàn)情況比想象中復雜因為每只小熊可以吃多顆糖。4.2 雙排序的解題框架我的做法分三步走第一步把小熊按戰(zhàn)斗力降序排列同時記錄它們原來的索引因為輸出時要按輸入順序輸出。第二步把所有糖的飽腹度排序。第三步按戰(zhàn)斗力順序遍歷小熊對于每只小熊從大到小遍歷剩余的糖只要這顆糖的飽腹度小于等于它的剩余饑餓值就吃掉它同時減少饑餓值。def bears_and_candies(bears, candies): # bears: [戰(zhàn)斗力, 饑餓值] # candies: [飽腹度] n len(bears) # 記錄原始索引 bears [(bears[i][0], bears[i][1], i) for i in range(n)] # 按戰(zhàn)斗力降序排列 bears.sort(keylambda x: x[0], reverseTrue) candies.sort(reverseTrue) result [0] * n used [False] * len(candies) for power, hunger, idx in bears: remaining hunger for i in range(len(candies)): if used[i]: continue if candies[i] remaining: remaining - candies[i] used[i] True # 零饑餓提前退出 if remaining 0: break result[idx] remaining return result4.3 復雜度分析與優(yōu)化方向最壞情況下每只小熊都要遍歷所有糖果復雜度是O(n*m)n是小熊數(shù)量m是糖果數(shù)量。如果n和m都達到10^4量級這個復雜度在筆試中可能會卡時間。怎么優(yōu)化關鍵是可以利用糖果的排序特性。糖果已經按降序排列了對于一只小熊找到第一顆不超過當前饑餓值的糖可以用二分查找快速定位。如果一棵糖被吃掉了可以用并查集并查集跳過已經用過的糖果位置讓查找效率接近線性。這里的貪心思路是“每次選能吃的最大糖”這保證了最優(yōu)解。為什么因為對于一只固定順序的小熊來說它消耗的饑餓值越大后續(xù)剩余饑餓越低。同樣的饑餓值下先吃大糖不會損害后續(xù)選擇因為在它選糖期間沒有其他熊能插隊。4.4 模擬題在筆試中的通用套路小熊吃糖這道題是我認為整套試卷里最“職場化”的一道題。 它的核心是在多種排序規(guī)則的場景下找到一種不會沖突的貪心策略。我做模擬題的經驗是不要急著寫代碼先紙上推演一遍完整流程。把“輸入排序”、“處理邏輯”、“輸出還原”三段式結構理清楚再動手編碼。這樣寫出來的代碼基本不會出現(xiàn)“明明邏輯對但輸出順序錯”的尷尬局面。5. 選靚號的復雜枚舉與字典序編程5.1 題目描述與問題轉化選靚號這道題是整套試卷的壓軸題。題目大意是給定一個手機號一串數(shù)字你可以把其中任意一個數(shù)字改成任意其他數(shù)字每次修改的代價是原始數(shù)字與目標數(shù)字差的絕對值?，F(xiàn)在最多允許修改k次要求修改后得到的號碼中至少存在一個數(shù)字出現(xiàn)次數(shù)最多不是指定數(shù)字是至少有一位數(shù)字出現(xiàn)了最大次數(shù)且需要讓這個號碼的字典序最小。說實話我第一次看這道題的時候人是懵的。因為變量太多了改哪個位置、改成什么數(shù)字、修改次數(shù)怎么分配、字典序怎么保證最小。解題的關鍵是不要試圖同時處理所有數(shù)字而是固定一個目標數(shù)字然后讓最大化它的出現(xiàn)次數(shù)。5.2 核心枚舉固定目標數(shù)字枚舉目標數(shù)字d從0到9把原始號碼的每一位數(shù)字都看作一個“候選”計算它變成d的代價。然后選擇k次修改中最小的k個代價對應的位置把這些位置改成d。這個思路看起來簡單但有一個極其關鍵的點這里有一個很反直覺的“越界修改”的問題。舉例來說把8改成0代價是8這在“把0變成8”的目標里是合理的。但如果你不限制修改次數(shù)把8改成0后再把0改成8就浪費了一次修改。所以要明確每個位置最多只能被修改一次。在計算代價時只需要計算|原數(shù)字 - d|修改一次到位不要出現(xiàn)二次修改。5.3 處理字典序最小優(yōu)先級策略固定目標數(shù)字d之后字典序最小怎么解決這個問題的難度甚至比“怎么選修改位置”更大。核心結論對于每位數(shù)字x如果它要變成d當d大于x時修改后數(shù)字變大這種情況要盡可能把修改機會放在高位當d小于x時修改后數(shù)字變小這種情況要盡可能把修改機會放在低位。為什么因為字典序是從高位向低位比較的。高位數(shù)字變小會直接讓整個號碼的字典序變小高位數(shù)字變大會讓字典序變大。所以如果d 原數(shù)字也就是要變小盡量在低位修改這樣高位保持原樣字典序更小如果d 原數(shù)字也就是要變大盡量在高位修改這樣高位變大后整個號碼雖然變大了但如果必須變大就讓它變在更低位這個優(yōu)先級關系可以用一個簡單的排序規(guī)則實現(xiàn)按代價升序排列代價相同的優(yōu)先修改更靠后的位置對于d 原數(shù)字的情況。但這里有一個特例如果d 原數(shù)字反而要優(yōu)先修改更靠前的位置。所以排序規(guī)則實際上是兩段的。這個細節(jié)是選靚號這道題里最容易出錯的地方。我當年第一次寫的時候只考慮了代價排序結果樣例過了但提交后大面積報錯。調試了很久才發(fā)現(xiàn)是字典序的優(yōu)先級問題。5.4 完整實現(xiàn)參考def beautiful_phone_number(num, k): n len(num) # 記錄每個數(shù)字出現(xiàn)的次數(shù) best -1 best_digit -1 for d in range(10): target str(d) # 計算每個位置變成目標數(shù)字的代價 changes [] for i, ch in enumerate(num): cost abs(int(ch) - d) changes.append((cost, i)) # 按代價排序代價相同按位置排序 # 這里的排序規(guī)則需要根據(jù)d和原數(shù)字的相對大小來定 # 簡化處理先按代價排序相同代價按位置降序優(yōu)先改低位 changes.sort(keylambda x: (x[0], -x[1])) cnt 0 total_cost 0 tmp list(num) for cost, pos in changes: if cnt k: break if cost 0: continue total_cost cost tmp[pos] target cnt 1 # 統(tǒng)計tmp中target出現(xiàn)的次數(shù) freq tmp.count(target) if freq best: best freq best_digit d best_arr tmp # 這個實現(xiàn)做了一點簡化完整版需要根據(jù)字典序精細調整排序方向 return .join(best_arr)注意這個實現(xiàn)是簡化的邏輯完整版還需要處理代價為0的情況、修改次數(shù)不足k但已經最大化的邊界情況等。這里展示的是核心枚舉框架。5.5 字典序相關的通用技巧選靚號的字典序處理包含了一個很重要的通用技巧枚舉優(yōu)先級控制。拿到任何一道“在多種方案里選取字典序最優(yōu)”的題目可以先固定方案的關鍵參數(shù)然后在調整過程中用一個明確的優(yōu)先級來指導每一步。優(yōu)先級通常來自“字典序的定義”——從高位到低位逐個比較。6. 筆試實戰(zhàn)時間分配與自測清單6.1 考場上的時間分配建議以2018拼多多內推筆試為例通常2到3小時做3到5道題。我的建議是第一題大整數(shù)乘法屬于送分題15分鐘內必須寫完并且確保對第二題最大乘積排序法5分鐘內搞定第三題數(shù)三角形暴力法先保底如果時間充裕再優(yōu)化第四題小熊吃糖30分鐘到40分鐘這是決定你能不能通過的分水嶺第五題選靚號最后做如果前面還有bug要修果斷放棄這題的優(yōu)化整體原則先易后難先拿到保底分再挑戰(zhàn)高分題。6.2 提交前的自查清單我在刷這套題時總結了一個筆試自測清單每題提交前逐條對照全0輸入測了嗎空數(shù)組/空字符串呢邊界值測了嗎比如最大值、最小值、負數(shù)、0。輸出格式對嗎題目要求每行一個結果還是結果用空格分隔變量類型對嗎大數(shù)溢出怎么辦如果有排序索引對應關系對了嗎時間復雜度和空間復雜度在題目限制下能過嗎特別是第一題和第五題邊界情況是重災區(qū)。寫完代碼后用幾個極端用例在腦子里跑一遍能抓住大量隱藏bug。6.3 筆試環(huán)境與IDE的磨合還有一個很多人忽略的細節(jié)筆試平臺用的是?？途W這類在線評測系統(tǒng)它的輸入輸出格式和本地環(huán)境不太一樣。有的平臺要求使用標準輸入輸出有的平臺會自動讀文件。如果你平時習慣本地IDE調試考前一定要先在模擬環(huán)境里做幾道題熟悉打印調試print調試的習慣因為你不能像在IDE里一樣設置斷點和單步執(zhí)行。另外代碼的輸入解析也是一大坑。筆試的輸入通常是多行文本需要自己按行讀取和拆分。C的cin和getline混用會出問題Python的input()和sys.stdin.readline()行為也不一樣。我見過太多人因為輸入解析卡住最后白白浪費時間的例子。7. 從校招筆試到工程能力這套題的長期價值7.1 算法題之外的東西刷完這套題除了算法本身還有一些更重要的收獲。第一題大整數(shù)乘法鍛煉的是“用基礎數(shù)據(jù)結構實現(xiàn)看似簡單但實際有陷阱的功能”的能力。在工作中處理訂單號拼接、金額計算、優(yōu)惠券疊加時你經常會遇到類似“直接相加會溢出需要自己維護精度”的問題。第三題數(shù)三角形本質上是在訓練“把幾何問題、組合問題轉化成純整數(shù)計算”的思維。這種能力在圖形學、游戲開發(fā)、甚至CAD軟件的應用中都有用武之地。7.2 邊界條件的工程意義很多人覺得筆試考邊界條件是“應試技巧”但我不這么認為。真實的生產環(huán)境里你寫的代碼要面對各種用戶輸入的邊界情況。一個會傳空字符串參數(shù)的調用方一個可能超出整型范圍的金額數(shù)值一個因為時區(qū)導致的時間邊界問題。每一個都是線上事故的隱患。拼多多這套題里反復出現(xiàn)的“負數(shù)、0、重復元素、前導0”其實就是編程基本功里最核心的幾個邊界類型。能把這幾類邊界問題處理得干凈利落的人寫工程代碼時也會有更強的容錯意識。7.3 后續(xù)可以繼續(xù)擴展的方向如果你刷完這套題還有余力我建議按這幾個方向繼續(xù)深入高精度運算的進一步擴展大數(shù)除法、大數(shù)取模、大數(shù)的進制轉換貪心算法的進階區(qū)間調度、哈夫曼編碼、活動選擇問題模擬題與狀態(tài)機很多業(yè)務邏輯本質上是一個狀態(tài)機面試時能畫出狀態(tài)轉移圖會讓人眼前一亮字典序問題的變體字典序的第K個排列、下一個排列、字符串字典序比較的變種這些內容在LeetCode和牛客網上都有大量對應習題難度覆蓋從入門到競賽級可以根據(jù)自己的水平逐步提高。7.4 最后再分享一點刷這套題時我發(fā)現(xiàn)一個很有意思的現(xiàn)象大多數(shù)人卡住的地方不在算法本身而在“理解題意”和“處理邊界”。比如選靚號明明枚舉目標數(shù)字的思路幾十行就能寫完但很多人在“字典序最小”這個要求上繞了很久。我的經驗是面對每一道編程題先用通俗語言把題目復述一遍把輸入輸出樣例手動推演一遍再動手寫代碼。這個習慣養(yǎng)成后不僅筆試正確率大幅提升連日常開發(fā)里接到需求時的理解速度都會快不少。拼多多這套2018校招內推題放在今天依然是很好的訓練材料。如果你能把這幾道題吃透達到看到題目就能快速梳理出“用什么算法、需要維護什么狀態(tài)、有哪些邊界要處理”的水平那你在技術面試中的算法環(huán)節(jié)基本上就有了扎實的底子。