【实习】微软（苏州）面试经验

一共三轮电话面试，每轮至少两个算法题，第三轮是leader面，前两轮单纯的做题，第三轮在开始做题之前聊了几分钟的天。HR很棒，由于不小心记错了第一二轮面试的时间，HR马上调整了一下，很快就重新安排了面试。最初投的时候是冬季实习，第三轮面试结束之后很快就接到HR的电话说可以了，她希望我能这个月底入职，但我最近又有了新的任务，无法实习，因此可以帮我直接转到夏季实习。

下面记录一下面试的过程，其实和网上记录的差不多，就是一直做题。

一面

面试官首先让我用英文做自我介绍，我有点懵逼，完全没准备，勉强讲了一堆我自己都没怎么听懂的话，然后再絮叨了一下就开始做题。面试官发了一个链接给我，是一个在线编辑器，然后就开始写题目。对语言没有要求，所以两个题我分别用的C++和Python。

第一个题是“Z字形打印二叉树”，给定一颗树，先打印根节点，从第二行开始先从左到右，再从右到左打印。第一次面试真的有点紧张，刚开始敲键盘的时候手都在抖。这个题其实是《剑指offer》上比较经典的题目了，还好我之前刷了一遍。所以在草稿纸上简单画了一下，就思路就比较清晰，给定两个栈，分别交替存储每层的节点。给面试讲了一下大致思路之后，就开始写代码了，为避免沉默的尴尬，一边写一边给面试官讲具体的思路。具体的代码可以参考牛客网-剑指offer-z字形打印二叉树，这里就不写了。

做完之后面试官让我计算一下复杂度，因为每个元素分别入栈和出栈一次，时间复杂度是O(N)。栈里存储的元素也不会超过N，所以空间复杂度也是O(N)。复杂度的计算感觉要求不是很严格，给出答案后面试官就没说什么，然后继续下一题。

第二题，图相关，找到最大的好友圈。给定N个club，每个club里有人员的ID，找出其中最大的好友圈。什么算好友圈呢， 举个例子比较容易理解：

有3个club，其中每个club拥有的会员如下：

clubI: [1, 2, 3]

clubII: [2, 3, 4]

clubIII: [5, 6, 7]

因为2和3都属于club1和club2，所以1,2,3,4都属于同一个圈子。最大的好友圈数量就是4。

看到这个题的第一反应是深度优先遍历（DFS），要做DFS的话，肯定得用字典，每个key对应一个list，然后遍历就好了。但是怎么设计key和list，还没想好。因为不想让面试陷入太长的尴尬期，就决定开始写。最初的想法是以人员ID作为key，club作为list，遍历每个人拥有的club id，再根据该id遍历该club下的人数，累加起来。但后来发现这种思路的复杂度太高，写起来也比较麻烦，大概写到一半后，面试觉得这样复杂度太高了，让我先停一下，让我算算这样做的复杂度，我估计了一下，没想好，反正就是很高。面试官让我再换个思路，想个简单一点的，我突然脑洞一开，觉得，我把他们每个club当个集合，求下并集和交集不就行了吗？如果两个集合有交集，那就合并，没有交集就不合并，代码很简洁，感觉几行就能写完。突然为自己的脑洞鼓掌….但是面试官又问，这样做的时间复杂度呢？最差的情况每两两集合做交集，这一步复杂度为O(N^2)，再求并集，至少O(N^3)。O(N^3)实在太高了，面试官又让我想想简单一点的，但是时间快到了，然后面试官就直接开始指引我了，把每个人的ID当作图的节点，用领接表来表示从一个点到另一个点可达，已经遍历了的点就标记一下，直到所有的点都被标记。面试官最后让我说这个算法的复杂度，我算了算，O(N)，确实好多了，代码也不用写了。

最后再问了问面试官部门的业务，然后就结束了。从头到尾面试官都挺和蔼的，感觉很不错。

二面

一面和二面是没有关系的，反正就是换个人来做题。其实我的二面应该是一面，但因为第一天把他放鸽子了，所以HR在第二天重新安排了面试。

