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] 哪个是有序的。

对于这种情况,只能将当前二分区间的左边界加一,右边界减一,然后在新区间上继续二分查找。
在这里插入图片描述

文末免费送电子书:七月在线干货组最新 升级的《2021最新大厂AI面试题》免费送!


问题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。

评论区回复 “2021”,七月在线干货组最新升级的《2021大厂最新AI面试题 [含答案和解析, 更新到前121题]》,免费送!

持续无限期更新大厂最新面试题,AI干货资料,目前干货组汇总了今年3月-6月份,各大厂面试题。
在这里插入图片描述


本文地址:https://www.6aiq.com/article/1632768589170
本文版权归作者和AIQ共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出