微软亚洲研究院实习面试总结［转］

这篇文章是我应聘微软亚洲研究院（MSRA）暑期实习的“面经”，由于二位面试官都没有要求我对面试过程保密，因此我在这儿写出来，但我不想写成纯面经，于是标题后又多了个“总结”。另外，我没去北京，所以两次“面试”都不是面对面的面试。

上上上周五，我直接把简历投给了MSRA创新工程组（Innovation Engineering Group）的邹欣老师，邹老师很快就安排了面试，正因为太快了所以我错过了——投简历的当天下午就安排了面试，但我去K歌了……由于第二天是周末，所以一面推迟到下个星期的星期一。

第一轮的面试官居然是Vczh，惊讶了一下。一面是聊天的形式，结果聊到了school days……用Vczh的话说就是“反正面试也就是想摸清楚对方的底细而已，形式都是不重要的，啊哈哈哈”。Vczh对 Functional Programming 也很感兴趣，所以我们首先聊了这方面的话题，比如问我用FP做过什么，有没有折腾过 Church number 之类的，从Haskell聊到LINQ，Vczh还展示了他在SQL Server组工作时写的代码。然后Vczh就开始介绍他们现在正在做的项目。之后Vczh说Feedback已发出，充分肯定了我的编程能力和passion，接下来就开始闲扯了，北京烤鸭啊、潮汕牛肉丸啊之类的……总的来说，一面是在轻松加愉快中度过了~

一天之后，另一位面试官打电话跟我约了时间，第二天2点，电话很准时地打了过来，开始了第二次面试。我迄今一共参加过5次面试（百度3次，微软2次），这次面试是我最紧张的一次，过后回想起来，也是水平最高的一次，所以在这里详细地说一说。

简单地寒暄之后，面试官首先让我做个自我介绍，说说自己的优缺点。我说自己最大的优势是就是热情和兴趣，Software Development是我愿意做一辈子的事业，并且基础好、基本功扎实；劣势就是缺乏工程经验，没有开发较大型软件经历。

尽管如此，面试官还是让我介绍一下自己做过的最满意的软件，我就简单介绍自己写过的一个非常mini的操作系统。面试官问我实现了什么功能，有什么不满意的地方，如果以后继续开发的话会从哪些方面改进。答曰，这个mini OS非常简单，只实现了引导启动、进入保护模式、多进程、TTY和一个naive的文件系统；不满意的地方就是内存和文件的管理太不灵活，虽然能实现多个进程同时运行，但进程的添加是写死在代码里，不能动态添加和退出，而文件虽然能动态的添加，但只能添加固定大小的文件；如果以后改进，会首先从内存管理入手，增加动态添加进程的功能。（有个小细节就是，面试官还问了我这个mini OS的引导过程，百度二面的面试官也问了我同样的问题~）

既然说到操作系统，面试官接着又问了个底层的问题：一个程序，访问函数中某个变量时，操作系统做了什么事情？我的第一反应是这个变量是存在可执行文件中，所以在访问这个变量的地址时，如果相应的页面加载到内存中了就可以直接访问，否则去交换区里头找；如果连交换区看里都没有，就上硬盘里找……说到这我才意识到，面试官问的是函数中的变量，即局部变量！刚才说的都是错的！哎哟我紧张得要命，赶紧解释说不好意思，刚才说错了……面试官很nice地说没关系，把你知道的说出来就行。我松了口气，把C语言运行时函数调用引起的栈帧变化解释了一下，访问局部变量就是访问fp加上相应偏移的地址。

面试官没有纠着我的错误，反而顺着问下去：刚才你说到页错误和交换区，那么操作系统如何处理页错误的呢？交换区的作用是什么？我说有两种情况会引起页错误，一种是访问不存在的页面、一种是对只读页面执行写操作，刚才说的页错误是缺页错误，就是第一种情况。这种情况下，被访问的内存地址会被写入CPU的寄存器中（CR2），操作系统可以访问这个寄存器从而知道引起缺页错误的内存地址，然后在交换区和硬盘中寻找相应的页面。而交换区的作用是利用局部性原理，存放***作系统置换出来的页面，在物理内存紧缺的时候，某些久不使用的页面就会被交换到交换区，这些页面仍然可能在将来被使用，放在交换区中可以更快地被找到。

接下来的阶段，面试提出两个问题，并让我给出解决方案（中间有个小插曲，面试官一度听不清我说话，我更紧张了-0-，只好去阳台，所以后面的面试我一直坐在阳台的地上……）。

