微软面经

0. 面试之前

参加微软面试其实是个很意外的事情（社招）。

16年12月，偶然收到了一份邮件，名为“Greeting From Microsoft”，大意是在Github上看到了我，目前微软苏州正在招人，问我是否感兴趣。

作为一个菜鸡，收到这种大厂的面试自然是十分兴奋，但是看了下招聘的岗位，并不是很符合我个人目前的技术栈，于是就很客气的回了一封邮件，表明了自己技术栈不符。不过微软的HR直接打了电话过来，本着试一试又不会怀孕的心态，就开始了微软的面试之旅。

1. 电话面

面试的岗位是Bing ADs的研发。跟HR几封邮件往来，确定了电话面的时间。

电话面的是一个SDE2的小姐姐。电话面的形式为Skype会议，需要一台有Skype的电脑，可以在HR的邮件中找到准备环境的内容。面试官会共享一个白板，可能会需要在白板上写代码。手写代码能力，这个是微软面试很看重的一点，几乎每一面，都有让我手写代码的过程。判空，程序边界，又是在手写代码的过程中很看重的一点。

整体面试可以分为两部分：介绍之前的工作、项目经验，做题。之后的每一轮面试，都是同样的形式，所以后面的介绍就以介绍题目为主。

工作、项目经验介绍：很常规的问了之前公司的一些项目，以及是否有一些个人的项目。因为对之前做过的东西非常熟悉，所以这一部分表现还不错。

做题：问了一道Jump Frog的题目。可以直接在LeetCode上搜到这道题，面试的时候稍作了改动。这是道动态规划的题目，由于之前没有想到面试会问DP的问题，所以没有答出来，不过由于项目介绍部分表现的还不错（又或者是微软真的缺人...），小姐姐给了个机会，让我在那天之内把这道题做出来发给她。临时拿出算法导论，看了一遍动态规划，憋了很久最终做了出来。电话面磕磕绊绊的通过了。

2. 一面

由于当时在北京工作，所以现场面试是丹棱街5号微软的楼里面进行的，两个大楼还是很气派的...

吐槽一点，现场面试的邮件中说是会有三到五轮，不过如果最后通过的话，基本都会面满五轮，可怜我按照三轮准备的...

一面还是个小姐姐。只记住了一个问题：给一个只包含正整数的数组，求第一个没有出现的正整数，写代码。

忘记了是否有序，不过可以按照有序、无序都做一遍，还是蛮有意思的。

有序情况下，常规的方法可以遍历一遍数组，O(n)的复杂度，之后又问了有没有什么优化的方法，想到了根据数组长度去判断，不过没有具体想出来怎么做。二分查找应该也可以将复杂度减少到O(n)以下。

3. 二面

二面整体答的比较流畅，所以答地快一些，问的问题也多了一些。

• Q: 一个int型数组，每一个数字都出现了两次，只有一个出现了一次，求出现一次的数字
  A: 从头到尾异或一遍，得到的就是出现一次的数字

• Q: 一个int数组，一个目标值target，求数组中是否有两个数的和是这个target，写代码
  A: 编程之美的原题，先进行排序，然后两个指针，从头和尾分别向中间遍历，然后比较目标值就可以了

• Q: 折纸，每次都是从右向左对折，凹痕为0，凸痕为1，求折n次的时候，折痕组成的10序列
  A: 实际折几下就可以看出规律了，每次展开，左右两侧的折痕是一个取反的关系（PS: 微软纸的质量不错）

• Q: 两个人分100枚金币，A提出方案，B同意则按A的方案分，B不同意则两个人都没有，A的方案是什么
  A: 好吧，五海盗分金币的简化版。面试官说这个是开放性试题，没有标准答案。根据五海盗问题，A可以选择自己拿99枚，B只拿1枚，这时候B只能同意，否则他一枚都拿不到。面试官又说，那么这么分B心里肯定不平衡，他可以不要，然后让A也拿不到...那么情况逆转，B贪到死，A1枚，B99枚...面试官继续说，其实，正常心态，一人一半就好了...WTF，好吧，就当宣扬儒家精神了

4. 三面

• Q: 二叉树，每一个节点存储了指向父节点的指针，现在给了一个节点，求中序遍历这个二叉树时，给出节点的下一个被遍历到的节点是什么
  A: 重点是把下一个节点可能的情况写出来，然后代码尽量没有问题，记得判空就好了，题目不是很难。不过当时略显紧张，把中序遍历都写了出来...把整个面试的时间用的差不多了，导致只问了这一个题目

5. 四面

HR发的邮件里面，说是会有3-5面，所以就按照3面准备了三个问题，对于接下来的面试基本是一脸懵逼的。

不过套路都是一样的，先问项目后做题。

• Q: 一面问题的升级版，不过这次还多了负数和0
  A: 不是冤家不对头，觉得一面这个题答得挺一般的，结果四面上来就是这个...

• Q: 给定两个字符串a和b，求a中的一个最小的子字符串，使之包含b中的所有字符（b中字符可能有重复）
  A: 大概就是用一个辅助的map，对于每一个出现的字符，记录其在数组中出现的下标，所有的都出现一遍之后，就可以根据最大最小的下标，计算出当前子串的长度。遍历一遍之后，即可得到最小的子串。这个题要求写代码，这种方法写出来还是很麻烦的...

6. 五面

五面的面试官是我未来的老板（好像提前透露了我过了面试...）

只有一个问题，平面上给出n个点的坐标，求出这n个点所能组成的最大的多边形的面积，提供可供编程的思路

提供可供变成的思路，算是这个题需要注意的一个点。在面试官的提示下，几经波折也算是想出了解

求面积的话，只需要知道所有凸多边形定点的坐标，然后上半部分相邻两个点围成的多边形的和，减去下半部分相邻两个点围成的多边形的和，就是凸多边形的面积。问题转换成了求凸多边形的顶点

分治法，可以根据横纵坐标最大最小，得到四个点，这四个点可以将未来的凸多边形分成四个部分，每个部分可以采用同样的算法求该部分的顶点

求顶点时，可以将相邻的两个点连线，在这条线上，离该直线距离最远的点，就是凸多边形的顶点之一。重复这一过程，可以把所有的顶点都求出来，进一步就能求出面积

7. 一些总结

最后顺利的拿到了Offer。整体来看，微软的面试还是以问算法为主，不会关注面试者使用的语言，即使是写代码的问题，面试者也可以选择任何自己擅长的语言。手写代码环节，需要考虑到一些边界情况，常见的判空等，而且代码写出来不要有什么编译过不了的问题，日常代码写的多的话，问题不大。

我个人买的第一本技术书籍，就是《编程之美》，这本书的副标题是微软面试心得，回顾一下整体面试的难度，跟这本书的难度差不多，可以作为复习的参考书之一。因为本人是写Java的，所以在复习的过程中也参考了另外两本书，《数据结构与算法分析，Java语言实现》和《算法导论》。

最后在补充一下，本人在面试微软的时候，只有不到两年工作经验，所以面试的级别不算高，不了解更高的级别面试的情况。面试的问题也会跟具体的面试官有关，本文只是记录下个人的面试经历，希望能对想要去微软的同学，提供一定的帮助。