笔试面经

回答一个面试问题的基本要点

是什么、
为什么（动机）、
怎么做（原理）、
使用场景、
一些细节（如果使用过的话）

Reference

BAT机器学习面试1000题系列（第1~305题） - CSDN博客

笔试

字节跳动 180812

Index

头条/字节跳动-深度学习/NLP 方向

一面

自我介绍
聊项目
深度学习基本问题
【算法】手写 K-Means
磕磕绊绊算是写出来一个框架，内部细节全是问题，面试官比较宽容，勉强算过了

二面

自我介绍
聊项目
深度学习基本问题
【算法】找数组中前 k 大的数字
我说了两个思路：最小堆和快排中的 partition 方法；让我选一个实现，我选的堆方法，然后又让我实现调整堆的方法

三面

自我介绍
为什么会出现梯度消失和梯度爆炸
- 分别说了下前馈网络和 RNN 出现梯度消失的情况
有哪些解决方法
- 因为提到了残差和门机制，所以又问
- 分别说下它们为什么能缓解梯度消失
- 因为说残差的时候提到了 ResNet，让我介绍下 ResNet（没用过，随便说了几句）
其他加速网络收敛的方法（除了残差和门机制）
- 我从优化方法的角度说了一点（SGB 的改进：动量方法、Adam）
- 提示我 BN，然后我就把 BN 的做法说了一下
- 然后问 BN 为什么能加速网络的收敛（从数据分布的角度随便说了几句）
传统的机器学习方法（简历上写用过 GBDT）
- 简单介绍下 XGBoost
- CART 树怎么选择切分点（基尼系数）
- 基尼系数的动机、原理（不会）

【算法】直方图蓄水问题

LeetCode 42. 接雨水；
当时太紧张没想出 O(N) 解法，面试一结束就想出来了，哎
附 AC 代码
```C++
class Solution {
public:
int trap(vector<int>& H) {
    int n = H.size();

      vector<int> dp_fw(H);
      vector<int> dp_bw(H);

      for(int i=1; i<n; i++)      // 记录每个位置左边的最高点
          dp_fw[i] = max(dp_fw[i-1], dp_fw[i]);

      for(int i=n-2; i>=0; i--)   // 记录每个位置右边的最高点
          dp_bw[i] = max(dp_bw[i+1], dp_bw[i]);

      int ret = 0;
      for (int i=1; i<n-1; i++)  // 取两侧较矮的点
          ret += min(dp_fw[i], dp_bw[i]) - H[i];

      return ret;
  }

};

```

四面（非加面）

因为流程出了问题，其实还是三面
【算法】和为 K 的连续子数组，返回首尾位置
LeetCode 560. 和为K的子数组
很熟悉的题，但就是没想出来；然后面试官降低了难度，数组改成有序且为正整数，用双指针勉强写了出来；但是边界判断有问题，被指了出来；然后又问无序的情况或者有负数的情况能不能也用双指针做，尬聊了几分钟，没说出个所以然。
如何无监督的学习句子表示
我说 Self-Attention
让我把公式写出来，因为写的不清楚，让我写原始的 Attention
然后问怎么训练，损失函数是什么（没说出来，除了词向量我基本没碰过无监督任务，而且我认为词向量也算不上无监督...）
如何无监督的学习一个短视频的特征表示
抽取关键帧，然后通过 ResNet 等模型对每一帧转化为特征表示，然后对各帧的特征向量做拼接或者直接保存为二维特征（瞎说的，别说视频，我连图像都没做过）

今日头条-算法工程师-实习

6.14今日头条算法工程师实习生笔经面经牛客网

一面

