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