小紅書2020校招算法筆試題卷三算是一套在社區(qū)里流傳比較廣的題目。前陣子有學(xué)弟準(zhǔn)備秋招翻出這套題來問我哪些知識(shí)點(diǎn)必須吃透我又把它整體過了一遍。說實(shí)話這套卷子的風(fēng)格很典型不考偏門怪題而是把數(shù)據(jù)結(jié)構(gòu)、字符串處理、機(jī)器學(xué)習(xí)基礎(chǔ)、經(jīng)典算法設(shè)計(jì)這些核心能力揉在一起既看你的代碼功底也看你對(duì)算法本質(zhì)的理解。對(duì)準(zhǔn)備算法崗、推薦崗、NLP崗校招的同學(xué)來說這套題很有參考價(jià)值。這篇博文我就按試卷的考點(diǎn)分布把每一類題目的解題思路、容易踩的坑、以及我實(shí)際寫代碼時(shí)的習(xí)慣都梳理一遍希望能幫到正在刷題的你。1. 筆試整體結(jié)構(gòu)與考點(diǎn)風(fēng)向1.1 卷三的題目構(gòu)成與出題思路先說這套卷子的整體感覺。小紅書2020校招算法筆試題卷三題目范圍覆蓋了字符串算法、排序、機(jī)器學(xué)習(xí)基礎(chǔ)、深度學(xué)習(xí)的常見概念以及幾道偏業(yè)務(wù)的場(chǎng)景題。它不是那種純粹刷LeetCode就能應(yīng)付的卷子因?yàn)橛幸徊糠诸}目會(huì)結(jié)合業(yè)務(wù)場(chǎng)景比如推薦系統(tǒng)里的召回、排序或者圖像處理里的基礎(chǔ)算子。這意味著你不僅要會(huì)寫代碼還得知道算法在真實(shí)場(chǎng)景里是怎么落地的。從出題思路來看這套卷子有幾個(gè)明顯的傾向。第一基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)考察得比較細(xì)尤其是字符串相關(guān)的KMP算法幾乎每年必考而且考的不是背模板而是next數(shù)組的推導(dǎo)過程。第二排序算法喜歡讓你比較不同算法在特定數(shù)據(jù)下的表現(xiàn)而不是單純讓你手寫快排。第三機(jī)器學(xué)習(xí)部分傾向于考察聚類、KNN這類經(jīng)典算法的原理和適用場(chǎng)景深度學(xué)習(xí)部分則集中在損失函數(shù)、優(yōu)化方法、過擬合處理這些高頻考點(diǎn)上。還有一個(gè)有意思的點(diǎn)這套卷子的算法題里出現(xiàn)了不少“邊界情況”的陷阱。比如快速冪的取模問題、KMP的next數(shù)組從0開始還是從1開始這些細(xì)節(jié)如果不提前注意很容易在筆試的時(shí)候翻車。后面我會(huì)針對(duì)這些細(xì)節(jié)單獨(dú)展開講。1.2 算法考點(diǎn)權(quán)重分析我把這套卷子里涉及的考點(diǎn)按出現(xiàn)頻率和重要性做了個(gè)排序方便你確定復(fù)習(xí)優(yōu)先級(jí)。第一梯隊(duì)是字符串算法和經(jīng)典數(shù)據(jù)結(jié)構(gòu)KMP、堆排序、快速排序這些是重中之重基本屬于必考內(nèi)容。第二梯隊(duì)是機(jī)器學(xué)習(xí)與深度學(xué)習(xí)的基礎(chǔ)知識(shí)聚類算法、KNN、損失函數(shù)、優(yōu)化器這幾個(gè)概念反復(fù)出現(xiàn)。第三梯隊(duì)是工程場(chǎng)景題集中在推薦系統(tǒng)召回策略、圖像處理基礎(chǔ)算子上。從復(fù)習(xí)策略上說如果你時(shí)間有限優(yōu)先把KMP的next數(shù)組推導(dǎo)、排序算法的復(fù)雜度對(duì)比、聚類算法的原理與評(píng)估這幾個(gè)點(diǎn)吃透就能拿到大部分基礎(chǔ)分。如果你還學(xué)有余力再去準(zhǔn)備粒子群算法、模擬退火這類智能優(yōu)化算法雖然它們?cè)谛〖t書的筆試?yán)锊凰愀哳l但作為加分項(xiàng)還是值得了解的。我個(gè)人的建議是不要只盯著題海要學(xué)會(huì)總結(jié)每一類題的解題框架。比如看到字符串匹配先想KMP看到需要找到最優(yōu)解的NP難問題可以考慮貪心或者模擬退火看到數(shù)據(jù)需要分組就往聚類方向想。這種“題目特征到算法選擇”的映射關(guān)系比單純刷題有用得多。2. 數(shù)據(jù)結(jié)構(gòu)與字符串算法的核心解法2.1 KMP算法的next數(shù)組推導(dǎo)細(xì)節(jié)KMP算法在這套卷子里被專門拎出來考而且明確給了模式串pabacaba作為例子要求寫出next數(shù)組。這題看起來簡(jiǎn)單但實(shí)際上是很多人的失分點(diǎn)因?yàn)閚ext數(shù)組的定義在不同教材里是有差異的。先說這個(gè)具體例子。模式串pabacaba長(zhǎng)度是7。我們逐個(gè)字符分析。第一個(gè)字符a沒有真前綴和真后綴的概念所以next[0]通常取-1或者0取決于你用的定義。第二個(gè)字符b前面的子串是ab最長(zhǎng)相等真前后綴長(zhǎng)度是0所以next[1]0。第三個(gè)字符a前面的子串是aba最長(zhǎng)相等真前后綴是a長(zhǎng)度是1所以next[2]1。第四個(gè)字符c前面的子串是abac最長(zhǎng)相等真前后綴長(zhǎng)度是0所以next[3]0。第五個(gè)字符a前面的子串是abaca最長(zhǎng)相等真前后綴是a長(zhǎng)度是1所以next[4]1。第六個(gè)字符b前面的子串是abacab最長(zhǎng)相等真前后綴是ab長(zhǎng)度是2所以next[5]2。第七個(gè)字符a前面的子串是abacaba最長(zhǎng)相等真前后綴是aba長(zhǎng)度是3所以next[6]3。這樣算出來的next數(shù)組是[-1, 0, 0, 1, 0, 1, 2, 3]如果第一位補(bǔ)-1的話。但如果你用另一種定義next[i]表示當(dāng)前字符不匹配時(shí)應(yīng)該回退的位置那含義會(huì)略有不同。所以考試的時(shí)候一定要先看清楚題目對(duì)next的定義否則容易滿盤皆輸。這里有一個(gè)實(shí)操中的細(xì)節(jié)我特別想說。很多同學(xué)在筆試的時(shí)候會(huì)臨時(shí)手寫KMP但寫到一半容易把next數(shù)組的遞推邏輯寫錯(cuò)。我建議你在準(zhǔn)備階段就把KMP的代碼寫得非常熟練尤其是失配時(shí)回退的循環(huán)邏輯。有一個(gè)小技巧是在求next數(shù)組的時(shí)候用一個(gè)指針j表示當(dāng)前已匹配的前綴長(zhǎng)度然后依次遍歷模式串。如果當(dāng)前字符匹配j加1next[i]等于j如果不匹配j回退到next[j]的位置直到匹配或者j變?yōu)?1。這個(gè)寫法可以避免很多邊界問題。2.2 排序算法選型與手寫注意事項(xiàng)排序算法在小紅書的筆試?yán)镆步?jīng)常出現(xiàn)。這套卷子雖然沒有直接給一道“手寫快排”的題目但在選擇題或者復(fù)雜度分析題里排序算法的比較是少不了的。尤其是堆排序、快速排序、歸并排序這幾種經(jīng)典算法的穩(wěn)定性、時(shí)間復(fù)雜度、空間復(fù)雜度你必須爛熟于心。這里我整理了一個(gè)對(duì)比表方便你考前快速瀏覽排序算法平均時(shí)間復(fù)雜度最壞時(shí)間復(fù)雜度空間復(fù)雜度穩(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(n)穩(wěn)定堆排序O(n log n)O(n log n)O(1)不穩(wěn)定快排最壞時(shí)間復(fù)雜度退化為O(n2)的情況是每次劃分都極端不平衡比如數(shù)據(jù)已經(jīng)有序而選取了固定基準(zhǔn)。解決方法是隨機(jī)化選取基準(zhǔn)或者取三數(shù)取中法。在實(shí)際筆試中如果題目要求你手寫排序算法我建議優(yōu)先寫清楚快排或者歸并排序因?yàn)樗鼈兊钠骄阅軆?yōu)秀。寫快排的時(shí)候要留意遞歸的終止條件和partition函數(shù)的邊界處理。我第一次寫快排的時(shí)候就是在partition返回值那里搞錯(cuò)了導(dǎo)致死循環(huán)后來形成了肌肉記憶才徹底解決。還有一個(gè)容易被忽視的點(diǎn)就是比較排序的時(shí)間復(fù)雜度下界是O(n log n)如果題目里出現(xiàn)要求O(n)級(jí)別的排序那就要考慮計(jì)數(shù)排序、桶排序或者基數(shù)排序這種非比較排序。小紅書的題里也出現(xiàn)過這種思路題目會(huì)給你一個(gè)特定范圍的數(shù)據(jù)暗示你用桶排序解決。3. 機(jī)器學(xué)習(xí)與深度學(xué)習(xí)考點(diǎn)拆解3.1 聚類算法的場(chǎng)景與評(píng)估機(jī)器學(xué)習(xí)基礎(chǔ)這部分聚類算法是高頻考點(diǎn)。卷子里提到了“聚類算法”這個(gè)熱詞而且從出題趨勢(shì)看不僅會(huì)問你K-Means的原理還會(huì)讓你解釋不同聚類算法的適用場(chǎng)景。K-Means的核心流程其實(shí)很簡(jiǎn)單隨機(jī)選擇K個(gè)中心點(diǎn)然后迭代執(zhí)行兩步第一步把每個(gè)樣本分配到距離最近的中心點(diǎn)第二步重新計(jì)算每個(gè)簇的中心點(diǎn)直到中心點(diǎn)不再變化。但真正理解K-Means你需要知道幾個(gè)關(guān)鍵問題。第一K值怎么選常用的方法是手肘法畫出不同K值對(duì)應(yīng)的SSE曲線找到下降趨勢(shì)明顯變緩的拐點(diǎn)。第二初始中心點(diǎn)的選擇會(huì)影響最終結(jié)果所以K-Means的初始化方式在實(shí)際中更常用它讓初始中心點(diǎn)盡可能分散。第三K-Means對(duì)異常值敏感因?yàn)榫涤?jì)算會(huì)被極端值拉偏。除了K-Means你還需要了解層次聚類和DBSCAN。層次聚類不需要預(yù)先指定K值它通過不斷合并或分裂簇來構(gòu)建樹狀圖。DBSCAN則基于密度能發(fā)現(xiàn)任意形狀的簇還能識(shí)別噪聲點(diǎn)。在小紅書的場(chǎng)景里提到聚類往往和用戶分群、商品類目聚合相關(guān)所以結(jié)合業(yè)務(wù)場(chǎng)景來理解這些算法會(huì)更有優(yōu)勢(shì)。聚類結(jié)果的評(píng)估也是一個(gè)考點(diǎn)。常用的內(nèi)部指標(biāo)有輪廓系數(shù)Silhouette Coefficient它綜合衡量了簇內(nèi)緊密度和簇間分離度取值在[-1, 1]之間越大表示聚類效果越好。外部指標(biāo)則需要有標(biāo)簽才能計(jì)算比如調(diào)整蘭德指數(shù)ARI和標(biāo)準(zhǔn)化互信息NMI。筆試的時(shí)候如果給你一組聚類結(jié)果讓你判斷效果好不好優(yōu)先想到輪廓系數(shù)。3.2 損失函數(shù)與優(yōu)化思路深度學(xué)習(xí)基礎(chǔ)方面這套卷子反復(fù)提到損失函數(shù)、優(yōu)化算法、過擬合處理這幾個(gè)方向。交叉熵?fù)p失、均方誤差損失是最常見的兩個(gè)。分類問題用交叉熵回歸問題用均方誤差這是最基本的搭配。但如果更深一層你需要知道為什么分類問題不直接用均方誤差。因?yàn)榻徊骒嘏浜蟂oftmax可以讓梯度更新更穩(wěn)定而均方誤差在Softmax輸出接近0或1的時(shí)候梯度會(huì)非常小導(dǎo)致學(xué)習(xí)速度變慢。優(yōu)化器這塊SGD、Momentum、RMSProp、Adam這幾代優(yōu)化器的演進(jìn)邏輯值得梳理。SGD簡(jiǎn)單但收斂慢且容易震蕩。Momentum在SGD基礎(chǔ)上引入了動(dòng)量項(xiàng)可以加速收斂并抑制震蕩。RMSProp對(duì)每個(gè)參數(shù)使用不同的學(xué)習(xí)率自動(dòng)調(diào)整步長(zhǎng)。Adam則是Momentum和RMSProp的結(jié)合在實(shí)際工程中使用最廣泛。這里我要提醒一個(gè)筆試中容易遇到的坑Adam雖然好用但有些任務(wù)里它的泛化性能可能不如SGD配合恰當(dāng)?shù)耐嘶饘W(xué)習(xí)率。這個(gè)觀察在很多圖像分類實(shí)驗(yàn)里都出現(xiàn)過。所以如果題目問“為什么有時(shí)候SGD效果比Adam好”你要能從泛化性、學(xué)習(xí)率退火、隨機(jī)性帶來的隱式正則化這幾個(gè)角度來分析而不是簡(jiǎn)單回答“Adam更好”。過擬合的常見手段也幾乎是必考題。L1/L2正則化、Dropout、早停法Early Stopping、數(shù)據(jù)增強(qiáng)這幾種方法在不同場(chǎng)景下的適用邏輯要能區(qū)分。L1正則化帶來稀疏解適合特征選擇場(chǎng)景L2正則化讓權(quán)重趨向于較小值是最常用的權(quán)重衰減Dropout在訓(xùn)練時(shí)隨機(jī)丟棄神經(jīng)元相當(dāng)于集成了多個(gè)子網(wǎng)絡(luò)數(shù)據(jù)增強(qiáng)則通過增加訓(xùn)練樣本多樣性來緩解過擬合。4. 高頻基礎(chǔ)算法題解題思路4.1 貪心與動(dòng)態(tài)規(guī)劃的選擇邏輯基礎(chǔ)算法設(shè)計(jì)題里貪心和動(dòng)態(tài)規(guī)劃是兩大主力。小紅的筆試題卷三里也少不了這兩類。很多同學(xué)遇到一個(gè)最優(yōu)化問題容易糾結(jié)到底該用貪心還是動(dòng)態(tài)規(guī)劃。我分享一下我的判斷方法。貪心算法適合“局部最優(yōu)能推出全局最優(yōu)”的問題也就是說每一步做當(dāng)前看起來最好的選擇最終結(jié)果就是全局最優(yōu)。經(jīng)典例子是找零錢問題如果用無限量的硬幣面額是整除關(guān)系貪心就能得到最優(yōu)解。但如果硬幣面額是任意組合貪心就可能失效。動(dòng)態(tài)規(guī)劃則適用于問題具有重疊子問題和最優(yōu)子結(jié)構(gòu)的情況。你不需要每一步做當(dāng)下最優(yōu)選擇而是通過狀態(tài)轉(zhuǎn)移方程枚舉所有可能的選擇保留每個(gè)狀態(tài)下的最優(yōu)值。典型的例子是背包問題、最長(zhǎng)遞增子序列、編輯距離。這里有一個(gè)我踩過的坑。有一次筆試我遇到一道題看起來可以用貪心我圖省事就直接寫了貪心解法結(jié)果只過了一部分測(cè)試用例。后來我意識(shí)到那道題存在后效性就是當(dāng)前選擇會(huì)影響后續(xù)狀態(tài)所以必須用動(dòng)態(tài)規(guī)劃。從那以后我遇到最優(yōu)解問題時(shí)會(huì)先問自己“當(dāng)前選擇有沒有可能堵住后續(xù)更好的路徑”如果有可能大概率是動(dòng)態(tài)規(guī)劃而不是貪心。動(dòng)態(tài)規(guī)劃的難點(diǎn)在狀態(tài)定義和狀態(tài)轉(zhuǎn)移方程。我的建議是拿到題先畫出遞歸樹看看有沒有重復(fù)計(jì)算。如果有就嘗試用備忘錄或者自底向上的表格法。狀態(tài)定義一般是“dp[i]表示前i個(gè)元素能得到的...”然后通過最后一個(gè)元素的狀態(tài)轉(zhuǎn)移來推導(dǎo)遞推關(guān)系。做題多了你會(huì)發(fā)現(xiàn)很多動(dòng)態(tài)規(guī)劃題的套路是相似的。4.2 快速冪等數(shù)學(xué)算法要點(diǎn)快速冪算法在小紅書筆試?yán)镆渤霈F(xiàn)過。它的核心思想是用二分的方式計(jì)算a的n次方時(shí)間復(fù)雜度從樸素法的O(n)降到O(log n)。原理很簡(jiǎn)單如果n是偶數(shù)a^n (a^(n/2))2如果n是奇數(shù)a^n a * a^(n-1)。通過不斷將指數(shù)減半可以在對(duì)數(shù)時(shí)間內(nèi)完成計(jì)算。寫快速冪的時(shí)候有兩個(gè)細(xì)節(jié)需要特別注意。第一個(gè)是取模。很多題目要求的冪結(jié)果非常大所以題目會(huì)給一個(gè)模數(shù)比如10^97要求在計(jì)算過程中隨時(shí)取模而不是等到最后再取。這里的原理是乘法取模的分配律(a × b) mod m ((a mod m) × (b mod m)) mod m。第二個(gè)細(xì)節(jié)是處理指數(shù)為負(fù)數(shù)或零的情況雖然筆試?yán)锒鄶?shù)是正整數(shù)指數(shù)但養(yǎng)成習(xí)慣總是好的。我用C寫一個(gè)快速冪的模板方便你參考long long quickPow(long long a, long long n, long long mod) { long long res 1; while (n 0) { if (n 1) { res res * a % mod; } a a * a % mod; n 1; } return res; }這段代碼的邏輯是每次循環(huán)判斷當(dāng)前指數(shù)的最低位是否為1如果是1就乘以當(dāng)前的a然后把a(bǔ)平方指數(shù)右移一位。整個(gè)過程把指數(shù)按二進(jìn)制拆解本質(zhì)上和“將n寫成若干2的冪之和”是等價(jià)的。筆試的時(shí)候只要你理解了二進(jìn)制拆分的思路即使忘了模板也能現(xiàn)場(chǎng)推出來。類似的數(shù)學(xué)算法還有GCD的歐幾里得算法以及求乘法逆元的擴(kuò)展歐幾里得算法。這些算法雖然簡(jiǎn)單但在組合數(shù)計(jì)算、概率題、加密相關(guān)題目里會(huì)頻繁出現(xiàn)建議也順手準(zhǔn)備一下。5. 推薦系統(tǒng)與圖像處理場(chǎng)景題5.1 推薦場(chǎng)景下的召回與排序小紅書的業(yè)務(wù)核心是內(nèi)容社區(qū)所以推薦系統(tǒng)的知識(shí)在校招筆試?yán)镎剂瞬簧俜至?。卷三里也出現(xiàn)了和推薦召回、排序相關(guān)的場(chǎng)景題。這類題不會(huì)讓你寫完整的推薦系統(tǒng)但會(huì)考察你對(duì)召回策略、排序模型、特征工程這些概念的理解。推薦系統(tǒng)一般分為召回、粗排、精排、重排這幾個(gè)階段。召回階段的任務(wù)是從全量?jī)?nèi)容庫中快速篩出幾百個(gè)候選集常用方法有基于物品的協(xié)同過濾、基于用戶的協(xié)同過濾、雙塔模型等。排序階段則對(duì)候選集做精細(xì)打分常用模型從早期的LR、GBDT到深度學(xué)習(xí)時(shí)代的DCN、DeepFM等。筆試?yán)锍？嫉囊粋€(gè)點(diǎn)是召回和排序的區(qū)別。曾經(jīng)有同學(xué)問我為什么不能直接用一個(gè)深度學(xué)習(xí)模型對(duì)所有內(nèi)容打分。原因是全量?jī)?nèi)容數(shù)量太大精排模型即使再快也不可能在毫秒級(jí)內(nèi)對(duì)所有物品完成推理所以必須先通過輕量級(jí)召回快速縮小范圍。這個(gè)邏輯理解了場(chǎng)景題才能答到點(diǎn)子上。還有一個(gè)高頻概念是協(xié)同過濾?；谖锲返膮f(xié)同過濾ItemCF的思路是如果用戶A和用戶B都喜歡物品X那么A可能也喜歡B喜歡的其他物品。這里的核心是計(jì)算物品之間的相似度常用余弦相似度或者皮爾遜相關(guān)系數(shù)。但I(xiàn)temCF有一個(gè)冷啟動(dòng)問題新物品沒有交互記錄就很難被推薦出去。解決思路包括基于內(nèi)容特征的冷啟動(dòng)策略利用物品的文字、圖片、標(biāo)簽等屬性計(jì)算相似度。5.2 圖像邊界特征的基礎(chǔ)算子圖像處理相關(guān)的考點(diǎn)雖然沒有推薦系統(tǒng)那么多但像Sobel算子、圖像銳化、拉普拉斯算法這類詞也出現(xiàn)在熱詞里。這說明卷三可能涉及圖像特征提取的基礎(chǔ)題目或者需要你理解卷積操作的基本原理。Sobel算子是一種離散微分算子用來計(jì)算圖像灰度函數(shù)的近似梯度。它通過兩個(gè)3×3的卷積核分別計(jì)算水平方向和垂直方向的梯度。水平方向的Sobel核是[[-1,0,1],[-2,0,2],[-1,0,1]]垂直方向是[[-1,-2,-1],[0,0,0],[1,2,1]]。把兩個(gè)方向的梯度幅值組合起來就得到了邊緣強(qiáng)度圖。拉普拉斯算子則是一個(gè)二階微分算子它不區(qū)分方向直接檢測(cè)灰度突變的位置。常用的3×3拉普拉斯核是[[0,-1,0],[-1,4,-1],[0,-1,0]]或者包含對(duì)角線的變體[[-1,-1,-1],[-1,8,-1],[-1,-1,-1]]。拉普拉斯算子對(duì)噪聲比較敏感所以一般先做高斯平滑再做拉普拉斯檢測(cè)這個(gè)組合叫做高斯拉普拉斯LoG。卷積操作的核心原理在這類題目中屬于基礎(chǔ)中的基礎(chǔ)。你只需要理解卷積核在圖像上滑動(dòng)每個(gè)位置做逐元素相乘再求和就得到輸出圖像的對(duì)應(yīng)像素值。邊界部分通常用零填充Zero Padding或者鏡像填充來處理。這些概念在深度學(xué)習(xí)里的卷積神經(jīng)網(wǎng)絡(luò)中也是完全一樣的理解了基礎(chǔ)算子后續(xù)看CNN會(huì)輕松很多。6. 實(shí)戰(zhàn)復(fù)盤與避坑清單6.1 典型失分點(diǎn)回顧刷這套卷子的時(shí)候我總結(jié)了一些高頻失分點(diǎn)寫在這里幫你避坑。第一個(gè)失分點(diǎn)是KMP的next數(shù)組定義不統(tǒng)一。不同教材、不同選手寫的模板next數(shù)組的下標(biāo)起點(diǎn)和含義都不一樣。如果你在筆試時(shí)照搬某個(gè)博主的模板而題目用的是另一種定義很容易出錯(cuò)。我建議你在試卷開頭花十秒鐘確認(rèn)題目給出的next定義再動(dòng)手推導(dǎo)。第二個(gè)失分點(diǎn)是排序算法復(fù)雜度記憶混亂。尤其是堆排序的空間復(fù)雜度很多人誤以為是O(n)因?yàn)樗褂脭?shù)組存儲(chǔ)堆結(jié)構(gòu)。實(shí)際上堆排序是原地排序空間復(fù)雜度是O(1)。歸并排序因?yàn)樾枰~外的臨時(shí)數(shù)組合并才是O(n)。這種細(xì)節(jié)在選擇題里很容易被拿來當(dāng)干擾項(xiàng)。第三個(gè)失分點(diǎn)是動(dòng)態(tài)規(guī)劃狀態(tài)轉(zhuǎn)移方程寫錯(cuò)邊界條件。比如最長(zhǎng)遞增子序列問題很多人會(huì)把dp[i]定義成前i個(gè)元素的最長(zhǎng)遞增子序列長(zhǎng)度但正確的定義是以第i個(gè)元素結(jié)尾的最長(zhǎng)遞增子序列長(zhǎng)度。這兩種定義寫出來的轉(zhuǎn)移方程完全不一樣。邊界條件寫錯(cuò)整個(gè)答案就廢了。第四個(gè)失分點(diǎn)是場(chǎng)景題回答太籠統(tǒng)。比如問你“如何解決推薦系統(tǒng)冷啟動(dòng)問題”如果你只回答“用熱門內(nèi)容推薦”得分會(huì)很有限。更好的回答是分場(chǎng)景展開新用戶冷啟動(dòng)可以用熱門內(nèi)容和注冊(cè)時(shí)選擇的興趣標(biāo)簽新物品冷啟動(dòng)可以用物品的內(nèi)容特征文本、圖片、類目計(jì)算相似度或者用多臂老虎機(jī)策略在探索和利用之間做權(quán)衡。這種結(jié)構(gòu)化回答才能體現(xiàn)出算法思維。6.2 備考建議與時(shí)間分配最后聊聊怎么備考這類校招算法筆試題。我的建議是把復(fù)習(xí)分成三個(gè)階段。第一階段是基礎(chǔ)鞏固用兩周時(shí)間把數(shù)據(jù)結(jié)構(gòu)數(shù)組、鏈表、棧、隊(duì)列、樹、圖、字符串算法KMP、Trie、排序算法、二分查找、貪心、動(dòng)態(tài)規(guī)劃這些核心模塊過一遍。這一階段不追求刷題數(shù)量而是追求理解每個(gè)算法的原理和適用場(chǎng)景。第二階段是專項(xiàng)突破針對(duì)目標(biāo)公司的真題風(fēng)格做訓(xùn)練。比如小紅書經(jīng)?？纪扑]場(chǎng)景題那么你就需要重點(diǎn)看協(xié)同過濾、Embedding、雙塔模型這些內(nèi)容?？梢哉乙恍C(jī)器學(xué)習(xí)系統(tǒng)設(shè)計(jì)的資料來補(bǔ)充場(chǎng)景知識(shí)。第三階段是模擬實(shí)戰(zhàn)卡著時(shí)間做整套真題。我自己的經(jīng)驗(yàn)是筆試的環(huán)境和平時(shí)刷題很不一樣有時(shí)間壓力、有頁面切換的干擾所以提前適應(yīng)真實(shí)場(chǎng)景很重要。每次模擬完一定要做錯(cuò)題復(fù)盤把每道題的知識(shí)點(diǎn)、錯(cuò)誤原因、正確解法記錄下來。這樣比漫無目的地刷一百道新題更高效。6.3 寫在最后的幾點(diǎn)心得我做完這套卷子后的體會(huì)是算法筆試到最后拼的其實(shí)是對(duì)基礎(chǔ)知識(shí)的熟悉程度而不是會(huì)不會(huì)幾個(gè)炫技的騷操作。所謂“熟悉”就是你看到一道題能快速判斷它屬于哪一類能用最穩(wěn)妥的方法在規(guī)定時(shí)間內(nèi)寫出可運(yùn)行的代碼。這種能力沒有捷徑只能靠長(zhǎng)期的刻意練習(xí)。另外我也特別想提醒一句筆試只是校招的第一關(guān)后面還有面試、項(xiàng)目考察、業(yè)務(wù)考察。算法題做得漂亮不等于你一定能通過所有輪次。但反過來如果算法基礎(chǔ)不扎實(shí)連筆試都過不了。所以還是踏踏實(shí)實(shí)把每一類高頻考點(diǎn)的原理吃透再把代碼寫得又快又穩(wěn)這才是最靠譜的路徑。最后分享一個(gè)小習(xí)慣。我在刷題的時(shí)候會(huì)把每一道做錯(cuò)或卡殼的題用一個(gè)簡(jiǎn)單的標(biāo)簽分類記錄下來比如“字符串-邊界條件”“動(dòng)態(tài)規(guī)劃-狀態(tài)定義”“機(jī)器學(xué)習(xí)-概念混淆”。到了筆試前一天我只復(fù)習(xí)這些標(biāo)簽省時(shí)又高效。希望這套方法也能幫到你祝你順利拿到心儀的offer。