感觉比上一个面试官要严肃一点，一来就直接做题，还说，“我们搞快点，尽量在45分钟内结束。”（HR定的是一个小时）。第一个完全没见过，叫格雷码（Gray Code，后来发现leetcode上有原题），传入一个N，要求返回第N行的格雷码。格雷码是这样的：

2: 00 01 11 10

3: 000 001 011 010 110 111 101 100

4: 0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000

他和二进制很相像，但是每次只变化一位。

完全没见过这种题（刷的题比较少），真的有点紧张，一开始想从二进制入手，但想了想没思路，于是就想单纯的找规律。看了一会，终于看出规律来了，比如3是由在2的格雷码前面先加个0，再把2反转一下加个1，提炼出来就是G(N + 1) = (0 + G(N)) +(1 + R(G(N)),R表示反转列表。发现规律后就很好写代码了。为了方便，这题直接用python。

first = ["00", "01", "11", "10"]
   dp = {}
   dp[2] = first
   def grayCode(n):
       if n in dp:
           return dp[n]
       else:
           temp = list(map(lambda x: "0" + x, grayCode(n - 1))) + 
                       list(map(lambda x: "1" + x, grayCode(n - 1).reverse()))
           dp[n] = temp
           return dp[n]

之后照例面试官让我讲一下复杂度，如果以N表示位数的话，时间复杂度就是O(N * 2 ^ N)，因为反转字符串需要花费2^N，空间复杂度是O(2^N)。这个时间复杂度挺吓人的，但是面试官也没说啥，就继续下一个问题。

由于时间问题，第二个问题面试官没有让我写代码了，只是说下思路和计算复杂度就行。问题是，给定一个整数数组，求子数组的数量，要求子数组的元素个数大于等于2，且顺序不能变。比如[1,2,3,4,5], [1, 2]或[1,3]是他的子数组，但是[2,1]不是。所以不能是简单的排列组合。

我的思路是等差数列的求和，

比如个数为2的时候，计算公式： F(2) = (n – 1) + (n – 2) + (n – 3) + … +2 + 1 = (n / 2) * (n – 1)

个数为3的时候， 递归，取出第一个元素后，对剩下的子数组又重复上面的计算。

这里感觉不是很严谨，还没有仔细验证，面试官就开始问下一个问题，求所有子数组中的递增子数组中长度最长的数组。

这里想了很久，没有想好，因为面试官先让我算子数组的个数，我潜意识里就以为是已经得到了所有子数组，要比较他们的长度和是否递增。最终还是没有想到解决方案，面试官说没事，面试就这样吧，语气也很友好。到面试快结束的时候才反应过来，其实没必要管所有子数组，只需要在原数组中查找最长的递增子数组就好了，但是具体怎么做也没思路，然后面试就结束了。

后来在leetcode上查了一下，有一个用动态规划的o(N^2)的解法，有个只需要O(NlogN)的解法要用到线段树，就直接放弃了，这里只贴下DP的解法吧：

class Solution(object):
    def findNumberOfLIS(self, nums):
        N = len(nums)
        if N <= 1: return N
        lengths = [0] * N #lengths[i] = longest ending in nums[i]
        counts = [1] * N #count[i] = number of longest ending in nums[i]

        for j, num in enumerate(nums):
            for i in xrange(j):
                if nums[i] < nums[j]:
                    if lengths[i] >= lengths[j]:
                        lengths[j] = 1 + lengths[i]
                        counts[j] = counts[i]
                    elif lengths[i] + 1 == lengths[j]:
                        counts[j] += counts[i]

        longest = max(lengths)
        return sum(c for i, c in enumerate(counts) if lengths[i] == longest)

三面

一二面结束之后就收到了三面的邀请，过了一天就开始三面。网上查的情况大多是三面只做一个题，结果我还是做了两个题。因为终面，面试官是个Leader，感觉得到他很有水平。一开始有个英文的自我介绍，因为有了一面时自我介绍的惨痛教训，所以这里稍微准备了一下，说得比较流利，结果面试官马上就开始英文问问题，聊聊为什么喜欢微软啊，还有项目啥的。没多久我就表示不行了，能不能说中文，他说OK，然后就切换到中文。

然后开始做题，和前两次在线编辑不一样的是，这一次做题让我打开本地的编辑器，他通过远程桌面看我做题。他问我平时用什么语言，我说C++和Python，他就让我用C++，于是我就打开了VSCode。

第一个题目是，写一个函数，验证输入的字符串是否是IPv4。IPv4的要求是有4段，每一段的数字在区间[0,255]内。这个题是蛮简单的，但是他要求我不能用任何STL的函数，string都不行，连字符串转int的方式也要自己写。但是写完之后还让我举出需要用到的测试用例，在不断举例的过程中，发现自己代码里存在着好多bug，最终改了好久，终于改完了。

bool judgeIPV4(char* s) {
    if (!s) return false;
    int digit = -1;
    count = 0;
    while (*s != '\0') {
        if (*s >= '0' && *s <= '9' && digit == -1) {
            digit = 0;
        }
        if (*s >= '0' && *s <= '9' && digit != -1) {
            int temp = *s - '0';
            digit = digit * 10 + temp;
            if (digit > 255) {
                return false;
            }
        } 
        else if(digit == '.') {
            if (digit < 0) {
                return false;
            }
            count += 1;
            if (count > 3) return false;
            digit = -1;
        } else {
            return false;
        }
        s++;
    }
    if (count != 3 || digit < 0) return false;
    return true;
}

这个题从算法上来说比较简单，但是需要考虑的情况很多，好多次我说我觉得没问题了，他还是让我再看看，果然还是有bug。。。最后一个bug是超过int范围了的问题。虽然磕磕碰碰了很久，但是最终还是完成了，又开始下一题。

我刚听到下一题的时候我内心是崩溃的，不是说好的三面只面一个题吗？？？结果还好，第二题是我见过的，真的是运气好。题目是给定前序遍历和中序遍历，重建二叉树。这个题的核心是知道前序遍历的第一个节点是root，中序遍历中在root之前的节点属于左子树，root之后的属于右子树。

#include<iostream>
#include<vector>
using namespace std;
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x): val(x), left(NULL), right(NULL) {}
};

