21 年 7 月底，字节推荐算法（DATA-EDU）面试题 5 道

文末彩蛋：七月在线干货组最新升级的《2021 大厂最新 AI 面试题 [含答案和解析， 更新到前 121 题]》免费送！

1、分词方法 BPE 和 WordPiece 的区别

BPE 与 Wordpiece 都是首先初始化一个小词表，再根据一定准则将不同的子词合并。词表由小变大

BPE 与 Wordpiece 的最大区别在于，如何选择两个子词进行合并：BPE 选择频数最高的相邻子词合并，而 WordPiece 选择能够提升语言模型概率最大的相邻子词加入词表。

2、残差网络有哪些作用？除了解决梯度消失？

解决梯度消失和网络退化问题。

残差网络为什么能解决梯度消失？

残差模块能让训练变得更加简单，如果输入值和输出值的差值过小，那么可能梯度会过小，导致出现梯度小时的情况，残差网络的好处在于当残差为 0 时，改成神经元只是对前层进行一次线性堆叠，使得网络梯度不容易消失，性能不会下降。

什么是网络退化？

随着网络层数的增加，网络会发生退化现象：随着网络层数的增加训练集 loss 逐渐下降，然后趋于饱和，如果再增加网络深度的话，训练集 loss 反而会增大，注意这并不是过拟合，因为在过拟合中训练 loss 是一直减小的。

残差网络为什么能解决网络退化？

在前向传播时，输入信号可以从任意低层直接传播到高层。由于包含了一个天然的恒等映射，一定程度上可以解决网络退化问题。

3、交叉熵损失，二分类交叉熵损失和极大似然什么关系？

不难看出，这其实就是对伯努利分布求极大似然中的对数似然函数(log-likelihood)。

也就是说，在伯努利分布下，极大似然估计与最小化交叉熵损失其实是同一回事。

可参考：
https://zhuanlan.zhihu.com/p/51099880

4、二叉树最大路径和（路径上的所有节点的价值和最大）

参考答案

方法一：递归

首先，考虑实现一个简化的函数 maxGain(node)，该函数计算二叉树中的一个节点的最大贡献值，具体而言，就是在以该节点为根节点的子树中寻找以该节点为起点的一条路径，使得该路径上的节点值之和最大。

具体而言，该函数的计算如下。
空节点的最大贡献值等于 00。
非空节点的最大贡献值等于节点值与其子节点中的最大贡献值之和（对于叶节点而言，最大贡献值等于节点值）。

例如，考虑如下二叉树。

叶节点 99、1515、77 的最大贡献值分别为 99、1515、77。

得到叶节点的最大贡献值之后，再计算非叶节点的最大贡献值。节点 2020 的最大贡献值等于 20+max(15,7)=35，节点 -10 的最大贡献值等于 -10+max(9,35)=25。

• 本文地址：21 年 7 月底，字节推荐算法（DATA-EDU）面试题 5 道
• 本文版权归作者和AIQ共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出

上述计算过程是递归的过程，因此，对根节点调用函数 maxGain，即可得到每个节点的最大贡献值。

根据函数 maxGain 得到每个节点的最大贡献值之后，如何得到二叉树的最大路径和？对于二叉树中的一个节点，该节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值，如果子节点的最大贡献值为正，则计入该节点的最大路径和，否则不计入该节点的最大路径和。维护一个全局变量 maxSum 存储最大路径和，在递归过程中更新 maxSum 的值，最后得到的 maxSum 的值即为二叉树中的最大路径和。

5、写题：找数组中第 k 大的数，复杂度

三种思路：一种是直接使用 sorted 函数进行排序，一种是使用小顶堆，一种是使用快排（双指针 + 分治）。

方法一：直接使用 sorted 函数进行排序
代码如下：

方法二：

维护一个 size 为 k 的小顶堆，把每个数丢进去，如果堆的 size > k，就把堆顶 pop 掉（因为它是最小的），这样可以保证堆顶元素一定是第 k 大的数。

代码如下：

时间复杂度：O(nlogk)

空间复杂度：O(k)

方法三：双指针 + 分治

partition 部分

定义两个指针 left 和 right，还要指定一个中心 pivot（这里直接取最左边的元素为中心，即 nums[i]）

不断将两个指针向中间移动，使得大于 pivot 的元素都在 pivot 的右边，小于 pivot 的元素都在 pivot 的左边，注意最后满足时，left 是和 right 相等的，因此需要将 pivot 赋给此时的 left 或 right。

然后再将中心点的索引和 k - 1 进行比较，通过不断更新 left 和 right 找到最终的第 k 个位置。

代码如下：

时间复杂度：O(n)，原版快排是 O(nlogn)，而这里只需要在一个分支递归，因此降为 O(n)

空间复杂度：O(logn)

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

持续无限期更新大厂最新面试题，AI 干货资料，目前干货组汇总了今年 3 月-6 月份，各大厂面试题。