MSRA面试总结

注:以下内容纯凭记忆,由于已经过去一个多月,不保证准确性。由于面试前没有签保密协议,本文透露了比较多的细节,如果有不合适的内容,请联系 bojieli AT gmail.com。

本来是想稳稳地保研,在创业团队好好干的,没想去 MSRA……因此直到申请截止前几天,我才从班主任那里知道这个消息,班主任说有个“微软小学者”奖,5000块钱呢,我想这么多奖学金肯定要啊,就用一天晚上用 MS Word 赶写了两页 Resume,第二天去教学秘书处开成绩单,比 deadline 晚一天提交了申请。后来才知道这个“微软小学者”跟“实验班”在某种程度上是绑在一起的,不过那个奖学金目前还没有得到任何消息。

根据邮件收件人列表,大概有67人报名微软实验班。面试时间是下午。面试前一个星期左右,西区的一位老师联系我,说有一位叫马毅的研究员,很牛,做图像的,想从少院招一个学生。他说我的项目经历和动手能力不错,但数学成绩不好,担心我能不能做得来,可以给我一个单独面试的机会。他说不 care 你的 overall GPA,比较 care 的是数学课程和专业课程的成绩。他让我看马毅博士的一篇代表作,不仅要看懂,还要理解其精髓。我回来一看,是把一个矩阵分解成一个稀疏矩阵和一个低秩矩阵之和的通用算法,可以用于图像去噪、视频监控等。就只看懂这么多,中间那些矩阵的复杂推导是一点也看不懂。我就觉得这个机会还是留给数学专业的同学吧。

由于知道面试是下午,面试前一天我熬得比较晚,手机又是静音,中午爬起来就发现上午有那个老师的一个未接来电,打过去一问才知道我错过了单独面试的机会……下午冒着雨,去西区科技实验楼面试。面试是单人单间,跟被请喝茶差不多,没有固定的时间限制,事情交代清楚了就可以出来了。

第一个面试的是系统与网络组的张老师(也是我现在的 mentor)。首先是自我介绍,然后他就抓住我数学成绩不好的小辫子开始问(都怪我当时没刷吉米多维奇)。我在简历上写了不少课外做的项目和课程项目,他就问我这些项目中感觉最有挑战的一个,我心想这些玩意有多少挑战呢?于是就随便说了说 blog.ustc.edu.cn 开发过程中,构造 PHP Sandbox 的几种尝试,以及现在感觉不合理的地方。(这个不合理的地方现在还没改,所以大家装插件经常会遇到问题)感觉分量有点不够,就补充了做实时磁盘文件系统课程实验的时候尝试的几种优化(嗯,这个是郭家华写的代码,所以也不是我的功劳),总结得到“真理”:在做系统的时候要找到瓶颈进行优化,如果选择了错误的部分则很麻烦且效果不好。

然后张老师就跟我谈做研究是什么感觉,在 MSRA 读博是什么样,等等。接着他问我哪门专业课学得好,我当时只回忆起了操作系统、编译原理(面试根本没准备)。他说操作系统,好,讲讲 Linux 的内存管理机制。《Linux 内核源代码导读》是一年前上的了……幸亏前些天读了一篇“手把手教你写 ramdisk” 的文章,就先说说用户地址空间和内核地址空间,高端内存的临时内存映射和永久内存映射,动态内存分配的伙伴系统和 slab 算法。面试官接着问我分页机制,我就把计算机组成原理上学的东西大概说了一下。他问了个很奇怪的问题,分页是硬件还是操作系统管理?我觉得是硬件查询页表,操作系统维护(修改)页表。他问我操作系统什么时候需要查询页表?除了缺页异常和修改页表以外我没想到其他的情形,面试官对我的答案不置可否。

张老师拿来纸笔,让我写个 bcopy 实现 memcpy 的功能。我首先写了个最简单的版本,随即改成了4字节一组的版本。他说我的程序里有 bug,我这才想到首尾不是4的倍数(即内存没有对齐)时会有问题,于是就在首尾加上了特殊处理。他又说我的程序会 segmentation fault,我百思不得其解,他最后告诉我,如果目标地址没有对齐,4字节复制就成了非对齐访问。我在32位 x86 上写过非对齐访问的程序,没有 segmentation fault 啊。他说你回去试一试,一定会 segmentation fault。这场面试就这样结束了……要是当初说学得好的课程时,说的是计算机网络而不是操作系统,估计回答起来就不这么吃力了……

画外音:面试全部结束后在LUG活动室的32位 Pentium 4 上做了个实验,4字节非对齐读写都不会 segmentation fault,而且结果是正确的。郭家华说,即使总线不允许非对齐访问,CPU也没做特殊处理,出现的也应该是 bus fault 而不是 segmentation fault。不过由于LUG要贴海报,就没回去跟面试官探讨。

