微软SDE面经（电面+onsite）

本人工作1年多了，正在准备跳槽中。刚刚参加完微软西雅图的面试，来分享一下自己的面试过程。一共7轮面试，其中1轮电面，6轮Onsite。

第一轮 电面1

第一轮是电面，先是让自我介绍，然后根据简历提了几个问题之后，就直接开始上题了。

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 了。

1. 最大正方形。在一个二维01矩阵中找到全为1的最大正方形。

LintCode原题：http://www.lintcode.com/problem/maximal-square/
参考答案：http://www.jiuzhang.com/solutions/maximal-square/

1. 在一个二维01矩阵中找出1最多且连续的一行。

第三轮 Onsite 2

在这轮只有1个问题，大约用了35分钟。

1. 设计题，设计BitSet API

第四轮 Onsite 3

问了一道二叉树问题。

1. 验证二叉查找树。给定一个二叉树，判断它是否是合法的二叉查找树(BST)。
   LintCode原题：http://www.lintcode.com/problem/validate-binary-search-tree/
   参考答案：http://www.jiuzhang.com/solutions/validate-binary-search-tree/

第五轮 Onsite 4

这一轮上来先让我做自我介绍。然后又让我讲了讲前面的几轮面试。后面就做了道算法题。

1. 合并两个排序链表。将两个排序链表合并为一个新的排序链表。
   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

面试官先问了我为什么选择微软，还有理想的工作地点。然后问了一下之前做过的项目遇见过的最大的挑战是什么，接着问了一道算法题。

1. 数据流中位数。数字是不断进入数组的，在每次添加一个新的数进入数组的同时返回当前新数组的中位数。
   LintCode原题：http://www.lintcode.com/zh-cn/problem/data-stream-median/
   参考答案：http://www.jiuzhang.com/solutions/median-in-data-stream/

基本上面试的过程就是这样了。