這篇文章記錄我自畢業以來，為大模型算法崗位面試準備的一些知識。這篇筆記主要基於個人實際經歷，希望可供後來者參考。
本人水平有限，文章内容不一定正確。本文的内容也難稱完整，會持續保持更新。
算法基礎知識
交叉熵、熵和KL散度之間的關係是什麼？
設\(P\)代表實際數據的分佈，\(Q\)是模型預測的分佈，那麼，
熵的定義： \[ H (P) = -\sum_x P(x) \log P(x) \] 交叉熵： \[ H_\text{CE}(P, Q) = -\sum_x P(x) \log {Q(x)} \]
KL散度的定義： \[ D_\text{KL}(P, Q) = \sum_x P(x) \log {P(x) \over Q(x)} \]
\[ H_\text{CE}(P, Q) = D_\text{KL}(P, Q) + H(P) \]
什麼時候優化KL散度等於優化交叉熵？
如前所述，如果數據分佈\(H(P)\)為常數（即不隨優化過程改變），那麼優化KL散度等價於優化交叉熵。
反過來，如果\(P\)隨著優化過程變化，那麼兩個優化目標就不能等價了。
LLM數據工程
数据去重为什么重要？有哪些数据去重的方法？
- 提升训练效率：重复数据让模型浪费算力做无用功，拖慢收敛速度。
- 防止过拟合与记忆：模型会“背下”重复样本，而不是学习泛化规律，导致测试效果差，甚至引发隐私泄露。
- 缓解长尾问题：高频数据重复会加剧数据不平衡，让模型忽视低频但重要的知识。
常用的去重方法：
- 精确去重：直接比对字符串或字节，移除完全相同的样本。常用哈希指纹（如MD5）来加速。
- 近似去重（模糊去重）：用于发现内容高度相似但不完全相同的文本。经典算法是MinHash + LSH。對於小規模數據，可以使用編輯距離去重。
偏好對齊方法為什麼需要准备成對的訓練數據？能不能只給正面數據，不提供負面數據？
我們從以下幾點分析這個問題。
1. 數據集中能不能只包含正面數據或負面數據？如果只給正面數據，那麼偏好對齊任務便退化為SFT任務。Jiwoo Hong等人(Hong, Lee, and Thorne 2024)指出，隨著SFT過程的進行，雖然模型產生訓練文本的概率會上升，但被拒絕文本的概率也隨之上升。這表明只給出正面數據（只做SFT）是無法作偏好微調的。類似的，可以推測如果只降低負面數據的出現概率，那正面文本的出現概率也會下降。
2. 為什麼PPO使用的是成對的正負樣本，而不是為每一個回復給出一個準確的分值？ - 標註噪聲：從標註規範制定的角度看，個例的打分結果會帶有噪聲，而同時進行成對的數據標註，有助於減少標註噪聲。 - 從reward model學習的角度看，reward model學習目標是正確地評估不同回復之間的相對優劣，而不是模型回復的絕對評分，因此標註過程中分數不是必要的。 - 評分的粒度問題：例如，有兩個模型回復都打了3分（5分制），那這兩個回復間就不能再分出優劣了嗎？即使兩個回復都打了同樣的分數，它們之間的差異也可能提供有價值的信息。 以上討論說明了為什麼PPO為什麼採用了成對正負樣本進行訓練。但是在項目實踐中，我也經歷過需要標註員標註具體分數的情況。在任務規範清晰、打分標準容易制定的前提下，規定具體的評分標準有好處：
- 詳細、嚴謹的規範有助於減少數據中的噪聲；
- 分值間的相對差異大小可以為訓練過程提供細化的指導。例如，可參考LLaMa 2(Touvron et al., n.d.)在reward model的損失中加入一個margin component，要求正負樣本相似時reward model的打分可以不用差距太大，反之則要求二者的打分要有顯著差異。
- 最後，即使是在標註員已經提供了具體分值的情況下，我們仍要求標註員對所有回復進行排序，即使有些模型回復的分值是相同的。不同標註員的排序一致性是評價數據質量的一個重要指標。
3. 訓練成本。 從訓練成本的角度來看，成對的偏好訓練數據更容易大規模收集（例如可以在用戶點踩的時候立即給出另一個備選回復），標註成本也更低。
预训练/後訓練/偏好對齊/强化学习
LoRA訓練的時候，如何選擇凍結的層？
LoRA本身只插入低秩適配器（Adapter）矩陣，原始權重是凍結的，因此問題的關鍵不在於「凍結哪些層」，而在於「對哪些層應用LoRA適配器」。常見的選擇策略如下：
- 只對Attention的Q和V矩陣應用LoRA：這是LoRA原始論文的做法，在參數量和效果之間取得平衡。Q和V的調整對模型行為影響較大，足以適應下游任務。
- 對所有Attention層（Q/K/V/O）應用LoRA：當下游任務與預訓練分佈差異較大時（如代碼生成、數學推理），對所有Attention投影矩陣都應用LoRA可以提升適配能力。
- 對FFN層也應用LoRA：FFN層存儲了大量知識，在需要注入新知識或改變模型行為模式時（如長CoT訓練），對FFN層也應用LoRA有幫助。
- 根據層深度選擇：底層（靠近輸入）捕獲通用語法/句法特徵，高層（靠近輸出）更偏向語義和任務相關特徵。因此：
- 若任務與原始領域差異不大，可只對高層應用LoRA；
- 若任務需要大幅改變模型行為，建議對所有層均應用LoRA。
- 根據參數重要性選擇：可計算各層權重的Fisher Information或梯度幅值，選擇重要性高的層應用LoRA，減少冗餘參數。
實踐中，最常見的配置是對所有Attention的Q和V矩陣應用LoRA（rank=8~64），再根據任務複雜度決定是否擴展到其他層。
PPO的critic model是做什麼的，為什麼需要critic model？
Critic model（也稱value model）在PPO中負責估計狀態價值函數 \(V(s)\)，即給定當前狀態（已生成的token序列），預測從該狀態出發能獲得的期望累積獎勵。
為什麼需要critic model？
- 降低梯度方差（Variance Reduction）：PPO使用advantage函數 \(A(s,a) = Q(s,a) - V(s)\) 來衡量某個動作相對於平均水平的優勢。直接使用reward作為信號，梯度方差極大，訓練不穩定。減去baseline \(V(s)\) 後，方差顯著降低。
- 提供逐位置的學習信號：reward model只在完整序列結束時給出一個獎勵（稀疏獎勵），而critic model可以在每個token位置估計未來回報，使得actor model在每個生成步驟都能獲得學習信號。
- GAE（Generalized Advantage Estimation）的依賴：PPO通常使用GAE來計算advantage，GAE需要在每個時間步都有value預測，以平衡bias和variance的trade-off。
為什麼不能直接用reward model代替critic model？
Reward model給出的是完整序列的獎勵評分，而critic model給出的是當前狀態的期望回報。二者角色不同：reward model是環境提供的評分信號，critic model是對該評分信號的擬合，用於降低方差。如果去掉critic model，PPO就退化為REINFORCE算法，方差會大幅增加，訓練難以收斂。
為什麼GRPO可以成功去除PPO的critic model？
核心改進在於用group內的相對優勢替代critic model的value估計。
具體來說：
Group-based advantage估計：GRPO對同一個prompt採樣多個回復（一個group），然後用group內各回復的reward相對於group均值的標準化分數作為advantage： \[A_i = \frac{r_i - \text{mean}(r_1,\dots,r_G)}{\text{std}(r_1,\dots,r_G)}\] 這本質上是用group內的其他樣本作為baseline，替代了critic model的value估計。
為什麼可以去掉critic model？
- Critic model的作用是提供baseline以降低方差。GRPO利用同一prompt下多個採樣結果的reward分佈來構造baseline，同樣能達到降低方差的效果。
- 省去critic model意味著減少了約一半的訓練參數（value model通常與policy model規模相當），顯著降低了顯存和計算開銷。
- 避免了critic model訓練不穩定或擬合不準確帶來的額外噪聲。
GRPO的侷限：GRPO依賴於group內樣本的多樣性。如果group內所有回復的reward相近（方差小），則advantage信號微弱，訓練效率降低。這也是後續DAPO提出Dynamic Sampling（丟棄reward方差為0的group）的原因。
GRPO方法在后续其它的工作中得到哪些改进？
DAPO：
- Clip higher：DAPO观察到训练过程中，actor model的entropy在不断降低，导致reward趋同且探索不足，故提出修改PPO-Clip策略，允許clip的下界和上界設置不同的值。通過提高上界，可以鼓勵探索。
- 移除KL散度。DAPO认为在长CoT训练的过程中，模型参数显著偏离原模型是寻常的，而且移除KL散度项不会严重影响效果；
- Dynamic Sampling：GRPO需要group內有reward差異，否則當前組內數據就不會產生梯度。如果一組rollout沒有reward variance，DAPO會直接將其丟棄。
- Token-Level Loss：原GRPO會進行sequence-level的loss平均，這會導致長回復的sample中，每個token的權重變小。DAPO採取token級別的平均，有利於長思維鏈學習。
- Overlong Reward Shaping：GRPO通常採用truncation和簡單的超長懲罰。DAPO提出length-aware penaly，在超長時給予線性的懲罰（從0線性降低到-1）。
GSPO：
- 序列級重要性採樣：GRPO逐token算重要性權重，長序列方差高，噪聲累積；GSPO用整個序列的聯合概率比（幾何平均），所有token等權重；
- 序列級裁剪與獎勵：裁剪和獎勵分配都改為全序列級別；
詳細介紹Clip higher這個技巧。
DAPO采用的目標函數具備這樣的形式： \[ \begin{aligned} \mathcal J(\mathbf \theta) &= \mathbb E \left[ \frac{1}{\sum_{i=1}^G|o_i|} \sum_{i=1}^G \sum_{t=1}^{|o_i|} \min(r_{i, t}(\mathbf \theta) \hat A_{i, t}, clip( r_{i, t}(\mathbf \theta), 1 - \epsilon_\text{low}, 1 + \epsilon_\text{high} )\hat A_{i, t} ) \right]\\ \end{aligned} \] 我們分情況討論$ (r_{i, t}() A_{i, t}, clip( r_{i, t}(), 1 - , 1 + )A_{i, t} )$這個核心算式：
- 如果\(r_{i, t}(\theta)\)處於上下截斷界限之間，公式簡化為\(r_{i, t}(\mathbf \theta)\hat A_{i, t}\)這樣的簡單情形，我們不做更多討論；
- 如果\(r_{i, t}(\theta)\)被截斷為\(1 - \epsilon_\text{low}\)，此時policy model比reference model更不偏好使用當前action。公式變成\(\min(r_{i, t}(\mathbf \theta) \hat A_{i, t}, (1 - \epsilon_\text{low})\hat A_{i, t})\)，此時如果\(\hat A_{i, t}<0\)，\(\theta\)的梯度就被截斷，阻止policy model進一步降低當前action的輸出概率；
- 如果\(r_{i, t}(\theta)\)被截斷為\(1 + \epsilon_\text{high}\)，此時policy model比reference model更偏好使用當前action。公式變成\(\min(r_{i, t}(\mathbf \theta) \hat A_{i, t}, (1 + \epsilon_\text{high})\hat A_{i, t})\)，此時如果\(\hat A_{i, t} > 0\)，\(\theta\)的梯度就消失，阻止policy model進一步增大對當前action的偏好；
DAPO將\(\epsilon_\text{low}\)和\(\epsilon_\text{high}\)設置為不同的值，並適當提高\(\epsilon_\text{high}\)，從而允許模型在\(\hat A_{i, t}\)為正的時候，減少對提高“exploitation token”概率的限制，從而鼓勵exploitation。
有時關閉DAPO的dynamic sampling，效果反而更好。為什麼？
因為DAPO的重新採樣改變了數據分佈。例如模型已經高概率答對了某個問題，但dynamic sampling會重新採樣，直到出現負例，導致模型過度訓練。
為什麼要做偏好對齊？只做SFT不行嗎？
只做SFT不做偏好對齊經常會導致一些問題。
1. 從訓練目標來看：預訓練、SFT任務本質上都是要求模型預測下一個token，而這與具体业务场景的目標——例如”以安全和有益的方式遵循人類指令”——是不一致的(Ouyang et al. 2022)。這種訓練目標的不對齊導致模型容易產生不安全、不忠實或有害的信息。 2. 曝光偏差問題：在預訓練、SFT階段，模型只是在訓練數據的分佈上進行下一個token的預測。一些基於強化學習的偏好對齊任務提供了一種在模型自身預測分佈上進行訓練的方法(Ranzato et al. 2015)，緩解了曝光偏差問題。
為什麼SFT後的大模型會有幻覺？
模型的幻覺是指模型誤認為自己能感知到一些實際感知不到的東西，或者以非常肯定的態度給出錯誤信息。例如，問”現在是幾點鐘？“，模型在不接入外部插件的情況下回答”現在是下午三點”，這便屬於模型幻覺。
預訓練、SFT任務本質上都是要求模型預測下一個token，而這與AI應用的目標——“以安全和有益的方式遵循人類指令”是不一致的(Ouyang et al. 2022)。這種訓練目標的不對齊導致模型容易產生不安全、不忠實或有害的信息，例如導致模型幻覺。
什麼是對齊稅？如何減少對齊稅？
在經過偏好對齊後，模型的通用能力可能下降，比如可能出現更多地生成不適當的”拒絕回答”現象，這一問題被稱為”對齊稅”。 那麼，我們要如何減少”對齊稅”，讓經過RLHF的模型盡量保持RLHF之前的能力呢？
- 訓練時不要偏離reference太多：在PPO算法中，除了reward model、policy model，還有一個reference model（同樣由SFT後的模型初始化得到）。PPO算法會限制policy model不過分偏離reference model。這可以視為一種限制policy model能力偏移的機制。（儘管reference model的作用不止於此。）InstructGPT(Ouyang et al. 2022)指出通過在PPO更新步驟中混入增加預訓練分佈的對數似然可以大幅降低模型的能力衰退。
- 強化學習/偏好對齊不一定帶來對齊稅：儘管多數研究未能消除偏好對齊對模型性能的損害，但也存在證據表明負對齊稅是可能實現的。OpenAI對大模型數學答題能力的一項研究(Lightman et al. 2023)顯示以合適的reward model設計為前提，模型的數學回答正確率能夠提升。儘管這項工作是針對數學任務進行的，但這一結論有可能可以推廣到一般的文本生成任務。
當前RLHF的流程有什麼值得優化的地方？
這是一個開放性問題。言之有理地回答即可。
個人認為可以討論的點：
- 更細粒度的reward：如Let’s Verify Step by Step(Lightman et al. 2023)一文指出的那樣，偏好對齊可有更細粒度的標註，給出更準確的reward反饋。現在普遍常見的偏好數據只針對完整的回答給出標註，而不是針對每一個句子給出標註。相比於標註整個回答的偏好，僅標註出第一個有問題的句子/步驟不會增加更多的標註代價，但能夠提升reward信號的精細程度。這樣的細粒度偏好數據是目前比較少見的，有待建設；
- BT模型的優化和精細化：大多數偏好對齊方法採用了BT模型。BT模型要求reward model拉開正負樣本的得分差距，但並沒有考慮到正負樣本間差異以及偏好程度差異的強弱問題。直覺上，對於回復相似，偏好差異不明顯的情況，應該給與比較低的權重；對於回復差異大，偏好對比明顯的情況，應該給與比較高的權重。一些工作(Touvron et al., n.d.; Meng, Xia, and Chen 2024)嘗試了人為設置規則或調整超參來調整BT model的margin，但也許還有自適應地調整BT model的margin且取得更好對齊效果的方法存在。
Qwen 3.5有哪些重要的優化點？
- 混合注意力機制：Gated Delta Network + 標準注意力。其中75%的層採用了混合注意力；
- 極致稀疏的MoE架構，極低的激活比。397B激活17B，35B激活3B；
- 原生多模態+early fusion，使用視覺token，而不是文本模型+外掛視覺；
- 原生多token預測支持
Agent設計
RAG
讲一讲NDCG（Normalized Discounted Cumulative Gain）这个reward/metric。
在介绍NDCG之前，先需要了解DCG和IDCG。
DCG:设召回模型返回n条结果， \[ DCG = \sum_{i=1}^n \frac{ 2^{\text{rel}_i} - 1 }{ \log_2(i+1) } \]
- \(\text{rel}_i\)表示第\(i\)个位置的搜索结果的相关性；我们可以用标注数据来定义相关性，如果第\(i\)个结果在标注的ground truth中，就让它的相关性为1，否则为0.
- 分子：相关性越高，贡献越大
- 分母：位置越靠后，折扣越大，按\(\log\)衰减。这是因为我们假设用户更关心排序靠前的结果。
IDCG：把所有结果按最佳排序（相关性从高到低）时的 DCG。
NDCG：\(\text{NDCG} = {\text{DCG}\over \text{IDCG}}\). 可以看出\(0 \le \text{NDCG} \le 1\). \(0\le \text{NDCG}\)是显然的。而\(\text{NDCG} \le 1\)可以这样理解：
假设存在\(i < j, g_i > g_j\)，其中\(g_i, g_j\)是DCG的分子。那么交换这两项带来DCG的差值为： \[ \begin{aligned} \Delta &= {g_i \over \log_2(j+1)} + {g_j \over {\log_2(i+1)}} -({{{g_i} \over {\log_2(i+1)}} +{ g_j \over {\log_2(j+1)}}})\\ &= {g_i - g_j\over\log_2(j+1) } + {g_j - g_i\over \log_2(i+1)}\\ &= (g_j - g_i)(\frac{1}{\log_2(i+1)} - \frac{1}{\log_2(j+1)})\\ & > 0 \end{aligned} \]
因此DCG这类问题的最佳排序方案就是为高权重的位置分配高价值的结果，因此\(\text{NDCG} \le 1\).
災難性遺忘
例子 8 ⭐SFT過程中會出現災難性遺忘嗎？如何應對災難性遺忘？
一般我們在項目中會通過SFT來獲得一個面向專門領域和特定任務的模型，例如心理診療模型、法律咨詢模型、醫療建議模型、論文修改模型。SFT的過程中大模型很容易忘記對象任務以外的知識，損失一部分通用能力。就目前的技術來看，災難性遺忘問題是不可避免的，但可以通過以下方法緩解：
限制偏離基模的程度：使用基模作為教師模型，引入KL散度約束，使模型的token分佈不要過於偏離預訓練模型。 數據重放：一種直接的做法是在SFT階段隨機地採樣一部分預訓練數據。（經驗上看，預訓練數據的採樣比例在SFT階段會起到比較大的影響。）
部分參數微調：與全量微調不同，可考慮採用LoRA、Soft Prompt等方法，通過調控參與訓練的參數量來控制SFT的擬合程度。（個人實踐中還是全量微調比較多。）
其它訓練參數的調整：可以嘗試調整學習率、epoch數等參數，使用early stop等技巧減少過擬合和遺忘現象。一般訓練13個epoch、損失降到0.50.3以下就好。訓練太多，訓練集擬合得太厲害也不是好事。
除了在訓練階段盡量緩解災難性遺忘問題，去彌補訓練後已經發生的遺忘也是一種可取思路。以下是一些工程上可以選擇的方法：
外部知識庫/知識圖譜/檢索增強：實際上指望大模型記住各種各樣瑣碎的知識是十分困難的。相比之下，賦予大模型隨時調用外部知識庫是一種彌補知識缺陷的有效方法。
一些相關的學術工作：LoRAMoE(Dou et al. 2024)通過凍結主幹網絡，迫使LoRA利用一部分世界知識來緩解災難性遺忘。
CoT
例子 9 ⭐你是如何構造CoT的？
多模態大模型
例子 10 ⭐你能列舉幾個常見的從視覺編碼器的圖像特征映射到大模型文本特征的方法嗎？
例子 11 ⭐各種多模態融合模塊的優缺點？ （注意）Q-Former容易破壞visual token之間的空間關係。
例子 12 ⭐如果讓你從頭開始訓練一個多模態大模型，你會如何設計模型結構、訓練流程和項目流程？
例子 13 ⭐對於多模態大模型，提高圖像的分辨率是十分重要的。為什麼現在的大模型往往使用如256x256這類低分辨率的圖像，無法做到高分辨率呢？
例子 14 ⭐你觀察到GPT4-V有哪些問題？為什麼會存在這些問題？
自然語言處理
例子 15 ⭐⭐⭐⭐旋轉位置編碼相對於原本的絕對位置編碼有何改進？
TODO
例子 16 🌙🌙手写Multi-Head Attention。
例子 18 🌙🌙爲什麽Transformer模型要使用LayerNorm而不是BatchNorm。
TODO
例子 19 🌙🌙介紹RMSNorm。
TODO
例子 20 🌙🌙請介紹幾種你熟悉的tokenization方法。
TODO
例子 21 Encoder-Decoder結構、Prefix LM和Causal LM有什麼不同？
T5論文的Figure 4很好地展示了三者的不同。 Encoder-Decoder結構下，Encoder的輸入token間是兩兩互相可見的，Decoder的attention mask則是單向可見的。
Prefix LM和Causal LM的結構相近，區別是Prefix LM中，前綴文本內的token是兩兩互相可見的，前綴文本後的token是單向可見的；而Causal LM中所有token都是單向可見的。
Prefix LM和Encoder-Decoder相比是類似的，都允許一部分token之間兩兩完全可見，但Prefix LM好比是實現了Encoder和Decoder的參數共享，減少了參數量。
當下Causal LM是被大模型廣泛採用的架構。雖然Encoder-Decoder和Prefix LM的雙向注意力理論上有優勢，但仍然被大模型領域所”淘汰”。這就引出了另一個問題，“為什麼大模型都採用Causal LM結構”
例子 22 ⭐⭐⭐為什麼大模型都採用Causal LM結構？
- KV-Cache優化：Encoder-Decoder和Prefix LM都不易採用KV-Cache優化，而支持KV-Cache的Causal LM對推理加速更友好；
- 訓練效率：Encoder-Decoder架構模型的Pipeline Parallel難以優化。即使模型架構能帶來理論上的性能優勢，但是卻帶來昂貴的訓練代價的話，那麼這種模型結構就會輸給那些更能充分利用算力的模型；
- 軌跡依賴：OpenAI使用Causal LM成功實現了GPT系列大模型，這使得後來者都更傾向於採用相近的配置進行實驗。
計算機視覺相關問題
例子 23 爲什麽要對圖像做預處理？
- 預處理將數據變換到統一的格式，方便模型學習；
- 通過提前提取有用的特徵，裁剪出感興趣區域來加快計算；
例子 24 ⭐ViT模型中是如何對位置信息進行編碼的？
TODO
例子 25 ⭐請比較Transformer和CNN
TODO
深度學習相關問題
例子 26 ⭐在訓練模型的過程中，我們經常遇到過擬合。有哪些常見的應對過擬合的方法？
- 數據層面：增加數據量、數據增強；
- 模型設計層面：Dropout、DropBlock、weight decay；
- 訓練策略：遷移學習、部分參數微調、early stop、輔助任務、不確定性估計；
- 推理策略：test-time augmentation；
機器學習問題
例子 27 ⭐手寫K-Means
例子 28 🌙特徵存在共綫性問題會有什麽影響？應當如何應對。
TODO
例子 29 🌙如果特徵維度很大而樣本又少，應該怎麽辦？
TODO
例子 30 🌙🌙MSE和MAE分別作爲損失函數會帶來什麽區別？
例子 31 🌙特徵存在共綫性問題會有什麽影響？應當如何應對。
TODO
算法題
接下来简单记录一些面试过程中实际遇到的或其它面試經驗推薦的題。
在面試過程中要求現場手寫的算法題常常不會很難，但作答過程中要思路清晰，能夠有效地與面試官溝通，盡量減少試錯次數，一次通過。
答題之前記得問清楚數據規模，時間複雜度和空間複雜度需求。
- ⭐最長回文子串
- ⭐二叉樹的最近公共祖先
- ⭐⭐兩數之和變體：設A、B是兩個有序數組，找出所有\(i, j\)滿足
A[i] + B[j] = k，要求常數空間複雜度，線性時間複雜度。
此題需要注意數組不是嚴格單調的，即可能連續出現若干個相同的數。編寫雙指針法時需要注意邊界條件，避免漏掉一些解。 - ⭐⭐三數之和：由兩數之和擴展而來的一道題。
- ⭐滑動窗口求最大值：要求\(O(n)\)時間複雜度。
- ⭐top k算法：寫出\(O(n\log k)\)的基於堆的方法並不困難，但最好能進一步掌握基於快排的\(O(n)\)時間複雜度的解法。
- 🌙岛屿数量：實際上屬於求連通域數量的算法，可用DFS/BFS/并查集方法解。
- 🌙反转每对括号间的子串：考察栈的用法。也可以不用栈来解。容易想到\(O(n^2)\)复杂度的算法，但实际也存在\(O(n)\)的解法。
- 🌙搜索選擇排序數組：考察二分法。需要做題者注意到選擇排序數組的特性。
- 🌙尋找兩個正序數組的中位數（困難）：更一般的，可以推廣為尋找兩個正序數組的第k小的數。考察二分法。需要思考應該對哪個量做二分查找。
- 🌙NER的BIO形式標註轉start，end形式（例子 38）：以命名實體識別（NER）任務為背景的簡單算法題。
- 🌙馬在棋盤上的概率：可以用動態規劃的方法求解，時間複雜度為\(O(n^2k)\)，這裏\(n\)為棋盤大小，\(k\)為步數。還可以想到本題所執行的動態規劃步驟實際上是一種捲積，且每一步的捲積核都是相同的，因此本題可以用快速冪的方式進行優化。
- 🌙整数拆分：將整數\(n\geq 2\)拆分為任意個正整數的和，使其乘積最大。容易想到基於動態規劃的解法，但不容易給出\(O(1)\)時間複雜度的，基於數學分析的解法。
- 問題延伸：如果題目改為將整數\(n\geq 2\)拆分為任意個正數的和，使其乘積最大。該如何分析？參考例子 39
- ⭐給定一個字符串和一個詞典，問字符串能否由詞典中的單詞拼接而成。用DFS可解。可考慮引入緩存等策略進行優化。
開放性問題
例子 32 ⭐在個人技術成長方面，你有什麼規劃？
例子 33 ⭐為什麼想要離職？
僅僅是解釋前東家的缺點是不夠的。每個公司有每個公司的缺點，不能保證下一家沒有相同的問題。一般可以將問題解釋為當前公司平臺無法提供更好的發展，而現在在看的機會能補充這方面的不足。最好不要表現出自己是當前工作上遇到困難而離職的，而應盡量表現出自己的事業當前處於上升期，但由於某些原因（工作地點、待遇、發展方向、職業規劃）而不得不離開。這時可以順帶説説自己有多麽適合這個新崗位。重要的是表現出自己與新公司是一個互相成就的關係。
例子 34 ⭐請介紹一下過往最困難的一個項目。
例子 35 ⭐你當前採用的項目方案的亮點是什麼？你對項目最重要的貢獻是？
例子 36 ⭐是什麼使你在項目中具有不可替代性？或者是什麼使你具備比他人更高的價值？
總結
筆記的重要性：只學習不總結就容易忘。不做筆記不行啊。最好每次面試過後，立即將記錄下來，時不時重新過一遍。
平時多練習，多刷題，保持手感。有的公司（例如Minimax）的算法测试会期望给出最优解，面試時 即使把題目做出來了，也可以問一下需不需要繼續改進，提一提能想到的改進點。
拿到Offer後，記得問以下重點問題。可以不直接問，但也需要間接地通過各種渠道去瞭解。要瞭解的包括但不限於：
- 績效的考核方式，KPI的考核情況
- 有沒有末位淘汰
- 有沒有輪流背D績效
- 績效工資佔縂工資比例
- 績效有沒有強制分佈
- 績效如何影響年終獎
股票和期權的行權規則
競業協議
- 是否需要背競業協議
- 競業協議是否與期權等權利挂鈎
一些經驗和感想：
- （不是絕對的）不論是體制内還是體制外，國企還是私企，只要在國内，就不要相信955的存在。一位HR可以毫無心裏負擔地告訴你它是955，但它也可以隨時轉變為996而不受到任何約束。同理，一家企業聲稱它是996，那麽你可以大膽推測它實際上已經是9106了。在这一点上面，猎头可能比HR更不可信。有一个猎头给我推荐了一家香港的初创公司，告诉我这是一家WLB（Work-Life Balance）的公司，但是我和创始人聊天的时候，他却笑着告诉我”初创公司不加班，还有谁敢来呀”。另一个猎头给我推荐宁德时代，告诉我那个组加班不严重。我觉得都不可不相信；
- 競業協議是不公平的。如果你簽下了競業協議，公司就有權阻止你入職同行業内的任何公司，並在你離職後提供一些微小的補償。但相反的，假如你主動離職去读博、考公，主動希望公司啟動競業協議，公司卻可以選擇不啟動競業。主動權總是掌握在公司手上。
一般來說，即使簽訂了協議，公司也不會捨得為一個初入職場的大頭兵啟動競業。因此初入職場的同學不必過於擔心這個問題。但不論如何，在簽訂新公司時還是要對競業協議保持謹慎。某些公司，例如拼多多，有很大的概率啓動競業協議，并且在员工離職後派人調查其去向；
附錄
例題
例子 37 ⭐兩個硬幣的後驗概率
有兩個硬幣，一個硬幣的兩面都是正面；另一個是正常硬幣：一面是正面，另一面是反面；
隨機選取其中一枚，拋擲五次，都是正面。問這枚硬幣是正常硬幣的概率是？
解：設\(A=\text{拋擲五次硬幣都是正面}\)，\(B={這是一枚正常硬幣}\)
題目要求\(P(B|A)\)
\[ \begin{aligned} P(B|A) &= P(A|B) P(B) / P(A)\\ &= 0.5^5 \times 0.5 / P(A) \end{aligned} \]
其中
\[ \begin{aligned} P(A) &= P(A|B)P(B) + P(A|\neg B)P(\neg B) \\ &= 0.5^5 \times 0.5 + 1 \times 0.5 \\ \end{aligned} \]
所以
\[ \begin{aligned} P(B|A) &= 0.5^5 \times 0.5/ P(A) \\ &= \frac{0.5^5 \times 0.5} {0.5^5\times 0.5 + 1\times 0.5}\\ &= \frac{1}{1 + 32}\\ &= \frac{1}{33} \end{aligned} \]
例子 38 🌙NER标注格式转换
描述: 在命名实体识别(NER)任务中,BIO标注方式是常用的标注格式之一。但在某些应用场景下,我们可能需要将BIO格式转换为start,end形式的标注。
请你实现一个Python函数,将BIO格式的NER标注转换为start,end形式。
函数输入:
- tokens: 一个字符串列表,表示分词后的句子
- bio_tags: 一个字符串列表,表示对应的BIO标注
函数输出: 一个字典列表,每个字典包含以下键:
- ‘entity’: 实体文本
- ‘start’: 实体开始位置
- ‘end’: 实体结束位置
- ‘type’: 实体类型
示例：
输入:
tokens = ['John', 'lives', 'in', 'New', 'York', '.']
bio_tags = ['B-PER', 'O', 'O', 'B-LOC', 'I-LOC', 'O']输出:
[
{'entity': 'John', 'start': 0, 'end': 1, 'type': 'PER'},
{'entity': 'New York', 'start': 3, 'end': 5, 'type': 'LOC'}
]请实现函数bio_to_span(tokens, bio_tags)来完成这个转换任务。
实体的end索引应该是实体最后一个词的索引+1
对于单个词的实体,start和end的差值应该是1
需要正确使用连续的多个词组成的实体
def bio_to_span(tokens, bio_tags):
tokens.append('<eos>')
bio_tags.append('O')
start = 0
end = 0
entity = []
typ = None
ret = []
for i, (t, b) in enumerate(zip(tokens, bio_tags)):
if b.startswith('B-'):
start = i
entity = [t]
typ = b[2:]
elif b.startswith('I-'):
assert typ == b[2:], '{} != {}'.format(typ, b[2:])
elif b == 'O':
if len(entity):
end = i
ret.append({
'entity': ''.join(tokens[start:end]),
'start': start,
'end': end,
'type': typ
})
entity.clear()
else:
raise Exception("Invalid BIO label: {}".format(b))
return ret 接下來用一些測試用例檢查給出的算法的正確性。在請求面試官檢查之前，先自己編寫一些測試用例是一個好習慣。
查看測試用例
test_cases = [
# case 1
{
"input": (["我", "爱", "北京", "天安门"], ["O", "O", "B-LOC", "I-LOC"]),
"output": [{'entity': '北京天安门', 'type': 'LOC', 'start': 2, 'end': 4}]
},
# case 2
{
"input": (["他", "是", "一位", "来自", "中国", "的", "医生", "，", "名叫", "张伟"],
["O", "O", "O", "O", "B-LOC", "O", "B-PROF", "O", "O", "B-PER"]),
"output": [{'entity': '中国', 'type': 'LOC', 'start': 4, 'end': 5},
{'entity': '医生', 'type': 'PROF', 'start': 6, 'end': 7},
{'entity': '张伟', 'type': 'PER', 'start': 9, 'end': 10}]
},
# case 3 (空实体)
{
"input": (["今天", "天气", "真好"], ["O", "O", "O"]),
"output": []
},
# case 4
{
'input': (
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'],
['O', 'B-PER', 'I-PER', 'O', 'B-ORG', 'I-ORG', 'I-ORG', 'O', 'B-LOC', 'O']
),
'output': [{'entity': 'bc', 'type': 'PER', 'start': 1, 'end': 3},
{'entity': 'efg', 'type': 'ORG', 'start': 4, 'end': 7},
{'entity': 'i', 'type': 'LOC', 'start': 8, 'end': 9}]
},
# case 5 (空序列)
{
'input': (
[], []
),
'output': []
},
# case 6 (只有O标签)
{
'input': (['a', 'b', 'c'], ['O', 'O', 'O']),
'output': []
},
# case 7
{
'input': (
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'],
['B-PER', 'I-PER', 'O', 'B-PER', 'O', 'B-PER', 'I-PER', 'I-PER']
),
'output': [{'entity': 'ab', 'type': 'PER', 'start': 0, 'end': 2},
{'entity': 'd', 'type': 'PER', 'start': 3, 'end': 4},
{'entity': 'fgh', 'type': 'PER', 'start': 5, 'end': 8}]
}
]
for test_case in test_cases:
out = bio_to_span(*test_case['input'])
assert len(out) == len(test_case['output']), 'Length inqueal! {} != {}'.format(out, test_case['output'])
for o1, o2 in zip(out, test_case['output']):
for k in o2.keys():
assert o1[k] == o2[k], '{} != {}'.format(o1, o2)
print('所有測試用例均通過。')例子 39 🌙如何將整數\(n\geq 2\)拆分為任意個正數的和，使其乘積最大？
設\(n\)被拆分為\(k\)個數，容易證明每個數都為\(n/k\)时乘積最大。（先證明\(k=2\)時，\(n\)應該被拆為\(\frac{n}{2} + \frac{n}{2}\)；然後通過構造條件滿足數學歸納法來證明。）
加下來，設將\(n\)拆為\(k\)份，可知其乘積應為\(f(n, k) = \left(\frac{n}{k}\right)^k\). 先不考慮\(k\)應為正整數的問題，令\(k \in \mathbb R^+\). \(f(n, k)\)是一個連續函數。
\[ \begin{aligned} f(n, k) &= e^{\ln \left(\frac{n}{k}\right)^k} \\ &= e^{k\ln n - k \ln k } \end{aligned} \]
\[ \begin{aligned} \frac{\partial f}{\partial k} &= e^{k\ln n - k \ln k }\cdot (\ln n - \ln k - 1) \end{aligned} \]
\[ \begin{aligned} \frac{\partial f}{\partial k} = 0 & \Rightarrow \ln n - \ln k - 1 = 0\\ & \Rightarrow k = \frac{n}{e} \end{aligned} \]
容易看出\(\frac{\partial f}{\partial k}\)隨著\(k\)的增加而單調上升。因此\(k=\frac{n}{e}\)是函數的極大值點。但是\(k\)需要是整數，因此我們可以考慮取\(k=\lceil \frac{n}{e} \rceil\)或\(k=\lfloor \frac{n}{e}\rfloor\)，取其中使乘積最大的\(k\)即可。
例子 40 求斐波那契數列1、1、2、3、5、8……的通項公式。
當\(n\geq 3\)時，有\(F_{n} = F_{n-1} + F_{n-2}\). 寫成矩陣形式為
\[ \begin{pmatrix} F_n\\ F_{n-1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} F_{n-1}\\ F_{n-2} \end{pmatrix} \]
於是可得
\[ \begin{aligned} \begin{pmatrix} F_n\\ F_{n-1} \end{pmatrix} &= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} F_{n-1}\\ F_{n-2} \end{pmatrix} \\ &= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^2 \begin{pmatrix} F_{n-2}\\ F_{n-3} \end{pmatrix} \\ &= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{n-2} \begin{pmatrix} 1\\ 1 \end{pmatrix} \\ &=\mathbf A^{n-2} \begin{pmatrix} 1\\ 1 \end{pmatrix} \end{aligned} \]
\(\mathbf A= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}\)的特征值為\(\lambda_1 = \frac{1 - \sqrt 5}{2}\), \(\lambda_2 = \frac{1 + \sqrt 5}{2}\)，對應的特征向量為 \(\vec x_1 = (\frac{1 - \sqrt 5}{2}, 1)^T\)， \(\vec x_2 = (\frac{1 + \sqrt 5}{2}, 1)^T\)
特征值的求解方法
設\(\lambda\)是\(\mathbf A\)的特征向量，\(\vec x\)是對應的特征向量，則有
\[ \mathbf A \vec x = \lambda \vec x \]
從而得到\(\lambda \mathbf E - \mathbf A\)的秩為0.
\[ \left| \begin{matrix} \lambda - 1 & -1 \\ -1 & \lambda \end{matrix} \right| = 0 \Rightarrow \lambda ^2 - \lambda - 1 = 0 \]
從而得到兩個解：\(\lambda_1 = \frac{1 - \sqrt 5}{2}\), \(\lambda_2 = \frac{1 + \sqrt 5}{2}\)
將\(\lambda_1, \lambda_2\)的值代入到\((\lambda \mathbf E - \mathbf A)\vec x = \vec 0\)可解得兩個特征向量
\[ \vec x_1 = (\frac{1 - \sqrt 5}{2}, 1)^T \]
和
\[ \vec x_2 = (\frac{1 + \sqrt 5}{2}, 1)^T \]
因此\(\mathbf A\)是可對角化的，即令
\[ \mathbf P = \begin{pmatrix} \vec x_1, \vec x_2 \end{pmatrix} ,\]
則有\(\mathbf P^{-1} \mathbf A \mathbf P = \mathbf\Lambda=\begin{pmatrix} \lambda_1 & 0 \\ 0 & \lambda_2 \end{pmatrix}\) 因此\(\mathbf A^{n-2}=(\mathbf P^{-1} \mathbf\Lambda \mathbf P)^{n-2}=\mathbf P \mathbf\Lambda^{n-2} \mathbf P^{-1}\)
\[ \begin{aligned} \mathbf P \mathbf\Lambda^{n-2} \mathbf P^{-1} \begin{pmatrix} 1 \\ 1 \end{pmatrix} &= \frac{1}{\lambda_1 - \lambda_2} \begin{pmatrix} \lambda_1 & \lambda_2 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} \lambda_1 & 0 \\ 0 & \lambda_2 \end{pmatrix}^{n-2} \begin{pmatrix} 1 & -\lambda_2 \\ -1 & \lambda_1 \end{pmatrix} \begin{pmatrix} 1 \\ 1 \end{pmatrix} \\ &=\frac{1}{\lambda_1 - \lambda_2} \begin{pmatrix} \lambda_1 & \lambda_2 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} \lambda_1^{n-2} & 0 \\ 0 & \lambda_2^{n-2} \end{pmatrix} \begin{pmatrix} \lambda_1 \\ \lambda_2 \end{pmatrix}\\ &=\frac{1}{\lambda_1 - \lambda_2} \begin{pmatrix} \lambda_1 & \lambda_2 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} \lambda_1^{n-1} \\ \lambda_2^{n-1} \end{pmatrix}\\ &=\frac{1}{\lambda_1 - \lambda_2} \begin{pmatrix} \lambda_1^n + \lambda_2^n\\ \lambda_1^{n-1}+\lambda_2^{n-1} \end{pmatrix}\\ \end{aligned} \]
即通項公式為\(F_n=\frac{1}{\lambda_1 - \lambda_2}(\lambda_1^n + \lambda_2^n)\)，代入特征值得到\(F_n=\frac{1}{\sqrt 5}((\frac{1+\sqrt 5}{2})^n - (\frac{1 - \sqrt 5}{2})^n)\)
參考資料：斐波那契數列通項公式求解
