我的微软现场面试经历
26号微软面试，不幸的是被微软拒了。
第一面：
面试官是个平头，看起来挺精神的小帅哥。
（1）面试官看我简历上写着hadoop。便让我用hadoop写一个矩阵相乘的算法。
楼主已经大半年没写过mapreduce程序了。 想了一阵子，中途面试官也不断提示。最后用两个mapreduce完成了这个算法。
（2）一个矩阵中元素分类的算法。一个矩阵中的元素和它周围八个元素是相邻的。如果两个元素相邻切相等就认为他们是一类。
输入m*n矩阵A，输出分类后的m*n矩阵B。
例如：
输入一个2*2矩阵
输出一个2*2矩阵
| 1 | 2 |
| 3 | 4 |
| a | b |
| c | d |
| 1 | 2 | 3 | 3 |
| 5 | 6 | 7 | 3 |
| 1 | 2 | 0 | 3 |
| 3 | 3 | 3 | 5 |
| a | b | c | c |
| d | e | f | c |
| h | i | j | c |
| c | c | c | m |
我说这是一个深度优先遍历问题。然后面试官说深度优先遍历肯定能解出来这道题。但如果m和n都特别大的时候，递归调用栈很深，可能栈会溢出，还有没有别的解法。
我想了想，又说出一种解法。从上往下遍历的时候，给元素标类，如果有冲突，就认为属于一类，先记下来。比如上图中遍历到最后一行第三个元素的时候，才知道k和c应该是同一类。这时候，把k和c标记为同一类。用一个容器存着对应关系。
| a | b | c | c |
| d | e | f | c |
| h | i | j | c |
| k | k | k | m |
第二次遍历的时候，把属于同一类的都换成同一个，这里把k都换成c。
面试官听我说完，说我这是一个m*n*p复杂度的算法,p是有冲突的对数。问我还有没有更优的解法。这时候面试时间快到了，每个面试官都要控制面试时间。我没想几分钟。他就说时间到了，然后面试官自言自语道，这一题算简单的。。。 我本着求知的精神，问他最优解是什么。他就balabala。说从上往下，再从下往上遍历。当时我也没时间细想。他问我有什么问题没。
我问，据我了解，微软面试很喜欢问算法。是因为微软很重视这一块吗？他回答说，微软希望招一些聪明的人。。他们更希望跟一些智商比较高的人一起工作，这样合作比较顺利。。然后说当然，勤能补拙。。。 反正听起来不是很舒服。尤其在只有两个人的***里。
一面之后，吃了顿微软的盒饭。。
第二面：
面试官没有第一个看起来那么精神。
先让我用English introduce yourself.
然后他看我简历上有课程学过，机器学习与数据挖掘，还有自然语言处理。他就让我选一个给他讲讲课程里的东西。
于是我就把机器学习课程里写过的一些算法。我就试着从分类，聚类，回归的角度说。朴素贝叶斯，KNN，决策树，SVM，Kmeans等算法都简要说了下。他问了我决策树里，信息增益和信息增益率都是什么。然后问了看过什么论文？知道最近某会议刚发表的一个分类算法吗？不知道。
然后就写了一个打印菱形的算法。输入菱形的高度，打印这个菱形。我一想，这么简单。
最后写了分上下两部分遍历的算法。上半部分一个for循环，下半部分一个for循环。
写了之后，他问了我如何优化。我看了看说这两部分其实可以合并的。但还是没有get到他的点。他最后说这里可用绝对值。最后用绝对值写了一个解法。面试结束。问了他两个问题。
第三面：
前两面后，等了两个小时才到第三面。
面试官穿着拖鞋，大神的既视感。 PS：穿着拖鞋还穿着袜子。。
自我介绍随便聊了聊，项目随便聊了些。然后又是一个算法题。
给一个二叉树 和一个值 判断，从根节点到叶子节点的路径中，有没路径之和等于给定值的路径。
看到这一题的时候想，这不是剑指offer上的吗。leetcode也刷过。
想都没想写了一个层序遍历的算法。但这一算法要改变节点上的值。面试官又说如果不能改变节点的值呢。我又写了一个前序遍历的算法。然后一直问我还能优化吗。在当时的情况下，确实没能想出更优化的算法了。
我问他最优化的算法是什么，他说这一题我一会还用呢。。。
三轮面完后，一个类似HR的人把我叫出去，谈了一会。委婉的告诉了我我被拒了，不match他们。尤其第三面的时候，没有搞清楚面试官的需求。
结构能不能改变，树中有没可能存在负数等，没有跟面试官好好沟通，以后见客户，做工作的时候这样不好之类的。。然后说了些需要加强coding
skills什么的，这次面试结果不影响秋招。
总结：微软面试其实考的还是算法，不仅写出解法，还要尽量写出比较优化的解法。由于去之前已经拿到阿里，网易offer了，心态有了些变化。没有在去苏州之前，再刷刷题。当然，认真准备都不一定能通过呢。。
这次苏州之行，虽然没有拿到offer。但面试官说的很对，需要不停的沟通，不停的了解，面试官或者客户真正想要的是什么。而不是给你一道题，照着自己的理解闷头写。
找实习的经历到此结束。接下来等秋招的时候，再看看是否跟MS还有缘分。
附上微软正面照一张，那天面试完，下起了雨。
腾讯公司福利 465人发布