2023年秋招那會(huì)兒我印象最深的一場(chǎng)筆試就是飛豬的算法崗。說(shuō)實(shí)話飛豬的筆試題量不算大但每道題都出得挺有水平既能篩掉基礎(chǔ)不牢的人又能看出候選人有沒(méi)有工程落地的感覺(jué)。當(dāng)時(shí)我刷了一圈面經(jīng)發(fā)現(xiàn)大家吐槽最多的就是“看似常規(guī)實(shí)則處處是坑”。這篇文章就把我當(dāng)時(shí)參加飛豬2023屆秋招算法崗筆試的全過(guò)程掰開(kāi)揉碎講一遍包括題型分布、考了哪些算法、正確的破題思路以及我踩過(guò)的坑。如果你正在準(zhǔn)備大廠算法崗或者想了解阿里的算法崗筆試風(fēng)格這篇應(yīng)該能幫你少走不少?gòu)澛?。飛豬算法崗筆試屬于典型的“基礎(chǔ)算法 機(jī)器學(xué)習(xí)原理 業(yè)務(wù)場(chǎng)景設(shè)計(jì)”組合和純刷題型的筆試有明顯區(qū)別。它不會(huì)一味考難題偏題但會(huì)在很多看似普通的考點(diǎn)上深挖細(xì)節(jié)比如KMP算法里next數(shù)組的手算、概率題里的公式推導(dǎo)、以及對(duì)模型選型的理解。這背后其實(shí)反映了一件事算法崗不只是要會(huì)寫代碼更要懂算法原理、能結(jié)合業(yè)務(wù)做取舍。下面我按模塊拆解把值得說(shuō)的細(xì)節(jié)和經(jīng)驗(yàn)都放進(jìn)去。1. 筆試整體認(rèn)知與題型拆解1.1 飛豬算法崗筆試到底考什么先給沒(méi)參加過(guò)的人還原一下現(xiàn)場(chǎng)。飛豬2023屆秋招算法崗筆試是在統(tǒng)一的在線筆試平臺(tái)上進(jìn)行的總共約120分鐘題目構(gòu)成大致如下單選題/多選題覆蓋機(jī)器學(xué)習(xí)基礎(chǔ)、概率統(tǒng)計(jì)、數(shù)據(jù)結(jié)構(gòu)與算法常識(shí)大概10到15道。編程題2到3道難度從LeetCode中等偏簡(jiǎn)單到中等偏難不等核心考點(diǎn)集中在字符串、動(dòng)態(tài)規(guī)劃、圖論和排序。簡(jiǎn)答/設(shè)計(jì)題1道業(yè)務(wù)場(chǎng)景題通常會(huì)給一個(gè)飛豬的業(yè)務(wù)場(chǎng)景比如旅行推薦、酒店價(jià)格預(yù)測(cè)要求寫出算法思路或技術(shù)方案。這個(gè)題型組合很典型但也有不少同學(xué)栽在時(shí)間分配上。選擇題看著簡(jiǎn)單實(shí)際很容易糾結(jié)編程題如果第一道卡太久后面的題基本就沒(méi)時(shí)間看。我當(dāng)時(shí)就是先快速掃了一遍所有題目把選擇題里拿不準(zhǔn)的標(biāo)記出來(lái)優(yōu)先做編程題里最有把握的一道最后再回頭啃選擇題。這個(gè)策略不一定最優(yōu)但至少能保證“該拿的分不丟”。1.2 考題背后的考察邏輯如果你只是把這當(dāng)成一場(chǎng)普通的算法刷題考試那就理解偏了。飛豬算法崗筆試的每類題目都在測(cè)不同的能力數(shù)據(jù)結(jié)構(gòu)與算法題考察代碼基本功、復(fù)雜度的敏感度、邊界條件的處理。機(jī)器學(xué)習(xí)原理題考察是否真的理解模型原理而不是只會(huì)調(diào)包。比如KL散度、ELBO、K-Means這些概念平時(shí)可能只是“聽(tīng)過(guò)”筆試卻要你推導(dǎo)或計(jì)算。業(yè)務(wù)場(chǎng)景設(shè)計(jì)題考察工程落地思維。飛豬的業(yè)務(wù)場(chǎng)景和“旅行”“交易”“推薦”“定價(jià)”相關(guān)能不能把算法和具體業(yè)務(wù)結(jié)合是拉開(kāi)差距的地方。我當(dāng)時(shí)在準(zhǔn)備階段反復(fù)提醒自己刷題只是底線真正決定上限的是對(duì)算法本質(zhì)的理解。就像KMP算法的next數(shù)組很多人能背代碼但真讓你手推一遍“abacaba”的next數(shù)組估計(jì)不少人會(huì)卡殼。筆試不考背代碼考的就是你能否在紙面上把邏輯理清楚。2. 數(shù)據(jù)結(jié)構(gòu)與算法高頻考點(diǎn)逐項(xiàng)拆解2.1 KMP算法與next數(shù)組一道題能卡住一半人先說(shuō)KMP。2023年秋招算法崗筆試?yán)镒址ヅ湎嚓P(guān)的高頻考點(diǎn)就是KMP尤其是next數(shù)組的手算。筆試那道題我記得很清楚給出模式串 p abacaba要求寫出 next 數(shù)組。這道題看起來(lái)簡(jiǎn)單但場(chǎng)內(nèi)至少有一半人栽在了定義上。next數(shù)組的定義在不同教材里有兩種約定一種表示“當(dāng)前字符匹配失敗后跳轉(zhuǎn)的位置”另一種表示“當(dāng)前字符之前的最長(zhǎng)相同前綴后綴長(zhǎng)度”。飛豬筆試采用的是后者next[i] 表示 p[0..i-1] 的最長(zhǎng)相同前綴后綴長(zhǎng)度。也就是說(shuō)next[0] -1next[1] 0然后逐個(gè)遞推。手推過(guò)程可以這樣拆解next[0] -1約定值next[1] 0長(zhǎng)度為1的子串沒(méi)有真前后綴對(duì)于 i 2前綴 p[0..1] ab最長(zhǎng)相等前后綴長(zhǎng)度為0所以 next[2] 0對(duì)于 i 3前綴 p[0..2] aba最長(zhǎng)相等前后綴是 a長(zhǎng)度1所以 next[3] 1對(duì)于 i 4前綴 p[0..3] abac沒(méi)有相等前后綴next[4] 0對(duì)于 i 5前綴 p[0..4] abaca最長(zhǎng)相等前后綴是 a長(zhǎng)度1next[5] 1對(duì)于 i 6前綴 p[0..5] abacab沒(méi)有相等前后綴next[6] 0對(duì)于 i 7前綴 p[0..6] abacaba最長(zhǎng)相等前后綴是 aba長(zhǎng)度3next[7] 3所以答案就是 [-1, 0, 0, 1, 0, 1, 0, 3]。如果考場(chǎng)里直接給這個(gè)結(jié)果可能不到5分鐘就能寫完。但我當(dāng)時(shí)看到很多人還在用暴力法一個(gè)個(gè)比較前后綴這就是基本功的差距。順便放一個(gè)標(biāo)準(zhǔn)的KMP匹配代碼C版本方便你對(duì)照理解#include vector #include string using namespace std; vectorint buildNext(const string p) { int m p.size(); vectorint next(m); next[0] -1; int j 0, k -1; while (j m - 1) { if (k -1 || p[j] p[k]) { j; k; next[j] k; } else { k next[k]; } } return next; } int kmpSearch(const string s, const string p) { int n s.size(), m p.size(); vectorint next buildNext(p); int i 0, j 0; while (i n j m) { if (j -1 || s[i] p[j]) { i; j; } else { j next[j]; } } if (j m) return i - j; return -1; }2.2 排序與TopK別只會(huì)調(diào)sort排序算法幾乎每次筆試都會(huì)碰見(jiàn)但飛豬不會(huì)直接讓你寫一個(gè)冒泡排序完事而是會(huì)結(jié)合數(shù)據(jù)量、穩(wěn)定性、內(nèi)存限制來(lái)考。選擇題里經(jīng)常有“以下哪個(gè)排序算法是穩(wěn)定的”“堆排序的時(shí)間復(fù)雜度是多少”“40億個(gè)數(shù)找最大的100個(gè)用什么方法”這類問(wèn)題。我整理了一個(gè)高頻對(duì)比表筆試前可以快速過(guò)一遍排序算法平均時(shí)間復(fù)雜度最壞時(shí)間復(fù)雜度空間復(fù)雜度穩(wěn)定性冒泡排序O(n^2)O(n^2)O(1)穩(wěn)定選擇排序O(n^2)O(n^2)O(1)不穩(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)定那道“40億個(gè)數(shù)找TopK”的題最優(yōu)解不是全局排序而是維護(hù)一個(gè)大小為K的小頂堆。時(shí)間復(fù)雜度是O(n log K)空間O(K)。如果內(nèi)存裝不下全部數(shù)據(jù)就用外部排序堆。這個(gè)點(diǎn)考察的是對(duì)海量數(shù)據(jù)場(chǎng)景的敏感度飛豬有大量用戶行為日志這類問(wèn)題不是純理論是真會(huì)遇見(jiàn)。2.3 貪心、動(dòng)態(tài)規(guī)劃與快速冪筆試實(shí)戰(zhàn)套路動(dòng)態(tài)規(guī)劃和貪心在編程題里出現(xiàn)頻率極高。飛豬筆試第二道編程題我當(dāng)時(shí)遇到的是區(qū)間調(diào)度變體給定若干個(gè)帶權(quán)活動(dòng)每個(gè)活動(dòng)有開(kāi)始時(shí)間、結(jié)束時(shí)間和收益選擇不沖突的活動(dòng)使總收益最大。這題貪心解不適用因?yàn)閹?quán)后局部最優(yōu)不等于全局最優(yōu)必須用動(dòng)態(tài)規(guī)劃按結(jié)束時(shí)間排序設(shè) dp[i] 表示前 i 個(gè)活動(dòng)能獲得的最大收益轉(zhuǎn)移時(shí)用二分查找找到“最后一個(gè)結(jié)束時(shí)間小于當(dāng)前活動(dòng)開(kāi)始時(shí)間”的活動(dòng)。這類題的通用破題套路是先判斷是貪心還是DP——如果局部最優(yōu)能達(dá)到全局最優(yōu)就選貪心否則考慮DP。判斷完之后寫狀態(tài)轉(zhuǎn)移時(shí)重點(diǎn)關(guān)注“不選當(dāng)前元素的情況”很多人丟分都丟在遺漏 dp[i-1] 這個(gè)不選分支?？焖賰缫彩枪P試的?？汀１热缬?jì)算 a^b mod mb 可以達(dá)到 10^18 級(jí)別。Python 里可以直接 pow(a, b, m)但筆試選擇題會(huì)要求你判斷時(shí)間復(fù)雜度或者讓你填充代碼。模板如下def fast_pow(a, b, m): res 1 a % m while b 0: if b 1: res (res * a) % m a (a * a) % m b 1 return res快速冪的核心思想是把指數(shù)折半把冪運(yùn)算從 O(b) 降到 O(log b)。同樣的思路還可以用在矩陣快速冪、斐波那契數(shù)列求第 n 項(xiàng)等場(chǎng)景。2.4 圖論與搜索Dijkstra、二分圖HK算法圖論基礎(chǔ)算法每年都有。飛豬業(yè)務(wù)里涉及大量路徑規(guī)劃、運(yùn)籌優(yōu)化所以 Dijkstra 這類最短路算法屬于必須掌握的。筆試真題里有一道題需要求一個(gè)無(wú)向加權(quán)圖中從起點(diǎn)到終點(diǎn)的最短路徑數(shù)據(jù)范圍不算大用優(yōu)先隊(duì)列優(yōu)化后的 Dijkstra 可以輕松通過(guò)。Dijkstra 的實(shí)現(xiàn)其實(shí)有固定的套路import heapq def dijkstra(graph, start): n len(graph) dist [float(inf)] * n dist[start] 0 pq [(0, start)] while pq: d, u heapq.heappop(pq) if d dist[u]: continue for v, w in graph[u]: if dist[u] w dist[v]: dist[v] dist[u] w heapq.heappush(pq, (dist[v], v)) return dist另外一個(gè)比較容易被忽視的是二分圖相關(guān)的算法。熱搜詞里的HK算法Hopcroft-Karp算法就是二分圖最大匹配的優(yōu)化版本核心思想是用BFS構(gòu)建增廣路徑層級(jí)圖再用DFS尋找增廣路時(shí)間復(fù)雜度比匈牙利算法的O(VE)優(yōu)化到O(E√V)。筆試一般不要求你手寫HK但選擇題可能會(huì)問(wèn)匈牙利算法和HK的區(qū)別或者給一個(gè)二分圖問(wèn)最大匹配數(shù)。知道“為什么用HK——減少增廣路的搜索次數(shù)”就夠了。3. 機(jī)器學(xué)習(xí)與智能算法筆試中的“算法”不只是數(shù)據(jù)結(jié)構(gòu)3.1 經(jīng)典ML原理KNN、聚類、邏輯回歸、集成學(xué)習(xí)飛豬算法崗筆試很大一部分選擇題和簡(jiǎn)答題會(huì)落在機(jī)器學(xué)習(xí)基礎(chǔ)。這些題不像編程題那么費(fèi)腦但特別考驗(yàn)概念是否扎實(shí)。我當(dāng)時(shí)遇到的幾個(gè)高頻考點(diǎn)KNN的K值影響、K-Means的收斂條件、邏輯回歸的損失函數(shù)推導(dǎo)、XGBoost和GBDT的區(qū)別。KNN這題問(wèn)的是“K值增大時(shí)模型的偏差和方差如何變化”。答案是K值增大模型變得越簡(jiǎn)單偏差增大、方差減小。這個(gè)反直覺(jué)的點(diǎn)很?？家?yàn)楹芏嗳酥庇X(jué)認(rèn)為“樣本用得越多越準(zhǔn)”但實(shí)際上K太大時(shí)會(huì)把距離很遠(yuǎn)的樣本也納入投票導(dǎo)致邊界過(guò)于平滑。K-Means的題則經(jīng)常問(wèn)“初始k個(gè)中心點(diǎn)如何選擇”。標(biāo)準(zhǔn)答案是隨機(jī)選擇但隨機(jī)選擇容易陷入局部最優(yōu)所以實(shí)際工程會(huì)用K-Means先隨機(jī)選第一個(gè)中心點(diǎn)再按距離平方加權(quán)概率選擇后續(xù)中心點(diǎn)讓初始中心點(diǎn)盡可能分散。這個(gè)細(xì)節(jié)在面試?yán)镆步?jīng)常被追問(wèn)。邏輯回歸那邊手寫梯度下降更新公式是常規(guī)操作。邏輯回歸的損失函數(shù)是交叉熵L -(1/N) * Σ [y_i * log(p_i) (1 - y_i) * log(1 - p_i)]其中 p_i 1 / (1 exp(-w·x_i))。對(duì) w 求梯度后得到?L/?w (1/N) * Σ (p_i - y_i) * x_i所以梯度下降更新就是 w : w - lr * (1/N) * Σ (p_i - y_i) * x_i?？紙?chǎng)里能寫出這一步基本就能說(shuō)明你是理解邏輯回歸而不是只會(huì) import。集成學(xué)習(xí)這塊飛豬筆試比較偏愛(ài)“隨機(jī)森林和GBDT的區(qū)別”。一個(gè)核心區(qū)別是隨機(jī)森林是Bagging并行訓(xùn)練多棵樹然后投票或平均GBDT是Boosting串行訓(xùn)練每棵樹擬合前面的殘差。XGBoost在GBDT基礎(chǔ)上加了二階泰勒展開(kāi)、正則項(xiàng)和列采樣訓(xùn)練速度和精度都更好。這類題不需要你寫公式推導(dǎo)但需要能說(shuō)清楚“為什么”。3.2 概率與信息論KL散度與ELBO的推導(dǎo)套路KL散度和ELBO是算法崗筆試中偏難的一類題。很多人看到這兩名詞就頭大但飛豬2023年筆試確實(shí)考了而且不是簡(jiǎn)單的概念判斷題而是讓你寫出KL散度的定義式并解釋它在變分推斷里的作用。KL散度的定義式是KL(P || Q) Σ P(x) * log(P(x) / Q(x))注意KL散度不對(duì)稱KL(P||Q) ≠ KL(Q||P)所以它不是一個(gè)真正的距離度量。筆試選擇題經(jīng)常挖這個(gè)坑。ELBO的推導(dǎo)其實(shí)是變分推斷的核心。我們想最大化證據(jù) log P(X)但直接算很難因?yàn)橐e分掉隱變量 Z。于是引入一個(gè)變分分布 q(Z)利用Jensen不等式得到log P(X) ≥ E_{q(Z)}[log P(X, Z) - log q(Z)]右邊的期望就是ELBO。它等于ELBO E_q[log P(X|Z)] - KL(q(Z) || P(Z))這個(gè)式子很有用最大化ELBO等價(jià)于在“擬合數(shù)據(jù)”和“逼近先驗(yàn)”之間做權(quán)衡。筆試如果只考到一個(gè)層面你寫出ELBO的分解式并解釋“第一項(xiàng)是重建似然第二項(xiàng)是正則項(xiàng)”就足夠了。如果面試追問(wèn)再往VAE上引。我當(dāng)時(shí)復(fù)習(xí)的時(shí)候特意把KL散度、ELBO、EM算法串起來(lái)理解EM算法里E步就是在固定參數(shù)時(shí)計(jì)算隱變量的后驗(yàn)分布本質(zhì)上也和KL散度有關(guān)。把這些點(diǎn)串成一條線比零散背誦效率高很多。3.3 智能優(yōu)化算法粒子群、模擬退火、遺傳算法熱搜詞里頻繁出現(xiàn)“粒子群算法原理”“模擬退火算法”這說(shuō)明這類智能優(yōu)化算法在算法崗筆試中的出鏡率不低。它們的定位是當(dāng)問(wèn)題規(guī)模大、或者目標(biāo)函數(shù)不可導(dǎo)時(shí)傳統(tǒng)梯度方法失效需要借助啟發(fā)式搜索。粒子群算法PSO的核心是模擬鳥群覓食每個(gè)粒子有位置和速度更新時(shí)受兩個(gè)因素影響——個(gè)體歷史最優(yōu) pbest 和全局歷史最優(yōu) gbest。速度更新公式v_i w * v_i c1 * r1 * (pbest_i - x_i) c2 * r2 * (gbest - x_i) x_i x_i v_i這里 w 是慣性權(quán)重c1 是自我認(rèn)知系數(shù)c2 是社會(huì)認(rèn)知系數(shù)。筆試選擇題?？肌皐過(guò)大會(huì)怎樣”——答案是全局搜索能力強(qiáng)但收斂慢w過(guò)小則容易陷入局部最優(yōu)。模擬退火算法的核心是Metropolis準(zhǔn)則在退火過(guò)程中當(dāng)新解更優(yōu)時(shí)一定接受更差時(shí)以一定概率接受概率隨溫度降低而減小。概率公式是 exp(-ΔE / T)。這個(gè)“以一定概率接受差解”的設(shè)計(jì)目的是跳出局部最優(yōu)和貪心算法“只接受更優(yōu)解”的機(jī)制完全不同。這類題飛豬筆試一般不會(huì)讓你寫完整代碼而是放在選擇題中讓你判斷“這種做法體現(xiàn)了什么思想”。答這類題的關(guān)鍵不是死記步驟而是理解每種優(yōu)化算法解決的核心問(wèn)題。3.4 控制與信號(hào)類算法PID、卡爾曼濾波、FOC你可能會(huì)覺(jué)得奇怪算法崗筆試為什么會(huì)出現(xiàn)PID、卡爾曼濾波、FOC這些偏控制領(lǐng)域的算法。其實(shí)不少大廠算法崗也會(huì)涉及IoT設(shè)備、硬件數(shù)據(jù)、時(shí)序信號(hào)處理所以這些詞出現(xiàn)在熱搜里不是偶然。PID算法筆試考得最多的是增量式PID公式Δu(k) Kp * (e(k) - e(k-1)) Ki * e(k) Kd * (e(k) - 2e(k-1) e(k-2))筆試選擇題常問(wèn)如果系統(tǒng)響應(yīng)太慢應(yīng)該增大哪個(gè)參數(shù)答案是增大Kp或適當(dāng)增大Ki。如果系統(tǒng)超調(diào)嚴(yán)重、震蕩頻繁應(yīng)該增大Kd來(lái)抑制變化?？柭鼮V波則是狀態(tài)估計(jì)算法筆試高頻考點(diǎn)是“預(yù)測(cè)—更新”兩步套路預(yù)測(cè)x_pred F * x_prevP_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不需要你把矩陣寫完但要能說(shuō)清楚Q和R分別代表過(guò)程噪聲和觀測(cè)噪聲的不確定性K卡爾曼增益決定了更相信模型預(yù)測(cè)還是更相信傳感器觀測(cè)。如果R很小說(shuō)明觀測(cè)噪聲小卡爾曼增益會(huì)偏大濾波器更信任觀測(cè)值。4. 實(shí)操過(guò)程從讀題到AC的完整復(fù)盤4.1 筆試環(huán)境與流程提前踩點(diǎn)更安心飛豬當(dāng)時(shí)用的是常見(jiàn)的在線筆試平臺(tái)支持C、Java、Python等主流語(yǔ)言但要注意平臺(tái)不會(huì)幫你自動(dòng)補(bǔ)全代碼也沒(méi)有本地IDE那么智能。很多人平時(shí)習(xí)慣用PyCharm或VSCode到了筆試平臺(tái)連個(gè)括號(hào)匹配提示都沒(méi)有寫起來(lái)特別別扭。我建議在正式筆試前至少花半天時(shí)間去熟悉平臺(tái)的代碼編輯器。具體來(lái)說(shuō)試一下縮進(jìn)是空格還是Tab、錯(cuò)誤提示怎么看、有沒(méi)有“測(cè)試用例”按鈕、代碼是單文件提交還是多文件。我當(dāng)時(shí)就吃過(guò)虧有一道題里要讀一行包含空格的字符串平臺(tái)自帶的輸入示例是用“\n”分隔的我一開(kāi)始沒(méi)看清導(dǎo)致解析錯(cuò)誤。另外要注意語(yǔ)言選擇。Python寫起來(lái)快但某些平臺(tái)對(duì)Python的支持比較“原始”遞歸層數(shù)會(huì)被限制如果趕上DFS或者遞歸DP的題很可能會(huì)爆棧。我當(dāng)時(shí)遇到一道題第一反應(yīng)是用遞歸做動(dòng)態(tài)規(guī)劃寫完后本地通過(guò)平臺(tái)卻報(bào)“棧溢出”改成自底向上的遞推才過(guò)。這個(gè)細(xì)節(jié)值得提前知道。4.2 真題一手推KMP的next數(shù)組題目還原給定模式串 p abacaba寫出它的next數(shù)組并說(shuō)明其中next[6]的含義。解題過(guò)程明確next數(shù)組定義next[i]表示p[0..i-1]的最長(zhǎng)相等前后綴長(zhǎng)度。逐項(xiàng)計(jì)算next[0]-1, next[1]0, next[2]0, next[3]1, next[4]0, next[5]1, next[6]0, next[7]3。next[6]的含義是當(dāng)匹配到p[6]失敗時(shí)模式串應(yīng)該回退到位置0因?yàn)閚ext[6]0即從頭開(kāi)始重新匹配。如果把 next[6]3則說(shuō)明p[0..2]p[4..6]aba匹配失敗時(shí)可以跳到位置3保留已經(jīng)匹配的“aba”前綴。這個(gè)答題思路在筆試?yán)锖苷急阋瞬皇侵粚懘鸢高€寫清楚推導(dǎo)過(guò)程和含義面試官能一眼看出你是真懂還是背題。4.3 真題二帶權(quán)活動(dòng)選擇動(dòng)態(tài)規(guī)劃題目還原有 n 個(gè)活動(dòng)每個(gè)活動(dòng)有開(kāi)始時(shí)間 s_i、結(jié)束時(shí)間 e_i 和收益 v_i選擇不沖突的活動(dòng)求最大總收益。n ≤ 10^5時(shí)間范圍 0 ~ 10^9。這是一道典型的“加權(quán)區(qū)間調(diào)度”問(wèn)題。貪心選結(jié)束時(shí)間最早只能保證數(shù)量最多不能保證收益最大。正確做法是按結(jié)束時(shí)間 e_i 升序排序。定義 dp[i] 為前 i 個(gè)活動(dòng)能獲得的最大收益。轉(zhuǎn)移方程dp[i] max(dp[i-1], dp[p[i]] v_i)其中 p[i] 表示“最后一個(gè)結(jié)束時(shí)間 s_i”的活動(dòng)編號(hào)。因?yàn)閿?shù)組已按結(jié)束時(shí)間排序所以 p[i] 可以用二分查找在 O(log n) 時(shí)間內(nèi)找到。核心代碼如下Pythonimport bisect # activities [(start, end, value)] activities.sort(keylambda x: x[1]) n len(activities) starts [a[0] for a in activities] ends [a[1] for a in activities] dp [0] * (n 1) for i in range(1, n 1): s, e, v activities[i-1] # 找到最后一個(gè)結(jié)束時(shí)間 s 的活動(dòng) j bisect.bisect_right(ends, s, 0, i - 1) dp[i] max(dp[i-1], dp[j] v) print(dp[n])這道題我當(dāng)時(shí)的失誤是忘記給活動(dòng)按結(jié)束時(shí)間排序就開(kāi)始寫轉(zhuǎn)移方程寫到一半發(fā)現(xiàn)不對(duì)又回來(lái)改。所以強(qiáng)烈建議看到區(qū)間類DP第一步永遠(yuǎn)是排序不是急著設(shè)狀態(tài)。4.4 真題三酒店價(jià)格預(yù)測(cè)的業(yè)務(wù)設(shè)計(jì)題題目還原如果你要為飛豬上一個(gè)“酒店未來(lái)30天價(jià)格預(yù)測(cè)”的功能你會(huì)怎么做要求給出技術(shù)方案、特征設(shè)計(jì)和評(píng)估指標(biāo)。這類開(kāi)放題沒(méi)有標(biāo)準(zhǔn)答案但答題框架很重要。我當(dāng)時(shí)的回答思路是三層第一層問(wèn)題拆解。酒店價(jià)格預(yù)測(cè)本質(zhì)上是一個(gè)時(shí)間序列預(yù)測(cè)問(wèn)題但又有特殊性——價(jià)格受節(jié)假日、供需關(guān)系、競(jìng)對(duì)價(jià)格、用戶預(yù)訂行為影響不是簡(jiǎn)單ARIMA能解決的。第二層方案選型。短中期預(yù)測(cè)可以用LightGBM/XGBoost把時(shí)間特征星期幾、是否節(jié)假日、距出行日天數(shù)、酒店特征星級(jí)、評(píng)分、歷史價(jià)格、市場(chǎng)特征周邊同等級(jí)酒店平均價(jià)格、搜索熱度作為特征輸入。如果需要捕捉長(zhǎng)期依賴再上LSTM或Transformer但實(shí)際業(yè)務(wù)里樹模型往往性價(jià)比更高、更容易解釋。第三層評(píng)估指標(biāo)。價(jià)格預(yù)測(cè)的誤差評(píng)估不能用單一指標(biāo)。我當(dāng)時(shí)寫的是整體用MAPE平均絕對(duì)百分比誤差但它對(duì)低價(jià)格酒店很不友好價(jià)格100元的酒店差50元和價(jià)格1000元的酒店差50元MAPE差異巨大。所以可以補(bǔ)充WAPE加權(quán)絕對(duì)百分比誤差或者分價(jià)格段評(píng)估。這道題其實(shí)考察的是“能不能把一個(gè)寬泛的問(wèn)題轉(zhuǎn)化為可執(zhí)行的算法方案”。平時(shí)如果只刷LeetCode遇到這種題容易手足無(wú)措。建議多積累幾個(gè)常用業(yè)務(wù)場(chǎng)景的算法方案比如推薦排序、價(jià)格預(yù)測(cè)、銷量預(yù)估、異常檢測(cè)。5. 常見(jiàn)問(wèn)題與避坑技巧實(shí)錄5.1 時(shí)間不夠怎么辦優(yōu)先級(jí)與取舍飛豬筆試的總時(shí)間是固定的但很多人在選擇題上花費(fèi)過(guò)多時(shí)間導(dǎo)致編程題倉(cāng)促收尾。我看到的普遍情況是選擇題里有幾道機(jī)器學(xué)習(xí)推導(dǎo)題比如KL散度的變形、梯度公式的推導(dǎo)容易讓人糾結(jié)。我的建議是把這類題控制在每題2分鐘內(nèi)如果超過(guò)2分鐘還沒(méi)有思路先標(biāo)記跳過(guò)去。合理的優(yōu)先級(jí)是會(huì)做的編程題 會(huì)做的選擇題 會(huì)做一半的編程題 糾結(jié)的選擇題。編程題一道完整AC的分值往往頂好幾道選擇題所以哪怕放棄一兩道選擇題也要保證編程題有充分的調(diào)試時(shí)間。5.2 邊界條件與數(shù)據(jù)范圍最容易翻車的地方筆試翻車最常見(jiàn)的不是思路不會(huì)而是邊界條件沒(méi)處理。比如KMP的 next 數(shù)組很多人計(jì)算到中間就忘了 next[0] 的約定動(dòng)態(tài)規(guī)劃的狀態(tài)數(shù)組往往會(huì)多開(kāi)一位結(jié)果初始化寫錯(cuò)二分查找的邊界條件更是重災(zāi)區(qū)。我的經(jīng)驗(yàn)是寫完代碼后不要急著提交先用三組數(shù)據(jù)進(jìn)行自測(cè)——最小輸入比如n1、極端輸入比如所有區(qū)間都重疊、隨機(jī)輸入。這大概多花3分鐘但能避免大量無(wú)謂的罰時(shí)。飛豬筆試平臺(tái)支持自測(cè)用例一定要用起來(lái)。還有一個(gè)容易被忽略的點(diǎn)數(shù)據(jù)范圍決定算法選型。如果 n ≤ 10^5O(n^2) 的算法基本會(huì)超時(shí)如果 n ≤ 20可以考慮狀態(tài)壓縮DP和搜索。做題前先看一眼數(shù)據(jù)范圍再?zèng)Q定寫哪種復(fù)雜度的算法這是基本功。5.3 “算法崗筆試是不是只看編程”的常見(jiàn)誤區(qū)不少準(zhǔn)備秋招的人以為算法崗筆試就是刷題把精力全投在LeetCode上結(jié)果到了考場(chǎng)發(fā)現(xiàn)還有大量機(jī)器學(xué)習(xí)選擇題和場(chǎng)景設(shè)計(jì)題一下子就懵了。飛豬這場(chǎng)筆試就很典型編程題只占一部分還有不少選擇題在考概率統(tǒng)計(jì)、模型原理。我的建議是準(zhǔn)備算法崗筆試要雙線并行一條線是數(shù)據(jù)結(jié)構(gòu)與算法刷題重點(diǎn)突擊字符串、DP、圖論、貪心另一條線是機(jī)器學(xué)習(xí)基礎(chǔ)復(fù)盤手推邏輯回歸、K-Means、KNN、KL散度、集成學(xué)習(xí)這些高頻考點(diǎn)。尤其到了秋招后期大廠筆試越來(lái)越重視對(duì)算法原理的理解這是趨勢(shì)。5.4 刷題準(zhǔn)備崗位匹配的復(fù)習(xí)路線結(jié)合飛豬的業(yè)務(wù)場(chǎng)景旅行推薦、價(jià)格預(yù)測(cè)、搜索排序、供需預(yù)測(cè)我給準(zhǔn)備投飛豬算法崗的同學(xué)劃個(gè)復(fù)習(xí)重點(diǎn)必刷算法題字符串匹配KMP、區(qū)間DP、背包DP、最長(zhǎng)上升子序列、TopK、Dijkstra、并查集。必會(huì)ML模型邏輯回歸、決策樹/隨機(jī)森林/GBDT/XGBoost、K-Means、KNN、樸素貝葉斯。必懂?dāng)?shù)學(xué)概念KL散度、極大似然估計(jì)、貝葉斯公式、期望/方差、正態(tài)分布。可以了解但不用死磕粒子群、模擬退火、遺傳算法等智能優(yōu)化算法知道核心思想即可。有時(shí)間再擴(kuò)展PID、卡爾曼濾波、FOC這些偏控制/信號(hào)的算法出現(xiàn)概率較低但一旦出現(xiàn)就是區(qū)分度很高的題。按這個(gè)路線準(zhǔn)備既能覆蓋大部分考點(diǎn)又不至于陷入無(wú)意義的題海。飛豬筆試?yán)锬菐椎雷屛矣∠笊羁痰念}事后復(fù)盤其實(shí)都在這條路線的覆蓋范圍內(nèi)。如果你能把上述內(nèi)容真正吃透就算題型換一換也基本能穩(wěn)住。