第一个问题与内存分配相关。面试官先问我会不会C和C++，我说必须会啊……然后问new和malloc的区别。我说它们的一个主要区别是用new来为自定义类型对象申请空间时，会自动调用默认构造函数，但malloc只是单纯的分配内存，不会执行默认构造函数。面试官说好，现在让你设计一个带有alignment功能的malloc，申请内存的时候严格按照8byte对齐，你会怎么做？我说可以用批发——零售的方式来实现这个功能，即先申请一大块内存，然后遇到申请的时候以8byte为单位分配出去，而这一大块内存用空闲链表管理。面试官问那你设计的这个malloc系统只能管理固定的对齐度是吗，我说是。

然后面试官加深了难度：如果存在不同对齐度的分配要求，该如何做？我问对齐度是不是都是2次幂，面试官说可以有这个假设。想了一下，内存管理、2次幂对齐度，就联想到伙伴系统，我说可以采取与伙伴系统类似的数据结构来管理内存，将内存区域依照不同的对齐度分组，比如说2byte对齐的region用一个链表管理，4byte对齐的region用另一个链表管理，然后遇到内存申请的时候就到相应对齐度的链表中寻找空闲区，如果相应链表没有足够的空间，可以从更高对齐度的链表中取出region然后分裂、也可以从更低对齐度的链表中取出两个region然后合并。用这种方式可以实现不同对齐度的malloc。随后我反问一个问题，问面试官这个对齐malloc的问题是凭空想出来的，还是实际开发中遇到的，面试官说在开发中确实有这种需求，为了提高***命中率、减少缺页错误，有时候会按照对齐的方式申请内存。

紧接着，面试官提出第二个问题，也是面试的最后一个问题：在一个二维平面上有一些点，用一个多边形把这些点全部围起来，可以把二维平面看成一块木板，点看成钉在木板上的钉子，包围的方式就像用胶箍去围木板上的钉子一样，问如何求解这个多边形？。我一听，一个计算机图形学的问题，直接命中我盲区……

我说给我想一想，然后在纸上乱画各种点，然后发现无论是什么情况，这些点之中最上、最下、最左和最右的四个点总是会与胶箍接触，面试官立即肯定了我的“发现”。那么将这4个点连在一起会形成一个四边形，进一步，这4个点会将四边形以外的区域分成4个部分：

四边形以内的点可以不用考虑，因为肯定会被胶箍围起来，关键是如何扩张这个四边形，让它像胶箍一样围住外面的点。所以，问题归约成如何扩张U（最上边的点）和L（最左边的点）之间的直线，让它们围住区域1所有的点。说到这，面试官问我怎么让它围住这些点？我当时唯一能想到的方法就是……枚举。那么接下来的问题就是：怎么枚举？怎么是否满足胶箍条件？

枚举的以UL为底、区域1的点为顶点的所有多边形，其中肯定有一个是满足胶箍条件。而不满足条件的多边形有两种：一种是没有围住所有点；另一种是围住所有点了，但是与胶箍围成的多边形不一样。我觉得，前一种情况，比如如果枚举完所有可能的四边形都不能围住所有点，那么胶箍围成的多边形边数一点大于4；而后一种情况很可能出现凹多边形的，那么此时的边数会大于胶箍多边形。基于这个假设，我提出按边数从少到多的顺序，枚举四边形外所有点与U,L两点形成的所有多边形的解答。就是说，先枚举所有三角形、再枚举所有四边形、然后枚举所有五边形……按照这个顺序，一旦遇到一个能把所有点都围起来的多边形，这个多边形一定与胶箍围成的多边形是一样的。

面试官接着问最坏情况下，这个算法的复杂度是多少。我跪了啊！最坏情况就是所有点都在四边形的外边，这样的话要计算所有多边形的排列数，还要把它们加起来，我说这个数列我不会求和-0- 面试官就让我说个近似，我说是阶乘级的。然后，然后就没有然后了……

这次面试的时间是1小时15分钟，说得很详细，因为印象很深刻。当时刚放下电话发现手在发抖~~~面试过程中多次出现说话不利索的情况= =

一周之后的星期一，Vczh告诉我邹欣老师已经批了我的intern request；又过了一周，还是星期一，收到了HR姐姐的intern offer。所以星期一真是我的幸运日啊~

讲完了面试经历，总结开始~首先是简历。

我的简历是在李樾学长的悉心指导下完成的，在此特别鸣谢:-p。非常建议在应聘一些比较特别的公司的时候，专门为这家公司准备一份简历。可以通过各种渠道（主要是互联网）先了解公司的文化、需要什么样的人才，然后在简历里写上自己符合公司需求的优势。

