字节跳动AI Lab面试经过

作者 Lucyyang 日期 2020-04-12
CS
字节跳动AI Lab面试经过

由于决定去读博士,所以大学这么几年并没有参与多少公司的面试,加上最近的一次一共只有三次实习生的面试。如果之后真的去读博的话,我还会很希望能去做几段不错的实习。作为一个可可爱爱又很能bb项目的妹子(好像只要不涉及coding的面试都发挥很好),阻拦我和tech公司之间的就只有手撕算法题目啦QAQ。

尤其是2019年的2月,参加完Google AI Winter Camp,肝了四天和队友拿下了Best Project,拿到了只需一轮的电话面试机会,结果没准备好一紧张就直接送了人头,而我的队友们都顺顺利利进入实习去吃GG的美食了QAQ。虽然后面一直安慰自己,我是EE出身,他们是CS出身,自己这样已经很不容易啦之类的,但是无奈人家公司不看你的出身背景啊orz。Anyway,只能决心努力补上差距了,不然以后都没法实习赚小钱钱玩了!

那么再说一说最近一次(3月20日)的字节跳动AI Lab的面试经过,由于是实习生面试,一共只有两轮,每次大约45min。先说下最后的结果:最后一位面试官在我面试完和我说想给我转到FPGA方面,因为他们组主要搞GPU,不过也是一个大组的,统属于AL Lab System组。当时我觉得可能是我面试表现太菜了叭不想要我,回去抱着昂一顿哭诉。不过3月26日HR给我打电话说我通过了前两轮的技术面试进行了HR面,然后到了晚上又一个HR给我打电话,说面试官想要给我转FPGA方面,然后希望重新再面2轮,所以下次面试就是4月7日啦!好吧,就当是去积累经验啦。

第一轮面试

第一轮面试感觉形式有点点奇怪,上来先让我自我介绍了下,接着聊了下我印象最深刻的项目,我给他稍微吐槽了下研究生期间的做的东西。大约花了10-15min左右。接着开始出题了:

假如每个字母代表一个8bit的信息,我想要传a-z26组信息,但是不直接传信息,而是传递经过随机编码的信息,例如{a, a^b, xyz...}。那么1.什么情况下是有解的?2.如果转换为矩阵的形式,复杂度为多少?

一眼看到这题有点傻,怎么和我想象的coding不太一样啊,不过面试官很好,非常耐心的引导我思考。他首先给我举了只有abc的情况(注意以后自己分析问题也要从最简单的例子开始),假如我们传输的情况是{a, b, c},那么就一定有解;如果传{a, a^b, abc}也有解。这个时候我想到了是类似高斯消元的做法:将传输的信息写成矩阵形式,然后根据高斯消元的方法化简到上三角,然后最后每一行都对应的一个接。如果矩阵的秩小于26,此时我们无法求解全部信息。一个帮助理解矩阵的秩的知乎回答

接着我们开始分析求解这个矩阵的复杂度,面试官降这个步骤划分为两步,第一步是将矩阵划为上三角的形式,第二步是在上三角的基础上求解最终答案。我们先分析的是第二步的复杂度,对于最坏情况(第一行全为1),假设我们其他行都已求出了结果,那么该行需要和其他所有行都进行求和,该行的计算复杂度为O(N),N代表行数,既传递的元祖个数。那么一共要求解N行,所以第二步的时间复杂度上限是O(N^2)。

接着分析第一步的复杂度,面试的时候由于时间关系,只分析到了这一步。

高斯消元算法介绍

第二轮面试

第二个面试官先问了下我最近在学什么,我给他稍微bb了下LLVM,然后他好像不是很了解这个,就直接上来做题了。

题目:有一组螺丝和螺母,螺丝相互之间不能比较大小,螺母相互之间也不能比较大小。但螺丝和螺母之间可以比较,即我们可以拿任意一个螺丝和螺母进行匹配,然后有大了/小了/正好三种可能,每个螺丝只有唯一匹配的螺母。请返回每个螺丝对应的螺母。

