2017年4月21日去面了微软的软件开发工程师，增长了很多见识，被面了3轮，每轮45min-1h，第1轮：基础算法+1个题【手写代码】；第2轮：谈项目+1个题【手写代码】；第3轮：谈简历+1个题【手写代码】。

(一)一面

1.基于比较的排序有哪些？快排、归并、冒泡、插入、堆、【希尔、选择】

a)选择排序：这应该是最直观的排序方法。在排序n个元素时，第一次遍历，找到最小的元素，将其与第一个元素互换；第二次遍历，找到次小的元素，将其与第二个元素交换；直至剩下最后一个元素。

b)冒泡排序：这应该是我们学到的第一种排序算法。基本思想就是，通过依次比较相邻的两个元素，如后值比前值小，则交换这两个值，小值被交换到前面，大值被交换到后面。这样一次遍历后，最大值被放到最后。而小值被交换到n-1前。然后再次遍历前n-1，n-2，直至最后2个元素。整个儿过程，小值随着不断的遍历过程，逐渐被交换到前面，很像气泡逐渐从水底逐渐冒出。所以被称为冒泡算法。

c)插入排序：这个算法的思想很直观。按照《算法导论》中的解释，这个算法可以参照我们平时打扑克的情形。当抓取一张牌的时候，按顺序比较手牌，将其插入到恰当的位置。这样保证了手中所有的牌依然有序。当已排序的值数量较多时，由于已经保证了有序，那么在确定新值插入位置的时候，可以通过二分查找的方法来去确定插入位置。

d)希尔排序：在冒泡算法中，所以小值只能以步长为1的速度向前面移动。希尔排序在步长上作了优化，开始以一个较大的m步长进行分组，每组进行插入排序，这样就实现了步长为m的移动。然后逐渐缩小步长m直至1。所以根本思想是尽可能的将元素移动较远的位置代替移动一位。

e)归并排序：该思想利用的是解决问题的一个常用思想，divide-and-conquer，即分而治之的思想。将n个元素每次2分，变为两个n/2个元素组，直至1个元素——1个元素，自然是排好序了。然后，再两两合并元素组，最终合并为一个元素组。归并算法，因为需要归并，所以必然需要一个额外的n空间来实现归并。

f)快速排序：同样是分而治之的思想，将原始数据分为2组。但是与归并算法直接将原始数据分为两部分不同的是，快排选择一个中值，新的两个子组，一个子组所有的元素都小于中值，另外一个子组所有的元素都大于等于中值，直至元素个数为1。当元素个数为1时，实际上快排已经完成了排序。这点与归并排序也不同，快排在子组完成以后，无需额外的操作。很明显，快排的效率依赖于中值的选择。如果中值可以将数据分为两个数量相等的子组，那么效率则为最高的。快排无需额外的存储空间，可以in-place进行排序。

g)堆排序：该思想是将原始元素视为一个平衡二叉树。然后要求父节点必须大于子节点的规则，调整该平衡二叉树。由于是平衡二叉树，所以数据被完美的等分。这样根节点即为最大值。这时，堆排序完成了最大值的选择。为排序，则将根节点与最后一个子节点交换。此时，树的规则被破坏，需要从根节点逐级verify规则。

2.非基于比较的排序：计数排序

a)计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值小于等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。

3.描述归并和快排的基本思路是什么？堆排序的原理是什么？堆如何原地排序？

4.图的搜索有哪两种是什么？他们分别依赖什么数据结构来实现的？

a)BFS：通过队列【先进先出】实现，每次将搜索节点未被访问过的邻接节点加入到队列末端。初始状态将起始节点放入队列。遍历队列中的点，直到队列为空。

b)DFS：通过栈【先进后出】来实现，每次将搜索的节点入栈，访问他的某个未被访问过的邻接点【入栈】，初始状态将起始节点放入栈。栈空，DFS遍历结束。

5.树的知识点没考，但我碰到一位从天津过去面试的朋友，她被考了二叉搜索树的题目。

a)给定区间[a,b]，从一颗二叉搜索树中找出这个区间的数【考察二叉搜索树的遍历，有些分支将不需要遍历，因为二叉搜索树本身是有一定大小关系的】；

b)有两棵二叉搜索树，找出两颗二叉搜索树中的公共数【暴力方式，遍历一棵树的数，在另一颗树里面搜】。

6.动态规划（手写代码）的题目：

a)n写成多个数的平方和，求平方数个数和最小，比如n=5，答案是2。

b)可以记忆化中间结果（更优化方法没答出来）。

c)问我要怎么构造测试例（负数，0，1，大数）。

附代码：n开根号要取整，i的平方是i*i，i^2这是或操作

7.面试官让问几个问题，总结答案如下：

a)做自己喜欢的事情

b)微软的弹性工作时间，很赞。

(二)二面

1.简历上项目实习经历相关内容，问你最近做的项目中收获最大的地方？

2.动态规划（手写代码）的题目：

a)一个格子从起始位置（1,1）到（m,n）位置的所有可能的走法。

b)如果在这个m*n中的某些格子加上障碍呢？

c)动态规划，要求不用递归写

附代码：

3.TCP相关的问题：TCP发包可能需要等待回复，如何优化这个发包流程

a)滑动窗口协议，设置窗口大小，收到多个包，只回复最后一个包的ack。

4.面试官建议下次面试要自备纸质简历，另外要多做准备【基本算法+快速思维能力】，建议python变量最好不要使用全局的

(三)三面

1.自我介绍，谈一个做的比较好的项目。

2.query的字符串list_query，输入多个title的字符串list_title，统计每个list_title里面list_query的个数。

a)对list_query建立hash表（python->dict（key, value））

b)List_title里面的每一个字符串，在dict里面找，找到之后value++

3.面试听说我要用python写伪代码，略诧异。感觉用C/C++/Java更主流