写在简历上的东西宁缺勿滥。建议只写必要的东西，而不是堆彻。所谓必要的东西，就是你认为最能吸引招聘者的东西，或者说比较特别的东西。当然具体还要视个人情况而定，比如某一类软件做了很多个（如编译器），可以都写出来，突出优势。简历上肯定有一些东西是做了比较久的，在面试之前一定要复习一遍，最好做到被面试官问起相关知识都能够流利回答的程度。

IT公司面试一个人主要考察他/她的能力，或者说专业技能（除此之外可能还包括性格、道德等），当然如果招收的是实习生，那么应聘者的潜力占的比重会多一些，但招聘仍然以了解应聘者的能力为主。那么公司会如何考察一个应聘者、一个程序员的能力呢？面试官会通过纸面上看得到的能力和纸面上看不到的能力两方面了解应聘者。

所谓“纸面上看得到的能力”，就是能写在简历上的东西，更准确的说是应聘者的积累。做过一个大型软件、看过100本书、获得的奖项，这些都是积累。对于程序员而言，能够吸引公司的积累包括：

工程经验（GitHub）：对于找工作的人，拥有丰富的工程经验是莫大的优势。这也是我目前最欠缺的。所谓实践出真知，在软件这个行业，确实有太多知识，如果你没有实践过，是永远学不会的。开发大型软件的经验尤其如此。Linus说“Word is cheap, just show me your code”，某种程度上说，没有比代码更好的简历了，你的技术水平将在代码中显露无遗。所以越来越多的公司甚至要求应聘者提供他们的Github页面。

读过的书（豆瓣）：一个勤思考的人如果遇到一本好书，那他将会进步得飞快。虽然有许多知识必须经过实践才能学会，但看书绝对是增长知识几乎最快的方法。这个行业技术近乎瞬息万变，唯有不断地学习才能适应。一个爱读书的程序员绝不会太差，因为好读书这本身就是一种上进的表现。另一方面，程序员们是脑力劳动者，这决定了只有不断思考的人才能站在行业的尖端（仅从技术上而言），读书恰恰能为思考提供巨大的助力。

技术博客：再一次，我强调写技术博客的好处。写博客不仅能促使人更成熟地思考，在面试的时候，一个记录了思考点滴的价值博客将会赢得面试官极大的青睐。

Stackoverflow：这个趋势在国内还不是特别明显，但是也已经有势头了：一个高reputation的Stackoverflow账号也能成为求职的砝码哦，不信请访问http://careers.stackoverflow.com/。之所以产生这种现象，是因为Stackoverflow这种社区维护得很好，大家都自觉的过滤那些“水帖”，久而久之，良性循环，只有真正有价值、对他人有帮助的Answer和Question才会获得大家的votes。

说到底，积累是应聘者能力最直接的体现，如果在求职（或求实习）的过程中能用自己的积累去打动招聘者，那么在面试之前，就已经有很大的把握了。

除去那些已经功成名就的人，大多数人求职的时候还是要经历面试的（当然也有例外，传闻Guido van Rossum老爹去Google找工作的时候只在简历上写了一句“I wrote Python”，结果面到第十轮Google才知道这句话的意思……）。面试是让面试官了解应聘者“纸面上看不到的能力”的过程。所谓“纸面上看不到的能力”，就是不那么直观的、需要交谈才能了解到的能力。基本的包括与简历相关的内容（真实性）、基本功、分析和解决问题的能力、编码能力（手写代码），进一步的还有反应速度、创新思维、交流能力等等等等。一次好的面试，面试官应该能让面试者尽可能全面地展现这些能力，这就是为什么我觉得MSRA的二面是一次好的面试，因为面试官在不多的时间里考察了基本功、分析和解决问题的能力，这些能力写在纸上都是苍白的，但却能在直接的交谈中展现。MSRA对实习生的要求没那么高，但我想如果是招聘FTE，那么我所提到的这些能力都有可能会被面试官考察。

说到面试，面试也是需要技巧的，我觉得最大的技巧就是尽可能的展现自己。面试官问1，尽量说到3；如果问到一个问题自己实在想不出来，千万不要慌，因为不会很正常。这种情况下就想到多少说多少，总之不要放弃思考。面试官肯定也清楚他问的问题有难度，所以他期望的不是面试者给出正确的答案，而是考察面试者分析问题的能力，以及思路是否清晰。

关于MSRA招人的标准，大家都知道是“编程好，数学好，态度好”的三好学生，但我觉得孔子有句话也许能更准确回答这个问题，“知之者不如好之者，好之者不如乐之者”。遗憾的是，成为好之者和乐之者却不能强求。

最后，对 Computer Science 和 Software Engineering 怀有热情的各位，如果不满足自己现在的环境，千万不要被束缚，请到一个合适的地方去追寻你们的梦想吧！！！