先和面试官讨论了下,这道题可以先拿出一个螺母,然后根据这个螺母把螺丝分成两部分,而这个螺母对应的螺丝也可以将螺母分成两部分,不听做下去,就能解决这个排列问题了。整个过程就很是QuickSort,不过面试的时候出了点问题,没有写完代码。感觉面试时候只能发挥60%写代码的能力,如果平时有地方有点疑惑没搞懂,那面试遇到这个问题是一定会挂。哎,还是得加强平时的练习,下面是我后面补上的解法,以供参考。

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
using namespace std;
void vec_print(const vector<int>& L){
for(auto i:L){
cout<<i<<" ";
}
}
int partition(vector<int>& LS, vector<int>& LM, int left, int right) {
int pivot = LM[right];
int pos = left;
int LS_pivot_pos = 0;
// 根据螺母处理螺丝的情况
for(int i = left; i <= right; i++){
if(LS[i] < pivot){
swap(LS[i], LS[pos]);
pos++;
}
if(LS[i] == pivot) // 必须放在swap的后面,这样才能保证获得经过交换后的LS中pivot的位置
LS_pivot_pos = i;
}
swap(LS[LS_pivot_pos],LS[pos]);
LS_pivot_pos = pos;
//根据螺丝处理螺母的情况
pivot = LS[LS_pivot_pos];
pos = left;
for(int i = left; i <= right; i++){
if(LM[i] <= pivot) { // 由于pivot是LM最后一个,因此会直接swap到分界点
swap(LM[i],LM[pos]);
pos++;
}
}
//螺丝和螺母的pivot停在的相对位置是一样的
return LS_pivot_pos;
}
void quicksort(vector<int>& LS, vector<int>& LM, int left, int right) {
if(left < right){ //注意判断啊
int pi = partition(LS, LM, left, right);
quicksort(LS, LM, left, pi-1);
quicksort(LS, LM, pi+1, right);
}
}
int main(){
vector<int> LS = {4,5,6,7,8,1,2,3,9,10};
vector<int> LM = {3,2,1,8,6,7,5,4,10,9};
int left = 0;
int right = LS.size()-1;
quicksort(LS, LM, left, right);
vec_print(LS);
cout<<endl;
vec_print(LM);
return 0;
}

HR面试

感觉这两轮面的都不是很好,但是很意外接到了HR面试,自己也很惊讶。主要问了下我的实验室情况,性格,印象最深刻的事情,身边的同学去了哪里,多久能入职,是偏好工程还是研究之类的,大约表现出比较想去我很坚强能扛得住打击的样子就好了吧。

第三轮面试

这次面试是4月7日了,因为target的岗位是FPGA加速之类的,所以基本都在问我和FPGA相关的经历。面试官先让我介绍了在微软的实习,然后对我的AES硬件实现比较感兴趣。接着问我是否了解跨时钟域的问题,我和他说了快慢时钟时处理方法,以及FIFO处理还有握手信号。但实际情况中,我好像一直没遇到跨时钟域的问题。放几张之前总结的跨时钟域的问题:

快慢时钟1 快慢时钟2 快慢时钟3

接着面试官又问了我如何用verilog实现一个FIFO,其实我已经很久不写verilog了,感觉有种淡淡的尴尬。然后我就开始和他说有8bit输入信号,8bit输出信号,面试官提示到还有读写信号,然后我又想起来还有full和empty指示信号。接着面试官问我用什么去存储,然后我说register或者memory,面试官表示赞同并说一般用memory。接着问题就转到了如何去实现full和empty指示,面试官和我主要解释了下其实读写是两个指针指向了memory地址,让我根据这个去判断。我最开始脑子一抽,考虑说如果是连续地址,可以直接判断指针指向的地址。我估计面试官听了想打人...,然后他提示我说读写有时候会同步做,然后我想起用cnt去计算,如果是写,就++,读就--。然后这个基本就是正常思路了,面试官又专门给我讲了下具体实现,其实会用5位去表示深度为16的FIFO,这样10000时最高位就是表示为full,我这个时候才记起是有这么个用法,尴尬。不过面试官也认可了我的做法,基本思路还是比较相似的。

