嗶哩嗶哩：2021 算法崗（實習(xí)）

問題

Python列表與元組的區(qū)別
元組一旦初始化后，就不可以再改變（無法直接修改元組內(nèi)對象的指針或者增刪元素，但是可以調(diào)用內(nèi)部元素的方法進行操作，如list.append），但是列表沒有這些限制。
深淺拷貝的區(qū)別

是否會對對象內(nèi)部的對象遞歸地拷貝（內(nèi)部對象指針指向原地址還是新的地址）。
類和對象的區(qū)別

類主要定義了方法，可以當做行為的模板；對象是數(shù)據(jù)的載體，并可以執(zhí)行類中定義的行為。
裝飾器的原理

裝飾器本身就是一個接收方法為參數(shù)的方法，可以在內(nèi)部調(diào)用被裝飾的方法前后執(zhí)行其他邏輯。
常見的排序算法

冒泡、插入、歸并、快排、堆排序、基數(shù)排序等。
歸并算法的思想與時間復(fù)雜度

思想：分治， $k$ 路歸并算法每次將 $n$ 個元素的排序問題分解成多個 $n/k$ 規(guī)模的子問題，在子問題求解完以后再對子問題的解進行合并，可遞歸地進行實現(xiàn)。

時間復(fù)雜度：子問題數(shù)量： $\log(n)$ ，分解與合并的復(fù)雜度 $O(n)$ ，整體的復(fù)雜度： $O(n\log (n))$ 。
數(shù)組與鏈表在原理、操作時間復(fù)雜度上的區(qū)別，以及應(yīng)用場景

原理：二者都擁有線性的邏輯結(jié)構(gòu)，區(qū)別主要在物理結(jié)構(gòu)上，數(shù)組的內(nèi)存大小固定且連續(xù)，鏈表中元素在內(nèi)存中不連續(xù)。

操作時間復(fù)雜度：
- 讀取、修改：數(shù)組 $O(1)$ ，鏈表 $O(N)$ ；
- 增、刪：數(shù)組 $O(n)$ （需要批量移動內(nèi)部元素），鏈表 $O(1)$ 。
應(yīng)用場景：
- 數(shù)組：數(shù)據(jù)量已知、固定，且讀取和修改操作的需求量大于增刪操作的需求量；
- 鏈表：數(shù)據(jù)量未知，且增刪操作較多。
如何用兩個棧實現(xiàn)隊列

假設(shè)有兩個棧 A、B：
- 對于隊列的入隊操作，直接全部壓到棧 A 的頂部，此時 A 中元素的順序與入隊的順序相反，初始時 B 為空棧。
- 一旦遇到出隊操作：
  - 如果 B 為空，則將 A 中的元素全部依次出棧并放入 B 中，此時 B 中元素的順序和入隊的順序是一致的，再將 B 中元素出棧；
  - 如果 B 不為空，則直接從 B 中將元素出棧；
  - 出隊操作完成后，不需要將 B 中元素再裝回 A 中，可直接用于下次出棧。
梯度爆炸與梯度消失的原因與理論基礎(chǔ)

理論基礎(chǔ)：反向傳播時的鏈式求導(dǎo)。

原因：
- 根本原因：反向傳播時，如果導(dǎo)數(shù)權(quán)重一直大于 $1$ ，則在鏈式求導(dǎo)的過程中梯度會越來越大，最終導(dǎo)致梯度爆炸；相反，如果導(dǎo)數(shù)權(quán)重一直小于 $1$ 則會導(dǎo)致梯度越來越小，最終導(dǎo)致梯度消失。
- 導(dǎo)致梯度問題的直接原因可能是：
  - 使用了不適當?shù)募せ詈瘮?shù)，如 sigmoid 容易導(dǎo)致梯度消失；
  - 模型復(fù)雜，深度過大，導(dǎo)致求導(dǎo)鏈過長；
  - 初始的特征、權(quán)重過大，導(dǎo)致輸出值方差較大，最終導(dǎo)致梯度過大。
如何處理梯度爆炸與梯度消失
- 處理梯度爆炸：
  - 對于梯度本身，可以考慮使用梯度裁剪限制每次優(yōu)化的幅度區(qū)間；
  - 使用 L1、L2 正則化，每次在優(yōu)化時對參數(shù)施加一個正則懲罰項，防止優(yōu)化幅度過大。
