2018微软预科生面试经历

原本打算大三暑假结束后再找实习，但是大部分企业只在上半年统一招收实习生，担心暑假之后没有什么好的实习可以找，而腾讯阿里都过了实习生招聘的时间。恰逢微软（苏州）进校现场招聘，于是就投了微软。

线上面试

原本定的是5月22日在费彝民楼面试，微软之后又改到了5月28日。由于报名人数较多，因此在线下面试前又进行了一次线上面试。

线上面试大概经历了35分钟，比我想的要快了一些，但涉及到的内容还是挺多的。

自我介绍与项目

首先是自我介绍，我大概说了一些自己的情况和擅长的领域。面试官说看我的学习成绩不错，是不是平时比较专注于学习，因为他看到我简历上项目只写到17年9月份，还问我是不是最新的简历。我提示他说我简历也有写18年的项目（回去之后就把项目改成了时间顺序）。

接下来就就是介绍一个自己写过的项目，我讲了最近个人完成的JavaEE课程项目，恰好项目部署在服务器上，就把URL发给了面试官，他看了之后表示还不错。

白板代码

算法题很简单，一道链表相关的题目：

去除已排序链表中的重复元素。

当时写的代码：

public Node removeDuplicate(Node head) {
    if (head == null) return head;
    Node p = head, next = head.next;
    int num = p.val;
    while (next != null) {
        if (next.val == num) {
            next = next.next;
            continue;
        }
        p.next = next;
        p = next;
        next = next.next;
        num = p.val;
    }
    p.next = null;
    return head;
}

现在回过头来看其实多定义了一个num变量，可以直接替换成p.val。

写完之后面试官让我写几个测试用例，也就是几个用于测试的链表。我在写的过程中意识到一开始少了return语句前的一句p.next = null;，也就是没有处理最后一个元素（失误），及时添加了上去。

排序与复杂度

下面面试官直接问我有没有学过判断算法时间复杂度，说一下几种排序算法的时间复杂度。在我说到快速排序的平均时间复杂度是O(nlogn)时，面试官让我解释一下为什么说是平均。

设计模式

下面面试官让我说一下项目中用过一些设计模式。我讲了工厂模式，在项目关于对象的创建是Spring管理的。他说不用考虑具体项目，说一个印象最深的策略模式。我介绍了一下策略模式，解释了一下策略模式的优点。

ArrayList与LinkedList

面试官提的问题之间似乎没有什么关联，接下来问了ArrayList和LinkedList的区别和实现机制，当我说到ArrayList会动态扩大数组时，面试官让我解释一下动态扩张数组的原理，我不确定他要问的原理有多深，而且我并没有看过ArrayList源码，因此我说对具体实现不太了解，面试官也就没有继续问下去。

LRU Cache

最后面试官问了LRU Cache，让我简单实现一个LRU Cache，我表示对LRU算法有了解，但是不记得具体实现。面试官让我按自己的理解写，我先说了自己的思路，一开始想的使用队列（说完意识到不对），面试官提示用LinkedList还是ArrayList，由于涉及到频繁的删除与插入操作，当然选择了LinkedList，接下来面试官问LinkedList查找的效率，O(n)明显比不上ArrayList，我想了之后说可以用Map来简化查找过程，key是Cache中的内容，value是指向LinkedList中元素的指针。面试官表示可以，之后也没让我再写代码。

后来发现本题是LeetCode上的原题LRU-Cache，可以使插入和查找时间均为O(1)，思路很巧妙。

线上面试总结

总的来说线上面试的内容还是比较简单的，毕竟只是线下面试前一轮的筛选工作，不过因为是第一次面试难免有点紧张，给自己发挥打个7分吧。

线下面试

一面

一面的面试官是个挺年轻的小伙子，自我介绍之后让我介绍一个的项目，我讲了花旗杯的项目。接着问了我Restful API是如何设计的，对账目的自动归类、数据库的Schema设计等细节问题，问得还是比较细的。

接下来手写算法题是：

假设二叉树的每一个节点都有一个指向父节点的指针，现在任给一个节点，找到这棵树的中序遍历中此节点的下一个节点。

简单思考了一下，分了两种情况，节点有右子树和没有右子树，顺利写完了代码。第一次写完有点小错，被面试官要求再检查一下的时候发现了错误及时改了过来。

二面

二面面试官是个小姐姐，比一面感觉亲切很多。一开始同样自我介绍然后讲项目，我还是讲的花旗杯的项目，跟一面比问的问题并不是很多。小姐姐还对云计算的项目表现出了一些感兴趣，问我懂不懂Hadoop，我说不是特别了解。

二面一开始问的似乎是一道智力题：

有25匹马，5个赛道，最少要比多少次能够找出最快的5匹马？

这题我确实想了很久，一开始给出的想法是，先分5组比5次，把每次里最快的拿出来再比一次，得出25匹马中最快的一匹，把最快的一匹马一开始所在组的第二拿出来再跟另外四匹比，得出第二快的一匹，由此类推。很容易想到的方法，但是比的次数不是最少的。

后来想可以用到排除法，经过小姐姐的提醒，前5组中最快的5匹比过之后，最慢的那匹所在组的后4匹不可能进前5，全部淘汰，同理，可以排除掉4+3+2+1=10匹马。然后小姐姐也没让我继续算下去，直接做算法题了。

找出二叉树中两个节点的最近公共父节点。

第一个想到的方法是，找出从根到这两个节点的路径，存在两个列表中，然后列表中的项两两一一比对，时间复杂度为O(n)。

一时想不出更好的方法，小姐姐就让我写了这种方法的代码。当时觉得时间已经过了挺久，所以写的时候有比较急，递归方法里写的有点乱。

本题也是Leetcode中的原题Common-Ancestor，有更好的递归解决方法。

三面

三面面试官是个挺和蔼的大叔（并不是老外，松了一口气），人很好。同样的自我介绍，他直接问了项目经历里第一个JavaEE项目，问我如果管理员想查看所有在线用户该怎么做，我一开始想的是把登录状态存数据库，但由于是Web项目，显然不太合理。于是想到监控Session，用Map存储在线用户的Session，他问我Map放在哪里，让我大概写一下如何实现。我写了一个简单的接口和实现类。

三面算法第一题：

把二叉查找树中一个节点的值变为原来的2倍。

二叉查找树的问题，想了想也就是一次删除和一次插入的操作，分别写了两个方法。

三面算法第二题：

给一个m*n的矩形，每一格有一个正整数值，从左上角开始走到右下角，每一次可以向上下左右四个方向走，问走到右下角所有路径中数字和的最小值以及对应的路径。

总算不是树的问题了，一开始我以为是一道典型的动态规划题（只能向下或向右走），听了描述之后发现不对。一时没想到什么好办法，用递归回溯暴力穷举写完了。（一开始的时候只求了最小值，并没有记录路径，后来面试官说要求得出路径，于是把代码怎么改大概描述了一下）。

问了几个问题，面试官说他是志愿者，也都不太了解，于是还带我去问了HR，人确实很不错。

总结

三次面试都是手写算法，而且写了三次二叉树···

总的来说题并不变态，想不到最优解法的话，基本的方法还是能想到的，多做一做LeetCode很有好处，手写代码最好提前写一写，不然可能像我二面的时候一样这儿插一点那儿涂一点看起来很乱。