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

問(wèn)題

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

• 深淺拷貝的區(qū)別

  是否會(huì)對(duì)對(duì)象內(nèi)部的對(duì)象遞歸地拷貝（內(nèi)部對(duì)象指針指向原地址還是新的地址）磕潮。

• 類和對(duì)象的區(qū)別

  類主要定義了方法，可以當(dāng)做行為的模板容贝；對(duì)象是數(shù)據(jù)的載體自脯，并可以執(zhí)行類中定義的行為。

• 裝飾器的原理

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

• 常見(jiàn)的排序算法

  冒泡、插入满力、歸并焕参、快排、堆排序油额、基數(shù)排序等叠纷。

• 歸并算法的思想與時(shí)間復(fù)雜度

  思想：分治， 路歸并算法每次將 個(gè)元素的排序問(wèn)題分解成多個(gè) 規(guī)模的子問(wèn)題潦嘶，在子問(wèn)題求解完以后再對(duì)子問(wèn)題的解進(jìn)行合并涩嚣，可遞歸地進(jìn)行實(shí)現(xiàn)。

  時(shí)間復(fù)雜度：子問(wèn)題數(shù)量： 掂僵，分解與合并的復(fù)雜度 航厚，整體的復(fù)雜度： 。

• 數(shù)組與鏈表在原理锰蓬、操作時(shí)間復(fù)雜度上的區(qū)別幔睬，以及應(yīng)用場(chǎng)景

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

  操作時(shí)間復(fù)雜度：

  • 讀取、修改：數(shù)組 澈蚌， 鏈表 摹芙；
  • 增、刪：數(shù)組 （需要批量移動(dòng)內(nèi)部元素）宛瞄，鏈表 浮禾。

  應(yīng)用場(chǎng)景：

  • 數(shù)組：數(shù)據(jù)量已知、固定份汗，且讀取和修改操作的需求量大于增刪操作的需求量盈电；

  • 鏈表：數(shù)據(jù)量未知，且增刪操作較多杯活。

• 如何用兩個(gè)棧實(shí)現(xiàn)隊(duì)列

  假設(shè)有兩個(gè)棧 A匆帚、B：

  • 對(duì)于隊(duì)列的入隊(duì)操作，直接全部壓到棧 A 的頂部旁钧，此時(shí) A 中元素的順序與入隊(duì)的順序相反吸重，初始時(shí) B 為空棧。

  • 一旦遇到出隊(duì)操作：

    • 如果 B 為空歪今，則將 A 中的元素全部依次出棧并放入 B 中嚎幸，此時(shí) B 中元素的順序和入隊(duì)的順序是一致的，再將 B 中元素出棧寄猩；
    • 如果 B 不為空嫉晶，則直接從 B 中將元素出棧；
    • 出隊(duì)操作完成后田篇，不需要將 B 中元素再裝回 A 中替废，可直接用于下次出棧。

• 梯度爆炸與梯度消失的原因與理論基礎(chǔ)

  理論基礎(chǔ)：反向傳播時(shí)的鏈?zhǔn)角髮?dǎo)斯辰。

  原因：

  • 根本原因：反向傳播時(shí)舶担，如果導(dǎo)數(shù)權(quán)重一直大于 ，則在鏈?zhǔn)角髮?dǎo)的過(guò)程中梯度會(huì)越來(lái)越大彬呻，最終導(dǎo)致梯度爆炸衣陶；相反，如果導(dǎo)數(shù)權(quán)重一直小于 則會(huì)導(dǎo)致梯度越來(lái)越小闸氮，最終導(dǎo)致梯度消失剪况。
  • 導(dǎo)致梯度問(wèn)題的直接原因可能是：
    • 使用了不適當(dāng)?shù)募せ詈瘮?shù)，如 sigmoid 容易導(dǎo)致梯度消失蒲跨；
    • 模型復(fù)雜译断，深度過(guò)大，導(dǎo)致求導(dǎo)鏈過(guò)長(zhǎng)或悲；
    • 初始的特征孙咪、權(quán)重過(guò)大堪唐，導(dǎo)致輸出值方差較大，最終導(dǎo)致梯度過(guò)大翎蹈。

• 如何處理梯度爆炸與梯度消失

  • 處理梯度爆炸：
    • 對(duì)于梯度本身淮菠，可以考慮使用梯度裁剪限制每次優(yōu)化的幅度區(qū)間；
    • 使用 L1荤堪、L2 正則化合陵，每次在優(yōu)化時(shí)對(duì)參數(shù)施加一個(gè)正則懲罰項(xiàng)，防止優(yōu)化幅度過(guò)大澄阳。
  • 處理梯度消失：
    • 對(duì)于線性的數(shù)據(jù)拥知，使用 LSTM 中的“門(mén)控”（gate）思想，每次“記住”前面一些時(shí)間步的“記憶”碎赢，防止梯度消失低剔。
  • 通用的優(yōu)化手段：
    • 選擇更好的激活函數(shù)，如 ReLU揩抡、LeakyReLU 等户侥；
    • 使用殘差連接的思想設(shè)計(jì)模型，提供降低模型復(fù)雜度的可能性峦嗤；
    • 預(yù)訓(xùn)練+微調(diào)，每次僅對(duì)一層模塊進(jìn)行訓(xùn)練優(yōu)化并固定其他層屋摔，從而得到一層模塊的局部最優(yōu)解烁设，在得到眾多的局部最優(yōu)參數(shù)后，通過(guò)全局的反向傳播進(jìn)行微調(diào)得到全局最優(yōu)钓试；
    • 對(duì)不同的模塊使用不同的學(xué)習(xí)率装黑；
    • 使用 BatchNorm 等正則化方法，對(duì)層的輸入進(jìn)行優(yōu)化弓熏，使得訓(xùn)練更加穩(wěn)定恋谭；

