一共三轮电话面试,每轮至少两个算法题,第三轮是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表示可以帮我转到夏季实习,但是等到夏季的之前,肯定就得早早的确定自己的方向了。

点击量:25194

分类: 面试

2 条评论

pyro · 2020年8月31日 上午10:31

二面第二题,(n / 2) * (n – 1)不就是组合数嘛

Jingli · 2021年1月18日 下午4:11

能不能加个微信呢?微信号:AmazingLife0; 目前浙大计算机研二,也想去苏州微软,主要技术栈是前端。认识一下呗。

pyro进行回复 取消回复

电子邮件地址不会被公开。 必填项已用*标注