然后基本问题就差不多了,面试官问了下我的兴趣,问了我是否了解FPGA加速AI相关的框架,我尴尬的表示不太了解,他推荐我去学下NVDLA,是Nivida推出的比较完善的硬件加速开源框架。然后夸了下我成绩不错,素质挺好的,而且有一些算法上的经验,LSTM,GRU什么的,就是后面要选好自己想走的路。这样今天上午的第一轮面试就差不多了。

第四轮面试

没想到遇到了从MSRA跳到头条的面试官,之前也是做FPGA在云上的运用,并且还认识我在MSRA的mentor果,颇有点点尴尬啊。面试官还是先聊了我在MSRA的实习,主要考了我NFA和DFA的区别,NFA在软件上实现有什么问题,DFA实现有什么问题。NFA主要是状态不确定,同一个时刻可以有多个状态,DFA问题是状态数量爆炸,这里我有点尴尬了。我最开始说DFA状态太多,然后面试官否定了,然后我就想不太出来了,后来发现是一个意思,唉。

接着问了我项目的问题,问我是否有有过时序优化的经历,我只能尴尬的表示没有。后面又和他聊了做AES时进行面积优化的问题。第四轮面试时间比较短,只有30min,而且感觉面试官非常平和,话不是很多,但人很聪明,总结的很好。我都没想到我的FPGA的经历可以总结为主要是在安全方面的实现。

Anyway,感觉MSRA有点下滑啊,人员真的是纷纷外跳,本来做FPGA的也不多,现在感觉基本都是搞CS的人做这个了。

第五轮面试

一个实习生面试快被我面成FTE了...

感觉第五面加面应该是第四轮面的时候,没来得及写verilog代码,只在BB了,所以那个leader让加面一轮coding。这次面了verilog和C++,感觉结果还不错。Verilog题目主要是让我实现了一个RAM,面试官挺好的,直接给了我输入输出接口,然后就很简单的分别写了读写逻辑,期间忘了memory的写法,面试给补全了,写read逻辑的时候typo用了阻塞赋值被指出来了。然后我很尴尬的表示我上一次写verilog是17年了。。。写完这道,面试官又出了一个问如何用组合逻辑找到第一个为1的地位信号,我用了一个非常暴力的if else判断写的。然后面试官问我用过for没,我说没有,面试官表示哦那好吧就这样吧。

接着考我C++,问了leetcode 43的接雨水问题,然后我先说了个O(N^2)做法,面试官听了表示很开心,直接让我先写了。然后大概写了一小会写完了,发现运行不出来,原来头文件没加,加完就没问题了。之后又和面试官讨论了下O(N)做法,面试官表示这一共才花了30min,有点太短了,得再bb几句。顺便告诉我这次结果肯定给过,面的挺好的,然后让我讲讲MSRA实习经历。然后我就bbb了半天,然后面试官听到了状态机这个词,就非常开心,又给我出了一道状态机相关的题目,然后我没想出来,想到了大概方法,面试官给我解释了下,其实也没听太懂。。。。不过感觉这个主要是用来凑时间的问题,之后面试官就和我愉快的88了。

希望能一切顺利啊!

TimeLine

3月14日: 投递

3月17日: HR约面试 (注意没准备好其实可以推)

3月20日: 面试

3月26日: HR面试

3月26日: 约了4月7日的面试

4月07日:两轮线上面试

4月08日:接到HR电话,说想再加一轮coding面试

4月12日:完成coding面试

4月13日:HR电话表示面试通过,接到offer