• 如何處理過(guò)擬合

  • 從網(wǎng)絡(luò)結(jié)構(gòu)層次的角度，可以采用殘差連接的方式挽鞠，提供降低模型復(fù)雜度的可能疚颊；
  • 從正向傳播的角度，可以使用 Dropout的方式信认，每次丟棄一部分特征材义，防止參數(shù)過(guò)分依賴訓(xùn)練數(shù)據(jù)，增加參數(shù)對(duì)數(shù)據(jù)集的泛化能力嫁赏；
  • 從反向傳播的角度其掂，可以通過(guò)正則化的方式，每一次計(jì)算loss時(shí)增加一個(gè)參數(shù)相關(guān)的懲罰項(xiàng)潦蝇，縮放參數(shù)值使輸出的區(qū)間更為穩(wěn)定合理款熬；
  • 從數(shù)據(jù)處理的角度深寥，通過(guò)進(jìn)行 shuffle 打亂數(shù)據(jù)的順序、對(duì)數(shù)據(jù)進(jìn)行增廣（增加噪音贤牛、變換等）惋鹅，避免參數(shù)對(duì)數(shù)據(jù)的依賴，提高泛化能力盔夜；
  • 從訓(xùn)練的角度负饲，可以考慮使用 EarlyStopping 在模型持續(xù)優(yōu)化一定 Epoch 后便提前停止訓(xùn)練。

• CNN
  卷積神經(jīng)網(wǎng)絡(luò)喂链，用于對(duì)規(guī)則的歐氏空間內(nèi)的數(shù)據(jù)進(jìn)行處理：通過(guò)一個(gè)共享的卷積核（kernel）返十，每次在輸入的矩陣中按照設(shè)定的卷積核大小、步長(zhǎng)（Stride）和填充（padding）進(jìn)行移動(dòng)椭微，輸出為一個(gè)新的矩陣洞坑。

  即使卷積核為 的，其計(jì)算也與 MLP 不同：MLP是不同維度對(duì)應(yīng)不同的權(quán)重蝇率；而 的卷積核是共享的迟杂，即所有維度共享同一個(gè)權(quán)重。

• 開(kāi)放思考題：有哪幾種方法（思路）來(lái)判斷APP的截圖中是否存在彈窗

  基本就是 CV 相關(guān)的領(lǐng)域了本慕，不涉及具體技術(shù)細(xì)節(jié)僅從解決思路來(lái)回答的話排拷，主要可以從以下幾個(gè)角度（訓(xùn)練 CV 相關(guān)的模型）進(jìn)行檢測(cè)：

  • 邊框：大部分彈窗以及其中的互動(dòng)按鈕都包含一些規(guī)則的邊框（如矩形、圓角矩形锅尘、圓形）等监氢，可提取這些邊框進(jìn)行識(shí)別，但是如果背景中存在邊框或者遇到不規(guī)則的彈窗（如有其他附加物）則難以準(zhǔn)確識(shí)別藤违；
  • 顏色：從彈窗的設(shè)計(jì)機(jī)制來(lái)說(shuō)浪腐，一般在彈窗出現(xiàn)時(shí)會(huì)通過(guò)降低背景界面的明度、飽和度等方式讓用戶聚焦于彈窗顿乒，從顏色的角度可以進(jìn)行識(shí)別议街；
  • 文本：使用 OCR 相關(guān)功能提取截圖中的文本，并判斷是否屬于彈窗相關(guān)的文本（如“關(guān)閉”璧榄、“確定”特漩、“注意”、“通知”等）犹菱；
  • 位置：彈窗一般位于截圖的中間拾稳、中上等用戶容易聚焦的位置，重點(diǎn)關(guān)注這些位置的信息可以提高彈窗識(shí)別的準(zhǔn)確度腊脱。

  將以上角度綜合進(jìn)行考慮就能基本覆蓋大部分彈窗場(chǎng)景访得。

總結(jié)

面試所考察的知識(shí)點(diǎn)不深且較廣（但也屬于正常該掌握的范圍），包含機(jī)器學(xué)習(xí)與 Python、算法悍抑、數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)鳄炉。

面試的部門(mén)偏向通過(guò) AI 算法為測(cè)試和研發(fā)提供技術(shù)支持，所以面試中涉及到的開(kāi)放思考題也和測(cè)試的業(yè)務(wù)有關(guān)搜骡。