小米2019秋招算法筆試題B這套卷子我前前后后刷了三遍。第一遍是照著網(wǎng)上的回憶版硬做卡在 KMP 的 next 數(shù)組上第二遍是整理考點發(fā)現(xiàn)它幾乎把算法筆試最核心的模塊都覆蓋了第三遍再刷已經(jīng)是拿它當面試前的自測清單用了。如果你正在準備算法崗的秋招或春招或者只是想看看自己的算法基本功有沒有退化這套題都值得認真過一遍。先說結(jié)論這套 B 卷放在當年大廠筆試里難度不算最變態(tài)但很“小米”——不追求偏題怪題更看重基礎(chǔ)是否扎實、代碼是否干凈。題型大致是選擇、填空、編程題混合覆蓋了字符串匹配、排序、動態(tài)規(guī)劃、貪心、圖論這幾大塊。網(wǎng)上熱詞里反復(fù)出現(xiàn)的 KMP、堆排序、Dijkstra、貪心算法基本就是當年考場上的真實畫風(fēng)。1. 先看全局B卷的考點分布與命題風(fēng)格1.1 題型結(jié)構(gòu)與時間分配2019 年小米秋招算法 B 卷并沒有公開的官方版本現(xiàn)在能看到的都是考過的同學(xué)回憶出來的題。我根據(jù)回憶版和自己的考場經(jīng)驗把結(jié)構(gòu)整理成了一張參考表。具體題號可能記不準確但考察范圍基本是確定的。題型題量參考主要考察內(nèi)容推薦用時選擇題10 - 15 道數(shù)據(jù)結(jié)構(gòu)、復(fù)雜度、排序穩(wěn)定性、圖論概念20 - 30 分鐘填空題5 - 8 道KMP next 數(shù)組、遞推式、概率計算、手算復(fù)雜度20 分鐘左右編程題2 - 4 道動態(tài)規(guī)劃、貪心、搜索、字符串處理60 - 80 分鐘簡答題0 - 1 道算法設(shè)計思路、復(fù)雜度優(yōu)化方案10 分鐘左右這個時間分配是我自己模擬考的時候驗證過的。選擇題和填空題看著分少但特別拉分因為算法崗的簡歷初篩很看重筆試成績一道概念題錯了可能就掉一個檔。編程題是主戰(zhàn)場但不宜死磕某一題卡了 15 分鐘還沒思路就先跳過把能拿的分都拿了再回來。1.2 高頻考點畫像我復(fù)盤的時候把高頻考點和網(wǎng)上的算法熱詞做了個對照B 卷真正想篩的其實就是下面這幾塊考點方向常見熱詞命中的原因字符串匹配KMP、AC 自動機、BM25字符串題最見基本功next 數(shù)組計算非常適合出填空排序算法快排、堆排、歸并、冒泡復(fù)雜度、穩(wěn)定性、手寫代碼全是選擇題素材動態(tài)規(guī)劃背包、編輯距離、LIS區(qū)分度大是編程題主力圖論Dijkstra、拓撲排序、二分圖少數(shù)人真正掌握用來拉差距數(shù)學(xué)快速冪、最大公約數(shù)、貪心代碼短、坑多特別能考察細節(jié)粒子群算法、模擬退火這類智能優(yōu)化算法偶爾也會出現(xiàn)在選擇或判斷題里但通常只是讓你判斷“哪個屬于確定性算法”或者“哪個不適用于離散優(yōu)化”屬于擴展知識。B 卷的主旋律還是經(jīng)典數(shù)據(jù)結(jié)構(gòu)和通用算法所以備考重心不用放在那些花哨的名詞上。2. 核心考點深度拆解2.1 KMP 的 next 數(shù)組到底怎么算KMP 算法是整套 B 卷里最出名的一道題因為網(wǎng)上討論最多的就是“模式串 pabacaba 的 next 數(shù)組是多少”。這個考點看起來簡單但它同時考察了三層能力懂不懂前綴和后綴的概念、能不能手算、能不能用代碼遞推出來。先明確一個基礎(chǔ)定義。對于模式串的一個前綴子串它的最長相等真前后綴長度指的是這個子串中既是前綴又是后綴、且長度小于子串本身的最長部分的長度。比如子串a(chǎn)bab前綴有a, ab, aba后綴有b, ab, bab最長公共前后綴是ab長度是 2。對于pabacaba我們逐位算一下最長相等真前后綴長度下標 i當前前綴最長相等真前后綴長度0a無01ab無02abaa13abac無04abacaa15abacabab26abacabaaba3這里就引出了很多同學(xué)栽跟頭的地方next 數(shù)組有兩種常見定義。一種是“前綴函數(shù)數(shù)組”記作 pi[i]直接存上面表格里的最長相等真前后綴長度另一種是“失配跳轉(zhuǎn)數(shù)組”表示第 i 位失配時應(yīng)該跳到哪個位置繼續(xù)匹配。這兩種定義在筆試題里都出現(xiàn)過如果題目沒有給明確公式一定要先看它要求的是哪一個。如果題目要求的是“第 i 位失配時跳到 next[i]”其中 next[0] -1那么pabacaba的 next 數(shù)組應(yīng)該是next [-1, 0, 0, 1, 0, 1, 2]這個結(jié)果怎么來的把上一張表的長度往右移動一位空出來的 next[0] 填 -1 就行。next[1] 對應(yīng) pi[0]0next[2] 對應(yīng) pi[1]0next[3] 對應(yīng) pi[2]1以此類推。如果題目下標從 1 開始那么可能寫成[0, 0, 0, 1, 0, 1, 2]。所以做題之前先看下標習(xí)慣別把所有版本混在一起。提示KMP next 數(shù)組題最容易犯的錯誤不是不會算最長前后綴而是不清楚題目用的是前綴函數(shù)還是失配跳轉(zhuǎn)。拿到題先看定義再動手。2.2 排序算法復(fù)雜度與穩(wěn)定性是選擇題重災(zāi)區(qū)排序算法在筆試里的地位非常穩(wěn)定幾乎必考。因為一個排序問題可以延伸出很多維度時間復(fù)雜度、空間復(fù)雜度、是否穩(wěn)定、是否原地排序、最好最壞情況、比較次數(shù)、適合數(shù)據(jù)規(guī)模等等。選擇題想拉開差距出排序是最劃算的。我當時整理的速查表是這樣的算法平均時間復(fù)雜度最壞復(fù)雜度空間復(fù)雜度穩(wěn)定性冒泡排序O(n2)O(n2)O(1)穩(wěn)定插入排序O(n2)O(n2)O(1)穩(wěn)定選擇排序O(n2)O(n2)O(1)不穩(wěn)定快速排序O(n log n)O(n2)O(log n)不穩(wěn)定堆排序O(n log n)O(n log n)O(1)不穩(wěn)定歸并排序O(n log n)O(n log n)O(n)穩(wěn)定筆試里快速排序的出現(xiàn)頻率最高因為代碼短但細節(jié)多。小米 B 卷有一道選擇題印象很深“快速排序在什么情況下退化到 O(n2)”答案是當每次 partition 選到的 pivot 都恰好是當前區(qū)間最小或最大值時比如對已經(jīng)有序的數(shù)組固定取第一個元素作為 pivot。這個點本身不難但很多人只記得平均復(fù)雜度忽略了退化條件。另外堆排序和歸并排序也常被用來考察“穩(wěn)定性”這個概念。很多前端或者客戶端方向的候選人容易混淆因為 JavaScript 的Array.prototype.sort()在不同引擎里的穩(wěn)定性都不一樣。筆試題基本都是基于經(jīng)典教材的定義別拿工程實踐來杠。手寫排序算法是編程題的一個備選項我后面會單獨拿一節(jié)來講快排的完整寫法。2.3 動態(tài)規(guī)劃先定狀態(tài)再寫轉(zhuǎn)移B 卷的編程題里動態(tài)規(guī)劃的出鏡率極高。小米的算法崗筆試不可能不考 DP因為 DP 最能看一個人的邏輯歸納能力。我復(fù)盤時遇到最有代表性的一個題是最長上升子序列LIS。題目很簡單給定一個無序整數(shù)數(shù)組找最長嚴格遞增子序列的長度。比如[10, 9, 2, 5, 3, 7, 101, 18]的答案是 4對應(yīng)[2, 3, 7, 101]。DP 的第一步是定義狀態(tài)。定義dp[i]表示以nums[i]結(jié)尾的最長上升子序列長度。這里的關(guān)鍵詞是“以 nums[i] 結(jié)尾”因為只有確定了結(jié)尾才能判斷下一個元素能不能接上去。第二步是初始化。每個元素都可以獨自成為一個子序列所以dp[i]初始為 1。第三步是轉(zhuǎn)移方程。對于每個i遍歷它前面所有j i如果nums[j] nums[i]說明nums[i]可以接在以nums[j]結(jié)尾的子序列后面此時dp[i] max(dp[i], dp[j] 1)。最后答案就是dp數(shù)組的最大值。def lengthOfLIS(nums): n len(nums) dp [1] * n for i in range(n): for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) return max(dp) if n 0 else 0這個解法的時間復(fù)雜度是 O(n2)在 n 不大的情況下夠用。如果 n 到 10?就必須用貪心加二分優(yōu)化成 O(n log n)。這個優(yōu)化思路叫“耐心排序”維護一個 tails 數(shù)組tails[k]表示長度為 k1 的上升子序列的最小末尾值然后對每個元素二分查找它的插入位置。寫法不一樣但背后的狀態(tài)含義更抽象。筆試時如果時間允許建議先寫 O(n2) 版因為不容易錯如果明確給了大數(shù)據(jù)范圍再寫二分優(yōu)化版。2.4 貪心與圖論從“看起來對”到“證明對”貪心算法的題在 B 卷里往往以中等難度出現(xiàn)最經(jīng)典的模型是區(qū)間問題。比如“給定一系列區(qū)間選出盡量多的互不重疊區(qū)間”或者“用最少的點覆蓋所有區(qū)間”。這類題的共同點是先排序再按某種策略逐個決策。以“最多互不重疊區(qū)間”為例正確策略是按照區(qū)間結(jié)束時間從小到大排序然后依次選擇第一個結(jié)束的區(qū)間再跳過所有與它重疊的區(qū)間。這個策略的直觀解釋是結(jié)束得越早后面能留下的空間越大所以越可能選到更多區(qū)間。筆試里除了寫出代碼還要能說清楚“為什么貪心策略是對的”這在簡答題里很加分。圖論部分B 卷經(jīng)常涉及 Dijkstra 和拓撲排序。Dijkstra 考得最多的是一個判斷題“Dijkstra 算法為什么不能處理負權(quán)邊”標準回答是Dijkstra 每輪從當前未訪問的點中選一個距離最小的點把它當成已確定最短路的點這個“已確定”依賴當前距離已經(jīng)是最小值如果存在負權(quán)邊后面可能出現(xiàn)“通過負權(quán)邊達到更小距離”的情況但這個點已經(jīng)被標記完成了無法再更新。記憶方法就是Dijkstra 本質(zhì)是貪心貪心的前提是局部最優(yōu)等于全局最優(yōu)負權(quán)邊會破壞這個前提。拓撲排序也有一個經(jīng)典實現(xiàn)套路叫做 Kahn 算法。維護一個入度表先把所有入度為 0 的點入隊然后逐個出隊每出隊一個點就把和它相鄰的點入度減 1如果某個相鄰點入度變成 0就繼續(xù)入隊。隊列為空時如果訪問過的點數(shù)不等于總點數(shù)說明圖里有環(huán)。def topoSort(n, edges): from collections import deque indeg [0] * n graph [[] for _ in range(n)] for u, v in edges: graph[u].append(v) indeg[v] 1 q deque([i for i in range(n) if indeg[i] 0]) res [] while q: u q.popleft() res.append(u) for v in graph[u]: indeg[v] - 1 if indeg[v] 0: q.append(v) return res if len(res) n else []如果返回空列表說明存在環(huán)。這段代碼在筆試中的通過率很高因為邏輯固定不太需要現(xiàn)場發(fā)揮但前提是你真的理解了入度表的含義。3. 實戰(zhàn)復(fù)盤高頻題手寫全過程3.1 手寫快排從遞歸到邊界處理快排在小米 B 卷里既可能出現(xiàn)在選擇題也可能出現(xiàn)在編程題第一題。我建議所有人把快排背成肌肉記憶因為它是很多復(fù)雜算法的底子比如 Top-K 問題可以用快排的 partition 思想做部分排序。我常用的快排實現(xiàn)是雙指針版本void quickSort(vectorint nums, int left, int right) { if (left right) return; // 空區(qū)間或單元素直接返回 int i left, j right; int pivot nums[(left right) / 2]; // 取中間元素作基準 while (i j) { while (nums[i] pivot) i; // 左邊找大于等于 pivot 的值 while (nums[j] pivot) j--; // 右邊找小于等于 pivot 的值 if (i j) { swap(nums[i], nums[j]); i; j--; } } quickSort(nums, left, j); quickSort(nums, i, right); }這里有兩個細節(jié)容易犯錯。第一pivot 不要固定取nums[left]否則遇到已經(jīng)有序的數(shù)組會退化到 O(n2)取中間元素能在絕大多數(shù)情況下避免這個坑。第二循環(huán)條件是while (i j)而不是while (i j)因為這樣才能保證分區(qū)后左邊和右邊都嚴格小于原區(qū)間不會出現(xiàn)無限遞歸。我見過很多人在這個條件上寫錯遞歸棧溢出直接白給。如果筆試環(huán)境不支持遞歸可以改成顯式棧模擬遞歸但一般情況下 Java 和 C 的遞歸深度足夠處理 10? 的數(shù)據(jù)不需要自己實現(xiàn)棧。3.2 KMP next 數(shù)組現(xiàn)場計算演示前面已經(jīng)講了手算 next 數(shù)組這里再補一個代碼版本。如果題目要你寫一個函數(shù)來計算 next 數(shù)組最穩(wěn)妥的方式是用前綴函數(shù)思想遞推vectorint buildNext(const string p) { int m p.size(); vectorint pi(m, 0); int j 0; for (int i 1; i m; i) { while (j 0 p[i] ! p[j]) { j pi[j - 1]; } if (p[i] p[j]) { j; } pi[i] j; } return pi; }這段代碼算出來的是前綴函數(shù)pi。如果你要的是失配跳轉(zhuǎn)數(shù)組還需要把pi整體右移一位next[0] -1。具體到這個題目模式串pabacaba算出來的pi是[0, 0, 1, 0, 1, 2, 3]右移后得到[-1, 0, 0, 1, 0, 1, 2]。這一步在很多題解里沒有寫清楚但恰恰是考試最容易丟分的地方。3.3 編輯距離的兩種寫法編輯距離是 DP 題里另一個高頻面孔。題目描述是給兩個字符串 word1 和 word2允許插入、刪除、替換三種操作求把 word1 變成 word2 的最少操作次數(shù)。狀態(tài)定義是dp[i][j]表示word1前 i 個字符變成word2前 j 個字符需要的最少操作數(shù)。初始化dp[i][0] i因為要把一個長度為 i 的字符串變成空串只能刪除 i 次同理dp[0][j] j。轉(zhuǎn)移方程考慮三種操作刪除dp[i-1][j] 1插入dp[i][j-1] 1替換如果word1[i-1] word2[j-1]則dp[i-1][j-1]否則dp[i-1][j-1] 1取三者最小值。def minDistance(word1, word2): m, n len(word1), len(word2) 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 word1[i-1] word2[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]由于每一行只依賴上一行和當前行可以用兩個一維數(shù)組滾動更新把空間復(fù)雜度從 O(mn) 降到 O(n)。筆試時如果沒要求優(yōu)化先寫二維版本因為編碼更直接不容易漏初始化。3.4 貪心小題區(qū)間選點B 卷的貪心題很可能給一個具體場景比如“有一些課程每門課有開始時間和結(jié)束時間選盡可能多的課程不能沖突”。這就是經(jīng)典的區(qū)間調(diào)度問題直接用貪心。def intervalSchedule(intervals): intervals.sort(keylambda x: x[1]) count 0 last_end float(-inf) for start, end in intervals: if start last_end: count 1 last_end end return count按結(jié)束時間排序是這類問題的通用解法。關(guān)鍵是為什么不能按開始時間排序因為一個開始早的區(qū)間可能很長會擋住后面很多區(qū)間而結(jié)束時間越早給后面留下的空間越大。這種反例在考試中一定要會舉比如區(qū)間[1, 100]和[2, 3]、[4, 5]如果按開始時間排序選了[1, 100]就只能選 1 個而按結(jié)束時間排序可以選 2 個。4. 刷題血淚史筆試里的常見坑與排查技巧4.1 next 數(shù)組定義不清導(dǎo)致功虧一簣這個坑我栽過而且是實實在在在模擬筆試里栽的。當時題目寫的是next[i]定義為“當?shù)?i 位失配時模式串跳轉(zhuǎn)到的位置”但我腦子里默認用了前綴函數(shù)的定義結(jié)果填出來的數(shù)組完全對不上。后來我發(fā)現(xiàn)很多培訓(xùn)機構(gòu)講 KMP 時用的是“最長相等前后綴長度”作為 next 值而考研教材和互聯(lián)網(wǎng)筆試題又常常用“失配跳轉(zhuǎn)位置”作為 next 值。兩種定義之間只差一個右移但題目不會告訴你它用的是哪種。我的建議是考場上看到 next 數(shù)組題先看題目有沒有給出定義公式。如果給了嚴格按照公式算如果沒給優(yōu)先采用失配跳轉(zhuǎn)位置的定義也就是next[0] -1或next[1] 0的版本因為這是大廠筆試最常見的寫法。同時為了保險可以把兩種定義都寫在草稿紙上對比一下再填答案。4.2 數(shù)據(jù)范圍決定算法選型算法筆試里最難受的不是不會做而是“我明明寫出了正確代碼但超時”。小米 B 卷的編程題不會明著告訴你數(shù)據(jù)范圍但它會在題目描述里給一些隱含線索比如“數(shù)組長度不超過 10?”?？吹竭@個量級基本可以排除 O(n2) 的暴力解法應(yīng)該直接往 O(n log n) 或 O(n) 方向想。我自己的習(xí)慣是拿到題目先看數(shù)據(jù)范圍心里估算一下。103 以內(nèi)可以用 O(n2)10? 左右要用 O(n log n)10? 以上基本要 O(n) 或者接近 O(n)。動態(tài)規(guī)劃題尤其要關(guān)注這一點因為 DP 的樸素寫法往往就是 O(n2)。如果代碼寫完了突然發(fā)現(xiàn)復(fù)雜度不對不要慌先看能不能優(yōu)化。比如最長上升子序列可以從 O(n2) 優(yōu)化到 O(n log n)編輯距離可以用滾動數(shù)組優(yōu)化空間快排可以用隨機 pivot 優(yōu)化退化情況。這些都是筆試考場上性價比很高的操作。4.3 輸入輸出與調(diào)試技巧在線筆試的輸入輸出格式和本地刷題很不一樣。小米用的筆試系統(tǒng)當年是賽碼網(wǎng)輸入可能有多組測試用例每組之間用空行隔開。很多人不是不會做而是卡在讀取數(shù)據(jù)上。經(jīng)驗教訓(xùn)是筆試前先熟悉常見輸入模板。比如 C 用cin讀取不知道有多少組的輸入時用while (cin n)Java 用hasNext()Python 用sys.stdin按行讀。另外輸出格式一定要精確到空格和換行有的題要求“每個答案占一行”有的要求“答案之間用空格分隔”少一個空格就是 Wrong Answer。還有一個調(diào)試技巧本地測試時除了題目示例一定要自己造幾個極端小數(shù)據(jù)尤其是空數(shù)組、單元素數(shù)組、全相等數(shù)組、最大數(shù)據(jù)范圍。這些邊界情況最容易暴露出代碼里的隱患。我在筆試時吃過虧的是求數(shù)組最大值時初始值設(shè)為 0結(jié)果數(shù)組里全是負數(shù)答案直接錯了。正確的初始值應(yīng)該是nums[0]或者INT_MIN。4.4 時間分配先做編程還是先做填空這可能是因人而異的但我的建議是先做有把握的填空和選擇因為它們拿分快能建立信心。KMP next 數(shù)組這種填空題只要定義看清了兩分鐘就能寫完。然后立刻跳去做相對簡單的編程題至少拿到一題的完整分數(shù)。最后把時間留給最難的 DP 或圖論題。千萬不要在一道編程題上死磕超過 20 分鐘。因為算法崗筆試的通過標準往往不是滿分而是看總排名。如果你把時間耗在一道 30% 通過率的難題上可能連基礎(chǔ)題都來不及寫。我刷這套 B 卷時做過一個測試先做編程題后做選擇總分反而低了因為時間被長代碼吃掉了。所以“先易后難先快后慢”是我目前最推薦的時間策略。5. 從B卷看算法面試的底層邏輯5.1 復(fù)雜度直覺比題目本身更重要這套 B 卷刷到最后我最大的感觸是它并不想靠偏題怪題難倒你而是想通過經(jīng)典題看你有沒有“復(fù)雜度直覺”。比如看到 KMP第一反應(yīng)是 O(mn) 的字符串匹配看到 LIS第一反應(yīng)是 O(n log n) 可以優(yōu)化看到區(qū)間調(diào)度第一反應(yīng)是按結(jié)束時間排序。這個直覺不是背題背出來的而是需要大量刷題和復(fù)盤才能形成的條件反射。面試官出題的時候也一樣他們看重的不是你把這道題做對了而是你分析問題的路徑能不能先暴力再優(yōu)化最后說清楚每種方案的復(fù)雜度和適用場景。如果你的答案里能主動說出“當數(shù)據(jù)量大時需要換一種思路”會比悶頭寫代碼好很多。5.2 錯題歸因把每道錯題歸到知識點我整理這套 B 卷的時候做了一個簡單的錯題表把每道錯題歸到對應(yīng)的知識點并標注錯誤原因是概念不熟、邊界沒考慮還是代碼實現(xiàn)有問題。比如 KMP next 數(shù)組那道題我標的是“定義混淆”LIS 那道題我標的是“忘了考慮空數(shù)組”。這樣做的好處是后續(xù)復(fù)習(xí)時不用重頭再來只需要看錯題表里高頻出現(xiàn)的知識點就行。5.3 復(fù)盤模板題目、思路、復(fù)雜度、容易錯點最后分享一個適合所有人的復(fù)盤模板。每做一道題不管對錯都在筆記里按四欄記錄題目簡要描述、核心思路、復(fù)雜度、容易錯點。小米這套 B 卷做完我的筆記大概長這樣題目核心思路復(fù)雜度容易錯點KMP next 數(shù)組最長相等真前后綴右移一位O(m)定義混淆快排雙指針分區(qū)O(n log n)pivot 選第一個導(dǎo)致退化最長上升子序列dp[i] 表示以 i 結(jié)尾O(n2) / O(n log n)初始化遺漏區(qū)間調(diào)度按結(jié)束時間排序O(n log n)排序依據(jù)搞錯這套模板用熟了之后你會發(fā)現(xiàn)很多題其實是在重復(fù)考同一個知識點。比如編輯距離、最長公共子序列、最長上升子序列本質(zhì)上都是二維或一維 DP狀態(tài)定義一換代碼邏輯就很相似。把這些共同點提煉出來筆試的備考效率會提高很多。最后說個我自己的小習(xí)慣。每次筆試結(jié)束不管考得好不好我都會趁熱把沒寫對的題重新歸類寫進同一個復(fù)盤文檔并標上錯誤原因。小米這套 B 卷的 KMP 題我當時就寫了四個字定義混淆。等下次再看到類似的 next 數(shù)組題我會先在草稿紙上把兩種定義都列出來再動手。筆試本來就是個熟練活復(fù)盤到位了下一次才能真正避開同一個坑。