TreeNode *rebuiltTree(vector<int> pre, vector<int> mid) {
    if (pre.size() == 0) return NULL;
    TreeNode *root = new TreeNode(pre[0]);
    vector<int> left_pre, right_pre, left_mid, right_mid;
    bool flag = false;
    for (int i = 0; i < mid.size(); i++) {
        if(pre[0] == mid[i]) {
            flag = true;
            continue;
        }
        if(!flag) {
            left_pre.push_back(pre[i + 1]);
            left_mid.push_back(mid[i]);
        } else {
            right_pre.push_back(pre[i]);
            right_mid.push_back(mid[i]);
        }
    }
    root->left = rebuiltTree(left_pre, left_mid);
    root->right = rebuiltTree(right_pre, right_mid);
    return root;
}

写完之后，他让我想想这个代码里存在的bug。我举了三种，首先是如果节点值超过了int的范围，第二是递归中占用的内存超过 了堆的限制，第三是如果有重复的元素。。。他问我有重复的元素咋办，我说那就没有办法重建了啊，他笑了笑说就这样吧，这也是一个待验证的问题。

总体下来感觉很愉快，最后他给我一分钟时间，让我有没有什么问题问他。前两个面试官我都是希望他们能介绍一下业务，这里我还是真的有问题的。其实我现在都没想好我到底找什么岗位的工作，因为我涉猎的领域比较多，机器学习、前后端、大数据啥的都搞过，课程设计还写过游戏，目前在算法和后端开发中纠结，感觉都能做，但都不是很精，如果深入学习的话，需要花大量时间，所以我就比较纠结该深入学习谁，于是我就问面试官我这种情况该怎么选择。毕竟这个面试官是leader嘛，在这行业应该很有经验了，所以希望得到一些他的看法。他的回答比较中肯，他说，如果你能得到这次冬季实习的offer的话，最好过来看看，我们这算法、大数据、研发都能做，你过来做了才知道你喜欢啥。但是比较遗憾，冬季实习肯定是没时间了，还好HR表示可以帮我转到夏季实习，但是等到夏季的之前，肯定就得早早的确定自己的方向了。

点击量：25797