盤：從KMP到卡爾曼濾波的硬核考點)
1. 先說說這份卷子為什么值得翻出來細看1.1 一道春招卷藏著一家公司對算法崗的全部期待很多人對直播公司的算法崗有個刻板印象不就是做推薦、做排序、調(diào)一調(diào)音視頻參數(shù)嗎真正拿到映客2020春招算法A卷的時候我才發(fā)現(xiàn)自己想簡單了。這套卷子從字符串匹配考到PID控制從KMP的next數(shù)組考到卡爾曼濾波跨度大得讓人一度懷疑自己投的是算法工程師還是全棧算法工程師。不過換個角度想這恰恰是直播業(yè)務(wù)的真實映射。映客這種以音視頻互動為核心的產(chǎn)品算法鏈路遠比普通App長內(nèi)容推薦需要機器學(xué)習(xí)排序直播流需要音視頻處理網(wǎng)絡(luò)波動需要碼率控制風(fēng)控需要規(guī)則引擎。所以一套算法筆試題覆蓋多個方向不是出題人隨意拼湊而是整個技術(shù)棧的縮影。我建議準(zhǔn)備算法崗筆試的朋友別只盯著LeetCode刷題。先把目標(biāo)公司的業(yè)務(wù)鏈路拆一遍看看它最依賴哪些算法模塊再針對性復(fù)習(xí)效率會高很多。這也是我復(fù)盤這份卷子時最大的感觸。1.2 從熱搜詞分布反推考察重點把這份卷子相關(guān)的熱搜詞攤開看能明顯看出幾個密集區(qū)字符串與數(shù)據(jù)結(jié)構(gòu)、機器學(xué)習(xí)與搜索排序、音視頻處理、控制與規(guī)則引擎、安全算法。這些不是孤立的考點而是映客這類直播產(chǎn)品技術(shù)體系的五個關(guān)鍵支撐。字符串算法KMP、BM25等對應(yīng)的是內(nèi)容檢索與匹配排序、貪心、堆等數(shù)據(jù)結(jié)構(gòu)題是算法基本功聚類、KNN、強化學(xué)習(xí)等對應(yīng)推薦與用戶增長音頻重采樣、圖像銳化、Sobel對應(yīng)音視頻處理鏈路PID、規(guī)則引擎對應(yīng)播放控制與內(nèi)容安全。所以這份卷子的解題思路其實很清晰先過基本功再看機器學(xué)習(xí)然后落到音視頻和工程細節(jié)。下面我按這個邏輯把每一類題的核心思路拆開講。2. 字符串與數(shù)據(jù)結(jié)構(gòu)題KMP、堆排序、快速冪的實戰(zhàn)拆解2.1 KMP的next數(shù)組兩種定義之間差了什么熱搜詞里有一個很具體的題目描述對于模式串 pabacaba其 next 數(shù)組next[i] 定義為...。這個題我印象太深了因為KMP的next數(shù)組在不同教材和不同題庫里有兩種常見定義答案完全不同。第一種定義next[i] 表示 p[0..i] 這個子串中最長相等前后綴的長度不包含子串自身。按這個定義模式串 abacaba 的 next 數(shù)組計算過程如下i子串最長相等前后綴next[i]0a無長度不能為自身01ab無a≠b02abaa 與 a長度為113abac無04abacaa 與 a長度為115abacabab 與 ab長度為226abacabaaba 與 aba長度為33所以 next [0, 0, 1, 0, 1, 2, 3]。第二種定義next[i] 表示當(dāng) p[i] 失配時模式串應(yīng)該回退到的位置下標(biāo)。這種定義下通常 next[0] -1然后后續(xù)數(shù)值有偏移。按這個定義abacaba 的 next 數(shù)組是 [-1, 0, 0, 1, 0, 1, 2]。我在筆試時吃過這個虧題目文字寫的是最長相等前后綴長度結(jié)果我按跳轉(zhuǎn)位置的定義填了答案白丟一道題的分。所以拿到KMP題第一件事不是動筆算而是先確認題目用的是哪種定義。如果題目給了next[i]的文字定義就嚴格按定義推如果沒給默認按最長相等前后綴長度來做同時注意是否需要 next[0]-1。def get_next(p): n len(p) nxt [0] * n j 0 for i in range(1, n): while j 0 and p[i] ! p[j]: j nxt[j - 1] if p[i] p[j]: j 1 nxt[i] j return nxt p abacaba print(get_next(p)) # [0, 0, 1, 0, 1, 2, 3]這個實現(xiàn)對應(yīng)第一種定義也是我平時寫KMP最順手的版本。筆試時不要現(xiàn)場推實現(xiàn)把模板背熟能省出大量時間給后面的大題。2.2 堆排序的空間復(fù)雜度與快速冪的二進制思維堆排序和快速冪是筆試常客但每次考的點不太一樣。堆排序常見的追問有三個時間復(fù)雜度、空間復(fù)雜度、穩(wěn)定性。堆排序建堆是 O(n)每次調(diào)整是 O(log n)整體時間復(fù)雜度穩(wěn)定在 O(n log n)。它最突出的優(yōu)點是空間復(fù)雜度能做到 O(1)因為完全可以用原數(shù)組存儲堆結(jié)構(gòu)不需要額外數(shù)組。但注意堆排序是不穩(wěn)定的同樣關(guān)鍵字的元素在排序后可能改變相對順序這在面試里經(jīng)常被追問。我當(dāng)時在卷子上寫堆排序時特意標(biāo)注了原地建堆、原地排序并解釋了建堆從最后一個非葉子節(jié)點開始的原因——下沉調(diào)整可以保證每個子樹先滿足堆性質(zhì)自底向上逐步構(gòu)建整體堆。這樣寫閱卷人能看出你不是背代碼而是真懂原理?？焖賰绲暮诵氖嵌M制分解。比如求 a^n把 n 拆成二進制形式從最低位開始每次將底數(shù)平方只有當(dāng)前位為1時才累乘到結(jié)果中。原理和通過乘法快速替代連乘是一樣的時間復(fù)雜度從 O(n) 降到 O(log n)。def fast_pow(a, n, modNone): res 1 while n 0: if n 1: res res * a if mod is None else (res * a) % mod a a * a if mod is None else (a * a) % mod n 1 return res快速冪在密碼學(xué)、大數(shù)運算、概率計算里經(jīng)常出現(xiàn)。如果卷子上有模運算的題記得每一步都取模防止中間結(jié)果溢出。筆試題不會只考一個孤立的快速冪通常會把它包裝成某個實際問題比如倒置鏈表、循環(huán)節(jié)計算、大數(shù)冪取模等。2.3 貪心與其他經(jīng)典題型的答題節(jié)奏貪心算法在筆試題里出現(xiàn)的頻率很高但考的不是能不能想到貪心而是能不能證明貪心正確?；顒舆x擇問題、區(qū)間調(diào)度、找零錢這些都是經(jīng)典題。我當(dāng)時答題時習(xí)慣先給出貪心策略再用反證法或交換論證法簡單寫兩行證明哪怕不完整也能展示思路。排序算法類的題目我建議把各種排序的復(fù)雜度、穩(wěn)定性、適用場景整理成一張表放在腦子里。筆試時遇到請設(shè)計一個時間復(fù)雜度O(n log n)且穩(wěn)定的排序算法第一時間想到歸并排序遇到內(nèi)存受限要求原地排序就選堆排序。這些判斷一定要形成條件反射。排序算法 平均時間 最壞時間 空間 穩(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)定貪心、二分、雙指針這類題答案本身往往不長但邊界條件很容易漏。比如二分查找的左右邊界收縮條件是還是中間值取(leftright)//2還是(leftright1)//2這些細節(jié)直接決定能否通過全部測試用例。我在A卷上做二分變種題時就因為mid的取整方向?qū)懛磁軖炝藘山M邊界數(shù)據(jù)這種失誤太可惜了。3. 機器學(xué)習(xí)算法題把推薦和搜索賽道的基本功吃透3.1 聚類、KNN與用戶分群從三個應(yīng)用能力說起熱搜詞里有一條knn算法的應(yīng)用能力包括哪三個方面這個表述很像是某道簡答題的原文。KNN的三個經(jīng)典應(yīng)用方向是分類、回歸、缺失值填充或異常檢測。分類是最常見的比如根據(jù)用戶行為特征判斷其是否可能付費回歸可以預(yù)測用戶的使用時長缺失值填充則利用近鄰樣本的信息估計缺失特征。不過直播平臺的KNN應(yīng)用場景更貼近用戶分群和相似用戶推薦。登錄映客這類產(chǎn)品時系統(tǒng)會根據(jù)你的年齡、地區(qū)、觀看偏好找到與你最相似的一群用戶然后把他們喜歡的主播推給你。這個邏輯本質(zhì)上就是KNN的思路找K個最近鄰匯總他們的行為偏好排序生成推薦列表。聚類和KNN經(jīng)常一起考。有一道比較經(jīng)典的簡述題是K-Means和KNN有什么區(qū)別。K-Means是無監(jiān)督學(xué)習(xí)KNN是有監(jiān)督學(xué)習(xí)K-Means用于聚類KNN用于分類/回歸K-Means訓(xùn)練過程是迭代更新聚類中心KNN訓(xùn)練過程只是存儲樣本。筆試時如果遇到這種對比題從有監(jiān)督/無監(jiān)督用途訓(xùn)練過程三個維度作答就能拿全分。3.2 強化學(xué)習(xí)、模擬退火與BM25直播場景里的隱藏考點強化學(xué)習(xí)在直播平臺最典型的應(yīng)用是推薦策略優(yōu)化。主播和用戶之間的匹配是一個不斷試錯、不斷獲得反饋的過程推薦一個主播用戶停留時間長、送禮了就是正向獎勵用戶秒退就是負向獎勵。強化學(xué)習(xí)的智能體在這種環(huán)境下學(xué)習(xí)最優(yōu)的推薦策略本質(zhì)上和AlphaGo學(xué)下棋的邏輯一致。模擬退火算法在熱搜詞里出現(xiàn)大概率是作為全局優(yōu)化算法考察。這個算法的思想很有意思物理退火時高溫讓粒子自由移動溫度降低后粒子逐漸穩(wěn)定到低能狀態(tài)。對應(yīng)到優(yōu)化問題里算法以一定概率接受比當(dāng)前解差的新解這個概率隨溫度下降而減小從而跳出局部最優(yōu)尋找全局最優(yōu)。BM25是搜索排序里的經(jīng)典算法騰訊視頻ckey、內(nèi)容搜索等場景經(jīng)常用到。BM25的核心是計算查詢詞和文檔之間的相關(guān)性得分它融合了詞頻、逆文檔頻率和文檔長度歸一化三個因素。筆試考BM25時往往不是讓手寫完整公式而是問它和TF-IDF有什么區(qū)別——BM25對詞頻有飽和機制一個詞出現(xiàn)太多次時增益會遞減而TF-IDF中詞頻是線性增長的。3.3 粒子群、剪枝與XGBoost擴展知識面的正確姿勢粒子群算法PSO是一種模擬鳥群覓食行為的群體智能優(yōu)化算法。每個粒子代表一個候選解粒子在搜索空間里飛行速度和方向受自身歷史最優(yōu)位置和群體歷史最優(yōu)位置影響。在算法崗筆試中粒子群常作為啟發(fā)式優(yōu)化算法的代表被考察與遺傳算法、模擬退火并列為三大經(jīng)典。剪枝算法在直播場景里最直接的應(yīng)用是搜索樹剪枝和推薦候選集剪枝。比如用Minimax算法做井字棋AI時通過alpha-beta剪枝可以大量減少搜索節(jié)點讓AI在有限時間內(nèi)算出最優(yōu)落子。這個知識點在熱搜詞里單獨出現(xiàn)了井字棋minimax算法實現(xiàn)詳解說明出題人可能想考察遞歸搜索與剪枝的結(jié)合。XGBoost和聚類算法則是業(yè)務(wù)實戰(zhàn)中的常客。XGBoost在特征稀疏、數(shù)據(jù)量大的場景下表現(xiàn)突出適合做用戶付費意愿預(yù)測聚類則用于主播分類、內(nèi)容標(biāo)簽聚合。這部分知識不一定在筆試中單獨出計算題但很可能以簡述你熟悉的機器學(xué)習(xí)算法及其適用場景這類開放性問題出現(xiàn)平時積累幾個有深度的案例很有必要。4. 音視頻鏈路里的算法細節(jié)重采樣、圖像銳化與卡爾曼濾波4.1 音頻重采樣直播場景避不開的基本功直播里不同端的音頻采樣率常常不一致主播端可能是48kHz觀眾端播放器可能要求44.1kHz或者需要從48kHz降到16kHz用于語音識別。這個轉(zhuǎn)換過程就是音頻重采樣。最簡單的重采樣是線性插值但工程上更常用的是多相濾波器組或基于FFT的重采樣方案。多相濾波器的思路是設(shè)計一個低通濾波器然后按采樣率轉(zhuǎn)換比例抽取或插值再通過多相結(jié)構(gòu)把計算量降下來。筆試如果考重采樣原理一般會從三個方面問為什么需要抗混疊濾波器、插值和抽取的順序是什么、采樣率轉(zhuǎn)換比例是整數(shù)還是分數(shù)時處理有什么區(qū)別。我當(dāng)時看到音頻重采樣算法這個熱搜詞第一反應(yīng)是出題人可能的問法是直播中回聲消除的延遲是如何影響重采樣設(shè)計的。因為回聲消除需要把遠端參考信號重采樣到近端采樣率重采樣的精度直接影響回聲路徑估計的準(zhǔn)確性。這類題沒有標(biāo)準(zhǔn)答案但抓住采樣率匹配和濾波器設(shè)計兩個核心點就能答到點子上。4.2 拉普拉斯與Sobel圖像銳化和邊緣檢測的題眼圖像銳化是直播美顏、特效模塊的基礎(chǔ)。拉普拉斯算子是一個二階微分算子它突出圖像中灰度突變的地方。用拉普拉斯算子銳化的標(biāo)準(zhǔn)公式是g(x, y) f(x, y) c * ?2f(x, y)其中 f 是原圖像?2f 是拉普拉斯算子作用后的結(jié)果c 是增強系數(shù)。拉普拉斯算子常用的離散卷積核是0 -1 0 -1 4 -1 0 -1 0或者帶對角線擴展的版本。卷積核的本質(zhì)是中心像素乘以4減去上下左右四個鄰域像素結(jié)果能提取出邊緣信息。把邊緣疊加回原圖圖像看起來就更清晰銳利。Sobel算子則是一階導(dǎo)數(shù)的近似它有兩個方向核分別計算水平梯度和垂直梯度Gx [-1 0 1; -2 0 2; -1 0 1] Gy [-1 -2 -1; 0 0 0; 1 2 1]圖像在某像素點的梯度幅值約等于 sqrt(Gx2 Gy2)。筆試時如果讓手寫Sobel邊緣檢測的步驟就是灰度化、分別與Gx和Gy做卷積、求幅值、閾值二值化。這幾個算子我在直播圖像處理項目里反復(fù)用過美顏的皮膚平滑、特效的邊緣增強底層都是這些東西。4.3 卡爾曼濾波從抖動的網(wǎng)絡(luò)里讀出真實碼率卡爾曼濾波是信號處理與控制領(lǐng)域繞不開的經(jīng)典算法。直播推流過程中網(wǎng)絡(luò)帶寬是波動的TCP擁塞窗口、發(fā)送緩沖區(qū)的長度都在變直接測量這些值得到的碼率估計值會劇烈抖動?？柭鼮V波做的事情是通過一個狀態(tài)空間模型把含有噪聲的觀測值和系統(tǒng)的運動規(guī)律融合起來估計出真實狀態(tài)。具體到直播場景可以把網(wǎng)絡(luò)可用帶寬看作系統(tǒng)的狀態(tài) x觀測值 y 是當(dāng)前的吞吐量或延遲變化。系統(tǒng)模型是帶寬緩慢變化過程噪聲小觀測模型是吞吐量受隨機干擾觀測噪聲大?？柭鼮V波的迭代分兩步預(yù)測用上一時刻的狀態(tài)估計當(dāng)前狀態(tài)和更新用當(dāng)前觀測值修正預(yù)測結(jié)果。筆試題里如果要寫卡爾曼濾波的五個核心公式基本是預(yù)測 x_pred F * x_prev P_pred F * P_prev * F^T Q 更新 K P_pred * H^T * (H * P_pred * H^T R)^(-1) x_new x_pred K * (z - H * x_pred) P_new (I - K * H) * P_pred這套公式在筆試中不一定要求完整默寫但至少要能解釋每個變量的含義F是狀態(tài)轉(zhuǎn)移矩陣H是觀測矩陣Q是過程噪聲協(xié)方差R是觀測噪聲協(xié)方差K是卡爾曼增益。理解預(yù)測更新的框架比死記公式更重要。5. 規(guī)則引擎、控制類算法與安全算法算法崗的跨界題5.1 Rete算法規(guī)則引擎Drools的事實匹配過程看到規(guī)則引擎drools的rete算法實現(xiàn)原理和事實匹配過程這個熱搜詞時我愣了一下因為規(guī)則引擎通常不在算法崗筆試的常規(guī)復(fù)習(xí)范圍內(nèi)。但仔細想想直播平臺的內(nèi)容安全、用戶風(fēng)控、審核策略都非常依賴規(guī)則引擎考這個并不突兀。Rete算法的核心思想是利用規(guī)則結(jié)構(gòu)的相似性減少重復(fù)匹配計算。它構(gòu)建一個網(wǎng)絡(luò)包含Alpha節(jié)點條件匹配單個事實的簡單條件和Beta節(jié)點多個事實之間關(guān)系的聯(lián)結(jié)。當(dāng)新事實進入工作內(nèi)存時它沿著網(wǎng)絡(luò)傳遞只經(jīng)過與它相關(guān)的路徑而不是把每一條規(guī)則都重新匹配一遍。筆試如果考Rete最可能出的簡答題是請簡述Rete算法相比樸素匹配的優(yōu)勢。答案要點是保存了規(guī)則匹配的中間狀態(tài)避免重復(fù)計算支持增量更新新增事實時只傳播受影響的路徑規(guī)則多、事實多時效率提升顯著。我有個朋友在風(fēng)控系統(tǒng)里用Drools寫了幾百條規(guī)則匹配性能要求極高Rete算法就是支撐這種場景的關(guān)鍵。5.2 PID、MPPT與FOC控制算法背后的工程思維PID控制算法在熱搜詞里有pid算法、增量式pid算法、pid算法在crps psu power的作用好幾條。PID是比例-積分-微分控制器的縮寫根據(jù)誤差的比例項、累積項和變化趨勢項來計算控制量。公式是u(t) Kp * e(t) Ki * ∫e(t)dt Kd * de(t)/dt增量式PID是數(shù)字控制中常用的變體它輸出的是控制量的增量而不是絕對控制量好處是執(zhí)行器可以平滑過渡誤動作影響小而且不需要累加歷史誤差不容易積分飽和。MPPT最大功率點跟蹤在光伏發(fā)電、電源系統(tǒng)里負責(zé)讓設(shè)備始終工作在最大輸出功率點附近。FOC磁場定向控制則廣泛應(yīng)用于無人機云臺、電機控制中。這幾個算法雖然更偏硬件和自動化但出現(xiàn)在直播公司算法試卷里很可能是結(jié)合了具體業(yè)務(wù)場景比如直播間的智慧燈光控制、電動云臺的穩(wěn)定跟隨、服務(wù)器電源的功耗管理。如果讓你現(xiàn)場手寫一個PID的代碼記住增量式PID的實現(xiàn)會比位置式更簡潔class IncrementalPID: def __init__(self, Kp, Ki, Kd): self.Kp Kp self.Ki Ki self.Kd Kd self.last_err 0 self.prev_err 0 def update(self, target, current): err target - current delta (self.Kp * (err - self.last_err) self.Ki * err self.Kd * (err - 2 * self.last_err self.prev_err)) self.prev_err self.last_err self.last_err err return delta5.3 弱哈希修復(fù)與國密算法安全方向的基本常識熱搜詞里有一條ssl證書使用了弱hash算法cve-2005-4900怎么修復(fù)這也是算法崗可能會碰到的實際安全問題。CVE-2005-4900涉及使用弱哈希算法如SHA-1簽名的SSL證書主要修復(fù)手段是用SHA-256或更強的哈希算法重新生成證書簽名請求向CA重新申請證書如果內(nèi)網(wǎng)自簽名證書需要更新簽發(fā)策略并重新部署到所有信任鏈節(jié)點同時檢查服務(wù)端SSL配置禁用不支持強哈希的加密套件。這里要注意的是證書的哈希算法和加密算法是兩回事。哈希算法用于證書簽名加密算法用于TLS握手時的密鑰交換。修復(fù)弱哈希問題核心動作是換簽名算法而不是換加密套件。我在實際項目里修過類似問題尤其是一些老舊的內(nèi)部系統(tǒng)證書鏈里藏著SHA-1簽名的根證書或中間證書光換葉子證書不檢查整條鏈問題依然存在。SM2、SM3、SM4和ZUC是國密算法體系分別對應(yīng)公鑰加密、哈希、分組加密和流加密。有些企業(yè)級項目會要求支持國密算法尤其是在政務(wù)、金融場景。算法崗筆試即使不細考國密算法的實現(xiàn)細節(jié)也可能會問它們和AES、RSA、SHA-256的區(qū)別。答這類題的關(guān)鍵是明確SM2基于橢圓曲線SM3輸出256位摘要SM4分組長度128位ZUC是祖沖之序列密碼。5.4 內(nèi)容簽名與版權(quán)保護一個容易被忽略的考點熱搜詞里還有騰訊視頻ckey5.x算法_php版這和視頻內(nèi)容的防盜鏈、版權(quán)保護有關(guān)。視頻平臺會在播放請求中附加簽名參數(shù)服務(wù)端校驗簽名是否合法、是否過期、是否為特定設(shè)備生成。這類算法的核心是請求參數(shù)密鑰時間戳的簽名邏輯通常是一套帶特定排列和哈希的算法。我不建議為了筆試去研究某個具體視頻平臺的簽名逆向那是另一個領(lǐng)域的事了。但算法工程師應(yīng)當(dāng)理解內(nèi)容簽名和防篡改背后的通用原理是HMAC或RSA簽名核心是密鑰不出客戶端、簽名可驗證、時間戳防重放。答題時能說清楚這個原理已經(jīng)能體現(xiàn)對該方向的理解。5.5 工業(yè)異常檢測與DC3算法邊角知識也有存在感工業(yè)異常檢測算法和dc3算法出現(xiàn)在熱搜詞里說明這份卷子的考察范圍并不局限于常規(guī)算法題。工業(yè)異常檢測通常用重構(gòu)誤差來判斷樣本是否異常訓(xùn)練一個自編碼器正常樣本的重構(gòu)誤差小異常樣本的重構(gòu)誤差大設(shè)定閾值即可區(qū)分。這個思路在直播場景的異常流量檢測、黑產(chǎn)賬號識別中也能遷移使用。DC3算法是線性時間構(gòu)造后綴數(shù)組的算法屬于字符串算法的進階內(nèi)容。KMP解決單模式匹配后綴數(shù)組解決多模式匹配、最長公共子串等問題。如果筆試里考到DC3大概率是問相比倍增加法O(n log n)DC3為什么能做到O(n)答案要點是把字符串分成三類位置遞歸構(gòu)造其中兩類的后綴排名再線性合并得到完整后綴數(shù)組。這類題平時見到的概率不大但真出現(xiàn)了能答出一個核心思路就已經(jīng)超過大多數(shù)考生。6. 現(xiàn)場筆試的答題順序與復(fù)盤總結(jié)6.1 我的答題策略先掃一遍全卷再按性價比切題拿到A卷后我習(xí)慣先花5分鐘快速瀏覽全部題目標(biāo)注難度和預(yù)估耗時而不是從第一題開始硬做。我的優(yōu)先順序是有明確答案的基礎(chǔ)題如KMP next數(shù)組、排序復(fù)雜度先做中等難度的算法實現(xiàn)題快速冪、堆排序次之簡述題如Rete算法原理、PID在業(yè)務(wù)中的作用再往后最后啃綜合大題的硬骨頭。這樣做的好處是保證基礎(chǔ)分先落袋不至于在一道大題上卡太久導(dǎo)致后面會做的題沒時間寫。我當(dāng)時估算每道題的時間是選擇題/填空題每題2分鐘代碼題每題10-15分鐘簡述題每題5分鐘大題20分鐘?？偡址峙浜蜁r間分配對上了考試才不會慌。6.2 我踩過的坑與改進方向現(xiàn)在回頭復(fù)盤有幾個坑值得提醒正在準(zhǔn)備筆試的朋友。坑一是看到熟悉的題就掉以輕心。我在KMP那道題上就是因為太自信沒看清題目對next數(shù)組的定義結(jié)果填錯了。無論多熟悉的題下筆前把題目要求完整讀兩遍尤其是那些定義為注意后面的文字。坑二是填空題留白。有些題不會做就直接跳但算法卷的填空題、簡答題往往有按點給分的潛規(guī)則哪怕只寫出部分公式、部分思路也能拿一些步驟分。用代碼實現(xiàn)題尤其如此寫出一個可運行但不夠優(yōu)化的版本分數(shù)會比空著高很多?？尤遣蛔⒁獯a的邊界條件?？焖賰鐩]取模、二分查找沒有處理空數(shù)組、遞歸沒有出口這些是筆試代碼最常見的問題。我后來養(yǎng)成一個習(xí)慣寫完代碼后先用一個極簡的測試用例在草稿紙上走一遍比如數(shù)組長度為0或1、n為0或1的場景能提前發(fā)現(xiàn)大部分bug。6.3 適合大多數(shù)人的備考Checklist根據(jù)這份A卷的考點分布給自己列一個備考清單字符串算法KMP的next數(shù)組兩種定義、后綴數(shù)組基本概念、BM25核心公式數(shù)據(jù)結(jié)構(gòu)排序時間復(fù)雜度與穩(wěn)定性、堆排序手寫、快速冪、二分查找邊界機器學(xué)習(xí)聚類與KNN區(qū)別、XGBoost適用場景、強化學(xué)習(xí)基本流程、模擬退火思想音視頻音頻重采樣原理、拉普拉斯與Sobel卷積核、卡爾曼濾波公式框架工程算法PID與增量式PID代碼、Rete算法匹配過程、異常檢測思路安全基礎(chǔ)弱哈希修復(fù)步驟、國密算法分類、內(nèi)容簽名通用原理。這份清單并不追求每個點都深挖到論文級但對于一場算法崗筆試來說覆蓋面已經(jīng)足夠了。關(guān)鍵是每個方向都能說出是什么、為什么、怎么用。我后來把這份卷子給準(zhǔn)備校招的幾個學(xué)弟學(xué)妹看過他們反饋最有用的是KMP的next數(shù)組定義對比和PID增量式實現(xiàn)那段因為網(wǎng)上的資料很少把筆試中的定義差異講得這么細。也正是這些看起來簡單但容易踩坑的知識點才最能拉開考生之間的差距。如果你也正在準(zhǔn)備算法崗筆試不妨把這份卷子當(dāng)作一份模擬題來限時訓(xùn)練做完之后再對著自己的薄弱點專項突擊。算法筆試考的從來不只是會不會更是在有限時間內(nèi)能不能穩(wěn)定做對這個能力只能靠反復(fù)實戰(zhàn)來打磨。 映客算法筆試復(fù)盤：從KMP到卡爾曼濾波的硬核考點
1. 先說說這份卷子為什么值得翻出來細看1.1 一道春招卷藏著一家公司對算法崗的全部期待很多人對直播公司的算法崗有個刻板印象不就是做推薦、做排序、調(diào)一調(diào)音視頻參數(shù)嗎真正拿到映客2020春招算法A卷的時候我才發(fā)現(xiàn)自己想簡單了。這套卷子從字符串匹配考到PID控制從KMP的next數(shù)組考到卡爾曼濾波跨度大得讓人一度懷疑自己投的是算法工程師還是全棧算法工程師。不過換個角度想這恰恰是直播業(yè)務(wù)的真實映射。映客這種以音視頻互動為核心的產(chǎn)品算法鏈路遠比普通App長內(nèi)容推薦需要機器學(xué)習(xí)排序直播流需要音視頻處理網(wǎng)絡(luò)波動需要碼率控制風(fēng)控需要規(guī)則引擎。所以一套算法筆試題覆蓋多個方向不是出題人隨意拼湊而是整個技術(shù)棧的縮影。我建議準(zhǔn)備算法崗筆試的朋友別只盯著LeetCode刷題。先把目標(biāo)公司的業(yè)務(wù)鏈路拆一遍看看它最依賴哪些算法模塊再針對性復(fù)習(xí)效率會高很多。這也是我復(fù)盤這份卷子時最大的感觸。1.2 從熱搜詞分布反推考察重點把這份卷子相關(guān)的熱搜詞攤開看能明顯看出幾個密集區(qū)字符串與數(shù)據(jù)結(jié)構(gòu)、機器學(xué)習(xí)與搜索排序、音視頻處理、控制與規(guī)則引擎、安全算法。這些不是孤立的考點而是映客這類直播產(chǎn)品技術(shù)體系的五個關(guān)鍵支撐。字符串算法KMP、BM25等對應(yīng)的是內(nèi)容檢索與匹配排序、貪心、堆等數(shù)據(jù)結(jié)構(gòu)題是算法基本功聚類、KNN、強化學(xué)習(xí)等對應(yīng)推薦與用戶增長音頻重采樣、圖像銳化、Sobel對應(yīng)音視頻處理鏈路PID、規(guī)則引擎對應(yīng)播放控制與內(nèi)容安全。所以這份卷子的解題思路其實很清晰先過基本功再看機器學(xué)習(xí)然后落到音視頻和工程細節(jié)。下面我按這個邏輯把每一類題的核心思路拆開講。2. 字符串與數(shù)據(jù)結(jié)構(gòu)題KMP、堆排序、快速冪的實戰(zhàn)拆解2.1 KMP的next數(shù)組兩種定義之間差了什么熱搜詞里有一個很具體的題目描述對于模式串 pabacaba其 next 數(shù)組next[i] 定義為...。這個題我印象太深了因為KMP的next數(shù)組在不同教材和不同題庫里有兩種常見定義答案完全不同。第一種定義next[i] 表示 p[0..i] 這個子串中最長相等前后綴的長度不包含子串自身。按這個定義模式串 abacaba 的 next 數(shù)組計算過程如下i子串最長相等前后綴next[i]0a無長度不能為自身01ab無a≠b02abaa 與 a長度為113abac無04abacaa 與 a長度為115abacabab 與 ab長度為226abacabaaba 與 aba長度為33所以 next [0, 0, 1, 0, 1, 2, 3]。第二種定義next[i] 表示當(dāng) p[i] 失配時模式串應(yīng)該回退到的位置下標(biāo)。這種定義下通常 next[0] -1然后后續(xù)數(shù)值有偏移。按這個定義abacaba 的 next 數(shù)組是 [-1, 0, 0, 1, 0, 1, 2]。我在筆試時吃過這個虧題目文字寫的是最長相等前后綴長度結(jié)果我按跳轉(zhuǎn)位置的定義填了答案白丟一道題的分。所以拿到KMP題第一件事不是動筆算而是先確認題目用的是哪種定義。如果題目給了next[i]的文字定義就嚴格按定義推如果沒給默認按最長相等前后綴長度來做同時注意是否需要 next[0]-1。def get_next(p): n len(p) nxt [0] * n j 0 for i in range(1, n): while j 0 and p[i] ! p[j]: j nxt[j - 1] if p[i] p[j]: j 1 nxt[i] j return nxt p abacaba print(get_next(p)) # [0, 0, 1, 0, 1, 2, 3]這個實現(xiàn)對應(yīng)第一種定義也是我平時寫KMP最順手的版本。筆試時不要現(xiàn)場推實現(xiàn)把模板背熟能省出大量時間給后面的大題。2.2 堆排序的空間復(fù)雜度與快速冪的二進制思維堆排序和快速冪是筆試常客但每次考的點不太一樣。堆排序常見的追問有三個時間復(fù)雜度、空間復(fù)雜度、穩(wěn)定性。堆排序建堆是 O(n)每次調(diào)整是 O(log n)整體時間復(fù)雜度穩(wěn)定在 O(n log n)。它最突出的優(yōu)點是空間復(fù)雜度能做到 O(1)因為完全可以用原數(shù)組存儲堆結(jié)構(gòu)不需要額外數(shù)組。但注意堆排序是不穩(wěn)定的同樣關(guān)鍵字的元素在排序后可能改變相對順序這在面試里經(jīng)常被追問。我當(dāng)時在卷子上寫堆排序時特意標(biāo)注了原地建堆、原地排序并解釋了建堆從最后一個非葉子節(jié)點開始的原因——下沉調(diào)整可以保證每個子樹先滿足堆性質(zhì)自底向上逐步構(gòu)建整體堆。這樣寫閱卷人能看出你不是背代碼而是真懂原理?？焖賰绲暮诵氖嵌M制分解。比如求 a^n把 n 拆成二進制形式從最低位開始每次將底數(shù)平方只有當(dāng)前位為1時才累乘到結(jié)果中。原理和通過乘法快速替代連乘是一樣的時間復(fù)雜度從 O(n) 降到 O(log n)。def fast_pow(a, n, modNone): res 1 while n 0: if n 1: res res * a if mod is None else (res * a) % mod a a * a if mod is None else (a * a) % mod n 1 return res快速冪在密碼學(xué)、大數(shù)運算、概率計算里經(jīng)常出現(xiàn)。如果卷子上有模運算的題記得每一步都取模防止中間結(jié)果溢出。筆試題不會只考一個孤立的快速冪通常會把它包裝成某個實際問題比如倒置鏈表、循環(huán)節(jié)計算、大數(shù)冪取模等。2.3 貪心與其他經(jīng)典題型的答題節(jié)奏貪心算法在筆試題里出現(xiàn)的頻率很高但考的不是能不能想到貪心而是能不能證明貪心正確?；顒舆x擇問題、區(qū)間調(diào)度、找零錢這些都是經(jīng)典題。我當(dāng)時答題時習(xí)慣先給出貪心策略再用反證法或交換論證法簡單寫兩行證明哪怕不完整也能展示思路。排序算法類的題目我建議把各種排序的復(fù)雜度、穩(wěn)定性、適用場景整理成一張表放在腦子里。筆試時遇到請設(shè)計一個時間復(fù)雜度O(n log n)且穩(wěn)定的排序算法第一時間想到歸并排序遇到內(nèi)存受限要求原地排序就選堆排序。這些判斷一定要形成條件反射。排序算法 平均時間 最壞時間 空間 穩(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)定貪心、二分、雙指針這類題答案本身往往不長但邊界條件很容易漏。比如二分查找的左右邊界收縮條件是還是中間值取(leftright)//2還是(leftright1)//2這些細節(jié)直接決定能否通過全部測試用例。我在A卷上做二分變種題時就因為mid的取整方向?qū)懛磁軖炝藘山M邊界數(shù)據(jù)這種失誤太可惜了。3. 機器學(xué)習(xí)算法題把推薦和搜索賽道的基本功吃透3.1 聚類、KNN與用戶分群從三個應(yīng)用能力說起熱搜詞里有一條knn算法的應(yīng)用能力包括哪三個方面這個表述很像是某道簡答題的原文。KNN的三個經(jīng)典應(yīng)用方向是分類、回歸、缺失值填充或異常檢測。分類是最常見的比如根據(jù)用戶行為特征判斷其是否可能付費回歸可以預(yù)測用戶的使用時長缺失值填充則利用近鄰樣本的信息估計缺失特征。不過直播平臺的KNN應(yīng)用場景更貼近用戶分群和相似用戶推薦。登錄映客這類產(chǎn)品時系統(tǒng)會根據(jù)你的年齡、地區(qū)、觀看偏好找到與你最相似的一群用戶然后把他們喜歡的主播推給你。這個邏輯本質(zhì)上就是KNN的思路找K個最近鄰匯總他們的行為偏好排序生成推薦列表。聚類和KNN經(jīng)常一起考。有一道比較經(jīng)典的簡述題是K-Means和KNN有什么區(qū)別。K-Means是無監(jiān)督學(xué)習(xí)KNN是有監(jiān)督學(xué)習(xí)K-Means用于聚類KNN用于分類/回歸K-Means訓(xùn)練過程是迭代更新聚類中心KNN訓(xùn)練過程只是存儲樣本。筆試時如果遇到這種對比題從有監(jiān)督/無監(jiān)督用途訓(xùn)練過程三個維度作答就能拿全分。3.2 強化學(xué)習(xí)、模擬退火與BM25直播場景里的隱藏考點強化學(xué)習(xí)在直播平臺最典型的應(yīng)用是推薦策略優(yōu)化。主播和用戶之間的匹配是一個不斷試錯、不斷獲得反饋的過程推薦一個主播用戶停留時間長、送禮了就是正向獎勵用戶秒退就是負向獎勵。強化學(xué)習(xí)的智能體在這種環(huán)境下學(xué)習(xí)最優(yōu)的推薦策略本質(zhì)上和AlphaGo學(xué)下棋的邏輯一致。模擬退火算法在熱搜詞里出現(xiàn)大概率是作為全局優(yōu)化算法考察。這個算法的思想很有意思物理退火時高溫讓粒子自由移動溫度降低后粒子逐漸穩(wěn)定到低能狀態(tài)。對應(yīng)到優(yōu)化問題里算法以一定概率接受比當(dāng)前解差的新解這個概率隨溫度下降而減小從而跳出局部最優(yōu)尋找全局最優(yōu)。BM25是搜索排序里的經(jīng)典算法騰訊視頻ckey、內(nèi)容搜索等場景經(jīng)常用到。BM25的核心是計算查詢詞和文檔之間的相關(guān)性得分它融合了詞頻、逆文檔頻率和文檔長度歸一化三個因素。筆試考BM25時往往不是讓手寫完整公式而是問它和TF-IDF有什么區(qū)別——BM25對詞頻有飽和機制一個詞出現(xiàn)太多次時增益會遞減而TF-IDF中詞頻是線性增長的。3.3 粒子群、剪枝與XGBoost擴展知識面的正確姿勢粒子群算法PSO是一種模擬鳥群覓食行為的群體智能優(yōu)化算法。每個粒子代表一個候選解粒子在搜索空間里飛行速度和方向受自身歷史最優(yōu)位置和群體歷史最優(yōu)位置影響。在算法崗筆試中粒子群常作為啟發(fā)式優(yōu)化算法的代表被考察與遺傳算法、模擬退火并列為三大經(jīng)典。剪枝算法在直播場景里最直接的應(yīng)用是搜索樹剪枝和推薦候選集剪枝。比如用Minimax算法做井字棋AI時通過alpha-beta剪枝可以大量減少搜索節(jié)點讓AI在有限時間內(nèi)算出最優(yōu)落子。這個知識點在熱搜詞里單獨出現(xiàn)了井字棋minimax算法實現(xiàn)詳解說明出題人可能想考察遞歸搜索與剪枝的結(jié)合。XGBoost和聚類算法則是業(yè)務(wù)實戰(zhàn)中的常客。XGBoost在特征稀疏、數(shù)據(jù)量大的場景下表現(xiàn)突出適合做用戶付費意愿預(yù)測聚類則用于主播分類、內(nèi)容標(biāo)簽聚合。這部分知識不一定在筆試中單獨出計算題但很可能以簡述你熟悉的機器學(xué)習(xí)算法及其適用場景這類開放性問題出現(xiàn)平時積累幾個有深度的案例很有必要。4. 音視頻鏈路里的算法細節(jié)重采樣、圖像銳化與卡爾曼濾波4.1 音頻重采樣直播場景避不開的基本功直播里不同端的音頻采樣率常常不一致主播端可能是48kHz觀眾端播放器可能要求44.1kHz或者需要從48kHz降到16kHz用于語音識別。這個轉(zhuǎn)換過程就是音頻重采樣。最簡單的重采樣是線性插值但工程上更常用的是多相濾波器組或基于FFT的重采樣方案。多相濾波器的思路是設(shè)計一個低通濾波器然后按采樣率轉(zhuǎn)換比例抽取或插值再通過多相結(jié)構(gòu)把計算量降下來。筆試如果考重采樣原理一般會從三個方面問為什么需要抗混疊濾波器、插值和抽取的順序是什么、采樣率轉(zhuǎn)換比例是整數(shù)還是分數(shù)時處理有什么區(qū)別。我當(dāng)時看到音頻重采樣算法這個熱搜詞第一反應(yīng)是出題人可能的問法是直播中回聲消除的延遲是如何影響重采樣設(shè)計的。因為回聲消除需要把遠端參考信號重采樣到近端采樣率重采樣的精度直接影響回聲路徑估計的準(zhǔn)確性。這類題沒有標(biāo)準(zhǔn)答案但抓住采樣率匹配和濾波器設(shè)計兩個核心點就能答到點子上。4.2 拉普拉斯與Sobel圖像銳化和邊緣檢測的題眼圖像銳化是直播美顏、特效模塊的基礎(chǔ)。拉普拉斯算子是一個二階微分算子它突出圖像中灰度突變的地方。用拉普拉斯算子銳化的標(biāo)準(zhǔn)公式是g(x, y) f(x, y) c * ?2f(x, y)其中 f 是原圖像?2f 是拉普拉斯算子作用后的結(jié)果c 是增強系數(shù)。拉普拉斯算子常用的離散卷積核是0 -1 0 -1 4 -1 0 -1 0或者帶對角線擴展的版本。卷積核的本質(zhì)是中心像素乘以4減去上下左右四個鄰域像素結(jié)果能提取出邊緣信息。把邊緣疊加回原圖圖像看起來就更清晰銳利。Sobel算子則是一階導(dǎo)數(shù)的近似它有兩個方向核分別計算水平梯度和垂直梯度Gx [-1 0 1; -2 0 2; -1 0 1] Gy [-1 -2 -1; 0 0 0; 1 2 1]圖像在某像素點的梯度幅值約等于 sqrt(Gx2 Gy2)。筆試時如果讓手寫Sobel邊緣檢測的步驟就是灰度化、分別與Gx和Gy做卷積、求幅值、閾值二值化。這幾個算子我在直播圖像處理項目里反復(fù)用過美顏的皮膚平滑、特效的邊緣增強底層都是這些東西。4.3 卡爾曼濾波從抖動的網(wǎng)絡(luò)里讀出真實碼率卡爾曼濾波是信號處理與控制領(lǐng)域繞不開的經(jīng)典算法。直播推流過程中網(wǎng)絡(luò)帶寬是波動的TCP擁塞窗口、發(fā)送緩沖區(qū)的長度都在變直接測量這些值得到的碼率估計值會劇烈抖動?？柭鼮V波做的事情是通過一個狀態(tài)空間模型把含有噪聲的觀測值和系統(tǒng)的運動規(guī)律融合起來估計出真實狀態(tài)。具體到直播場景可以把網(wǎng)絡(luò)可用帶寬看作系統(tǒng)的狀態(tài) x觀測值 y 是當(dāng)前的吞吐量或延遲變化。系統(tǒng)模型是帶寬緩慢變化過程噪聲小觀測模型是吞吐量受隨機干擾觀測噪聲大?？柭鼮V波的迭代分兩步預(yù)測用上一時刻的狀態(tài)估計當(dāng)前狀態(tài)和更新用當(dāng)前觀測值修正預(yù)測結(jié)果。筆試題里如果要寫卡爾曼濾波的五個核心公式基本是預(yù)測 x_pred F * x_prev P_pred F * P_prev * F^T Q 更新 K P_pred * H^T * (H * P_pred * H^T R)^(-1) x_new x_pred K * (z - H * x_pred) P_new (I - K * H) * P_pred這套公式在筆試中不一定要求完整默寫但至少要能解釋每個變量的含義F是狀態(tài)轉(zhuǎn)移矩陣H是觀測矩陣Q是過程噪聲協(xié)方差R是觀測噪聲協(xié)方差K是卡爾曼增益。理解預(yù)測更新的框架比死記公式更重要。5. 規(guī)則引擎、控制類算法與安全算法算法崗的跨界題5.1 Rete算法規(guī)則引擎Drools的事實匹配過程看到規(guī)則引擎drools的rete算法實現(xiàn)原理和事實匹配過程這個熱搜詞時我愣了一下因為規(guī)則引擎通常不在算法崗筆試的常規(guī)復(fù)習(xí)范圍內(nèi)。但仔細想想直播平臺的內(nèi)容安全、用戶風(fēng)控、審核策略都非常依賴規(guī)則引擎考這個并不突兀。Rete算法的核心思想是利用規(guī)則結(jié)構(gòu)的相似性減少重復(fù)匹配計算。它構(gòu)建一個網(wǎng)絡(luò)包含Alpha節(jié)點條件匹配單個事實的簡單條件和Beta節(jié)點多個事實之間關(guān)系的聯(lián)結(jié)。當(dāng)新事實進入工作內(nèi)存時它沿著網(wǎng)絡(luò)傳遞只經(jīng)過與它相關(guān)的路徑而不是把每一條規(guī)則都重新匹配一遍。筆試如果考Rete最可能出的簡答題是請簡述Rete算法相比樸素匹配的優(yōu)勢。答案要點是保存了規(guī)則匹配的中間狀態(tài)避免重復(fù)計算支持增量更新新增事實時只傳播受影響的路徑規(guī)則多、事實多時效率提升顯著。我有個朋友在風(fēng)控系統(tǒng)里用Drools寫了幾百條規(guī)則匹配性能要求極高Rete算法就是支撐這種場景的關(guān)鍵。5.2 PID、MPPT與FOC控制算法背后的工程思維PID控制算法在熱搜詞里有pid算法、增量式pid算法、pid算法在crps psu power的作用好幾條。PID是比例-積分-微分控制器的縮寫根據(jù)誤差的比例項、累積項和變化趨勢項來計算控制量。公式是u(t) Kp * e(t) Ki * ∫e(t)dt Kd * de(t)/dt增量式PID是數(shù)字控制中常用的變體它輸出的是控制量的增量而不是絕對控制量好處是執(zhí)行器可以平滑過渡誤動作影響小而且不需要累加歷史誤差不容易積分飽和。MPPT最大功率點跟蹤在光伏發(fā)電、電源系統(tǒng)里負責(zé)讓設(shè)備始終工作在最大輸出功率點附近。FOC磁場定向控制則廣泛應(yīng)用于無人機云臺、電機控制中。這幾個算法雖然更偏硬件和自動化但出現(xiàn)在直播公司算法試卷里很可能是結(jié)合了具體業(yè)務(wù)場景比如直播間的智慧燈光控制、電動云臺的穩(wěn)定跟隨、服務(wù)器電源的功耗管理。如果讓你現(xiàn)場手寫一個PID的代碼記住增量式PID的實現(xiàn)會比位置式更簡潔class IncrementalPID: def __init__(self, Kp, Ki, Kd): self.Kp Kp self.Ki Ki self.Kd Kd self.last_err 0 self.prev_err 0 def update(self, target, current): err target - current delta (self.Kp * (err - self.last_err) self.Ki * err self.Kd * (err - 2 * self.last_err self.prev_err)) self.prev_err self.last_err self.last_err err return delta5.3 弱哈希修復(fù)與國密算法安全方向的基本常識熱搜詞里有一條ssl證書使用了弱hash算法cve-2005-4900怎么修復(fù)這也是算法崗可能會碰到的實際安全問題。CVE-2005-4900涉及使用弱哈希算法如SHA-1簽名的SSL證書主要修復(fù)手段是用SHA-256或更強的哈希算法重新生成證書簽名請求向CA重新申請證書如果內(nèi)網(wǎng)自簽名證書需要更新簽發(fā)策略并重新部署到所有信任鏈節(jié)點同時檢查服務(wù)端SSL配置禁用不支持強哈希的加密套件。這里要注意的是證書的哈希算法和加密算法是兩回事。哈希算法用于證書簽名加密算法用于TLS握手時的密鑰交換。修復(fù)弱哈希問題核心動作是換簽名算法而不是換加密套件。我在實際項目里修過類似問題尤其是一些老舊的內(nèi)部系統(tǒng)證書鏈里藏著SHA-1簽名的根證書或中間證書光換葉子證書不檢查整條鏈問題依然存在。SM2、SM3、SM4和ZUC是國密算法體系分別對應(yīng)公鑰加密、哈希、分組加密和流加密。有些企業(yè)級項目會要求支持國密算法尤其是在政務(wù)、金融場景。算法崗筆試即使不細考國密算法的實現(xiàn)細節(jié)也可能會問它們和AES、RSA、SHA-256的區(qū)別。答這類題的關(guān)鍵是明確SM2基于橢圓曲線SM3輸出256位摘要SM4分組長度128位ZUC是祖沖之序列密碼。5.4 內(nèi)容簽名與版權(quán)保護一個容易被忽略的考點熱搜詞里還有騰訊視頻ckey5.x算法_php版這和視頻內(nèi)容的防盜鏈、版權(quán)保護有關(guān)。視頻平臺會在播放請求中附加簽名參數(shù)服務(wù)端校驗簽名是否合法、是否過期、是否為特定設(shè)備生成。這類算法的核心是請求參數(shù)密鑰時間戳的簽名邏輯通常是一套帶特定排列和哈希的算法。我不建議為了筆試去研究某個具體視頻平臺的簽名逆向那是另一個領(lǐng)域的事了。但算法工程師應(yīng)當(dāng)理解內(nèi)容簽名和防篡改背后的通用原理是HMAC或RSA簽名核心是密鑰不出客戶端、簽名可驗證、時間戳防重放。答題時能說清楚這個原理已經(jīng)能體現(xiàn)對該方向的理解。5.5 工業(yè)異常檢測與DC3算法邊角知識也有存在感工業(yè)異常檢測算法和dc3算法出現(xiàn)在熱搜詞里說明這份卷子的考察范圍并不局限于常規(guī)算法題。工業(yè)異常檢測通常用重構(gòu)誤差來判斷樣本是否異常訓(xùn)練一個自編碼器正常樣本的重構(gòu)誤差小異常樣本的重構(gòu)誤差大設(shè)定閾值即可區(qū)分。這個思路在直播場景的異常流量檢測、黑產(chǎn)賬號識別中也能遷移使用。DC3算法是線性時間構(gòu)造后綴數(shù)組的算法屬于字符串算法的進階內(nèi)容。KMP解決單模式匹配后綴數(shù)組解決多模式匹配、最長公共子串等問題。如果筆試里考到DC3大概率是問相比倍增加法O(n log n)DC3為什么能做到O(n)答案要點是把字符串分成三類位置遞歸構(gòu)造其中兩類的后綴排名再線性合并得到完整后綴數(shù)組。這類題平時見到的概率不大但真出現(xiàn)了能答出一個核心思路就已經(jīng)超過大多數(shù)考生。6. 現(xiàn)場筆試的答題順序與復(fù)盤總結(jié)6.1 我的答題策略先掃一遍全卷再按性價比切題拿到A卷后我習(xí)慣先花5分鐘快速瀏覽全部題目標(biāo)注難度和預(yù)估耗時而不是從第一題開始硬做。我的優(yōu)先順序是有明確答案的基礎(chǔ)題如KMP next數(shù)組、排序復(fù)雜度先做中等難度的算法實現(xiàn)題快速冪、堆排序次之簡述題如Rete算法原理、PID在業(yè)務(wù)中的作用再往后最后啃綜合大題的硬骨頭。這樣做的好處是保證基礎(chǔ)分先落袋不至于在一道大題上卡太久導(dǎo)致后面會做的題沒時間寫。我當(dāng)時估算每道題的時間是選擇題/填空題每題2分鐘代碼題每題10-15分鐘簡述題每題5分鐘大題20分鐘?？偡址峙浜蜁r間分配對上了考試才不會慌。6.2 我踩過的坑與改進方向現(xiàn)在回頭復(fù)盤有幾個坑值得提醒正在準(zhǔn)備筆試的朋友。坑一是看到熟悉的題就掉以輕心。我在KMP那道題上就是因為太自信沒看清題目對next數(shù)組的定義結(jié)果填錯了。無論多熟悉的題下筆前把題目要求完整讀兩遍尤其是那些定義為注意后面的文字。坑二是填空題留白。有些題不會做就直接跳但算法卷的填空題、簡答題往往有按點給分的潛規(guī)則哪怕只寫出部分公式、部分思路也能拿一些步驟分。用代碼實現(xiàn)題尤其如此寫出一個可運行但不夠優(yōu)化的版本分數(shù)會比空著高很多?？尤遣蛔⒁獯a的邊界條件?？焖賰鐩]取模、二分查找沒有處理空數(shù)組、遞歸沒有出口這些是筆試代碼最常見的問題。我后來養(yǎng)成一個習(xí)慣寫完代碼后先用一個極簡的測試用例在草稿紙上走一遍比如數(shù)組長度為0或1、n為0或1的場景能提前發(fā)現(xiàn)大部分bug。6.3 適合大多數(shù)人的備考Checklist根據(jù)這份A卷的考點分布給自己列一個備考清單字符串算法KMP的next數(shù)組兩種定義、后綴數(shù)組基本概念、BM25核心公式數(shù)據(jù)結(jié)構(gòu)排序時間復(fù)雜度與穩(wěn)定性、堆排序手寫、快速冪、二分查找邊界機器學(xué)習(xí)聚類與KNN區(qū)別、XGBoost適用場景、強化學(xué)習(xí)基本流程、模擬退火思想音視頻音頻重采樣原理、拉普拉斯與Sobel卷積核、卡爾曼濾波公式框架工程算法PID與增量式PID代碼、Rete算法匹配過程、異常檢測思路安全基礎(chǔ)弱哈希修復(fù)步驟、國密算法分類、內(nèi)容簽名通用原理。這份清單并不追求每個點都深挖到論文級但對于一場算法崗筆試來說覆蓋面已經(jīng)足夠了。關(guān)鍵是每個方向都能說出是什么、為什么、怎么用。我后來把這份卷子給準(zhǔn)備校招的幾個學(xué)弟學(xué)妹看過他們反饋最有用的是KMP的next數(shù)組定義對比和PID增量式實現(xiàn)那段因為網(wǎng)上的資料很少把筆試中的定義差異講得這么細。也正是這些看起來簡單但容易踩坑的知識點才最能拉開考生之間的差距。如果你也正在準(zhǔn)備算法崗筆試不妨把這份卷子當(dāng)作一份模擬題來限時訓(xùn)練做完之后再對著自己的薄弱點專項突擊。算法筆試考的從來不只是會不會更是在有限時間內(nèi)能不能穩(wěn)定做對這個能力只能靠反復(fù)實戰(zhàn)來打磨。