微软中国（Microsoft）

电话面试，我是做android的，电面主要是问了一些简历上项目的东西，大概面了一个多小时，然后问我算法，我一下子就蒙了，毕业之后算法那块接触的少，脑子一片空白，问了几个很简单的都没打上来（二叉树的先序后序遍历都忘了）最后面试官让我写一个算法，O（1）时间复杂度删除一个二叉树，想了一会没答上来，然后面试官说给我一个小时的时间写出来发他邮箱。然后就先把电话挂了。我想了一会，想到了用栈实现 但是复杂度不为O(1), 由于太久没有接触算法了，有点蒙，上网搜了下确实有O(1)的算法，但是太精妙了 如果照抄过来，肯定有点假。索性就把自己用栈实现的算法发给了他。 然后直接悲剧了。

楼主一个月前在校园BBS上看到师弟发布的社招信息，对苏州微软的这个研发职位比较感兴趣，就发邮件帮忙内推下。师弟很爽快的答应了，没多久就收到了苏州微软的面试电话。   电话面试，电话面试首先做了简单自我介绍，然后最近做的项目，接下来就是开始问编程和算法题了。面向对象的多态和隐藏的概念，优先级对列的实现，堆排序初始化过程时间复杂度（楼主这题答错了 ，应该是o(n)，理解成了堆排序的时间复杂度）。算法题：判断单链表是否存在环节点，找到环节点的入口点（楼主当时没想好，面试完了自己回去画图才推导出来）。最后面完了，面试官说感觉挺不错，后面会邀请On Site面试。果然两天后HR的电话来了，就在端午之后安排了苏州之行。 一面楼主从上海赶到苏州微软正好10点，面试安排在11点。在微软的茶水间喝了点水，吃了点点心，然后负责面试的第一位面试官把我带入面试的会议室，告诉我今天的一天面试都会在这个房间。可能是因为早上6点起床太早，头还有点晕晕的，楼主闭目养神了会，安静等待第一位面试官来临。一面的是一名SDE，简单聊了下最近的项目，他貌似对我最近的一个机器学习项目很感兴趣，想了解我们是怎么做的，我就BALABALA。还剩半个小时，开始算法题了：一个文件中包含多个网段 （IP地址/子网掩码），要求将他们合并。楼主想了想，这不是路由汇聚吗，然后最后转化成01字符串最长公共前缀问题。我把我的分析告诉他，不过他说不对（其实我还是怀疑我的做法是对的），然后问我知道前缀树不。我想了下最后用Trie树，加标记位解决了。 二面，二面是我大学的一个数学系师弟也是SDE，简单自我介绍后，他也对我的机器学习项目很感兴趣。聊聊10分钟后又是算法题：求整型数组的最大连乘积，并输出下标i,j。楼主想了想，这是标准的动态规划，不过要考虑负数情况，要用二维数组来搞定（当前最大值，当前最小值）。楼主用一个全局变量保存最大值max，一个变量保存最后的终点下标j，最后求开始下标i的时候楼主用的是max开始往前除以数组值直到1为止，忘了特殊情况处理最大值就是0（直接返回j,j）。然后是一道求连通区域个数的矩阵题：一个n*n矩阵，里面的元素都是1或者0，0表示不通，1表示通，四向连通的1构成连通区域， 求矩阵里的连通区域和最大连通区域中元素1个个数。楼主想了下就不就是类似朋友圈关系问题吗（A认识B，B认识C，A就认识C），可以用并查集来做，想到用HASHTABLE来保存每个位置的元素和该元素隶属的集合，连通的元素在同一个集合。不过楼主在写代码的时候卡主了，如果一个元素左边的元素在一个连通区域，上面的元素在另一个连通区域，那该元素所属的连通区域就有二义性了（面试后回来想了想，直接把这两个集合并下不就解决了）。然后面试官提示DFS，豁然开朗。不过他提示后，我也给出一种效率低点的解决方案：每个1初始化成1个集合，集合元素就是该1的位置（i,j）.如果两个集合中存在两个位置四向相邻就把两个集合做UNION。这个操作终止的时候有多少个集合就是最后结果。 三面，三面的是一个个子蛮高的面试官SDE2，他也对机器学习的项目感兴趣，我开始BALABALA，然后他问我KNN分类器的训练过程是怎么样的，也许是面试的有点累了，脑子一段路没答上来（其实这个我有看过，KNN的训练过程主要是在寻找最合适的K）。然后又是算法：给一系列CPP文件，每个文件都包含若干个INCLUDE （可能是0个），现在给你一个目标文件，求所有合法的编译顺序。比如文件D.CPP中INCLUDE了A.CPP和C.CPP，C.CPP又INCLUDE了B.CPP， 那么合法的编译顺序就是ABCD,BACD,BCAD三种，楼主当时画了下结构有点向树（其实是图，因为有可能所有的文件都依赖于一个CPP，比如A.CPP和B.CPP又都依赖于E.CPP）。之后面试官提示是图的时候，问题就转化成拓扑排序了，楼主对拓扑排序有些了解，取入度为0的节点，从图中移除并输出，直到所有节点都输出完。但是楼主当时卡在如何打印所有的合法序列，其实回来之后楼主想了下，用栈保存和恢复状态不就行了吗！面试回来上海之后自己手写了代码，测试就通过了。 四面，四面是一个35岁左右的SR DE，跟他聊了下组里主要做的项目，然后又是开始算法：数组中第K大的数，楼主当时对这类题已经比较的心应手了，告诉他我准备借用快排的PARTION思想，通过PARTION后的下标位置来递归找。之后又是白板代码，自己脑子里跑了下过程，面试官看了之后觉得可以。 然后就是跟他们项目相关的N-GRAM问题，硬盘上有一个超大文件，计算机内存不够大，如何求这个文件的所有N-GRAM。楼主想了下，马上想到了队列，不过这个队列大小是固定的N。满足长度N就输出一个N-GRAM，否则就就是入队，并入队的同时出队。这样内存开销空间为O（N），一个维护读取外设文件的指针，面试官听了之后挺满意。 然后马上面试官又问如何一次求得所有的LESS-N-GRAM， 也就是1-GRAM，2-GRAM...N-GRAM。 楼主想了想，在队列上放几个哨兵分别放在第一个单词结束位置，第二次单词结束位置...第N个单词的结束位置，这样每次只要扫描从队列头到哨兵的位置就是1-GRAM，2-GRAM...N-GRAM，接下来就是重复的入队，出队操作。不过面试官提示这个方法有个缺陷，前N-1个单词（队列长度还没到达N）需要先统计下，不过无伤大雅，因为N一般不大（他们的模型一般不超过3）。 BOSS面，四面结束后，已经是4点。面试官告诉我，等下和BOSS聊下，不过BOSS在北京开会，等下SKYPE上找我。大概一个小时，BOSS姗姗来迟，简单自我介绍后，BOSS开始问我一些工作习惯，性格，与同事相处，与美国同事合作方式，一些偏软性问题。BOSS还比较关注我的机器学习项目的背景，我承担的工作，之前有过机器学习的经验，还问我有没特地为了面试刷题准备了下。说实话，刷题准备是有，不过微软的面试题很少外面有现成的，不过刷题的过程中明白了之前学习过程中对一些概念理解不深的地方。自己最深的感触就是现在遇到二叉树的递归方面题深有体会，彻底明白各种遍历的作用以及在二叉树相关算法题中自底向上的思路解决该类算法题的高效性。跟BOSS聊得挺欢的，最后BOSS告诉我，他去和HR准备OFFER的事情。到这里，我觉得一天的战斗终于有了美好的结果，心情豁然开朗。     两天后，我如愿接到HR电话，告诉我OFFER的TITLE是SDE2，告诉我苏州的BASE。我考虑了下估计没多久会离开上海，投入微软的怀抱了。