Microsoft面经汇总
Saber_Ji 9月之前
面经1：
11月14号终于迎来的找工季的第一个onsite。幸好第一个面的是微软，题目都不是很难，就是太久没练白板，手有点生。早上11点半到Building 111. 跟其他人一样，当天有大概4个组的hiring event. 见了面试官才知道面的是outlook组。所有的面试都是在Building 111里。recruiter大概11点45分的时候带着大家去食堂吃饭，每个人有20刀的饭卡。楼主找了个自助餐迅速打好饭开始吃，同桌的校友去排了一个吃teriyaki的餐馆，结果就是楼主吃完还没见校友回来。。12点30集合，12点15才见校友捧着teriyaki再次出现。。所以各位去餐厅打饭的时候注意一下队伍的长度，以免耽误了面试。下午一点面试准时开始。
三哥: LC 179 largest number2. 白人大姐：LC 69 sqrt(x).
在微软待了17年的三哥: 给一个句子，把所有B开头的单词删掉。注意面试官这里强调说不能用split,join啊什么的function。要求inplace。可以assume string是mutable的，或者assume input是list of chars。说白了就是考察你string manipulation的熟练度。
白人大哥：LC 74: Search a 2D Matrix
面完第一面楼主就知道自己应该是挂了，后来的确题目越来越简单也印证了这个猜想。不过微软真的是财大气粗，定的是个超级高大上四星hotel，king room with view. location在Bellevue downtown,对面就是鼎泰丰，走两步就是臭臭锅，对面还有商场，等等等。。而且酒店里的吃喝都是directly billed to microsoft， 你只要负责点餐和签字就可以~ 虽然也许没有offer，但是西雅图的三日游还是挺开心的。
面经2：
四轮四道题：
（1）给一个数字代表时间，转化成英文表示的string，例如：input 1310, output: “one ten pm”
（2）在linkedlist中删除所有值是n的倍数的node
（3）leetcode word search ii变形，每次只能沿一个方向走
（4）spiral matrix。
面经3：
楼主是学校career fair和微软人员聊天拿到的on-campus interview，面过一星期之后出了过的结果，第二天选择面试时间。选择了10月25日在雷德蒙。面的是Cloud & Enterprise组。
第一轮：
中国大姐，人非常nice，聊了很多简历上的项目，问到了research中人际交往遇到的困难。题目是给一个string，返回其中是否存在重复的字符（duplicate characters）。只有英文字母。我提出用52长度的boolean array存储，遇到true直接return。然后问如果有各种character怎么办？我说hashset。然后问如果只有字母，有什么方法可以节省空间？我说可以用integer位操作。对方挺满意的，然后让我稳了两个问题。
第二轮：
美国大叔，在微软工作了17年。问了research的两个project，叫我讲了其中算法。技术问题是fizz buzz和优化。然后是很多的聊天，问我research有没有遇到过出来的结果和预期不相符的情况。
第三轮：
印度大妈，人非常好，刚进来我没有说话，她就滔滔不绝介绍组里的项目，讲了许多许多，然后我提了几个问题。最后才开始做题：reverse words in a string。我是先转成char array然后两次反转做的。对方叫了讲了几种test case，然后问我有没有考虑index变量（integer）有没有覆盖不了的情况。我说用long。然后就结束了。
面经4：
十月中旬on campus面试，两周后通知onsite，但是安排到12月才面上。面试从中午开始，先是hr组织面试的小伙伴们一起吃午饭，然后回面试的楼里等面试，一轮45分钟，每轮中间15分钟休息。
楼主只面了3轮(据说组和组不一样，所以有人面3轮有人面4轮).
第一轮：
面试官是一个manager，但不清楚是不是hiring manager，先问了一些之前的经历。
spiral matrix
evaluate expressions
第二轮：
一个口音超不清楚的中东小哥只问了一个找已知input string是否在dictionary的题(希望没有理解错。。。）
接下来就是问以前的projects，交流不是很顺（感觉他也听不懂我说话。。。)希望不要挂在这.
第三轮：
印度姐姐？。。讲英文很清楚.
find the starting node of the loop in linkedlist
sort linked list
design a movie theatre, list all the corner cases.
总体感觉面试的人都很友好，题不难，问之前的project比较多。去过MS家onsite的小伙伴都说体验不错。
面经5：
第一轮：
印度大叔。上来简单盘问简历，然后问我如何处理high volume的requests，完全没看system design，就把脑子仅存的一点知识都用上了，从load balancing到replication，sharding啥的全说了，他还是不满意。之后就开始做题。题目是他有一坨印度飞饼，有大有小，然后要将这些飞饼从小到大排序。但条件是要利用他给的API - void flip(int[] nums, int index)，这个method会把包括index及其之前的数颠倒。例如：[1, 5, 3, 2, 6]， 若flip(nums, 3)，array变成[2, 3, 5, 1, 6]。大概思考了2两分钟，他见我还没做声，就迫不及待的要提醒我。。。在他的提醒下，两分钟写完code后，就开始问哪里能optimize，特别细致。因为我的方法是每次找最大的数，先flip到array最前面，然后flip到正确的位置。就不停提醒我如果当前数已经在正确的位置呢？当前数已经在array最前面呢？虽然感觉没什么卵用，但还是顺着他的意思乖乖的加了两个条件。又问我能不能变得更快，比如nlogn，我说maintain一个heap来保存最大值，他说能不能不用extra space呢？我当时已经晕了，他看我快不行了，就另外让我设计一个API，题目很简单，在array里找target，他想让我回答的就是如果找不到return -1。他一离开我才想起他之前是想让我用quickselect，后悔莫及。这轮感觉从头到尾被拖着走，顿时感觉整个面试没什么希望了。所以也就特别放松了。
第二轮：
白人大哥。上来问简历，问behavior，如何处理同事之间的矛盾，大概花了20分钟，中途让我介绍了一些我做的项目的REST API design。。。问完开始做题，让我设计一个average request number per minute calculater。一开始是理解题意，跟他交流过程中发现他只想让这个问题越简单越好，所以我就先直接写了一个如何查询过去一分钟request number的method。写完我就主动告诉他这个有什么缺陷，并不能查询历史记录，然后就问他想我怎么maintain这个历史记录，是每分钟的都记录下来呢，还是只保存一个值然后用当前新的一分钟来更新这个值。没想到他说不用写这么复杂，你这个看起来还行，walk me through吧。。。最后optimize了一下，把map换成了fixed size array - nums[60]。
第三轮：
应该是国人大哥吧？上来看我简历，“咦？你在某个国家待过？我是那里博士毕业的诶，给我讲讲你在那做了些什么”。就这样关系亲近了不少（偷笑）。简历大概聊了20多分钟，感觉他对我做过的project还挺有兴趣，可能是自带亲切属性。。。然后是怎么也逃不过的behavior，问了我为什么要跳槽，然后就告诉了他我的真实想法，他也挺感同身受。然后就是灾难性的做题了，题目是经典的longest common subsequence，然而我并没做过。。。上来想了一会没什么简单思路，就只能brute force，然而这是一个NP-hard。。。可是大哥人很好很耐心，说他接受任何brute force，然后我就一步一步给他讲解我的思路，听完说行得通，你能写下代码吗？我说我写不出来。。。然后他说这样吧，你试试dp，看能不能做出来，顿时喜出望外，然而倒腾了几分钟也没把方程写出来，然后他就拿着笔直接在黑板上帮我写了方程式。。。时间不多了，也没写代码，他就问我怎么输出所有的sequence呢？我说backtracking，他似乎不太喜欢这个笼统的答案，就让我画dp table，然后说顺着这个数字增大的方向，就能找到sequence啦。。。这轮做完没啥遗憾了，遇到这么好的面试官。
第四轮：
印度大哥。他以为走错了房间，结果是拿错了简历。简历walk through 5分钟，然后让我介绍现在做的东西，从db design到system design都问了，也是答的稀里糊涂。然后直接做题，就说复制一个linkedlist，我说有啥要求吗？他说考虑所有情况。。。那不就是要考虑有环的情况咯？他不苟言笑，似是而非的点了点头。。。然后用hashmap很快写完了。大概还有十多分钟，他出了个问答题：有millions of integers，内存很小，不能排序，如何找到top k numbers。我说bit set，他有些疑惑。我就给他解释了下，他说不错行的通。然后让我问他问题。
就这样，四轮结束了，整个面试体验是很好的，四轮的面试官都非常的nice，都特别耐心，说实话这对面试效果是有很大的辅助作用的。当然自己心里清楚总体表现是不太好的，主要还是自身能力不够，从准备跳槽到现在也就一个月时间，题刷了一半，好多topics还没来得及看。然而。。。第二天却收到了offer
面经6：
1轮
简历，问实习期间做了啥，有分歧咋办，做过code review没。 问了一个拓扑排序
2轮
简历，实习做了啥。 hashmap的N种版本，通常版本，读远多于写版本，写多于读版本，高并发版本，不用写代码，要讲清楚加锁方式。 第二题一个大型user log。 如何快速取出 过去5分钟， 1小时，1天某个user访问最多的一个地址。说了用heap. 他让我省空间，我说
用斐波拉契堆。 他说你可以不用从数据结构考虑，。。最后讨论无果。
3轮
感谢校友，感谢校友，感谢校友。
4轮
三哥，这就是RP守恒吧。从头到尾不吊我。 给我口述题目，我听不清想让他打出来，他说不行，你自己听。几番纠缠总算把题目弄出来了。 一个矩阵里边查找一个target value， 如果找到了，把target所在的value行列都设置为0. 要求访问元素的次数尽可能少。 注意一个边界就行了，
就是target value本身就是0. 所以我用set存target value的col, row index。避免了这个错误。 第二题，打印文件最后n行。 先统计，然后定位，打印。 要求只能扫一次。先用队列存，最后他要求我用链表实现，也解决了。还剩5分钟， 开始让我问问题，感觉这个三哥好气，没有
抓到我的小辫子。
这个时候又来了一波转折，问完问题，三哥突然说，我是最后一个啊，你不着急吧，不着急的话： actually，I have some other questions for you. 于是： 啥是thread, process.他们share什么东西，这俩定义我早记熟了。我说share heap memory, data segment, text segment, core segment和其他shared library. 不过每个thread 自己有自己的 stack. 这个时候他说 你刚刚讲的几个segment都有什么用，编程中哪些情况对应使用哪个segment. 于是又讲了一些。最后问了触发segment fault可能因为啥。作为把《深入理解计算机系统》看了三遍的，这些还是轻松搞定。
面经7：
两道题
给你一个一维数组，和一个index，看是否能根据算好的下个index，找到数组里边的0。找到的话，返回True， 没有或数组越界的话，返回False。
下一个index计算方式为: nextIndex = index - Array[index] or index + Array[index]
例如：
输入： Array = [2, 4, 1, 2, 0, 1] Index = 2
得出： nextIndex = 2 - Array[2] = 2 - 1 = 1 or 2 + Array[2] = 2 + 1 = 3
本次得出的nextIndex将作为下一次的输入， 依次类推。直至找到0为止。
所以相当于去两个方向找， 我是用recursion写的，代码如下，有其他办法欢迎交流。
s = set()
def landOnZero(nums, index):
l = len(nums)
if not nums or index < 0 or index >= l
return False.
if index in s:
return.
if nums\[index\] == 0:
return True
s.add\(index\)
cur = nums\[index\]
one = index + cur
if landOnZero\(nums, one\):
return True.
two = index - cur
if landOnZero\(nums, two\):
return True
return False
print landOnZero([2,4,1,2,0,1], 3) // True
给定两个字符串string1和string2, 判断其中长字符串中和短字符串同时拥有的字符，是否按照短字符串字符的排列顺序依次排列。
例如：
string1 = "abc"
string2 = "ambmc"
返回 True
string1 = "abc"
string2 = "amcmb"
返回 False.
string1 = “Rdd Waitn”.
string2 = "Redmond Washington"
返回 True.
第一题耽误了点时间，后来这道题交的并不是最终调试好的答案，估计会挂在这道：
def compareOrder(str1, str2):
size1 = len(str1)
size2 = len(str2)
if size1 < size2
return compare(str1, str2)
else:
return compare(str2, str1).
def compare(str1, str2):
i = 0
j = 0
count = 0.
while i < len(str1):
while j < len(str2):
if str1[i] != str2[j]:
j = j + 1
else:
break
if j < len(str2):
count = count + 1
i = i + 1
return i == count
print compareOrder(“Rdd Waitn”, “Redmond Washington”) // True
print compareOrder(“Rdd Waitn”, “Redmond Washingon”) // False
作者：匿名用户
链接：https://www.zhihu.com/question/23688335/answer/173623680
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
本人工作1年多了，正在准备跳槽中。刚刚参加完微软西雅图的面试，来分享一下自己的面试过程。一共7轮面试，其中1轮电面，6轮Onsite。
第一轮 电面1
第一轮是电面，先是让自我介绍，然后根据简历提了几个问题之后，就直接开始上题了。
- 给出一个字符串（假设长度最长为1000），求出它的最长回文子串，你可以假定只有一个满足条件的最长回文子串。
LintCode原题：http://www.lintcode.com/problem/longest-palindromic-substring/ 参考答案：http://www.jiuzhang.com/solutions/longest-palindromic-substring/ follow up: 问了类似于找出最长且长度为奇数／偶数的回文子串的这种问题。
电面总体感觉还不错，没过多久HR联系我告知电面通过，可以做接下来的准备了，并且约定了Onsite 的时间。
第二轮 Onsite 1
面试官先进行了自我介绍，然后问了我3个最擅长的编程语言，聊了一下就开始coding 了。
- 最大正方形。在一个二维01矩阵中找到全为1的最大正方形。
LintCode原题：http://www.lintcode.com/problem/maximal-square/ 参考答案：http://www.jiuzhang.com/solutions/maximal-square/
- 在一个二维01矩阵中找出1最多且连续的一行。
第三轮 Onsite 2
在这轮只有1个问题，大约用了35分钟。
- 设计题，设计BitSet API
第四轮 Onsite 3
问了一道二叉树问题。
- 验证二叉查找树。给定一个二叉树，判断它是否是合法的二叉查找树(BST)。 LintCode原题： http://www.lintcode.com/problem/validate-binary-search-tree/ 参考答案： http://www.jiuzhang.com/solutions/validate-binary-search-tree/
第五轮 Onsite 4
这一轮上来先让我做自我介绍。然后又让我讲了讲前面的几轮面试。后面就做了道算法题。
- 合并两个排序链表。将两个排序链表合并为一个新的排序链表。 LintCode原题： http://www.lintcode.com/problem/merge-two-sorted-lists/ 参考答案： http://www.jiuzhang.com/solutions/merge-two-sorted-lists/
第六轮 Onsite 5
这一轮相对轻松了许多，基本上就是在聊天，主要针对我简历上写的项目经验问了一些问题，然后进行了coding。
1.对十亿个整型数排序，并尽可能使用最小的存储量
第七轮 Onsite 6
面试官先问了我为什么选择微软，还有理想的工作地点。然后问了一下之前做过的项目遇见过的最大的挑战是什么，接着问了一道算法题。
- 数据流中位数。数字是不断进入数组的，在每次添加一个新的数进入数组的同时返回当前新数组的中位数。 LintCode原题： http://www.lintcode.com/zh-cn/problem/data-stream-median/ 参考答案： http://www.jiuzhang.com/solutions/median-in-data-stream/
基本上面试的过程就是这样了。