2021年8月，字节秋招算法5道面试题分享！

问题1：搜索旋转排序数组带重复值问题

该题为leetcode第81题，搜索先转排序数组II

对于数组中有重复元素的情况，二分查找时可能会有 a[l]=a[mid]=a[r]，此时无法判断区间 [l,mid] 和区间 [mid+1,r] 哪个是有序的。

例如nums=[3,1,2,3,3,3,3]，target=2，首次二分时无法判断区间 [0,3][0,3] 和区间 [4,6][4,6] 哪个是有序的。

对于这种情况，只能将当前二分区间的左边界加一，右边界减一，然后在新区间上继续二分查找。




2：二叉树的之字形遍历，递归和非递归

方法一：层序遍历 + 双端队列
利用双端队列的两端皆可添加元素的特性，设打印列表（双端队列） tmp ，并规定：
奇数层 则添加至 tmp 尾部 ，
偶数层 则添加至 tmp 头部 。

算法流程：
特例处理：当树的根节点为空，则直接返回空列表 [] ；
初始化：打印结果空列表 res ，包含根节点的双端队列 deque ；
BFS 循环：当 deque 为空时跳出；
新建列表 tmp ，用于临时存储当前层打印结果；
当前层打印循环：循环次数为当前层节点数（即 deque 长度）；
出队：队首元素出队，记为 node；
打印：若为奇数层，将 node.val 添加至 tmp 尾部；否则，添加至 tmp 头部；
添加子节点：若 node 的左（右）子节点不为空，则加入 deque ；
将当前层结果 tmp 转化为 list 并添加入 res ；
返回值：返回打印结果列表 res 即可；

问题3：Transformer Encoder和decoder的区别

Decoder和Encoder的结构差不多，但是多了一个attention的sub-layer，这里先明确一下decoder的输入输出和解码过程：

输出：对应i位置的输出词的概率分布输入：encoder的输出 & 对应i-1位置decoder的输出。所以中间的attention不是self-attention，它的K，V来自encoder，Q来自上一位置decoder的输出解码：这里要注意一下，训练和预测是不一样的。在训练时，解码是一次全部decode出来，用上一步的ground truth来预测（mask矩阵也会改动，让解码时看不到未来的token）；而预测时，因为没有ground truth了，需要一个个预测。

 问题4：transformer对lstm的优势

Transformer 和 LSTM 的最大区别，就是 LSTM 的训练是迭代的、串行的，必须要等当前字处理完，才可以处理下一个字。而 Transformer 的训练时并行的，即所有字是同时训练的，这样就大大增加了计算效率。

 问题5：Self-Attention公式为什么要除以d_k的开方

避免出现梯度消失点积注意力被缩小了深度的平方根倍。这样做是因为对于较大的深度值，点积的大小会增大，从而推动softmax函数往仅有很小的梯度的方向靠拢，导致了一种很硬的（hard）softmax。

例如，假设Q和K的均值为0，方差为1。它们的矩阵乘积将有均值为0，方差为 d_k 。因此，d_k 的平方根被用于缩放（而非其他数值），因为，Q和K的矩阵乘积的均值本应该为0，方差本应该为1，这样会获得一个更平缓的softmax。