「面试」商汤科技研究院 - 见习计算机视觉研究员

前言

9.2 晚上突然收到这样一条短信:

????????

回想了一下,我的确在大约十天之前投递了一份简历,但是投过去之后没收到任何反馈,我还以为简历直接挂了。这突然让我去面试,我连啥时候去哪都不知道,这面个毛线。

正要回短信问 HR 什么情况时,我突然想到了什么,打开我的 Gmail 邮箱,果然……

此时我的内心一万匹草泥马奔腾而过,Gmail 我给您跪下了。

看了下时间明天上午 10:00,还好和下午的 MEGVII 不冲突,那就去吧。

基本情况

  • 面试岗位:商汤科技研究院——见习计算机视觉研究员
  • 投递渠道:北邮人论坛邮件投递
  • 面试时间:2019.9.3

一面(30min)

面试官:我看你代码经验挺丰富,先来写个代码题吧

我:好(……)

面试官:写一个计算器,包括加减乘除括号

然后我就假装淡定开始写了,开始回想数据结构大作业,然后开始coding。写的时候还是有点小紧张,仔细思考了一下运算符的优先级,大概十分钟写完了。测试了几组发现左括号处理错了,然后改完似乎没问题了。

面试官试了几组样例都没问题,松了一口气。

(由于商汤是在自己电脑上写,附一下代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

#include <iostream>
#include <string>
#include <stack>
using namespace std;

stack<int> num;
stack<char> opt;

int getval(char c) {
if (c == '(') return 0;
if (c == '+') return 1;
if (c == '-') return 1;
if (c == '*') return 2;
if (c == '/') return 2;
}

int calc(int lhs, int rhs, int nowopt) {
if (nowopt == '+') return lhs + rhs;
if (nowopt == '-') return lhs - rhs;
if (nowopt == '*') return lhs * rhs;
if (nowopt == '/') return lhs / rhs;
}

int main() {
string str;
cin >> str;
int len = str.length();
for (int i = 0; i < len;) {
char c = str[i];
if (c >= '0' && c <= '9') {
int tmp = 0;
while (str[i] >= '0' && str[i] <= '9') {
tmp = tmp * 10 + str[i] - '0';
i++;
}
num.push(tmp);
}
else if (c == '(') {
i++;
opt.push(c);
}
else if (c == ')') {
i++;
while (!opt.empty() && opt.top() != '(') {
int rhs = num.top();
num.pop();
int lhs = num.top();
num.pop();
char nowopt = opt.top();
opt.pop();
num.push(calc(lhs, rhs, nowopt));

}
opt.pop();
}
else {
i++;
int val = getval(c);
while (!opt.empty() && getval(opt.top()) >= val) {
int rhs = num.top();
num.pop();
int lhs = num.top();
num.pop();
char nowopt = opt.top();
opt.pop();
num.push(calc(lhs, rhs, nowopt));
}
opt.push(c);
}
}
while (!opt.empty()) {
int rhs = num.top();
num.pop();
int lhs = num.top();
num.pop();
char nowopt = opt.top();
opt.pop();
num.push(calc(lhs, rhs, nowopt));
}
cout << num.top() << endl;
return 0;
}

面试官:还不错,再来一个,求将一个字符串变成另一个字符串所需的最少操作数,每次操作可以添加或删除一个字符。

思考了一会答案应该是 len(S) + len(T) - 2 * LCS(S, T),其实当时还有点虚不知道对不对,还是硬着头皮写了,面试官跑了几组似乎没问题,就顺利过了。

附一下代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <string>
using namespace std;

const int N = 1005;

char s[N], t[N];
int f[N][N];

int main() {
scanf("%s", s + 1);
scanf("%s", t + 1);
int n = strlen(s + 1), m = strlen(t + 1);
f[0][0] = f[0][1] = f[1][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (s[i] == t[j]) {
f[i][j] = f[i - 1][j - 1] + 1;
}
else {
f[i][j] = max(f[i - 1][j], f[i][j - 1]);
}
}
}
cout << n + m - 2 * f[n][m] << endl;
return 0;
}

写代码的部分应该就到此结束了,然后进入唠嗑环节。

面试官:你高中就搞过信息学竞赛啊,你是哪个学校的?

我:我是山东的,我们学校竞赛不太强,搞的人也不多,大家主要都是自学。

面试官:哇,那我们还是老乡

我:(假装微笑)

面试官:你山东那里的

我:潍坊的,昌邑一中的

面试官:哦……(没听说过)

