2021年8月，字節(jié)秋招算法5道面試題分享！

問(wèn)題1：搜索旋轉(zhuǎn)排序數(shù)組帶重復(fù)值問(wèn)題

該題為leetcode第81題，搜索先轉(zhuǎn)排序數(shù)組II

對(duì)于數(shù)組中有重復(fù)元素的情況，二分查找時(shí)可能會(huì)有 a[l]=a[mid]=a[r]，此時(shí)無(wú)法判斷區(qū)間 [l,mid] 和區(qū)間 [mid+1,r] 哪個(gè)是有序的。

例如nums=[3,1,2,3,3,3,3]，target=2，首次二分時(shí)無(wú)法判斷區(qū)間 [0,3][0,3] 和區(qū)間 [4,6][4,6] 哪個(gè)是有序的。

對(duì)于這種情況，只能將當(dāng)前二分區(qū)間的左邊界加一，右邊界減一，然后在新區(qū)間上繼續(xù)二分查找。




2：二叉樹(shù)的之字形遍歷，遞歸和非遞歸

方法一：層序遍歷 + 雙端隊(duì)列
利用雙端隊(duì)列的兩端皆可添加元素的特性，設(shè)打印列表（雙端隊(duì)列） tmp ，并規(guī)定：
奇數(shù)層 則添加至 tmp 尾部 ，
偶數(shù)層 則添加至 tmp 頭部 。

算法流程：
特例處理：當(dāng)樹(shù)的根節(jié)點(diǎn)為空，則直接返回空列表 [] ；
初始化：打印結(jié)果空列表 res ，包含根節(jié)點(diǎn)的雙端隊(duì)列 deque ；
BFS 循環(huán)：當(dāng) deque 為空時(shí)跳出；
新建列表 tmp ，用于臨時(shí)存儲(chǔ)當(dāng)前層打印結(jié)果；
當(dāng)前層打印循環(huán)：循環(huán)次數(shù)為當(dāng)前層節(jié)點(diǎn)數(shù)（即 deque 長(zhǎng)度）；
出隊(duì)：隊(duì)首元素出隊(duì)，記為 node；
打印：若為奇數(shù)層，將 node.val 添加至 tmp 尾部；否則，添加至 tmp 頭部；
添加子節(jié)點(diǎn)：若 node 的左（右）子節(jié)點(diǎn)不為空，則加入 deque ；
將當(dāng)前層結(jié)果 tmp 轉(zhuǎn)化為 list 并添加入 res ；
返回值：返回打印結(jié)果列表 res 即可；

問(wèn)題3：Transformer Encoder和decoder的區(qū)別

Decoder和Encoder的結(jié)構(gòu)差不多，但是多了一個(gè)attention的sub-layer，這里先明確一下decoder的輸入輸出和解碼過(guò)程：

輸出：對(duì)應(yīng)i位置的輸出詞的概率分布輸入：encoder的輸出 & 對(duì)應(yīng)i-1位置decoder的輸出。所以中間的attention不是self-attention，它的K，V來(lái)自encoder，Q來(lái)自上一位置decoder的輸出解碼：這里要注意一下，訓(xùn)練和預(yù)測(cè)是不一樣的。在訓(xùn)練時(shí)，解碼是一次全部decode出來(lái)，用上一步的ground truth來(lái)預(yù)測(cè)（mask矩陣也會(huì)改動(dòng)，讓解碼時(shí)看不到未來(lái)的token）；而預(yù)測(cè)時(shí)，因?yàn)闆](méi)有g(shù)round truth了，需要一個(gè)個(gè)預(yù)測(cè)。

?問(wèn)題4：transformer對(duì)lstm的優(yōu)勢(shì)

Transformer 和 LSTM 的最大區(qū)別，就是 LSTM 的訓(xùn)練是迭代的、串行的，必須要等當(dāng)前字處理完，才可以處理下一個(gè)字。而 Transformer 的訓(xùn)練時(shí)并行的，即所有字是同時(shí)訓(xùn)練的，這樣就大大增加了計(jì)算效率。

?問(wèn)題5：Self-Attention公式為什么要除以d_k的開(kāi)方

避免出現(xiàn)梯度消失點(diǎn)積注意力被縮小了深度的平方根倍。這樣做是因?yàn)閷?duì)于較大的深度值，點(diǎn)積的大小會(huì)增大，從而推動(dòng)softmax函數(shù)往僅有很小的梯度的方向靠攏，導(dǎo)致了一種很硬的（hard）softmax。

例如，假設(shè)Q和K的均值為0，方差為1。它們的矩陣乘積將有均值為0，方差為 d_k 。因此，d_k 的平方根被用于縮放（而非其他數(shù)值），因?yàn)椋琎和K的矩陣乘積的均值本應(yīng)該為0，方差本應(yīng)該為1，這樣會(huì)獲得一個(gè)更平緩的softmax。