面试时间：2019年10月

岗位：微软亚洲工程院-软件工程师

形式：视频面试

一面

1.英文自我介绍

2.项目介绍

3.手写代码：

特殊质数的定义：本身是质数，并且他的所有的组合也全是质数。例如13就是特殊的质数，因为（13,31）都是质数。而123不是，因为（123,132,213,231,312,321）中有数不是质数。

问题：求1~N中出现特殊质数的个数

二面

1.英文自我介绍

2.手写代码

（1）合并俩条有序链表

（2）合并K条有序链表

三面

1.自我介绍（没说英文，我就用中文了）

2.项目介绍

3.手写代码

给定一个二叉树，并给出两个节点，求他们最近的公共父节点

要求：要处理边界条件，就是这俩个节点都有可能不在这个二叉树上。并且不能提前判断，就是不能提前判断节点是否在一棵二叉树上。要边遍历边判断

四面

1.自我介绍

2.项目介绍

3.项目难点已经参与的工作

4.专业以及成绩排名

5.首先代码

原题目是：求一个二叉树中序遍历中，指定节点的前一个节点。

但是因为面试官是用英文说的，而且当时网速也不是很好，所以我听成了 求二叉树的先序遍历。

然后我给出了非递归的形式。面试官问我时间空间复杂度。我说时间是O(n),空间是O(h).面试官不满意。所以我当时就慌了，心想不愧是AA面。因为我知道有一个神奇的方法求二叉树的遍历，不用辅助空间，大家可以搜索 “Morris遍历”。但是我这个方法很久没写了，所以我只能硬着头皮现场边推边写。最后写出来了，但是面试官说我写的完全不对，仔细询问之后，发现题目都听错了。但是面试官可能以前没听说过这个遍历方法，我解释了半天，最后用了一个他的测试样例，现场跑了一遍，他才信。最后他有让我写了一个O(1)时间遍历中序的。最后他又回到了原问题，问了我的解题思路，不用写代码了。最后也完成。

总结

微软这种外企，考察更多的是算法能力就是不太注重当前的项目，主要考察基础能力，具体的经验和技能去了再学，他们更看重快速的学习能力。在11月初的时候，微软打电话说通过了，但是由于地域和其他原因，最终忍痛放弃了微软，也希望自己以后不要后悔。