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面试中沉着冷静，展现个性和风采！