網(wǎng)易2018校園招聘算法工程師有道筆試卷這是一套很有代表性的校招真題。那會兒我還在準備秋招刷到這套卷子的時候第一感覺是相比純互聯(lián)網(wǎng)大廠動輒四道編程題的卷子網(wǎng)易有道的算法筆試題更“綜合”除了寫代碼還會認真考察概率統(tǒng)計、機器學習基礎和業(yè)務思維。如今回看雖然年份稍早但其考點分布和命題思路依然值得準備算法崗的同學考古參考。特別是KMP的next數(shù)組推導、動態(tài)規(guī)劃、貪心、圖論和機器學習基礎這些內(nèi)容在校招筆試里出現(xiàn)的頻率一直很高。這套卷子的內(nèi)容目前網(wǎng)上能搜到的基本是當年考生在?？途W(wǎng)、知乎、博客里的回憶版并非官方完整原卷。但正因為是回憶整理反而更接近實際考場上大家能感知到的重點。這篇文章我按“試卷結構 → 核心考點拆解 → 編程題實操復盤 → 機器學習與概率統(tǒng)計 → 備考建議”來寫盡量把每一類題背后的知識點和解題套路講透。1. 試卷整體結構網(wǎng)易有道的算法筆試到底考什么1.1 從崗位倒推考點網(wǎng)易有道2018年時的主要產(chǎn)品線包括有道詞典、有道翻譯、有道云筆記、有道精品課等這些產(chǎn)品都有大量搜索、推薦、NLP相關的業(yè)務場景。所以它的算法工程師筆試不是純粹的LeetCode刷題比賽而是帶著業(yè)務味道的選拔既要求你數(shù)據(jù)結構與算法基本功扎實又要求你懂機器學習基礎還希望你有一定的概率統(tǒng)計功底。這一點可以從題型分布上看出來。一個典型的算法崗筆試試卷大致會有單選題、多選題、編程題以及問答/簡答題。單選題里會出現(xiàn)“以下哪種排序算法平均時間復雜度最低”這類送分題也會出現(xiàn)“一個袋子里有紅球白球取兩次不放回求第二次取到紅球的概率”這類概率題。編程題一般有兩到三道難度梯度拉開第一道往往是字符串或者模擬題后面會出現(xiàn)DP或者搜索題。我當時拿到這套卷子第一反應是先把所有題目瀏覽一遍標出會做的和不會做的優(yōu)先把送分題拿下再啃硬骨頭。這個策略在時間緊張的筆試中非常關鍵。1.2 典型題型分布按照常見校招算法筆試的口徑我把這類卷子的模塊和占比整理成一張表方便你對照復習考察模塊常見考點預估占比數(shù)據(jù)結構與算法棧、隊列、鏈表、二叉樹、哈希、排序、KMP、二分、貪心、DP、圖論35% - 45%概率統(tǒng)計與數(shù)學古典概型、條件概率、期望、隨機變量、排列組合10% - 15%機器學習基礎過擬合、正則、交叉驗證、特征選擇、常見模型對比10% - 15%深度學習與NLP詞向量、RNN/LSTM、注意力機制、文本分類5% - 10%編程題字符串處理、動態(tài)規(guī)劃、搜索、模擬、手寫數(shù)據(jù)結構30% - 40%當然每年每套卷子的權重會有浮動但這張表基本能反映網(wǎng)易有道的命題傾向。相比騰訊筆試喜歡出大量計算機基礎比如網(wǎng)絡和操作系統(tǒng)網(wǎng)易有道的算法崗試卷明顯更聚焦在“算法與數(shù)據(jù)科學”相關的內(nèi)容上。1.3 命題風格里藏著的業(yè)務影子做這套卷子你會發(fā)現(xiàn)題目有時候會披著一層業(yè)務外衣。比如“用戶在搜索引擎輸入一個詞返回一系列結果如何評估排序質(zhì)量”、“給定一批用戶行為日志如何設計特征預測點擊率”之類的描述。這類題目表面考機器學習實際是看你能不能把算法落地到具體場景里。有道的算法工程師很大一部分工作涉及詞典數(shù)據(jù)挖掘、翻譯質(zhì)量評估、搜索排序和推薦。筆試環(huán)節(jié)出現(xiàn)業(yè)務化描述是為了提前篩選出那些“只會調(diào)包但不懂業(yè)務邏輯”的候選人。所以備考時不要只看算法題還要想想這些算法用在哪、為什么用、有什么坑。2. 核心考點拆解數(shù)據(jù)結構和算法部分2.1 ?？紨?shù)據(jù)結構棧、隊列、二叉樹與哈希表數(shù)據(jù)結構部分選擇題和編程題都會涉及到。棧?？嫉氖抢ㄌ柶ヅ洹⒈磉_式求值隊列?？嫉氖荁FS和循環(huán)隊列二叉樹是重頭戲遍歷方式、層級遍歷、二叉搜索樹性質(zhì)、最近公共祖先都是高頻考點哈希表則更多是結合工程設計來考比如哈希沖突的解決方式、負載因子、擴容策略。我建議你把二叉樹的非遞歸遍歷寫法背到條件反射的程度。筆試環(huán)境下遞歸容易棧溢出而且有些題目明確要求迭代實現(xiàn)。非遞歸前序、中序、后序、層序遍歷各寫一遍其實也就幾十行代碼但考場上省下來的時間很寶貴。哈希表部分要理解鏈地址法和開放定址法的區(qū)別以及為什么Java的HashMap在鏈表過長時會轉成紅黑樹。這些內(nèi)容看起來基礎單選多選都能出而且容易被忽視。2.2 排序算法不只是背復雜度排序算法幾乎必考但很少直接讓你寫一個快速排序。更多考察的是復雜度分析、穩(wěn)定性、適用場景以及排序算法思想在其它題目中的應用。比如快速排序最壞時間復雜度是O(n^2)堆排序是O(n log n)且不穩(wěn)定歸并排序穩(wěn)定但需要額外空間。這些知識點本身不難但要在選擇題里快速判斷就需要你真的理解每一層遞歸發(fā)生了什么。像“在完全亂序的大數(shù)據(jù)量場景下哪種排序最快”“STL的sort底層用了什么混合策略”這類問題考察的就是對排序工程實現(xiàn)的了解。另外堆排序的思想經(jīng)常用于TopK問題歸并排序思想用于外部排序。如果你在編程題里遇到“從海量數(shù)據(jù)中找最大的K個數(shù)”能想到用小頂堆而不是全排序這就體現(xiàn)出了工程思維。2.3 KMP算法與next數(shù)組推導字符串匹配是校招筆試里的常客KMP更是熱搜詞里的高頻內(nèi)容。網(wǎng)易有道的試卷里出現(xiàn)KMP相關的題我并不意外。這類題不會讓你從零發(fā)明KMP而是考察你是否理解next數(shù)組的推導以及模式串失配時到底怎么跳。以模式串 p abacaba 為例常見定義是 next[i] 表示 p[0:i1] 這個子串的“最長相等真前后綴長度”不包含子串自身。我們逐步推導i 0子串是 a沒有真前后綴next[0] 0。i 1子串是 ab前綴 a后綴 b不等next[1] 0。i 2子串是 aba前綴 a 等于后綴 a最長長度為1next[2] 1。i 3子串是 abac前綴 a、后綴 c不等前綴 ab、后綴 ac不等next[3] 0。i 4子串是 abaca前綴 a 等于后綴 anext[4] 1。i 5子串是 abacab前綴 ab 等于后綴 ab長度為2next[5] 2。i 6子串是 abacaba前綴 aba 等于后綴 aba長度為3next[6] 3。所以 next 數(shù)組為 [0, 0, 1, 0, 1, 2, 3]。但注意很多教材和網(wǎng)上的模板會把 next[0] 定義為 -1next[i] 表示前 i 個字符長度為 i的最長相等真前后綴長度。比如《算法導論》的 π 數(shù)組和國內(nèi)教材里的 next 數(shù)組定義有差異。如果按 -1 偏移的那套定義上面這個模式串可以寫成 [-1, 0, 0, 1, 0, 1, 2, 3]。在考場上我強烈建議先看清楚題目給的 next[i] 到底是哪種定義再開始填數(shù)不然容易整道題崩掉。下面給出一段C的KMP next數(shù)組求解代碼寫代碼時建議使用“前綴函數(shù)”的定義邏輯清晰且不容易出錯vectorint buildNext(const string p) { int m p.size(); vectorint next(m, 0); for (int i 1, j 0; i m; i) { while (j 0 p[i] ! p[j]) { j next[j - 1]; } if (p[i] p[j]) { j; } next[i] j; } return next; }KMP的匹配過程其實就是“主串指針不回溯模式串指針按next跳轉”。理解了next數(shù)組的遞推邏輯做匹配部分的代碼就是順手的事。這道題如果出在選擇題一般會給一個模式串和一段主串問你匹配過程中比較了幾次本質(zhì)上還是考察next數(shù)組理解得透不透。2.4 圖論與搜索Dijkstra、拓撲排序圖論在算法崗筆試里不會像ACM那樣考得很難但基礎算法必須會。Dijkstra是單源最短路里的明星算法哪怕不讓你完整手寫也會考“優(yōu)先隊列優(yōu)化后的時間復雜度”“負權邊能不能用Dijkstra”這類概念題。你要能說清楚為什么Dijkstra不能處理負權邊以及Bellman-Ford和SPFA分別適合什么場景。拓撲排序也值得重視。給定一個有向無環(huán)圖輸出拓撲序列。這個知識點可以結合“課程安排是否存在循環(huán)依賴”這種業(yè)務化問題來考。Kahn算法是直觀做法統(tǒng)計每個節(jié)點的入度把入度為0的節(jié)點放入隊列依次處理并減少后繼節(jié)點的入度。這個算法在判斷有向圖是否有環(huán)時也很有用。我當時復習圖論時有個習慣把所有經(jīng)典算法的適用條件和復雜度寫在一張卡片上比如Dijkstra是貪心思想要求非負權BFS能求無權圖的最短路拓撲排序只適用于有向無環(huán)圖。這樣面對選擇題時可以快速排除錯誤選項。3. 編程題實操復盤思路、代碼與踩坑3.1 動態(tài)規(guī)劃從狀態(tài)定義到邊界條件網(wǎng)易系的編程題動態(tài)規(guī)劃是?？?。常見題型包括編輯距離、最長公共子序列、最長上升子序列、背包問題、股票買賣問題等。這些題在LeetCode上都有原型但筆試里往往會在輸入輸出上做些包裝考察你能不能把實際問題抽象成狀態(tài)轉移。以最長上升子序列為例最直觀的O(n^2)做法是定義dp[i]為以第i個元素結尾的最長上升子序列長度轉移方程是 dp[i] max(dp[j] 1)其中 j i 且 nums[j] nums[i]。如果數(shù)據(jù)范圍到10^5就需要借助貪心加二分的O(n log n)解法用tail數(shù)組維護上升子序列的最小末尾。我在復盤這類題時總結了一個步驟先定義狀態(tài)再寫轉移方程然后確認初始化和遍歷順序最后考慮能否優(yōu)化空間。筆試時間緊如果一開始不知道用DP可以先試試暴力遞歸畫出遞歸樹后再看有沒有重疊子問題。這個方法在緊張狀態(tài)下很管用。3.2 貪心算法什么時候敢用貪心貪心算法在筆試里考得比較多的是區(qū)間類問題。比如“給定一系列會議的開始和結束時間最多能安排多少場不沖突的會議”這個經(jīng)典題按結束時間排序然后依次選擇就是正確答案。但貪心最怕的是“感覺對但實際上是錯的”。我建議在寫貪心解法前先用小數(shù)據(jù)在草稿紙上模擬一遍至少排除明顯的反例。比如經(jīng)典的“硬幣找零最少硬幣數(shù)”問題在硬幣面額為1、5、11時貪心選最大面額不一定得到最優(yōu)解這種反例要能舉出來。校招筆試一般不會出太偏的貪心但考察方式往往是把貪心和排序結合起來讓你先排序再掃描一遍所以排序比較器的寫法要熟練。3.3 手寫代碼的常見坑邊界、溢出與輸入輸出編程題最容易翻車的不是算法本身而是邊界條件和輸入解析。當年我用C做筆試經(jīng)常在快排的邊界、二分查找的循環(huán)條件、字符串分割上浪費大量時間。后來我把這些常見坑整理成了檢查清單空數(shù)組、鏈表只有一個節(jié)點時程序是否正常二分查找的左閉右開還是左閉右閉循環(huán)條件是否與mid更新一致整數(shù)加減乘除是否可能溢出尤其是求中位數(shù)用 (left right) / 2 時left right 可能超出int范圍。字符串輸入是否可能包含空格如果包含用cin、scanf還是getline要想清楚。輸出格式是否要求保留小數(shù)點后幾位題目沒說就不要畫蛇添足。筆試環(huán)境通常不允許調(diào)試太久所以這些邊界問題必須在寫代碼時就有意識規(guī)避。我的習慣是寫完代碼后手動構造三組測試正常輸入、極端輸入最大值/最小值、空輸入。3.4 一道完整示例旋轉數(shù)組中的二分查找網(wǎng)易的編程題出現(xiàn)過類似“在一個有序數(shù)組經(jīng)過旋轉后查找目標值”的題目。這道題能綜合考察二分查找的邊界意識非常典型。我給出一個完整的C實現(xiàn)int search(vectorint nums, int target) { int left 0, right nums.size() - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { return mid; } if (nums[left] nums[mid]) { // 左半部分有序 if (nums[left] target target nums[mid]) { right mid - 1; } else { left mid 1; } } else { // 右半部分有序 if (nums[mid] target target nums[right]) { left mid 1; } else { right mid - 1; } } } return -1; }注意 mid left (right - left) / 2 而不是 (left right) / 2就是為了防止整數(shù)溢出。很多題解不會強調(diào)這個細節(jié)但筆試和面試里這屬于加分項。另外這道題還有一個變體如果數(shù)組中存在重復元素nums[left] nums[mid] 這個判斷就可能失效因為可能出現(xiàn)“左指針、中指針、右指針三者相等”的情況此時只能暴力縮小范圍。這個點如果在選擇題里出現(xiàn)值得你展開想一想。3.5 考場上編程題的答題順序遇到兩三道編程題我的策略永遠是一道一道做但會先花30秒判斷每道題的難度。簡單字符串題一般10分鐘內(nèi)搞定中等DP或搜索題控制20到25分鐘如果某題想了10分鐘還沒有思路先跳過把后面能拿的分拿穩(wěn)再回頭啃。網(wǎng)易的筆試系統(tǒng)通常允許在本地IDE里寫然后粘貼到網(wǎng)頁代碼框。建議先在本地跑通樣例再提交到在線判題系統(tǒng)。畢竟網(wǎng)頁上的編譯報錯信息往往比較簡略本地能更快速定位問題。4. 機器學習與概率統(tǒng)計的考察重點4.1 機器學習基礎過擬合、正則化與模型對比算法工程師的筆試不會只考代碼機器學習基礎是拉開差距的關鍵。常見考點集中在過擬合、正則化、交叉驗證、特征選擇、邏輯回歸和SVM等經(jīng)典模型。過擬合這塊你要能說出“訓練誤差低但測試誤差高”的現(xiàn)象以及對應的緩解手段增加訓練數(shù)據(jù)、降低模型復雜度、正則化、Dropout、早停、數(shù)據(jù)增強。正則化里L1要比L2更容易產(chǎn)生稀疏權重這一點理解L1的梯度在0附近的不連續(xù)性就能明白。邏輯回歸與SVM的對比也是高頻。邏輯回歸輸出的是概率天然適合做排序和CTR預估SVM適合小樣本高維分類核技巧能處理非線性問題。但SVM不直接輸出概率需要做Platt縮放。這些對比在單選多選里經(jīng)常出現(xiàn)所以復習時最好自己整理一張“經(jīng)典模型速查表”。4.2 概率統(tǒng)計古典概型與期望計算概率題是網(wǎng)易筆試卷里穩(wěn)定出現(xiàn)的部分。常見的題型有袋子里有3個紅球5個白球不放回取兩次求第二次取到紅球的概率。一枚不均勻硬幣正面朝上的概率為p連續(xù)拋n次求恰好出現(xiàn)k次正面的概率。隨機變量X服從某個分布求期望和方差。貝葉斯公式的條件概率問題。這類題的核心是不要憑直覺而是把事件空間寫清楚。比如“第二次取到紅球”這個問題全概率公式可以拆成“第一次取紅球第二次取紅球”加“第一次取白球第二次取紅球”兩部分答案自然算出來。期望計算上線性性質(zhì)常常能簡化問題比如“n個獨立事件出現(xiàn)次數(shù)的期望等于各事件期望之和”這個性質(zhì)能解決很多看起來復雜的題目。4.3 深度學習與NLP基礎有道做詞典和翻譯所以深度學習與NLP的相關知識在筆試里出現(xiàn)的可能性不低。2018年時Transformer剛提出不久校招考察不會太深但詞向量、RNN/LSTM、注意力機制、文本分類這些概念要懂。詞向量要理解one-hot的缺點和word2vec的基本思想LSTM要知道它通過門控機制緩解RNN的梯度消失問題注意力機制最簡單理解是“在解碼時動態(tài)地關注輸入的不同部分”。如果題目給出一個小場景比如“用深度學習做情感分類文本長度不一怎么辦”那你需要想到padding、截斷、或者用LSTM處理變長序列。我當時備考NLP的一個取巧方法不追求手推公式而是把每個模型“解決什么問題、核心思想是什么、有什么局限性”三句話說清楚。筆試選擇題考察的是理解不是推公式。4.4 遇到不會的題怎么辦考試總有不會的題。我的原則是選擇題不會先排除明顯錯誤選項再用常識猜多選題拿不準的選項寧可不選因為少選還能得部分分錯選直接0分編程題不會完整做也盡量寫出暴力解法或部分通過很多在線判題系統(tǒng)是按測試點給分的。曾有一個考過網(wǎng)易筆試的同學告訴我他一道DP題沒想出來但寫出了能過前30%測試點的暴力版本最后筆試依然通過了。暴力解不是恥辱在有限時間里拿分才是硬道理。5. 常見問題與備考復盤5.1 校招算法筆試復習看什么書如果你現(xiàn)在離筆試還有三個月建議按這個順序復習先過一遍《劍指Offer》的經(jīng)典面試題培養(yǎng)常見算法題的解題手感。然后用LeetCode或?？途W(wǎng)刷題重點刷數(shù)組、字符串、鏈表、二叉樹、動態(tài)規(guī)劃、二分查找、貪心這幾類。不需要刷難題中等題熟練就夠了。算法基礎薄弱的可以把《算法第4版》或者在線的“代碼隨想錄”刷一遍配合圖解理解數(shù)據(jù)結構。最后留一到兩周做歷年真題按筆試環(huán)境模擬練習時間分配。5.2 容易忽略但必須會的知識點不少人刷題只刷熱門題結果筆試選擇題里一些“冷門”知識點反而扣分。我整理了幾個容易被忽略、但出現(xiàn)頻率不低的知識點位運算異或的性質(zhì)、用位運算判斷奇偶、n (n-1) 去掉最低位1。二分查找的變體查找第一個大于等于target的位置、最后一個小于等于target的位置。大數(shù)據(jù)量處理海量數(shù)據(jù)去重、TopK、外部排序要知道位圖和布隆過濾器的思想。手寫常見數(shù)據(jù)結構棧實現(xiàn)隊列、隊列實現(xiàn)棧、LRU緩存。5.3 復盤一套真題的正確姿勢很多同學刷真題做完對答案就扔這是最虧的。我建議每套卷子做三遍第一遍限時模擬按真實考試節(jié)奏做做完只看分數(shù)不細看答案。第二遍逐題分析把每道題背后的考點寫出來標記不會的題目找到對應知識點重新學習和刷相同類型題。第三遍隔一周后重做尤其關注錯題和蒙對的題確認自己真的掌握了。如果你把一套網(wǎng)易道筆試試卷按這個流程走下來收獲會超過盲目刷十道新題。畢竟校招筆試考來考去就是這些基本功反復錘煉才是王道。5.4 簡歷里的項目也要經(jīng)得起追問筆試通過后還有面試而面試官很喜歡從你簡歷里寫到的算法往下問。比如你寫了“用粒子群算法優(yōu)化參數(shù)”那就要能回答粒子群算法和遺傳算法的區(qū)別、慣性權重怎么設置、為什么收斂快但容易早熟。你寫了“用BM25做搜索排序”就要理解BM25的詞頻、逆文檔頻率和文檔長度歸一化是怎么結合的。所以備考筆試時順便把簡歷里的算法過一遍概念既能幫助筆試又能銜接面試。畢竟算法工程師這個崗位筆試只是敲門磚真正決定offer的是對算法本質(zhì)的理解和落地能力。