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语言实现》和《算法导论》。
最后在补充一下,本人在面试微软的时候,只有不到两年工作经验,所以面试的级别不算高,不了解更高的级别面试的情况。面试的问题也会跟具体的面试官有关,本文只是记录下个人的面试经历,希望能对想要去微软的同学,提供一定的帮助。
网友评论