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