面试官:那问下项目吧,介绍下你做的这个大创吧

我:blabla…

面试官:这个其实你还可以多挖掘很多信息呀,比如作者之间引用的拓扑关系等等,有很多可以挖掘的点

我:嗯,我看最近唐杰老师的 Aminer 就添加了很多这方面的功能

面试官:你也知道唐杰老师啊

我:听说过听说过

面试官:那再问点深度学习相关的吧,了解 CNN 么

我:了解一点

面试官:简单说下你了解的 CNN 吧

我:大概就是由卷积层、池化层、全连接层组成,卷积层就是一个滤波器在图像上从上到下、从左到右移动,进行卷积运算,池化层比如比较常见的 MAX-POOLING、AVERAGE-POOLING,全连接层就和传统的神经网络类似

面试官:你觉得这种结构有什么好处,比起传统的只有全连接层的神经网络

我:这种形式的网络实现了参数共享,大大减少了参数的数量,而且这种形式更容易捕捉到图片的特征

面试官:说下池化层的作用吧

我:池化层能减小图像的规模,又尽量保留了图片原有的性质

面试官:之后读研还是出国有打算吗

我:打算明年保研吧

面试官:嗯,你基础不错,实习的同时可以考虑联系一下实验室去干点活

我:thx

二面

面完一面被告知二面面试官鸽了,等通知ing

9.5 下午 14:00 又来到了商汤面试,面试官见到我后问我哪个院的,我说计院(警觉),然后面试官表示他也是北邮计院的,很想问一句学长是哪一届的,因为 我发现他头顶已经秃了。

面试官:了解 CNN 吗

我:了解一些

面试官:简单讲一下吧

我:(和上一个面试官问的怎么一样,又复读了一遍)

面试官:OK,如果要你实现以下卷积运算的话,你知道有哪些参数吗?

我:滤波器大小 $f\times f$,填充 $p$,步长 $s$

面试官:那你用代码实现一下吧,输入是一个 $n\times m$ 的图像,然后还有你说这些参数

然后我大概是这样写的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
double calc(img input, img conv, int r, int c) {
double ans = 0.0;
int f = conv.n;
int n = input.n, m = input.m;
for (int i = r; i < r + f; i++) {
for (int j = c; k < c + f; j++) {
if (i >= 0 && i < n && j >= 0 && j < m) {
ans += input[i][j] * conv[i - r][j - c];
}
}
}
return ans;
}

img ConvOperation(img input, img conv, int p, int s) {
img output;
int r = 0;
int n = input.n, m = input.m;
for (int i = -p; i <= n + p - f; i++) {
int s = 0;
for (int j = -p; k <= m + p - f; j++) {
output[r][s++] = calc(input, conv, i, j);
}
r++;
}
return output;
}

面试官:你的 padding 在哪?

我:我默认填充 0 了,所以没有实际进行 padding,在计算卷积的时候特判了一下

面试官:哦……你这个特判倒是还比较巧妙,不过没说填充一定是 0 啊

我:好吧,那如果不是 0 的话,的确需要先对 input 进行 padding

面试官:你这样是以一个格子作为 kernel 的左上角进行卷积对吧,我们一般做的是中心卷积,就是以一个格子为 kernel 中间l

我:好吧,这个我之前没太注意,那这样把循环的上下界改一改就好了

面试官:嗯,有一点就是,你这个 p 一般不作为参数,而是根据 f 算出来的,对吧

我:啊对对

面试官:好,那现在考虑一下,你现在这个 output 是每次 new 出来的吧,如果图像很大的话内存开销会很大,有没有方法减少开销?

这里我还是想了两三分钟,手动画了下使用 $3\times 3$ kernel,padding = 1 的情况,填充过后我要以图像的 $(i,j),1\leq i\leq 3,1\leq j\leq 3$ 为中心进行卷积,而格子 $(0,0)$ 在计算完以 $(1,1)$ 为中心的卷积后就不会再被用到了,因此可以把$(1,1)$的中心卷积填充到格子 $(0,0)$ 中,同理我们只要按照 $(1,1)\to(1,2)\to(1,3)\to(2,1)\to…\to(3,3)$ 的顺序计算这些格子$(i,j)$的中心卷积,然后将结果填入$(i-1,j-1)$格子中即可。

面试官:嗯,那你再想一下时间上还可以加速吗

这里我想了好久,又反复观察了一下,感觉实在是没有能优化的地方。

面试官:可以用上你知道的各种数据结构