自我介绍；
二分查找；
Algorithm_for_Interview/常用子函数/二分查找模板.hpp
判断链表是否有环；
Algorithm_for_Interview/链表/链表中环的入口结点.hpp
将数组元素划分成两部分，使两部分和的差最小，数组顺序可变；
Algorithmfor_Interview/查找与排序/[暴力搜索划分数组使和之差最小.hpp](https://github.com/imhuay/Algorithm_for_Interview-Chinese/blob/master/Algorithm_for_Interview/查找与排序/暴力搜索_划分数组使和之差最小.hpp)
智力题，在一个圆环上随机添加3个点，三个点组成一个锐角三角形的概率；
../数学问题/#1
推导逻辑斯蒂回归、线性支持向量机算法；
../机器学习/逻辑斯蒂回归推导
../机器学习/线性支持向量机推导

二面

在一个圆环上随机添加3点，三个点组成一个锐角三角形的概率；
用积分计算上述概率；
用程序解决上述问题
多次采样求概率，关键是如何判断采样的三个点能否构成锐角三角形，不同的抽象会带来不同的复杂度。
最直接的想法是，根据边长关系，此时需要采样三个 x 坐标值，相应的 y 坐标通过计算得出，然后计算三边长度，再判断，循环以上过程，计算形成锐角的比例。
更简单的，根据 ../数学/#1 中提到的简单思路，原问题可以等价于“抛两次硬币，求两次均为正面的概率”——此时，只需要采样两个(0, 1)之间的值，当两个值都小于 0.5 意味着能构成锐角三角形。
深度学习，推导反向传播算法，知道什么激活函数，不用激活函数会怎么样，ROC与precesion/recall评估模型的手段有何区别，什么情况下应该用哪一种？深度学习如何参数初始化？
../深度学习/反向传播算法
../深度学习/激活函数
../深度学习/参数初始化
介绍kaggle项目，titanic，用到了哪些框架，用到了哪些算法；

三面

自我介绍；
分层遍历二叉树，相邻层的遍历方向相反，如第一层从左到右遍历，下一层从右向左遍历；
介绍AdaBoost算法；
介绍梯度下降，随机梯度下降
../深度学习/梯度下降法
写出逻辑斯蒂回归的损失函数；
C++，虚函数，虚析构函数。

2019 美团 AI - NLP 提前批

2019美团AI算法提前批面试经验笔经面经牛客网

一面（NLP平台）

论文/项目相关

意图识别数据怎么标注
怎么样做实体抽取
怎样进行 aspect-level 情感分析
模型中增强学习的 reward 如何设计的；为什么这样设计

一面（广告平台）

论文/项目相关

seq2seq 中 scheduled sampling 如何做的
RL部分训练过程中数据集如何构造
如何防止过拟合，你都采用了哪些方法，还有哪些你没有用到的方法
深度学习/正则化
【编程题】给定整数n，求离根号n最近的整数。
二分查找最优解模板

二面（广告）

论文/项目相关

RL + Seq2seq相关问题
- Seq2seq怎样和RL结合，这里的action与state都是什么
- 如何设计reward，为什么选取这样的reward
- 具体训练流程是怎样的

深度学习相关

BiLSTM 相比 LSTM有哪些 case 上的提升
Attention 是如何加的取得了哪些效果的提升
能介绍几个传统的机器学习模型吗，列举了：决策树，SVM, RF等
- 具体说明一下决策树如何划分，写出相应的公式
- 具体解释一下RF
【编程题】类似求一个旋转数组的拐点位置
二分查找；153. 寻找旋转排序数组中的最小值 - LeetCode

拼多多 180722 笔试

共 4 道编程题

1. 数组中的最长山谷

问题描述：LeetCode 845. 数组中的最长山脉
原题是找山脉，这里改成了山谷
示例：
    输入：
        [4,3,2,5,3,1,4,8]
    输出：
        5
    说明：
        [5,3,1,4,8]
“坑”点说明
输入就是字符串 "[4,3,2,5,3,1,4,8]" 包括括号和标点
问题是，直接返回 0 也有 20% 的正确率，导致我一直没想到是输入上的问题，直到最后都卡在 20%
建议所有需要处理字符串的问题，都使用 Python，这里只要 A = eval(input()) 就完事了；而 C++ 如果不熟悉 STL 的话，处理输入都比题目本身难了
思路：暴力枚举；看代码更直观
C++ 代码 [code]（没做输入处理）

2. 字符串构造

问题描述

一个长串由一个字串循环构成，即 s[i]=t[i%n]，比如 "abcabc" 由 "abc" 构成

注意："abcabcab" 也是由 "abc" 构成的，答题时没注意这个又只过了一部分

*建议使用 Python 解决字符串相关问题

思路：暴力枚举前缀
Python 代码 [code]

3. 到达指定位置

题目描述：Leetcode 754. 到达终点数字
数学题
思路：一道乐视网的面试题，求解答？ - 知乎
C++ 代码 [code]

4. 靓号

问题描述

A 国的手机号码由且仅由 N 位十进制数(0-9)组成，可以有前导 0，比如 000123456。一个手机号码中至少有 K 位数相同则被定义为靓号（不要求连续）。
如果想把自己的手机号修改为一个靓号，修改一个数字的金额为新数字与旧数字之间的差的绝对值，比如 1 修改为 6 或 6 修改为 1 都要花 5 块钱。
求对给定手机号，修改为靓号最少要花的钱数以及新的号码（如果有多个，输出字典序最小的）。

输入：
    第一行包含两个整数 N 和 K，分别表示 手机号码的位数和靓号要求的位数
    第二行为 N 个数字，数字之间没有空白符

    数据范围 2 <= K <= N <= 10000

示例：
    输入：
        6 5
        785785
    输出：
        4
        777577
    说明: 777577 比 777775 字典序小

思路：
统计每个数字出现次数counter，以每个数字为基准，按照与基准差值对counter排序，优先替换差值小的数字；关于字典序的问题，如果替换的数比基准大则从前向后替换，如果替换的数比基准大，则从后向前替换，得到的就是字典序最小的字符串，时间复杂度O(n)
拼多多算法岗笔试python解决方案笔经面经牛客网
TODO 目前还没看到完全 AC 的代码

最后更新于5年前