2018年春招那會兒我還在為研究生的暑期實習到處投簡歷。網(wǎng)易這個崗位開放時我第一時間投了NLP算法實習生。筆試是在在線平臺上完成的兩個小時題量不算小從機器學習基礎(chǔ)到字符串算法再到一些開放性場景題都有涉及。做完最大的感受是基礎(chǔ)不牢真的會當場露餡。后來我又陸續(xù)參加了其他幾家公司的筆試回過頭來再看網(wǎng)易這套題其實代表了一批互聯(lián)網(wǎng)公司NLP實習筆試的典型風格基礎(chǔ)概念占比大、算法題有硬貨、開放題看思維習慣。這篇文章就把這類筆試的考察方向、常考原理和答題思路掰開聊一聊給準備NLP算法實習崗的同學一個可參考的復(fù)盤樣本。1. 整張卷子長什么樣題型分布與考察意圖1.1 題量、時間與分值結(jié)構(gòu)從我在線筆試的實際體驗來看網(wǎng)易這類大廠實習生招聘筆試基本都是客觀題加主觀題混合出題時長在90到120分鐘之間。我印象中當時的題型大致可以分成四塊單項選擇題、多項選擇題、編程題、開放問答。單選題每道分值不高但架不住量大覆蓋范圍非常散多選題最麻煩的地方在于漏選、錯選都不得分對知識點的精確度要求很高編程題一般一到兩道難度中等偏上考的是數(shù)據(jù)結(jié)構(gòu)和基礎(chǔ)算法開放問答通常會結(jié)合業(yè)務(wù)場景比如“如何設(shè)計一個短文本情感分析模塊”這樣的題考察你把理論轉(zhuǎn)化為工程方案的能力。用一個表格來還原我當時遇到的考察范圍分布會更直觀一些題型考察內(nèi)容舉例大概占比單選機器學習基礎(chǔ)、NLP基礎(chǔ)、數(shù)學概率、線性代數(shù)35%多選模型原理細節(jié)、邊界條件、易混淆概念20%編程題字符串處理、數(shù)據(jù)結(jié)構(gòu)、動態(tài)規(guī)劃、貪心25%開放題場景設(shè)計、方案選型、問題排查思路20%這個比例不是精確的原始卷面數(shù)據(jù)但方向上八九不離十。如果你準備的是其他公司的NLP實習筆試大概率也會在類似框架內(nèi)浮動。1.2 網(wǎng)易這屆筆試風格透露出的三個信號第一個信號是重基礎(chǔ)且基礎(chǔ)題不送分。比如貝葉斯公式、TF-IDF的平滑處理、樸素貝葉斯為什么在特征強相關(guān)時效果變差這些看起來“人人都知道”的知識點題目會往細節(jié)處挖。很多同學只背結(jié)論不推公式遇到“換了個說法”的選擇題就懵。第二個信號是編程題不追求偏題怪題但要求一次寫對。在線筆試的編程題不像面試手撕代碼那樣有面試官提示你面對的只有題目描述和編譯器?？疾熘攸c集中在KMP、排序、動態(tài)規(guī)劃、貪心等經(jīng)典問題但數(shù)據(jù)范圍設(shè)置得很“陰”暴力解法往往只能過部分用例。這意味著你不僅要會寫還要寫對復(fù)雜度正確的解法。第三個信號是開放題沒有標準答案但很看答題結(jié)構(gòu)。同樣是“如何解決數(shù)據(jù)稀疏問題”有的人答兩三行籠統(tǒng)的話有的人會從回退平滑、加一平滑、詞向量擴充、子詞切分幾個層面遞進展開。后者在閱卷人眼里就是明顯的加分項。這也是為什么我建議準備筆試時不要只刷題要刻意練習“結(jié)構(gòu)化表達”。2. NLP基礎(chǔ)理論考點從n-gram到CRF必須吃透的原理2.1 語言模型與n-gram平滑和困惑度是高頻點語言模型這塊我當時遇到的選擇題主要集中在n-gram模型的概率計算、平滑方法的作用、以及困惑度的比較。n-gram的核心假設(shè)是馬爾可夫性一個詞出現(xiàn)的概率只和前面n-1個詞有關(guān)。一般化公式是P(w_i | w_1...w_{i-1}) ≈ P(w_i | w_{i-n1}...w_{i-1})實際計算時用極大似然估計P(w_i | w_{i-n1}...w_{i-1}) count(w_{i-n1}...w_i) / count(w_{i-n1}...w_{i-1})問題出在數(shù)據(jù)稀疏語料里總會出現(xiàn)沒見過的n-gram組合直接算概率是0這在很多任務(wù)里會直接崩掉。所以平滑方法就成了必考點。加一平滑Laplace平滑把每個n-gram的計數(shù)加1簡單但會過度懲罰高頻詞Kneser-Ney平滑在當年屬于進階內(nèi)容實習筆試一般不會考到那么深但至少要知道“平滑是解決零概率問題而不是簡單改變詞頻”。困惑度的定義也需要理解得透徹一點。對測試集計算困惑度公式是PP(W) P(w_1 w_2 ... w_N)^(-1/N)。困惑度越低說明模型對測試集的預(yù)測概率越高泛化能力越好。但筆試可能會反過來問為什么困惑度低的模型不一定在具體任務(wù)上表現(xiàn)更好這時候要從“語言模型是生成式建模而下游任務(wù)往往是判別式需求”的角度去答。2.2 詞向量與分布式表示one-hot、TF-IDF、word2vec的差異NLP筆試幾乎必考詞表示。one-hot向量的問題很直觀維度爆炸、無法體現(xiàn)詞與詞之間的相似度。TF-IDF解決了一部分“常見詞權(quán)重過高”的問題但它仍然是基于詞袋的稀疏表示對語義相近的詞無能為力比如“汽車”和“轎車”在TF-IDF空間里完全獨立。word2vec是當年的高頻考點也是現(xiàn)在很多模型的啟蒙。它的核心思路是用一個淺層神經(jīng)網(wǎng)絡(luò)把詞映射成低維稠密向量使得語義相近的詞在向量空間中距離更近。CBOW是根據(jù)上下文預(yù)測中心詞Skip-gram是根據(jù)中心詞預(yù)測上下文。筆試常見問題包括為什么用負采樣因為softmax歸一化需要對詞表里所有詞計算概率詞表幾十萬維太慢。負采樣把多分類問題轉(zhuǎn)化為二分類問題只采樣少量負樣本做區(qū)分。層次softmax是怎么優(yōu)化的利用霍夫曼樹把softmax的計算復(fù)雜度從O(V)降為O(log V)。word2vec和Glove有什么區(qū)別word2vec利用局部滑動窗口信息Glove還引入了全局共現(xiàn)統(tǒng)計兩者在訓練方式和優(yōu)化目標上不同但都能得到有意義的詞向量。這類問題不需要背誦答案關(guān)鍵是要能畫出模型結(jié)構(gòu)圖講清楚損失函數(shù)的形式以及訓練時間和效果之間的權(quán)衡。2.3 序列標注與概率圖HMM和CRF到底哪里不一樣NLP算法崗筆試里序列標注是逃不開的話題。因為分詞、詞性標注、命名實體識別都依賴它。HMM是生成式模型它建模的是聯(lián)合概率P(X, Y)要算出轉(zhuǎn)移概率和發(fā)射概率然后通過維特比算法求最優(yōu)狀態(tài)序列。CRF是判別式模型直接建模條件概率P(Y|X)用特征函數(shù)的方式把上下文信息糅合進來再通過前向-后向算法和維特比算法做推斷。我當年遇到的經(jīng)典選擇題是CRF相比HMM的優(yōu)勢是什么答案的核心有兩點。第一CRF可以引入任意形式的特征函數(shù)不止是當前的詞和當前的標簽還可以是前綴、后綴、詞形、詞典匹配等而HMM只能通過發(fā)射概率間接利用觀測特征。第二CRF解決了標注偏置問題。HMM和MEMM在做局部歸一化時轉(zhuǎn)移分數(shù)低的路徑會被過早抑制而CRF在全局范圍做歸一化能選出一條全局最優(yōu)的序列。這里給一個便于理解的類比HMM像是一個只能看前后相鄰兩站來決定路線的公交司機CRF則像拿著全局地圖同時考慮整條線路的站點分布來選最優(yōu)路線。筆試中如果遇到“給定一個句子用HMM標注結(jié)果可能哪里出錯”這類題思路就是站在“只看局部”的角度找漏洞。2.4 檢索與文本匹配TF-IDF和BM25的細節(jié)不能含糊搜索引擎、問答系統(tǒng)、關(guān)鍵詞抽取都繞不開TF-IDF和BM25。我在復(fù)習時發(fā)現(xiàn)很多同學只知道TF-IDF是“詞頻乘以逆文檔頻率”但具體公式寫不全。這里把關(guān)鍵公式寫出來TF(t, d)詞t在文檔d中出現(xiàn)的次數(shù) / 文檔d總詞數(shù)或者用原始頻次都可以不同實現(xiàn)略有差異。 IDF(t) log(N / df(t))N是文檔總數(shù)df(t)是包含詞t的文檔數(shù)。BM25在TF-IDF的基礎(chǔ)上引入了文檔長度歸一化和詞頻飽和機制公式里k1和b兩個參數(shù)很關(guān)鍵。k1控制詞頻飽和度k1越大詞頻對分數(shù)的貢獻越不容易到達上限b控制文檔長度的影響程度b0時完全不考慮文檔長度b1時完全歸一化。真題可能會給出一個具體檢索場景問“某個長文檔和短文檔都包含同一個關(guān)鍵詞BM25會如何區(qū)分它們”。答案就是短文檔的得分會更高因為短文檔中出現(xiàn)一個關(guān)鍵詞意味著這個關(guān)鍵詞對文檔主題的代表性更強。這種題沒有復(fù)雜的計算但概念不清就答不出來。3. 編程題里的算法硬仗KMP、排序、DP與貪心的真實考法3.1 KMP的next數(shù)組用abacaba完整推導一遍編程題里字符串處理是重頭戲KMP作為經(jīng)典模式匹配算法出鏡率非常高。但很多人在筆試現(xiàn)場會卡在next數(shù)組的定義上。這里必須提醒一句不同教材對next數(shù)組的定義是有差異的有的直接是前綴函數(shù)也就是最長相同前后綴長度有的是失配時模式串指針回退到的位置還有的會整體右移一位再補-1。做題前先看清題目給的公式別自己想當然。以模式串 p “abacaba” 為例我完整推一遍前綴表也就是最長相同前后綴長度下標從0開始。先算每個前綴子串的最長相同前后綴p[0] “a”前綴集合空后綴集合空最長前后綴長度為0。p[0..1] “ab”前綴{“a”}后綴{“b”}沒有交集為0。p[0..2] “aba”前綴{“a”, “ab”}后綴{“ba”, “a”}最長交集為“a”長度1。p[0..3] “abac”前綴{“a”, “ab”, “aba”}后綴{“bac”, “ac”, “c”}無交集為0。p[0..4] “abaca”前綴{“a”, “ab”, “aba”, “abac”}后綴{“baca”, “aca”, “ca”, “a”}最長交集為“a”長度1。p[0..5] “abacab”前綴{“a”, “ab”, “aba”, “abac”, “abaca”}后綴{“bacab”, “acab”, “cab”, “ab”, “b”}最長交集為“ab”長度2。p[0..6] “abacaba”前綴{“a”, “ab”, “aba”, “abac”, “abaca”, “abacab”}后綴{“bacaba”, “acaba”, “caba”, “aba”, “ba”, “a”}最長交集為“aba”長度3。所以前綴表 pi [0, 0, 1, 0, 1, 2, 3]。如果題目把next數(shù)組定義為“失配時需要回退到的位置”采用的是將前綴表右移一位、首位補-1的做法那對應(yīng)的next數(shù)組就是 [-1, 0, 0, 1, 0, 1, 2]。答題時先寫明自己的定義再列結(jié)果閱卷人就不會覺得你錯了。KMP前綴表的計算代碼基本就是這套模板vectorint prefixFunction(const string s) { int n s.size(); vectorint pi(n, 0); for (int i 1; i n; i) { int j pi[i - 1]; while (j 0 s[i] ! s[j]) { j pi[j - 1]; } if (s[i] s[j]) { j; } pi[i] j; } return pi; }筆試中如果時間緊張我建議先把暴力匹配寫出來拿部分分再優(yōu)化成KMP。暴力匹配在絕大多數(shù)在線判題系統(tǒng)中只能過30%到50%的用例但拿了分總比卡死在一道題上好。3.2 排序算法與復(fù)雜度不只背結(jié)論要會推排序算法在筆試里考察頻率極高但很少直接考“快速排序時間復(fù)雜度是多少”這種送分題更多是考察你在一組約束條件下的選擇能力。比如鏈表排序應(yīng)該用什么排序算法答案通常是歸并排序因為鏈表不支持隨機訪問快排的partition操作在鏈表上效率很低而歸并排序天然適合用指針合并。我當時復(fù)習時自己做了一張對比表筆試前反復(fù)看幾遍排序算法平均時間復(fù)雜度最壞時間復(fù)雜度空間復(fù)雜度穩(wěn)定性冒泡排序O(n^2)O(n^2)O(1)穩(wěn)定快速排序O(n log n)O(n^2)O(log n)不穩(wěn)定歸并排序O(n log n)O(n log n)O(n)穩(wěn)定堆排序O(n log n)O(n log n)O(1)不穩(wěn)定插入排序O(n^2)O(n^2)O(1)穩(wěn)定希爾排序O(n log^2 n)O(n^2)O(1)不穩(wěn)定常見考點還包括堆排序建堆的時間復(fù)雜度是多少答案不是O(n log n)而是O(n)。很多人會在這里栽跟頭。為什么因為從最后一個非葉子節(jié)點開始自底向下調(diào)整每個節(jié)點的調(diào)整代價和節(jié)點高度相關(guān)整體時間復(fù)雜度攤下來是O(n)。另一個高頻考點是穩(wěn)定性的實際意義。比如按“先按分數(shù)排序再按姓名排序”希望最終結(jié)果中分數(shù)相同的人仍然按姓名有序這時候第二輪的排序算法必須選擇穩(wěn)定排序。不穩(wěn)定排序會破壞第一輪已經(jīng)排好的順序。3.3 DP和貪心的邊界什么時候不能用貪心動態(tài)規(guī)劃和貪心算法是筆試編程題里拉開差距的主要陣地。常見題目包括編輯距離、最長公共子序列、背包問題、最長上升子序列、區(qū)間調(diào)度等。考得多了你會發(fā)現(xiàn)出題人喜歡在一個經(jīng)典問題上加一個約束條件讓“一眼貪心”的解法失效。我拿一個很經(jīng)典的例子說明找零錢問題。如果硬幣面額是1、5、11需要湊出15元貪心會先拿11元剩下4元需要4個1元總共5枚硬幣但最優(yōu)解是3個5元只需要3枚硬幣。這就是貪心失效的典型場景。硬幣面額不滿足倍數(shù)關(guān)系時必須用動態(tài)規(guī)劃。筆試中遇到一個題目先判斷貪心是否正確靠不靠譜。一個簡單的判斷標準是選擇當前局部最優(yōu)之后是否會影響后續(xù)選擇的效果。如果影響那大概率不能用貪心。另外動態(tài)規(guī)劃的題目要學會寫狀態(tài)轉(zhuǎn)移方程。編輯距離的狀態(tài)轉(zhuǎn)移是dp[i][j] min(dp[i-1][j] 1, dp[i][j-1] 1, dp[i-1][j-1] (s1[i-1] s2[j-1] ? 0 : 1))這道題幾乎每年都在實習生筆試里出現(xiàn)不管是字節(jié)還是阿里只是換了個業(yè)務(wù)包裝。建議把最長公共子序列、編輯距離、背包三種題型的代碼模板背熟筆試現(xiàn)場能省很多思考時間。3.4 位運算與快速冪容易被忽視的送分題網(wǎng)易這套筆試題里還出現(xiàn)了一些和位運算相關(guān)的題目。位運算不是NLP的專屬考點但NLP算法實習生的筆試里它有奇怪的高頻屬性?？赡芤驗槌鲱}人覺得搞AI的人如果連位運算都搞不定寫工程代碼容易出問題。常見的位運算考點包括判斷一個整數(shù)是不是2的冪n 0 (n (n - 1)) 0統(tǒng)計二進制中1的個數(shù)n (n - 1) 循環(huán)清零最低位的1不使用臨時變量交換兩個數(shù)a ^ b; b ^ a; a ^ b?？焖賰缡橇硪粋€?？?。計算a^b mod p如果b很大直接循環(huán)乘會超時需要用二分的思想把指數(shù)拆成二進制long long fastPow(long long a, long long b, long long p) { long long res 1; a % p; while (b 0) { if (b 1) res res * a % p; a a * a % p; b 1; } return res; }快速冪的思想在NLP里其實也有用武之地比如一些概率計算涉及大量乘法需要取模加速。筆試中遇到這類題直接上模板就行。4. 開放題與場景題沒有標準答案的答題思路4.1 設(shè)計一個短文本情感分析模塊從哪幾個維度答開放題里最典型的一道就是“設(shè)計一個短文本情感分析模塊說明你的技術(shù)方案”。這類題沒有唯一答案但答題結(jié)構(gòu)決定了你能拿多少分。我的建議是不要只寫思路要把一個完整的技術(shù)鏈路鋪開數(shù)據(jù)、特征、模型、評估、上線。數(shù)據(jù)層面明確訓練數(shù)據(jù)來源標注樣本規(guī)模正負樣本不均衡的問題怎么處理?？梢杂们楦性~典擴充樣本也可以用遠程監(jiān)督方式通過表情符號打標簽。特征層面?zhèn)鹘y(tǒng)方法用詞袋模型、TF-IDF、情感詞典得分深度學習方法用word2vec初始化Embedding再進BiLSTM或TextCNN。模型層面對比幾個候選模型。樸素貝葉斯簡單快速但效果一般TextCNN在小樣本短文本上效果很好BiLSTM能捕獲長距離依賴但訓練較慢BERT如果是2018年那會可以說BERT剛出來理念可以引入可以從預(yù)訓練模型微調(diào)。評估層面除了整體準確率還需要看類別F1特別是負樣本的召回率。上線后還要考慮推理延遲、模型更新頻率。這種答案結(jié)構(gòu)的好處是閱卷人能夠一眼看出你有沒有真正做過項目而不是背了幾篇博客。4.2 數(shù)據(jù)稀疏與未登錄詞從工程角度給方案開放題喜歡追問數(shù)據(jù)稀疏問題。因為真實業(yè)務(wù)里用戶輸入太隨意了表情、錯別字、中英混搭、網(wǎng)絡(luò)新詞任何一個都是未登錄詞的重災(zāi)區(qū)。筆試題里會問一句“集美們沖鴨”這類文本怎么讓模型理解你能拿分的關(guān)鍵在于不要只提一個方案而是形成一套組合策略詞典層維護領(lǐng)域詞典和網(wǎng)絡(luò)新詞詞典對未登錄詞做詞典匹配直接標注。切詞層采用子詞切分方案比如BPE或WordPiece把“沖鴨”切成更細的片段即使整詞沒出現(xiàn)過片段也能匹配到訓練語料。表示層用詞向量相似度召回。詞表里沒有“沖鴨”但“沖鴨”和“加油”的詞向量可能距離較近可以通過近鄰擴充。模型層用字符級別的Embedding或字向量繞開分詞環(huán)節(jié)。中文按字切分天然不怕詞表外詞。這樣的回答體現(xiàn)了工程落地的層次感比單說“平滑一下”要好得多。我也在復(fù)習時發(fā)現(xiàn)很多公司開放題問的其實是同一個點你遇到模型效果不好時怎么排查這個問題本質(zhì)上就是在考察你對數(shù)據(jù)、特征、模型三個環(huán)節(jié)的掌控力。4.3 一些進階算法名詞被考到的概率從我當時收集到的一些筆試反饋來看題目中偶爾會出現(xiàn)粒子群算法、模擬退火算法、卡爾曼濾波、KL散度與ELBO、BM25這類偏進階的名詞。它們不一定是主流考點但會出現(xiàn)在多選題的一個選項里或者在開放題中作為可選方案出現(xiàn)。以粒子群算法和模擬退火為例這類元啟發(fā)式優(yōu)化算法在NLP里一般用于超參數(shù)搜索、特征選擇等場景。筆試如果單獨考原理常見問法是“模擬退火如何避免陷入局部最優(yōu)”。核心就兩點以一定概率接受更差的解溫度隨時間下降。粒子群的核心是每個粒子根據(jù)自身歷史最優(yōu)和群體歷史最優(yōu)來更新速度與位置。不需要會推導細節(jié)但要知道它們屬于無梯度優(yōu)化適合離散或非凸空間。卡爾曼濾波在詞性標注、目標跟蹤這類時序預(yù)測問題里有應(yīng)用核心是狀態(tài)預(yù)測加觀測更新兩個步驟。考的概率不高但一旦考到答出“用上一時刻狀態(tài)預(yù)測當前狀態(tài)再用當前觀測修正預(yù)測”就能拿大部分分。KL散度和ELBO在變分推斷里是核心概念如果你在回答開放題時提到用變分推斷近似后驗分布會讓閱卷人覺得你讀過不少機器學習原文。5. 筆試之后的復(fù)盤與備考路線建議5.1 時間分配原理、刷題、項目各占多少我自己的備考周期大概是三到四周時間分配可以給大家參考機器學習與NLP基礎(chǔ)原理占40%編程刷題占40%項目復(fù)盤占20%。這個比例可能和很多人的直覺不一樣因為很多人會把時間全花在刷題上。但NLP算法實習生的筆試里基礎(chǔ)概念題占了一半以上的分值這些題不刷LeetCode也能答對但背不下來就是拿不到分。刷題部分不建議按照題號順序刷而是按題型集中突破。我當時的順序是數(shù)組與字符串、排序與查找、鏈表與樹、DP與貪心、圖論與字符串匹配。每一類題刷到能在20分鐘內(nèi)寫出無bug代碼為止。面試筆試不是算法競賽出題范圍有限不需要碰那些超級難的競賽題。項目復(fù)盤也不能忽視。常見問題包括你在這個項目中負責哪部分為什么選這個模型數(shù)據(jù)怎么處理的遇到bad case怎么分析這些在筆試開放題里不會直接出現(xiàn)但會以場景題的方式隔空考察。把項目里的技術(shù)決策梳理清楚開放題自然有東西可寫。5.2 我踩過的坑和對你的建議第一多選題目千萬不要掉進“理想化”陷阱。很多選項單獨看似乎沒問題但要結(jié)合題目語境判斷。比如“word2vec能得到詞向量所以它適合解決一詞多義問題”這個陳述前半句對后半句錯。2018年的word2vec確實不處理多義詞每個詞只有一個向量這直到后來的ELMo和BERT才被打破。筆試題里很喜歡用這種“半對半錯”的選項來篩人。第二編程題先寫暴力解再優(yōu)化AC。在線筆試的判分通常是部分通過制哪怕只過了30%的用例也有分。我見過不少同學一上來憋KMP憋了四十分鐘寫出來還是錯的最后整道題零分。正確策略是先花五分鐘寫暴力版本確保自己理解了題意再花時間優(yōu)化到正解。第三開放題答案不要只有一句話。閱卷人快速掃一遍答案時最直觀的判斷就是有沒有分點、有沒有流程。哪怕你列的方案不是最優(yōu)的只要邏輯鏈完整分數(shù)都會比擠牙膏式答案高一檔。最后分享一點我在實際復(fù)習中的體會NLP算法崗筆試與其說是考察你會不會某個具體算法不如說是考察你面對一個不熟悉的問題時有沒有一套穩(wěn)定的分析框架。這個框架來自對基礎(chǔ)原理的反復(fù)揣摩也來自大量項目的試錯經(jīng)驗。如果你現(xiàn)在準備時間有限可以先把本文提到的幾個核心考點過一遍再用幾套往年題練手會比漫無目的地刷題更高效。