- 處理梯度消失：
  - 對于線性的數(shù)據(jù)，使用 LSTM 中的“門控”（gate）思想，每次“記住”前面一些時間步的“記憶”，防止梯度消失。
- 通用的優(yōu)化手段：
  - 選擇更好的激活函數(shù)，如 ReLU、LeakyReLU 等；
  - 使用殘差連接的思想設(shè)計模型，提供降低模型復(fù)雜度的可能性；
  - 預(yù)訓(xùn)練+微調(diào)，每次僅對一層模塊進行訓(xùn)練優(yōu)化并固定其他層，從而得到一層模塊的局部最優(yōu)解，在得到眾多的局部最優(yōu)參數(shù)后，通過全局的反向傳播進行微調(diào)得到全局最優(yōu)；
  - 對不同的模塊使用不同的學(xué)習(xí)率；
  - 使用 BatchNorm 等正則化方法，對層的輸入進行優(yōu)化，使得訓(xùn)練更加穩(wěn)定；
如何處理過擬合
- 從網(wǎng)絡(luò)結(jié)構(gòu)層次的角度，可以采用殘差連接的方式，提供降低模型復(fù)雜度的可能；
- 從正向傳播的角度，可以使用 Dropout的方式，每次丟棄一部分特征，防止參數(shù)過分依賴訓(xùn)練數(shù)據(jù)，增加參數(shù)對數(shù)據(jù)集的泛化能力；
- 從反向傳播的角度，可以通過正則化的方式，每一次計算loss時增加一個參數(shù)相關(guān)的懲罰項，縮放參數(shù)值使輸出的區(qū)間更為穩(wěn)定合理；
- 從數(shù)據(jù)處理的角度，通過進行 shuffle 打亂數(shù)據(jù)的順序、對數(shù)據(jù)進行增廣（增加噪音、變換等），避免參數(shù)對數(shù)據(jù)的依賴，提高泛化能力；
- 從訓(xùn)練的角度，可以考慮使用 EarlyStopping 在模型持續(xù)優(yōu)化一定 Epoch 后便提前停止訓(xùn)練。
CNN
卷積神經(jīng)網(wǎng)絡(luò)，用于對規(guī)則的歐氏空間內(nèi)的數(shù)據(jù)進行處理：通過一個共享的卷積核（kernel），每次在輸入的矩陣中按照設(shè)定的卷積核大小、步長（Stride）和填充（padding）進行移動，輸出為一個新的矩陣。

即使卷積核為 $1\times 1$ 的，其計算也與 MLP 不同：MLP是不同維度對應(yīng)不同的權(quán)重；而 $1\times1$ 的卷積核是共享的，即所有維度共享同一個權(quán)重。
開放思考題：有哪幾種方法（思路）來判斷APP的截圖中是否存在彈窗

基本就是 CV 相關(guān)的領(lǐng)域了，不涉及具體技術(shù)細節(jié)僅從解決思路來回答的話，主要可以從以下幾個角度（訓(xùn)練 CV 相關(guān)的模型）進行檢測：
- 邊框：大部分彈窗以及其中的互動按鈕都包含一些規(guī)則的邊框（如矩形、圓角矩形、圓形）等，可提取這些邊框進行識別，但是如果背景中存在邊框或者遇到不規(guī)則的彈窗（如有其他附加物）則難以準確識別；
- 顏色：從彈窗的設(shè)計機制來說，一般在彈窗出現(xiàn)時會通過降低背景界面的明度、飽和度等方式讓用戶聚焦于彈窗，從顏色的角度可以進行識別；
- 文本：使用 OCR 相關(guān)功能提取截圖中的文本，并判斷是否屬于彈窗相關(guān)的文本（如“關(guān)閉”、“確定”、“注意”、“通知”等）；
- 位置：彈窗一般位于截圖的中間、中上等用戶容易聚焦的位置，重點關(guān)注這些位置的信息可以提高彈窗識別的準確度。
將以上角度綜合進行考慮就能基本覆蓋大部分彈窗場景。