从第一场面试出来,等了五分钟,工作人员就把我叫到了第二个面试官的房间里。面试官是做计算机图形学的童老师。他看了我的简历,对 Robogame 盲人阅读器和 freeshell 比较感兴趣。在聊 freeshell 的时候,我提到 OpenVZ 可以实现热迁移,他就问我热迁移的原理,我刚好看过一本云计算的书就答出来了,他问我是怎么想出来的,我说这个不是我想的,是书上的,而且 OpenVZ 也是现成的工具,我只是调用了它的API。他的结论是,“不说你这些项目结果怎么样,单是主动在课外去做这一点,就能说明很多问题”。

童老师接着问我,是喜欢做偏工程的研究还是偏理论的研究(具体的问法不记得了)。我当时答的是,比较喜欢通过理论推导和系统方法得到的结果,不太喜欢通过调参数“凑”出来的结果,顺便扯了扯马毅博士的论文。然后他表示没什么可问的了,我就请教了他三维重建方面的问题(不过他说的那个算法我出来就忘掉了,白问了)。这场面试比较快,20分钟就结束了,至少比第一场面试短一半。

过了几天,搞数据挖掘的谢研究员(少院校友)跟我邮件要求面试,安排在高性能计算中心,是通过 Skype 视频面试。去了才知道,面试地点是网络中心402,就是LUG每周小聚的地方啊有木有,工作人员则是跟陈张和我一起做 Linux Software Store 的赵聪师兄(怎么这么巧)。言归正传。在自我介绍兼听力试音之后,谢研究员就抓住了我数学成绩不好的小辫子。然后就开始问我简历上写的数据挖掘课程上用 KDDcup 2009 数据做的实验。因为那门课之后再也没碰过数据挖掘,只好硬着头皮编了几句。他肯定听出来了,就让我换个近期做的项目,于是我把 blog 讲了一遍。

谢研究员问我前面两个面试官分别是做什么的,我如实招来。他接着问,你是喜欢做系统研究呢,还是做理论研究呢?好像跟童研究员问的问题差不多。他说看起来我比较喜欢做系统。下面的问题比较狠,如果在系统、计算机图形学和数据挖掘之间选择,你更喜欢哪个呢?其实就我个人而言是比较喜欢人工智能的,在学校的实验室也是做智能机器人的,所以我就说是比较喜欢偏智能方向的,系统也不错。图形学里全是数学,我估计玩不转。他说我的想法比较矛盾,喜欢系统研究,但数据挖掘属于理论研究。20分钟固定时间面试就在矛盾中结束了。

出来的时候,在电梯门口正好遇到一个来参加面试的妹子,她特别紧张,担心被问到跟上次面试不一样的问题,我就安慰她内容都差不多的,跟面对面面试的形式完全一样。似乎紧张会影响人的发挥,我高中的时候本来没想来科大,面试的时候特别放松,结果面试成绩挺好的。这次又是本来没想去微软。也许不准备就是最好的准备……

最后一场面试是张老师实验室的一个台湾人进行的电话面试,我坐在电脑前面,在 collabedit 上现场写代码。心想这个老师真有意思,面对面的时候就让写代码,还给安排了一次专门写代码的面试,而其他面试官都没让写一行代码。面试题是他临时想的,我写程序的时候,他也在写同一个程序。

第一题是不用递归,用 O(1) 的空间复杂度实现二叉树的遍历,二叉树的每个节点有 parent 指针。由于一开始我没想清楚,写了又改,改了又写,中间电话还断了一次,折腾了一个小时才勉强交上去。

第二题是求一个 n*n 的黑白点阵图中,黑色连通片的个数(上下左右相邻视为连通)。我觉得 floodfill 法太简单了,于是就写了个每个点只扫描一次的贪心算法。按照行列顺序扫描,当前方格为黑色时,若左边上边都是黑色,编号相同则复制,编号不同则复制左边的,并增加 merge counter;若左边是黑色或上边是黑色,则复制其编号;不然,新开一个编号。最后的连通片数就是 (分配出去的编号数 - merge counter)。过了好几天我才想清楚,这个算法是错误的,问题出在左边上边均为黑色且编号不同时,无论复制左边的还是上边的编号都不行。如果对编号改用并查集,上述情况下将两个编号合并,以后判断编号相等时从并查集里找,好像就没有问题了。

这么简单的两道题,一共刚超过100行代码,竟然耗了1小时45分钟……到底是多年不搞OI,也没参加ACM,老了……当天晚上面试官发邮件(当然是英文)跟我说:我能理解你的基本思路,但程序里有很多 bug,尤其是第二题,不过不要担心,这样两道题本来就不是在短时间内能轻松解决的。

不知怎么的,MSRA 的面试就水水的过了。我觉得要是碰上几个 ACM 大牛,再碰上几个 GPA 神牛,我肯定不会被选中的。人力资源部的人跟我确认 check in 的时间,当时我正在去 LUD(Linux User Dinner)的路上,没听清,她跟我说是“入职”,我想我又不是到微软工作,怎么变成“入职”了?后来才打听到,我们实验班是跟微软实习生一样的编制。

哇……总结超过3000字了。我们实验班的18个人就要开始新的征程了,也祝愿学弟学妹们在来年的MSRA面试中沉着冷静,展现个性和风采!