拼多多2018校招的技術(shù)筆試在當(dāng)年可以說是“畫風(fēng)清奇”的存在。別的公司還在出“反轉(zhuǎn)鏈表”“求子數(shù)組最大和”這種經(jīng)典題型時拼多多直接扔出了一堆和業(yè)務(wù)場景強(qiáng)相關(guān)的應(yīng)用題比如多多的拼團(tuán)邏輯、優(yōu)惠券計算、物流路徑規(guī)劃。我當(dāng)年刷這套題的時候第一反應(yīng)是“這考的真是算法嗎”后來做多了才明白它考的是“用工程思維解決真實業(yè)務(wù)問題”的能力。這份題匯總在求職圈流傳了很久幾乎成了準(zhǔn)備電商類公司筆試的必刷清單。這篇文章不打算把每道題都貼一遍完整代碼那樣篇幅太長而且網(wǎng)上已經(jīng)有很多現(xiàn)成答案。我更想站在一個過來人的角度把這套題里反復(fù)出現(xiàn)的題型、背后的知識點(diǎn)、容易踩的坑以及當(dāng)時我們幾個一起刷題的同學(xué)總結(jié)出來的答題策略完整地拆給你看。如果你正在準(zhǔn)備大廠校招尤其是電商、交易、物流方向的技術(shù)崗這篇文章應(yīng)該能幫你少走不少彎路。1. 內(nèi)容整體設(shè)計與思路拆解1.1 這套題到底在考什么先給沒做過這套題的朋友掃個盲。拼多多2018校招編程題匯總網(wǎng)上能搜到的大概有十來道覆蓋了數(shù)組操作、字符串處理、動態(tài)規(guī)劃、貪心算法、圖的遍歷、二叉樹這幾個經(jīng)典板塊。但它的“皮”和傳統(tǒng)ACM題完全不同——它把算法包裝在了一個個電商場景里。比如有一道題是“多多君在小區(qū)門口開了一家水果店每天要配送水果到各個樓棟給定每個樓棟的需求量和距離求最短配送路徑”。這題剝掉外殼核心其實是圖論里的最短路徑或旅行商問題的簡化版。再比如有一道和“優(yōu)惠券疊加”有關(guān)的題本質(zhì)上是一個區(qū)間覆蓋或背包問題的變體。我當(dāng)年第一次看到這些題最大的感受是題目描述特別長信息密度特別高如果不快速提取關(guān)鍵條件很容易被繞進(jìn)去。而且很多題的時間復(fù)雜度約束很緊O(n^2)都不一定穩(wěn)過必須想清楚再動手。為什么拼多多要這么出題我個人的理解是校招筆試不是單純篩“會不會寫代碼”而是要篩“能不能把模糊的業(yè)務(wù)描述轉(zhuǎn)化成清晰的算法模型”。你將來進(jìn)公司要面對的需求絕大多數(shù)都不是“給你一個數(shù)組求最大值”這種句式而是“用戶領(lǐng)了一張滿100減20的券又參加了一個秒殺活動結(jié)算時系統(tǒng)該怎么算錢”。能快速識別出“哦這是背包問題”或“哦這是區(qū)間DP”比單純會背模板重要得多。1.2 準(zhǔn)備這套題的合理路徑如果你拿到這套題我不建議按順序從第一道刷到最后一道。更高效的做法是先把題目按考點(diǎn)歸類然后集中突破。我當(dāng)時的分類方法是這樣的純考基礎(chǔ)功的數(shù)組遍歷、字符串匹配、排序這類題必須全對不能丟分。考算法模型的動態(tài)規(guī)劃背包、區(qū)間DP、貪心、DFS/BFS、最短路徑這類題占大頭需要重點(diǎn)練思路。考代碼實現(xiàn)細(xì)節(jié)的大數(shù)運(yùn)算、高精度、邊界條件處理這類題不難但特別容易在細(xì)節(jié)上翻車。分類之后你會發(fā)現(xiàn)這套題的核心難點(diǎn)就兩個一是從長題干里抽取出數(shù)學(xué)/算法模型二是在限定時間內(nèi)寫出無Bug的代碼。這兩件事都需要刻意練習(xí)。另外說一句這套題雖然叫2018校招題但現(xiàn)在拿來練手完全不過時。因為大廠筆試的風(fēng)格有很強(qiáng)的延續(xù)性現(xiàn)在很多公司出的題依然能看到當(dāng)年那套題的影子。尤其是“場景包裝”這個思路幾乎是電商系公司出題的標(biāo)準(zhǔn)范式。2. 高頻考點(diǎn)與核心知識點(diǎn)拆解2.1 貪心算法看上去簡單證明才是關(guān)鍵拼多多這套題里貪心算法出現(xiàn)頻率很高而且往往是那種“你覺得你對了其實你錯了”的題。舉一個典型的例子多多的貨物裝車問題——有一批貨物每件有重量和價值卡車有載重上限問怎么裝能讓總價值最大。很多人一看就覺得是貪心按單位價值從高到低裝就行但這其實就是背包問題貪心恰恰不保證最優(yōu)解。這類題給我們的啟示是選錯算法模型比不會做更可怕。因為選錯之后你會沿著錯誤的方向思考很久浪費(fèi)時間不說最后交上去的代碼還是錯的。我的經(jīng)驗是只要題目里出現(xiàn)“最大價值”“最小成本”“最優(yōu)方案”這類詞第一反應(yīng)不是去套貪心而是先問自己三個問題局部最優(yōu)能不能推導(dǎo)出全局最優(yōu)有沒有反例能推翻我的貪心策略這道題是不是應(yīng)該用DP尤其在考試環(huán)境下貪心算法的“證明”環(huán)節(jié)經(jīng)常被忽略。大家總覺得“看起來對就行了”但很多貪心策略的漏洞恰恰藏在看似理所當(dāng)然的細(xì)節(jié)里。如果你能快速舉出一個反例立刻轉(zhuǎn)DP往往是最優(yōu)解。2.2 動態(tài)規(guī)劃從記憶化搜索到狀態(tài)壓縮動態(tài)規(guī)劃是這套題的絕對主力。2018年的題里至少有三四道是DP的變體包括經(jīng)典的背包問題、區(qū)間DP、狀態(tài)壓縮DP。我當(dāng)時刷題最大的體會是DP的難點(diǎn)不在寫轉(zhuǎn)移方程而在定義狀態(tài)。狀態(tài)定義一旦對了轉(zhuǎn)移方程就是水到渠成的事狀態(tài)定義錯了后面全亂。以“多多君分糖果”這類題為例具體題目是給不同權(quán)重的孩子分糖果要求滿足一定條件然后求最少糖果數(shù)如果你定義的狀態(tài)是“當(dāng)前分到第i個孩子當(dāng)前剩余糖果數(shù)j”那這個二維DP是能做的。但如果你把狀態(tài)定義成“前i個孩子已經(jīng)滿足條件的最小糖果數(shù)”就漏掉了“剩余糖果數(shù)”這個關(guān)鍵維度錯誤地簡化了問題。這套題還特別喜歡考“區(qū)間DP”。區(qū)間DP的特征是你優(yōu)化的目標(biāo)是一個區(qū)間上的某種最優(yōu)值而且大區(qū)間的解依賴于小區(qū)間的解。常見套路是先枚舉區(qū)間長度再枚舉區(qū)間起點(diǎn)然后枚舉分割點(diǎn)。我當(dāng)時整理過一個模板到現(xiàn)在還在用for (int len 2; len n; len) { for (int i 1; i len - 1 n; i) { int j i len - 1; dp[i][j] INF; for (int k i; k j; k) { dp[i][j] min(dp[i][j], dp[i][k] dp[k1][j] cost(i, j)); } } }這類題的坑在于初始化。很多同學(xué)忘記把長度為1的區(qū)間初始化好或者忘記把不可達(dá)狀態(tài)設(shè)成INF導(dǎo)致答案永遠(yuǎn)是0。這些小細(xì)節(jié)筆試的時候特別容易翻車。2.3 圖的遍歷與最短路徑場景包裝的重災(zāi)區(qū)拼多多2018校招題里有一類題是“物流配送”“好友推薦”“拼團(tuán)關(guān)系鏈”——這些都是圖的典型場景。對算法基礎(chǔ)薄弱的同學(xué)來說最大的障礙不是不會寫B(tài)FS或Dijkstra而是看不出這是一道圖論題。給你一個場景“多多個用戶之間有關(guān)注關(guān)系如果A關(guān)注BB關(guān)注C那么C會出現(xiàn)在A的推薦列表里現(xiàn)在給定關(guān)注關(guān)系求某用戶的二度人脈列表”。這就是典型的BFS層次遍歷只是沒有直接給你鄰接矩陣或鄰接表而已。我當(dāng)時總結(jié)的經(jīng)驗是題目里出現(xiàn)“關(guān)系”“網(wǎng)絡(luò)”“路徑”“可達(dá)”“最短”這些關(guān)鍵詞就要往圖的方向去想。實現(xiàn)的時候注意三點(diǎn)一是用鄰接表而不是鄰接矩陣省空間也省時間二是BFS要用隊列DFS要用棧或遞歸不要搞混三是visited數(shù)組的標(biāo)記時機(jī)很關(guān)鍵——入隊時標(biāo)記和出隊時標(biāo)記會導(dǎo)致完全不同的結(jié)果。2.4 字符串與數(shù)學(xué)題細(xì)節(jié)是魔鬼這套題里有一批“不那么算法”的題比如大數(shù)相加、字符串循環(huán)移位、括號匹配、回文判斷等。這類題看起來簡單但想拿全分不容易。舉個大數(shù)相加的例子。題目會給你兩個特別長的數(shù)字字符串讓你求它們的和。思路很簡單從低位到高位逐位相加用一個變量記錄進(jìn)位。但我那次筆試這道題掛了很多人原因五花八門沒有處理長度不同的情況短的字符串越界了。沒有處理最后一位的進(jìn)位比如991得到00而不是100。沒有處理結(jié)果前導(dǎo)零的問題。這些問題每一個單獨(dú)看都特別蠢但在考場那種緊張狀態(tài)下就是會犯。我后來養(yǎng)成了一個習(xí)慣寫完代碼先跑三個用例——最小輸入、最大輸入、邊界輸入。最小輸入能暴露越界最大輸入能暴露超時和溢出邊界輸入能暴露進(jìn)位和特殊邏輯問題。90%的代碼Bug都能靠這三類用例查出來。3. 典型真題實戰(zhàn)解析3.1 真題一多多的排列計算題目描述大致是給定一個由數(shù)字1到n組成的排列按照字典序從小到大排列求第k個排列是什么。看過LeetCode的同學(xué)應(yīng)該知道這就是“第K個排列”。當(dāng)年這道題出現(xiàn)在拼多多的卷子里迷惑性極強(qiáng)——它看起來像是讓你把所有排列生成出來然后排序?qū)嶋H上n可能非常大全排列的復(fù)雜度根本過不了。正確做法是使用“階乘數(shù)系統(tǒng)”的數(shù)學(xué)方法。思路是這樣的最高位每固定一個數(shù)剩下的排列數(shù)就是 (n-1)! 個。所以我們可以通過 k 除以 (n-1)! 來確定第一位數(shù)字然后更新 k 為 k % (n-1)!繼續(xù)確定下一位。我當(dāng)時寫這道題的時候花了很多時間在“第k個”是從0開始還是從1開始的問題上。如果用0-based索引k要減1如果用1-based直接用。我當(dāng)時選擇了一個最穩(wěn)妥的方案先把k做減一處理k--然后用0-based索引計算每一位。這樣處理起來邏輯最清晰也不容易出邊界問題。這道題的核心考點(diǎn)其實有兩個一是階乘運(yùn)算會不會溢出n大于20的時候long long都不夠用所以必須用數(shù)組或字符串存儲結(jié)果二是二分的思想——每次用除法定位區(qū)間用取余更新目標(biāo)位置。這也是“按值定位”思想的經(jīng)典應(yīng)用。3.2 真題二多多的字符路徑這道題的原型是給定一個二維字符矩陣從某個起點(diǎn)出發(fā)每次只能走上/下/左/右四個方向不能走重復(fù)格子按順序收集字符拼成一個字符串求字典序最大的結(jié)果。剝掉外殼它是DFS回溯的典型題目而且涉及一個很重要的剪枝優(yōu)化如果當(dāng)前路徑的字典序已經(jīng)不可能超過已知最優(yōu)解就直接放棄。說實話這道題當(dāng)年得分率很低因為它有兩個關(guān)鍵難點(diǎn)。第一個難點(diǎn)是DFS的終止條件不好定——是要走到?jīng)]有可行的相鄰字符為止還是走固定步數(shù)第二個難點(diǎn)是“字典序最大”的全局性——你不能只貪心地每一步選最大的那個字符因為可能當(dāng)前這步選了稍小的字符下一步能接到一個極大的字符整體字典序反而更大。我和同學(xué)討論之后一致認(rèn)為這道題最穩(wěn)妥的思路是先用DFS枚舉所有可達(dá)路徑然后用一個全局變量記錄最優(yōu)答案。如果n和m都很小比如不超過5這種暴力枚舉完全可行如果矩陣很大就需要加入剪枝比如記錄“當(dāng)前路徑字典序剩余最大可能字符”有沒有可能超過已知最優(yōu)解。這類題給我最大的教訓(xùn)是不要一上來就寫DFS先估算狀態(tài)空間。如果狀態(tài)空間在可接受范圍內(nèi)DFS暴力枚舉反而是最不容易出錯的方案。反過來如果狀態(tài)空間很大又沒法剪枝那大概率是你理解錯了題意。3.3 真題三多多的求和問題這是一道典型的“數(shù)論二分”題目原題大意是給定一個數(shù)n求和為n的連續(xù)正整數(shù)序列的所有可能方案。比如n9時945也等于234所以答案是2。這道題其實有兩種主流解法。第一種是數(shù)學(xué)公式法連續(xù)序列的長度為len起點(diǎn)為start那么 [(start (startlen-1)) * len] / 2 n。這個公式可以化簡為 (2*start len - 1) * len 2n。于是問題轉(zhuǎn)化為找一個len使得 2n 能被 len 整除且解出來的 start 是正整數(shù)。如果一個一個遍歷len時間復(fù)雜度是O(sqrt(n))完全可行。第二種是雙指針滑動窗口法維護(hù)窗口[l, r]的和如果和小于n就右移r如果和大于n就左移l等于n時記錄答案。這種方法的時間復(fù)雜度是O(n)思路簡單不容易出錯。我當(dāng)時面試的時候用了滑動窗口因為公式法的整除條件很容易漏解尤其是當(dāng)len是偶數(shù)的時候必須滿足 (2n/len - len 1) 是偶數(shù)這個條件特別容易搞混。滑動窗口雖然慢一點(diǎn)但勝在直觀可靠。筆試?yán)锓€(wěn)定拿分比追求最優(yōu)時間復(fù)雜度更重要。4. 常見問題與答題技巧實錄4.1 時間不夠用怎么辦拼多多這套題總共的考試時間大概是90分鐘到120分鐘有四五道編程題。我當(dāng)年最大的感受就是時間根本不夠用。很多人掛在第一題上非要寫出最優(yōu)解結(jié)果后面的題全空了。我的策略是先把所有題都快速看一遍每道題先寫好暴力解或部分分的解確保每個用例都能過一部分。然后重新審視哪道題最有可能在剩余時間內(nèi)優(yōu)化出Full Score集中精力攻那一道。這套題是按用例給分的暴力解通常能拿40%到60%的分比空著強(qiáng)一百倍。注意考試系統(tǒng)一般有“編譯并測試”和“提交”兩個按鈕測試不扣分提交才計入成績。所以寫完后一定要先測試再提交。別怕測試次數(shù)多就怕不測試直接交。4.2 輸入輸出格式的坑筆試題目看起來在考算法其實也在考你的輸入輸出處理能力。拼多多這套題里有幾個特別容易踩的輸入坑第一行給一個整數(shù)T表示有T組測試數(shù)據(jù)。很多同學(xué)只處理了一組。數(shù)組可能用逗號分隔而不是空格。你習(xí)慣性地用空格split直接就解析錯了。輸入數(shù)據(jù)可能有多余的空格和換行不要用讀一行然后split的方式要用統(tǒng)一的tokenizer處理。我后來養(yǎng)成一個習(xí)慣每次筆試前先把IO模板準(zhǔn)備好。無論是“第一行是N第二行是N個數(shù)字”還是“多組輸入直到EOF”都直接復(fù)制模板不現(xiàn)場寫。這個習(xí)慣幫我省下了大量時間。4.3 代碼的正確性驗證方法就算你覺得代碼邏輯對也要學(xué)會自己構(gòu)造測試用例去驗證。我最常用的是三類用例最小用例比如n1、數(shù)組長度為1能最快暴露越界和邏輯漏洞。最大用例比如n10^9看會不會超時、會不會溢出。反例構(gòu)造針對貪心或DP的策略專門構(gòu)造一個極端場景驗證你的算法會不會算錯。有一個經(jīng)驗是所有“看上去很簡單的題”都要特別小心。筆試題目里那些讀題只需要30秒的題往往藏著最深的坑。這種題不要求你算法多高深但你一旦大意就是整道題零分。4.4 筆試的答題順序怎么安排說一下我總結(jié)的答題順序不一定適合所有人但值得參考。我的順序是先把所有題讀一遍大概估算每道題的難度和所需時間在草稿紙上標(biāo)好“先做”和“后做”。先做簡單的字符串和數(shù)組題先把該拿的分都拿到穩(wěn)定軍心。再做數(shù)據(jù)結(jié)構(gòu)題比如二叉樹、鏈表相關(guān)。最后再做DP、貪心這類需要長時間思考和驗證的題。這樣安排的核心邏輯是把“確定性高”的任務(wù)放在前面把“不確定性高”的任務(wù)放后面。因為考試越到后面心態(tài)越容易崩把難題放最后即使沒做出來前面的分?jǐn)?shù)也夠了。5. 復(fù)盤這套題對現(xiàn)在的求職還有什么用5.1 為什么現(xiàn)在仍然值得刷其實距離2018年已經(jīng)過去了很久你可能覺得刷一套老題沒什么意義。但我的看法剛好相反校招筆試這塊技術(shù)棧和語言迭代很快但算法題的核心考點(diǎn)幾乎沒有變過。拼多多2018年出的這些題現(xiàn)在來看仍然是電商標(biāo)配的題型模板——字符串處理、DP、貪心、圖論、數(shù)學(xué)公式這些東西在任何一屆校招筆試?yán)锒际侵仡^戲。更重要的是這套題很好地訓(xùn)練了“長題干閱讀能力”。現(xiàn)在的筆試題目題干越來越長場景包裝越來越花哨。如果你能靜下心把拼多多這些題啃下來再去做其他公司的題你會發(fā)現(xiàn)自己的信息提取速度快了一大截。5.2 從題目反推團(tuán)隊技術(shù)偏好從這套題里你還能看出一點(diǎn)有意思的東西拼多多的技術(shù)面試官很看重“業(yè)務(wù)落地能力”。那些和拼團(tuán)、物流、優(yōu)惠券相關(guān)的題目本質(zhì)上就是在暗示“我們公司就是做這個的我們希望招進(jìn)來的人能快速把技術(shù)應(yīng)用到真實業(yè)務(wù)上”。如果你在筆試之后的面試環(huán)節(jié)里能主動把某道題和拼多多的實際業(yè)務(wù)場景做一個結(jié)合會是一個很加分的表現(xiàn)。我當(dāng)時在面試中被問到“你做過最難的項目是什么”我特意提到了自己用DP優(yōu)化了一個配送路徑規(guī)劃的小項目面試官明顯來了興趣追問了很多細(xì)節(jié)。雖然不是直接對應(yīng)筆試題目但這種“把算法和業(yè)務(wù)結(jié)合”的能力確實是拼多多這類公司很看重的。5.3 延伸學(xué)習(xí)的建議如果你刷完這套題之后覺得不過癮可以從下面幾個方向繼續(xù)深入把題里出現(xiàn)的DP模型全部總結(jié)一遍包括背包、區(qū)間DP、狀態(tài)壓縮數(shù)字DP每類找兩三道同類題鞏固。把圖的BFS/DFS應(yīng)用場景熟悉一遍尤其是拓?fù)渑判蚝妥疃搪窂竭@些都是電商場景的高頻考題。把數(shù)論里常見的整除、取余、質(zhì)因數(shù)分解等知識點(diǎn)過一遍因為很多看似“數(shù)學(xué)題”的編程題本質(zhì)是在考這些基本功。我在刷完這套題后最大的收獲不是背住了某道題的解法而是建立了一個“業(yè)務(wù)場景→算法模型”的反射弧。看到“拼單”想到“分組”看到“優(yōu)惠”想到“DP”看到“網(wǎng)絡(luò)”想到“圖”。這種反射弧需要大量刷題才能形成而拼多多的這套題恰好是一個很合適的訓(xùn)練場。5.4 最后一件事別只刷題要寫博客復(fù)盤我個人經(jīng)驗里最有效的刷題方式不是悶著頭一遍遍做題而是每做完一道有價值的題就寫一篇博客記錄下來。寫的時候你會自然地把題目的場景、解法思路、復(fù)雜度分析、易錯點(diǎn)都過一遍這個過程比單純做題的收獲要大得多。很多知識你以為自己懂了但一寫出來就發(fā)現(xiàn)邏輯順序是亂的。寫博客、做輸出其實是在逼自己把“模糊的懂”變成“清晰的懂”。我當(dāng)年刷拼多多這套題的時候博客里記了好幾篇總結(jié)后來面試前翻一翻很快就能把高頻考點(diǎn)和代碼模板撿起來。這份東西到現(xiàn)在還留在我的筆記里偶爾溫習(xí)依然覺得很受用。