第一题是按序输出格雷码。输入的参数是格雷码长度N。

刚上来可能紧张，没什么思路。面试官问了我一下，就提示我是不是可以从前一个序列中找到规律。我一下子反应过来，就跟他说了我的想法。

一般在交流后如果觉得你的思路没问题，就开始在白板上写代码。要求是能运行的代码。

第二题是最长递增子序列。Longest Increasing Subsequence - LeetCode
我首先想到动态规划方法，就跟面试官说了一下。他说可以的，你想一下方程吧。
想好后和他交流了一下，这次没让我写代码，但让我继续优化。不过这次始终没想起来。

 

第一题:  格雷码

第二题：最长递增子序列 （动态规划O(n^2), 二分优化到O(nlogn）

也就几分钟之后开始做题。这次题目是求二叉树中任意两点形成的路径上节点（每个节点有个值）之和的最大值。（Leetcode 124）
我想到方法后也是先跟他确认，然后开始写代码。写的时候我还问他节点值是否可能为负。
写好代码之后他会仔细看代码。（一面面试官也很仔细）几乎是一行一行地读。
这次读代码解释代码的时间比较久。就没有第二题。

三面应该是个Leader？也是先聊天，还说之前去南大宣讲我记不记得他。哈哈，我说你这么一说我才想起来。
他就空着手过来，不像一二面面试官（顺带一提，二面面试官用的 MacBook + macOS）。
就闲聊了几句，我就记得问我觉得自己的优势是什么。然后问了前两面问了啥题，然后开始做题。
这次这个题目罗里吧嗦的：
有三个转盘（A-Z），处于某一个状态start，比如MSF。求出将start转到另一个状态target所要转动转盘而形成的字符串序列。比如MSF->OFC：[MSF,NSF,OSF,OSE,...,OFC。此外，有另一个参数BlockList，是个字符串列表，输出的序列不能包含BlockList中的字符串，即转动时不能经过这些状态。
问我有没有问题他就出去了，我就开始写，我就组合了一个BFS和递归写了一个，有点乱，白板上也不好改。没过多久他就回来了。开始也像前两面一样逐行读代码，解释。我也不知道对不对🤦‍♂️。看他的表情也不知道对不对。
不过这次因为快到下班时间了，就很快结束了。

 

一面

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

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

 

BFS遍历题目

 

 

第二题，图相关，找到最大的好友圈。给定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] = firstdef 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] = tempreturn 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 Nlengths = [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的范围，第二是递归中占用的内存超过 了堆的限制，第三是如果有重复的元素。。。他问我有重复的元素咋办，我说那就没有办法重建了啊，他笑了笑说就这样吧，这也是一个待验证的问题。

 

面试结束后不久就收到了hr电话，通过了