好的,终于开始写微软的面试经了.感受颇多啊,三月投的简历,然后4月去哈工大笔试,过笔试后安排了一次线上的面试,本来过了线上面后通知第二天去北京onsite面的,由于当时刚从哈尔滨面完TX回来,加上也还没怎么认真的复习,就推脱说去不了,跟HR约定5月6号去onsite面,没想到过了6号还没通知去面试,说是人事还没有安排好,还得再等一两个星期,好吧…过了一个星期之后,终于来电话了,说是得加面一轮线上,面呗.然后..就开始了悲剧地面试之路,第一次加面的时候面得非常烂,问了两题,一题都没答上,第二次面完非常失落,以为肯定没戏了,也已经开始写这篇总结了,写了一半了都,后来HR居然来电话说再加面一轮,最后一共面了三次线上面试,没能去北京onsite.
笔试
笔试为20道不定向选择题,全英文,题目意思都挺好理解,基本上能考上大学的都能看懂,微软的笔试恶心的就在于,做对了加分,做错了扣分,不做0分,选不全的得部分分,所以有可能出现负分的情况…笔试去的哈工大,叫同学请吃了一顿中午饭,下午2点开始考,75分钟,题目我就不贴了,网上搜一下就有,考完回来估分可能刚过60.笔试考得不难,都是基础的东西,甚至有一题问你类似于一个大小为a[3][2]的数组中取a[0][2]的值是什么,所以我非常替没去考的同学感到遗憾的.
第一轮线上面试
笔试完过了有一个星期吧,接到了面试通知,说笔试已经通过了,到时候会有人电话我约一个时间进行线上的面试,线上面试的前一天刚好去哈尔滨参加TX的面试,所以线上的面试是在宾馆里进行,时间为一个小时,线上面试得安装一个叫Lync attendee的会议软件,上线之后双方能语音,视频,还有一个共享白板,在上面打字对方能看见,是展示代码用的,面我的面试官的STC的,以下是问题
-
首先万年不变的自我介绍,我介绍都大同小异,之前说过了
-
介绍完之后,他就说那我们开始做题吧- -!第一题,有一个很多的数组,其中乱序的存着数,请找出相差最大的两个数
这题思路很明确,首先先对这个数组中的排序,然后逐个遍历两数之差就能找出来了,对于数组的话,之前在哪看过说用归并排序比较好吧,然后时间复杂度是O(nlogn) + O(n),然后叫用代码实现,听到写代码我就慌了,之前也没有练过即兴写代码,虽然归并排序的原理还算清楚,但是突然要写还是有点手忙脚乱.草草写完代码,说实话我自己看都觉得写得好丑,面试官稍稍看了一下,也没说有没有错误,就问还有更优的方案吗?暂时想不出来…
-
第二题,一个n级的阶梯,一个人可以选择一次上阶或是两阶,问上这n级阶梯有多少种走法
说实话,这题在什么地方看到过,但是解法不记得了….幸好有同学在旁边提示,写了一个费波拉契递推式给我,答曰,其实这题在网上看到过,结果是f(n) = f(n – 1) + f(n -2),对方说对对,其实就是一个费波拉契数列,既然你看过…那你写一个费波拉契数列的非递归实现吧.这个简单,10多行代码就搞定
-
接下来他说时间不多了,就问最后一个问题吧,一个链表找倒数第n个节点
之前有看过面经过说如果面试的时候有问到之前看过的或者是上轮面试重复的题目,千万不要暗自高兴然后告诉他正解是你自己当时想出来的,这样的话如果之后面试复查发现了问题就足以说明你的诚信问题了,所以一定要跟面试官说明,首先这说明你很诚实,如果题目是你之前看到过的,还可以体现你准备得很充分.当然你也不要不懂装懂,看到不会的问题就推说自己看过让面试官换题,人家一问答案你就傻了.总之,这题也很简单,网上满天是,我就说我之前在网上看到过这题了,用的是两个指针,他说你看到过,那我们就换一题吧
-
说有n个人在玩一个猜数字的游戏,一个人可以在1-100中任选一个数,最后把n个人选的数字加起来取平均值再乘以2/3得到结果m,如果这n个人中谁选的数字最靠近这个m那么这个人就赢得这个游戏,问题是,如果现在给你选一个数字,你最应该选什么使你最有可能赢?
当时也没有什么思路,就往简单的方面想了,既然要值平均值,那么用1到100这100个数加起来再除以100就得50.5这个平均数,然后再乘以2/3得到大约是34吧,也不知道对不对,就跟他说应该选的是34吧,然后把思路跟他说了一遍,似乎蒙对了一点…他说好,那现在如果进行第二轮游戏,如果之前大家看到之前选34是正确的,现在大家都选了34,那这轮你应该选什么呢?如果这样一直下去,那最后应该选什么呢?最后……那应该是选1吧?他说对了.这题的临界点就在1上,如果每个人都选了1,那么答案永远就是1了,这是一个博弈的问题
问完这题看看时间已经过了一小时,面试官说他的问题问完了,问我有什么问题要问的.闲扯了一阵之后问他对我的面试有什么建议,他说感觉我准备得挺充分(呃…其实是碰巧问到的题目都有看过一点啦..),他自己也好久没有面试人了,出的题可能都比较老,网上都有看到
第二轮线上面试
第一轮线上面之后的第二天早上就通知面试已经通过,问我能不能明天去北京onsite面,自己想多留点时间复习一下,再加上刚刚从哈尔滨回来非常疲惫,就说明天去不了了,于是改到5月6号,说五一之后再联系我.挂完电话后赶紧发邮件给面试官感谢他的面试.可是直到6号都还没有人联系我去面试,遂回电话给HR,被告知现在人事还没有安排好,可能还得等一两个星期,让我等等到时候通知吧,谁知过了几天后的中午,却来电话说得在下午5点加面一轮,于是乎匆匆准备了一下午,总有一种不祥的预感…….
-
自我介绍
-
说我简历上写的对java比较熟,就问起java相关的问题.问java会不会出现内存泄漏?
这个…..还真没有认真研究过…基础不牢啊,回答说java存在GC,一般情况下应该不会出现内存泄漏吧,不过个人感觉应该还是会出现的,在什么情况下现在内存泄漏….不清楚..木有遇到过(之后上网查了,在一个长生命周期的对象调用一个短生命周期的对象时,由于短生命周期的对象存在在长生命周期中没有被及时释放回收就可能出现内存泄漏)
-
问java中final关键字的作用?
答:就和C++中的const差不多..用final修饰后变量必须初始化,并且不能再次改变变量值
那如果用final修饰一个类有作用?
这个..居然一时想不起来了!!!T_T内牛满面,只好说不记得了……(限制类不能被继承啊!!!)
-
问我设计模式会不会..我说会一点,不太多,之后就开始问算法题了,首先是字符串循环移位的问题
很基础吧,网上到处都是,记得之前还看过,但是解法不记得了…老是看了题不记…..然后,当时还有点紧张,没午休,状态很差,英文的题目看了老久都还没有理解讲的什么意思,面试官讲解了一下,然后开始解题,当时居然也没有什么思路,就说了最笨的办法,先把要移位的字符先放到一个辅助空间上,把剩下的字符放到另一个辅助空间中,两个空间组合就行了- -!他说我觉得你应该没有理解题目的意思,题目上写的in place,说的是在原字符串中操作,我就问是不是不能用辅助空间,他说是的….然后我就郁闷了..不用辅助空间这玩意儿还能解?想了一会,我说不用辅助空间的话应该用原字符串中要移位的字符跟其他字符通过些交换实现吧.他说,你再好好想想,后来想想也不对啊,交换字符也是需要辅助空间的,想了好一会,即使是通过用字符交换来实现循环移位我也想不出什么算法来,最后放弃了这题
(后来上网查了一下,可能当时没有理解好不能用辅助空间的意思,他说的"不能用辅助空间"想要表达的意思应该不是说一点辅助空间都不能用,只是不能申请太大的辅助空间,像我说的这种最笨的算法空间复杂度在O(n^2)级别的,简单的解法应该是,比方说让abcdef左移两位变成cdefab,先把原串中的前两位ab逆序:bacdef,再把余下的cdef逆序:bafedc,最后把整个字符串bafedc逆序就得出cdefab了,算法控制得好空间复杂度应该可以得到O(1))
-
第二题是给出一个android手机那种连线解锁的3*3矩阵,算出有多少种连线方法,规定连过线的点不能重复用,但是连过线的点可以被越过,比如矩阵是a[3][3],连线是(0,2)-(1,1)-(2,0)-(1,0)-(1,1)-(1,2)其中(1,1)在第二次被连上的时候算是被越过
我表示基本上没有什么思路,想了好一会说,只想到了穷举法,3*3矩阵是对称的,可以只算出这个矩阵基于(0,0)-(0,1)-(0,2)这边上的所有连线有多少种,再乘以4就基本可以了,他问那你怎么算出来呢?怎么处理越过点的情况?或者用到什么数据结构?当时思维有些堵塞,就说应该用一个双向链表储存点,每个点至多有8个相邻点,至多有3种越过点连线的情况..然后也不知道怎么算了,直到最后也还是没有找到好的思路
就这样,两题都没有答出来,对自己非常失望,之前看的老多算法都没有能用上.问了他MS员工是不是规定一定到用IE,他说没有这个规定,他还说感觉我算法掌握得不太好.面完之后自己感觉肯定没戏了,后来也没再想
第三轮线上面试
第二轮面过了整整一个星期后,刚上完实验课去食堂吃饭,看手机有一个北京来的未接电话,居然之前还有过通话记录,第一感觉就MS的HR打来的,回电话过去果然是,说再得加面一轮,在第二天下午.简直是意外惊喜啊,居然还有机会,我也深知这应该是最后的机会了,第二次面之后也想了好久,感觉自己算法这块还是不太熟,光看了理论算法,题目练得还不够多,其它方面的基础也不是很好,还得好好的去复习做题,既然有机会就好好把握,能不能过都是一次经验.
面试开始时间到约定的要早,我提前了10分钟上线等待面试官,他刚好也在线,问我提前开始有没有问题,我说没问题
-
可能他也知道我之前面过了两次了,上来也不叫我自我介绍了,直接做题,他举例子说比如有一个有序循环的字符串4567123,找出这个字符串中是否存在某个数,如果存在输出下标,不存在输出-1,跟他一顿交流后知道,可以默认把字符串看成升序,而且字符的顺序不是连续的,就是字符串可能是4679123这样的
思路很明确,比如要找的数字是a,首先找出循环终止点,上面例子中是4679|123,由于是升序的很容易知道a是在前半段还是后半段,然后再用二分查找,他问找出循环终止点用什么方法,想不出好的方法,穷举比较吧…….
-
说有一些数可以分解成2^a*3^b*5^c的形式,其中a,b,c>=0的整数,现在给出一个数n,算出所有小于n的满足上面条件的数,从小到大列出来
这题感觉像是找规律的问题,先列出前几个数分别是1,2,3,(4当时没有想到),5,6,8,9…在面试官的提示下想到当(a,b,c)取(0,0,0)情况下是1,(1,0,0)情况是2,(0,1,0)情况下是3,(0,0,1)情况下是5,(1,1,0)情况下是6……..最后的递推关系可能会是由前几项相乘而得,想了10分钟还是没有想出来,而且题目要从小到大列出,不太好确定大小顺序,能力有限最后还是没有把这题解出来
最后问了一下他,MS实习生转正的是否容易点,他说难度跟正式招人差不多,对英语的要求是不是很高,他说过了四六级的同学基本都没有问题,给我建议是算法这块掌握不太好,需要加强.几天之后HR给我发感谢信了,大体内容是说没有适合的职位什么的,到此,我的MS的实习生面试结束了
总结
怎么说呢,距离进入真正的大公司仅一步之遥了,多少有些遗憾,毕竟自己能力有限,也没有做好充分的准备,感觉像MS,Google,Facebook这等世界级的大公司面试主要看中的是应聘者的算法基础和思路,看看MS这三次面全都面的是算法,一次1小时,两到三题,onsite面的话要在纸上coding,所以像<<编程之美>><<编程珠玑>>之类的书得多看多练,多多在纸上练习Coding,多上网看看别人写的算法文章,JULY和董的博客我都挺喜欢的,上TopCoder,CareerCup之类的网站上找些题目练练会很有好处.当然啦,面试这个东西运气因素也会占一定的比例,像我之前看的后缀数组,KMP,BM等等好多的算法都没有在面试中用上,考的主要还是你的解题思路吧.面了几次试后突然感觉自己知道的真的好少,还有好多的书要看,还有好多的知识要学习,还有好多的东西得巩固,所以除非有特别好的机会,实习先不去找了,暑假打算回家好好看书,把基础打牢了,题目练熟了,准备好迎接9月找工作的浪潮!