太难了！B站2021校招算法岗笔试题剖析（一）

TechFlow-承志

发布于 2022-09-22 14:53:17

9110

发布于 2022-09-22 14:53:17

文章被收录于专栏：TechFlowTechFlow

作者 | 梁唐

出品 | 公众号：Coder梁（ID：Coder_LT）

大家好，我是梁唐。

今天继续和大家聊聊B站2021的校招笔试题，上次我们看了算法题，今天我们来看看选择题。

和之前一样，题目来源于牛客网，感兴趣的同学可以点击阅读原文跳转。

实话说，选择题的难度还不小，有一题老梁还是请教了大佬才搞清楚答案。

第一题

在一个空闲的多核环境下，以下c++代码运行时间为？（精确到秒）

#include <iostream>
#include <future>
#include <thread>
using namespace std::literals::chrono_literals;
void foo(int n) { std::this_thread::sleep_for(n * 1s); }

int main(){
 std::async( std::launch::async, foo, 10 );
 std::async( std::launch::async, foo, 5 );
 return 0;
}

这题老梁就不知道答案，因为C++里面的async函数我没有用过。从名字来看，这是一个异步调用函数。既然是异步函数，那么两个sleep应该是并行的，总体上应该休眠10s，所以我选了B。

但答案是C。

为此，老梁专门请教了群里搞C++的大佬，感谢隔壁的小黑饼为本题提供解答：

future（大佬笔误了）是async调用之后返回的结果，这个结果是线程函数的执行结果。std::async会自动创建一个线程去调用线程函数，它返回一个std::future，这个future中存储了线程函数返回的结果，当我们需要线程函数的结果时，直接从future中获取，非常方便。

由于程序当中我们没有设置变量去接收这个future，所以这个future会被析构。这在C++当中非常常见，称为临时变量析构。关于async函数以及临时变量析构都是一个比较大的话题，这里不做过多解释了，感兴趣的同学可以自行搜索相关内容。

总之由于async返回的结果析构了，所以它必须得等待函数foo执行结束。如此一来，就相当于两个函数串行执行，自然需要的时间就是15s了。

如果我们把代码改一改，改成这样：

auto r1 = std::async( std::launch::async, foo, 10 );
auto r2 = std::async( std::launch::async, foo, 5 );

由于我们有了变量接收，所以不会触发临时变量析构，那么析构将会发生在main函数结束的时候，这样的话两个函数就是并行等待了，那么一共只需要等待10s。

想要把这题答对还是挺难的，需要对C++有比较深入的理解。

第二题

C++中，下面哪个容器不提供resize()操作：

这题比较简单，除了array之外，其他的都是容器。

显然数组是无法resize的，所以选择A。

第三题

对k-means算法以下说法正确是:

这题考察的是机器学习基础，基本的K-means算法的理解。

老实讲我也不太清楚聚类算法的划分标准，所以也不清楚K-means到底属于什么聚类方法，不过我们可以使用排除法。

首先可以排除AD，K-means并不是层次聚类算法，其次K-means算法一定会收敛，所以答案在BC之间。

其中B选项也可以排除，问题在于K-means不一定可以得到最优解，即使确定了K，往往收敛在局部最优解。所以通过排除法答案是C。

第四题

以下哪种方式通常不能帮助解决决策树过拟合:

送分题，只要认真看过决策树的原理，不难看出ABC都是常规的限制模型复杂度以及防止过拟合的方法。

所以答案选D，即使不知道ABC，通过原理分析也可以得出答案。因为对于过拟合的模型来说，增加新特征并不能避免模型对于老特征的过度刻画。

第五题

ROC曲线和AUC常被用来评价一个二值分类器（binary classifier）的优劣。对于模型的ROC曲线，与哪一点越接近，表明该分类器的性能越好？

基础题，需要结合AUC原理来判断。

这是典型的ROC曲线，AUC指的是曲线围成的阴影面积。对于模型来说，AUC越大，说明模型的性能越好。

显然，AUC越大，越接近左上角。即FPR=0，TPR=1的点。

简单解释一下AUC的概念，其中FPR指的是false positive rate，翻译过来即假阳率，TRP指的就是true positive rate，即真正率，有些书里叫做召回率。我们用True表示真，False表示假，Positive表示正样本，Negative表示负样本。

那么TP表示预测正确的正样本，TN表示预测正确的负样本，FP表示预测错误的正样本，FN表示预测错误的负样本。

那么，FPR = \frac {FP}{FP + TN}，TPR=\frac{TP}{TP+FN}。

结合公式我们可以看出，假阳率越高，说明模型把更多的负样本认成了正样本，而召回率越高，说明模型找出了更多的正样本。从曲线我们可以看到，这两者是正相关的。其实很好理解，假阳率越高，说明模型很宽松把更多的负样本当成了正样本。那么必然召回率也就越高。反过来，假阳率越低，说明模型越严格，没有被认出来的正样本也就越多，自然召回率也就越低。

第六题

下面哪个优化算法避免了长期累积梯度所导致的学习率趋向于0的问题

这一题考察的是优化器。

如果熟悉这四种优化器的原理的话，那么很容易选出正确答案是B。

防止有些同学不熟悉，我们简单介绍一下。

首先是Batch SGD，即批量随机梯度下降算法。该算法计算梯度就是批量样本的梯度均值，所以也就没有梯度累计一说，可以排除。

其次是Momentum SGD，momentum即动量，通过给梯度加上动量来减少随机采样带来的动荡。

体现在公式上就是：

\begin{align} v_t &= \gamma v_{t-1} + \eta \nabla_{\theta}J(\theta)\\ \theta_{t+1} &= \theta_t - v_t \end{align}

这里的\gamma 是一个时间衰减的参数，一般设置在0.9左右。我们可以把动量看成是类似惯性的东西，也就是说之前的梯度的值给当前算出来的梯度施加一个惯性，来防止它震荡。显然也不存在由于梯度累计导致趋近于0的问题，所以A排除。

我们再来看C，Adagrad算法的特点是可以对低频的参数做较大的更新，对高频参数做较小的更新。因此对于稀疏数据的表现很好，很好地提升了SGD的鲁棒性。

我们来看下公式：

\begin{align} \theta_{t+1, i} &= \theta_{t, i} - \frac{\eta}{\sqrt{G_{t,ii + \epsilon}}}\cdot g_{t,i} \\ g_{t, i} &= \nabla_{\theta}J(\theta_i) \end{align}

其中g_{t, i} 表示t时刻，参数\theta_i 的梯度。G_t 是一个对角矩阵，G_{t,ii} 表示的是t时刻，参数\theta_i 的梯度平方和。

显然，公式中是有梯度累计的，并且随着梯度的累计，会导致算出来的梯度越来越小，最终趋近于0。也就是说C是拥有这个问题的算法，所以最终只剩下了B。

B选项是RMSProp，它是Adagrad算法的改进版本。改进的内容非常简单，它引入了另外一个参数p，采用了指数衰减平均的方式来淡化过去对于未来的影响。我们用字母r表示累计的梯度，公式可以写成：

\begin{align} r_{t+1} &= p\cdot r + (1-p) g_t^2 \\ \theta_{t+1} &= \theta_{t} - \frac{\eta}{\sqrt{r + \epsilon}} g_t \end{align}

由于我们对过去的累计值做了时间衰减，可以避免长期累计导致梯度趋近于0的问题。所以答案是B。