然后我就想能否从某个格子对最后 output 的贡献来考虑,因为一个格子会对 $f\times f$ 个卷积有贡献,并且分别出现在 kernel 中的每一个位置。比如说我们的 kernel 是 $[[1,2,3],[4,5,6],[7,8,9]]$,格子$(i,j)$的数字为$x$,那对于 $i-1\leq i’\leq i+1, j-1\leq j’\leq j+1$ 会对这 $f\times f$ 个格子分别贡献 $[[9x, 8x, 7x], [6x, 5x, 4x], [3x, 2x, x]]$,然后我感觉这个东西并不能用数据结构加速……然后就想不下去了,gg

面试官:你知道我们一般用什么硬件来做神经网络吗

我:GPU

面试官:用 GPU 有什么好处知道吗?

我:并行计算吧

面试官:对,所以是不是可以从多线程的角度考虑一下?

我:(说好的数据结构呢),emm,我想想

面试官:有多线程编程的经历吗?

我:没写过(捂脸

这个问题的话,如果我们不考虑刚才的内存优化,那么直接随便分成几部分并行计算就 OK 了。因为内存优化会覆盖掉原始图像中的某些格子,我们需要安排一个合理的顺序。

还是以 $3\times 3$ 为例,我们可以发现,首先我们必须要计算完 $(1,1)$ 的中心卷积,然后才能计算 $(1,2)$、$(2,1)$ 的中心卷积,否则 $(0,1)$、$(1,0)$ 的值覆盖掉会影响 $(1,1)$ 中心卷积的计算。同时我们也可以发现,$(1,2)$ 与 $(2,1)$ 的中心卷积的计算是互不影响的。

这样思路就比较明朗了,这里对于 $n+m-1$ 条 ‘/‘ 方向的对角线来说必须是串行的,只有一条对角线上的所有卷积都计算完之后,才可以计算下一条对角线上的卷积。而同一条对角线上的各个卷积之间计算是互不干扰的,可以用多线程来加速。

面试官:能用代码实现一下吗?

然后我就写了下伪代码:

1
2
3
4
5
6
for (int i = 0; i <= n + m - 2; i++) {
/* 并行计算以下 for 循环 */
for (int j = 0; j <= i; j++) {
calc(j, i - j);
}
}

面试官:这个思路是可以的,不过你这样线程是怎么分配的?你一个线程应该是一直在跑一个程序,可以接收一个输入然后给出输出

我:emm,就所有的线程都运行计算卷积的程序呗,然后就是扔进去一个坐标返回一个卷积值

面试官:这样由于blabla(我也没听懂)可能导致开销还是比较大……

我:好吧,可能是实现上有些困难,这个我不太熟悉

面试官:概率论学的不错?

我:考的分还行……

面试官:有什么熟悉的概率模型吗

我:(深思熟虑半分钟),好像没什么(捂脸),用的比较多的还是高斯分布吧

面试官:知道高斯卷积高斯核吗?算了我估计你应该不知道

我:(……那你还问我干啥),确实不知道

面试官:那换个问题吧,我看你写了个这个单词消除游戏,这里面有什么你认为比较有趣的算法吗?

我:这个主要还是偏工程,基本没什么算法在里面

面试官:诶,我看你这有个大创项目,你在数据挖掘中遇到什么问题了吗?

我:我们还没做到那一步……(这告诉我们没做完的大创不要随便往简历上写)

面试官:那你觉得你这个项目最大的瓶颈在哪

我:(md还没怎么做我怎么知道有什么瓶颈,胡扯了几个)

面试官:我觉得你这些问题都不是瓶颈,应该都比较容易解决

我:好吧

(之后面试官问了一个操作系统中关于 LRU 实现的问题,感觉和面试官不在同一个频道,最后不了了之……反正肯定是减分项了)

后续

拿到了 offer

思前想后还是拒了,主要还是时间的问题

商汤其实时间要求蛮低的了……我说三个月+3天商汤也表示 OK,每天早9晚6,一个小时弹性调节。然而一是因为周三下午又加了节csapp,让我周三就算上班也不得不早退;二是就算可以去三天,可能也只能做一些辅助性的工作,虽然已经比 Momenta 那种号称算法岗实际 C++ 开发的好多了;三是看了身边几个在实习的同学的状态,发现尽管只去三天也没有那么轻松,真的开始工作可能一周下来会很累,总归有一些其他事情还要去做。

拒的时候 HR 小姐姐各种挽留,最后还是拒掉了(我好残忍

希望不要被拉黑啊555,商汤真的是从头到尾体验很好,明年如果有机会还是想来实习的!