年月字节秋招算法道面试题分享
问题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://geek.zshipu.com/post/%E4%BA%92%E8%81%94%E7%BD%91/%E5%B9%B4%E6%9C%88%E5%AD%97%E8%8A%82%E7%A7%8B%E6%8B%9B%E7%AE%97%E6%B3%95%E9%81%93%E9%9D%A2%E8%AF%95%E9%A2%98%E5%88%86%E4%BA%AB/
- 版权声明:本作品采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议进行许可,非商业转载请注明出处(作者,原文链接),商业转载请联系作者获得授权。
- 免责声明:本页面内容均来源于站内编辑发布,部分信息来源互联网,并不意味着本站赞同其观点或者证实其内容的真实性,如涉及版权等问题,请立即联系客服进行更改或删除,保证您的合法权益。转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。也可以邮件至 sblig@126.com