微软中国（Microsoft）

楼主一个月前在校园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。我考虑了下估计没多久会离开上海，投入微软的怀抱了。

面试官有好几个，都是男性。面试内容涉及数据库，算法，人工智能等多个领域。其中算法比较难，写了满满一白板，中途面试官有提问，比如某部分code是什么作用，自己想不出了也可以问面试官，面试官也会有提醒。

中午2点开始面试，skype调了很久，才可以，因为需要在白板上面写代码，面试官全程看着。 一面：0）聊了点项目，不过我的项目跟机器学习相关的，面试官一点也不care。 1）一个有序数组，找出两个数，和为指定的一个数sum； 2）手写快速排序； 二面：0）同样项目； 1）手写无序数组里找到第k大的数；尝试用类似快排二分的思想写，没写出来，失败。

1、网申（要去微软的招聘网站去注册，然后填写你的简历） 2、网申通过以后HR会发两份网上测验的连接，一个是编程的测试（只针对研发相关的岗位），一个是英语测试。编程测试是用的Hihocoder编程测试网站，四道题2个小时（我水平超级差，好久没用C编过程序了，一个都不会，但是竟然意外的还接收到了一面的通知，我自己也觉得很奇怪）。英文测试也是一个链接，题目是包含了听，说部分。时间不长。需要打电话去一个号码，然后回答机器的提问。有些是让你读一段英文，有的是听完问题以后去回答。 3、都通过以后就是一面，微软的服务我觉得很棒啊，外地过来的话报销路费，如果需要的话还提供午餐。

内推一样要笔试，笔试被虐得怀疑人生。面试共3轮，全部是手写算法，正常人加起来会有5题，但每轮题目数量不固定。我的第一轮是个2选1，一题是二维矩阵深度遍历题目不记得了，没做这题，做的另一题是旋转一个矩阵，注意一下下标就OK了；第二面3题，第一题二维坐标系所有整数坐标都是一个格点，任取两个格点，求连线段上共有几个格点，是个求最大公约数的问题，第二题ax+by=1，已知a和b求x和y，面试官自己问题没问清，我一直提示他a和b是不是整数他说不是，我做完之后他才想起来a和b应该是整数，具体题目他自己貌似忘了，立马尴尬地换了一题。第三题是个dp，已知a1，a2.an,m1,m2,…mn和z，求a1b1+a2b2+anbn=z，其中b1<=m1,b2<=m2…bn<=mn.我很不擅长dp，但用递归做出来了，做完之后面试官让我用dp再做一遍，我没能做出来，面试官问我知不知道背包问题我说不知道，然后给我点提示，然后我还没做出来，然后疯狂给我提示，dp表都基本画出来给我了，然后我还是没能做出来~~三面是个旋转打印二维数组，一开始题目是正方形，写完面试官又让写长方形。

第一轮人事的电话面试，面试有深度广度，主要询问加入微软的目的，个人价值观，性格特点，以及职业规划。我通过了两轮电话面试，进入部门面试，部门面试比较侧重于英语口语表达能力，以及临场的应变能力，还有专业能力。

一面：1. N个平均长度为M的链表，链表中数字是排好序的，求出在N个链表中都出现的数字。（扩展，求出大于N/2的数字）2. 甲和乙做游戏，有一排硬币，面纸不等，可以为任何正整数，a1,a 2,...,an. 甲和乙轮流抓硬币，每次只能从两头抓，问先抓的人有无必胜策略？怎样抓才最优？ 3. 包含2n+1个节点的二叉搜索树重构：使得根节点两侧节点数目都为n 二面：先问了项目经验1. 单链表逆序； 2. 在二叉搜索树中查找给定整数，找到返回这个节点，否则返回和它差的绝对值最小的节点。 3. 假定有N台机器可以调度，每天的任务量为一个sin函数，中午最高，晚上最低，问怎样调度才能合理，既保证省电也减少机器的开关次数？ 三面：问了项目经验。一些琐碎的问题：如果你的程序马上发布，却出bug了，你怎么办？如果你同事不合作，怎么办等等。