首先感谢热心助人的崔同学，耐心给我讲解猿题库的面试风格，让我能安心只准备了算法和system design。不过算法也没准备，最近正常刷题而已；system design也只是复习了下搜狗的项目。相当于是裸面了。。。万幸其他方面一点都没有问，最后也拿到了实习offer。
一面
一面的面试官看起来不到30，应该是普通研发，当然很可能是准mentor。进屋介绍了下面试流程和公司，然后让我问问题。我觉得过不过都没准呢有什么好问的，所以接话茬问了几个面试流程相关的问题。
算法
都说猿题库主要考算法，我以为是暴力的上来就写题，这面试官不错，先让我自我介绍放松了一下，然后就说，“我们写个题吧”。
链表，交换两元素
给定一个单链表的头结点head，两个值v1、v2，在链表中找到这两个结点并交换。
跟面试官确定的信息：
- 有无prev
- Node的结构（val，next）
- 返回值
题目很简单，那很可能在考察边界条件和coding style；算法方面cc大神说的好，链表靠画图；交换数组需要记录前置节点，给头结点增加前置节点dummyNode，简化代码，也简化边界条件。
刚要写，面试官就拦住我，跟我说可以先聊聊思路，能先动嘴皮我万分感谢啊，，，“边界条件先不管，算法的主要过程是……”。面试官肯定之后才让我写代码。
算法很简单，直接看代码吧：
// define of Node(val, next)
public Node swap(Node head, int v1, int v2) {
// no need to swap
if (head == null || head.next == null) {
return head;
}
// no need to swap
if (v1 == v2) {
return head;
}
Node dummy = new Node(0, head);
Node prev1 = dummy;
Node prev2 = dummy;
Node prev = dummy;
while (prev.next != null) {
if (prev.next.val == v1) {
prev1 = prev;
}
if (prev.next.val == v2) {
prev2 = prev;
}
}
// no need to swap
if (prev1 == dummmy || prev2 == dummmy) {
return head;
}
internalSwap(prev1, prev2);
return dummy.next;
}
private void internalSwap(Node prev1, Node prev2) {
if (prev1.next == prev2) {
internalSwapNextTwo(prev1);
return;
}
if (prev2.next == prev1) {
internalSwapNextTwo(prev2);
return;
}
Node next1 = prev1.next;
Node next2 = prev2.next;
prev1.next = next2;
prev2.next = next1;
Node tmp = next1.next;
next1.next = next2.next;
next2.next = tmp;
return;
}
private void internalSwapNextTwo(Node first) {
Node second = first.next;
Node third = second.next;
second.next = third.next;
third.next = second;
first.next = third;
return;
}
写完代码，面试也是先让我拿着代码讲讲思路。这部分主要是免去面试官硬读代码的麻烦，也方便面试官考察你代码的模块性，甚至一些变量、函数的命名。算法主体刚才讲过，于是我一句话带过，重点讲了swap方法中的边界条件，然后面试官就开始自己看代码。之后又让我讲internalSwap方法的原理，我也是先讲算法主体，再讲边界条件。
矩阵旋转
面试官说这个题很常见，但是我只听说过，，，后悔自己当时没看。
给定一个
n*n的矩阵，元素为整数，将矩阵旋转。
跟面试官确定的信息：
- 是按照旋转后的顺序输出矩阵元素即可，还是要改变原来的矩阵
- 返回值
我只知道有矩阵旋转这道题，所以刚听完题目的我是懵逼的。那没办法，只能硬着头皮上。
这道题我开始没沟通好，没有问返回值，以为只要按照旋转后的顺序输出矩阵元素即可（控制循环顺序）。说完思路，面试官意识到我理解错了题意，耐心告诉我要返回一个矩阵。但也没有急着否定我的方法，而是问我这种方法的时间复杂度和空间复杂度。那就都是O(n^2)了，面试官就说也可以改变原来的矩阵，降低空间复杂度。
我想了一会，想到reverse操作一般是O(1)的，而且经常能通过各种reverse的组合达到神奇的效果。于是就想着先按照斜主对角线reverse一下，也就是斜翻——还差点；再按照竖中轴线reverse一下，也就是对翻，握草正好搞定。
我用3*3的矩阵跟面试官说了思路后，面试官又让我实验4*4的矩阵，，，我以为有问题，结果画完发现是正确的。面试官就说，“恩，实验了也对吧。这其实是个数学问题，跟矩阵的性质有关，你能不能证明一下？”我大学线代课都是睡过去的，跟面试管坦诚线代真的忘光了，于是就直接让我写代码了。
代码：
public int[][] transfer(int[][] matrix) {
if (matrix == null || matrix.length <= 1) {
return matrix;
}
if (matrix[0] == null || matrix[0].length <= 1) {
return matrix;
}
xiefan(matrix);
duifan(matrix);
return matrix;
}
private void xiefan(int[][] matrix) {
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < i; j++) {
swap(matrix, i, j, j, i);
}
}
}
private void duifan(int[][] matrix) {
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length / 2; j++) {
swap(matrix, i, j, i, matrix[0].length - 1 - j);
}
}
}
private swap(int[][] matrix, int x1, int y1, int x2, int y2) {
int tmp = matrix[x1][y1];
matrix[x1][y1] = matrix[x2][y2];
matrix[x2][y2] = matrix[x1][y1];
}
后面的过程跟上一题一样，分析时间复杂度与空间复杂度等。
网上更流行的解法是直接旋转一圈，我面试时也想到了，不过觉得不好推导，没有reverse的性质通用。不过我觉得需要掌握这种用法，也不用硬记，看过一遍key point，面试时很快能推出来。参考LeetCode：Rotate Image的解法2。
简单聊项目
两道算法题之后，时间就差不多了，面试官让我介绍下我在搜狗最满意的一个项目，我回答的非常乱，还好这次主要不是面试system design。然后面试官让我等一下二面就走了，我赶紧复习之前整理的项目介绍。
二面
二面的面试官，，，确实很帅，让我想起了去年9月份在nice的面试，不过面到一半去开会了，让我等20分钟，，，结果我等了一个小时。中间还有更尴尬的事情，不过这不重要，也不是人家故意的，面试最重要。
本来是先考system design，再考算法，不过system design考到一半面试官就去开会了，丢给我一道算法题，开完会也是先讲的算法题，所以这里先介绍算法部分。
算法
非递归版归并排序
只考了一道算法题，而且面试官说完题意，看我没有思路就先走了，留给我20分钟思考+代码。
知道归并排序吧？归并排序一般用递归实现，如果不用递归怎么实现呢？
跟面试官确定的信息：
- 返回值
对，才开始刷题的我也没见过这道题。但是过了一会也想通了，就是用循环模拟递归版归并排序的执行过程，算法描述如下：
- 申请数组B，大小为A.length
- 设segLen为1，定义长度为segLen的子数组为1个seg
- 每两个seg为一组，分别做2路归并
- 将数组B拷贝回A
- segLen = segLen * 2
- 如果segLen小于A.length，则回到步骤3；否则继续
- 返回数组A
因为面试官出去开会了，所以我直接写了代码：
public int[] mergeSort(int[] array) {
if (array == null || array.length <= 1) {
return array;
}
int[] arrA = array;
int[] arrB = new int[arrA.length];
for (int seg = 1; seg < arrA.length; seg *= 2) {
for (int i = 0; (i + 1) * seg < arrA.length; i++) {
merge(arrA, i * seg, (i + 1) * seg, seg, arrB);
}
System.arrayCopy(arrB, arrA);
}
return arrA;
}
private void merge(int[] arrA, int start1, int start2, int seg,
int[] arrB){
int l = start1;
int r = start2;
int i = start1;
while (l < start1 + seg && r < start2 + seg
&& l < arrA.length && r < arrA.length) (
if (arrA[l] <= arrA[r]) {
arrB[i] = arrA[l];
l++;
} else {
arrB[i] = arrA[r];
r++;
}
i++;
)
while (l < start1 + seg && l < arrA.length) {
arrB[i] = arrA[l];
l++;
i++;
}
while (r < start2 + seg && r < arrA.length) {
arrB[i] = arrA[r];
r++;
i++;
}
return;
}
后面也是分析时间复杂度和空间复杂度等。注意如何分析这道题的时间复杂度：外层循环O(logn)，内层循环O(n)，数组拷贝O(n)，所以算法整体是O(nlogn)。
system design
背景不表，精简描述如下：
学生每天都会做题，要求设计一个架构，学生做题后，能实时看到自己的排名、前100名的排行榜，作业量每天更新。
跟面试官确定的信息：
- 排行榜按照什么排序——作业量
- 作业量是计算作业次数还是总量——总量
有一些system design的题目很经典，在面试中经常出现。我不知道这种属于经典题还是面试官自己出的题目，反正我都没见过，也没准备，做起来是一样的。不过如果有精力，建议多看看经典案例，真的能学到不少key point。
题目概括起来有四个要求：
- 所有查询都是实时的
- 学生能查看自己的排名
- 维护排名前100的排行榜
- 作业量每天清零，从新计算
第4点没什么意思，分库分表，甚至每天清空一次数据库都可以，可以不考虑。对于高并发的系统而言，可概括为两个需求：
- 学生能实时查询自己的排名
- 排行榜能实时更新
我设计的方案以一个桶为核心——之所以想到桶，多半是因为面试前还在复习ConcurrentHashMap的源码。ConcurrentHashMap是java.util.concurrent包中的一个神器，也算是面试常考点，你知道它的size()方法是怎么实现的吗？我忘记了，不过我在书里的笔记讨论了三种方案：
- 维护size变量；每次有段更新时，同步修改size变量。并发瓶颈在于size变量上的锁，相当于退化回了串行更新。
- 不维护size变量，但维护每段的segSize；每次有段更新时，仅修改segSize；每次调用size()方法，把所有segSize加起来。可根据一致性要求选择不同的segSize加和策略：要求完全一致性就在计算时所处所有seg，那么调用size()方法时产生了并发瓶颈；要求弱一致性，可直接加和。
- 维护size变量；当segSize修改时，将size置为-1；调用size()方法时，如果size为-1，则重新计算size，同上；如果size不为-1，则表示期间未修改seg，直接返回size。方案3主要针对方案2，相当于缓存了size值，这样不需要在未修改segSize时重复计算size。
好好理解这三种方案，我的设计基于方案2.
需求1
对于需求1，相当于ConcurrentHashMap中调用size()方法的操作。不同的是，可能存在上千万个学生，对每个学生都维护size显然是不合适的，而不需要维护size的就只有方案2了。
具体来说，可以认为作业量有上限，一个学生不可能一天做无数作业。则可以维护一组有限的有序桶（桶内是否有序可根据读写比例调整），每个桶代表一段作业量的范围（桶的范围可根据并发规模设置，作业量频率高的桶可继续分成更小的桶，作业频率低的桶可合并成更大的桶），桶之间不重合。则：
当前学生的排名 = 当前学生之前所有桶的size之和 + 当前学生在其桶内的排名
需求1的实时性要求一般没有那么高，因为用户只看自己的排名，就算有一定延迟也不会影响用户体验，因此，每次用户查看排名都计算一次的消耗是可以接受的。当然，我们可以进一步优化，比如维护截止到每段开头的总排名R，不过这需要增加一个服务实时去维护该段之后段的总排名R'，很可能是得不偿失的。
需求2
称作业量高的桶为大端桶，作业量低的桶和小端桶。对于需求2，相当于要维护大端桶中的前100个学生。由于假定作业量是有限的，则可以从最大作业量所在的桶开始遍历，直到遍历非空桶，且已按照作业量递减的顺序遍历了100个学生为止，返回排行榜。
可以做一个优化——记录当前最大作业量maxCnt，则最大桶的上界不超过maxCnt，且最大桶的size也不超过阈值sizeThreshold，那么每次可直接从最大的空桶开始遍历。
可以继续优化——由于我们关心的是固定前100个学生，那么直接维护一个最大堆maxHeap是更好的选择。对于排行榜而言，显然只有插入和查询（取前100）操作，baseline模型相当于插入O(1)查询O(nlogn)；或者插入排序，则插入时O(n)，查询时O(1)；而最大堆插入时O(logn)，查询时O(1)。
由于作业量高的学生总是极少数的，所以大端桶的并发量要远小于其他桶，维护maxCnt和maxHeap的成本非常小，收益却相当可观。
最后，可以在maxHeap前加一层缓存，异步更新，以加速前端访问。
follow up
在基本的架构介绍完后，面试官又给出了几个follow up问题：
- 现在的服务都是单点的，如何解决单点故障？
- 你的桶要保存在内存里，发生了单点故障怎么办？
对于问题1，我把Hadoop的HA方案套上了。面试官似乎不了解Hadoop的内容，觉得我答的不错。对于问题2，我清楚分析了不应该把桶与服务保存在同一份内存中，而应该尽量让服务无状态，桶交给存储层，不需要关心桶的结构。把问题2转换成了问题3，“如何解决存储的单点故障”。
首先，HA的方案仍然有效。但老一套没意思，我就说可以换一种方案。服务端多实例，客户端挂载服务端的实例列表，写数据时让客户端维护服务端的数据一致性（全部写才算写成功），还顺带解决了读数据时负载均衡的问题；用事务id解决客户端写失败导致的一致性问题。
现在写面经的时候才发觉这里回答的并不好。这种方案的写负载太高了，而并发写时往往涉及同步问题，就更麻烦了。如果还是基于客户端挂载的方案，那么可以参照NRW策略，只需要保证R+W>N，就可以保证强一致性。不过总感觉还是不够好，比如这种设计没有考虑到可伸缩性，距离真正的分布式存储系统差距还非常大。
PS：
- N代表数据所具有的副本数。
- R表示完成读操作所需要读取的最小副本数，即一次读操作所需要参与的最小节点数目。
- W表示完成写操作所需要写入的最小副本数，即一次写操作所需要参与的最小节点数目。
总结
哎，面试完已经7点半了。从下午4点半开始，3个小时，还是挺熬人的，累累累，不过当场拿到offer十分满足。
最后询问面试官对我的评价：
- 反应快——可能因为看出来我后面两题都没做过却自己想出来了。
- 代码写的很好——受宠若惊啊，太不好意思了！！！
- 系统设计也不错，给出基本问题，能清楚设计出可行的方案，虽然可能没有怎么接触业界的方案，但自己想的方案也比较完整。
二面的面试官是部门总监（创业公司的总监都相当年轻），这么评价，程度上肯定有夸张了。不过方向上应该值得参考，帮助自己扬长避短。
我还询问了今天面试跟正式校招的难度差距。面试官说跟校招难度类似，略微低一些，但差距不大。我挺惊讶的，都说猿题库面试重算法，比较难，面试之前我以为自己一道题就会被轰走，没想到撑到了最后。。。第一场面试经历如此甜美，幸福幸福~
给自己的建议：
- 乖乖刷题，题量太小，碰到新题就龟速
- 听强爷的多练习表达，特别在系统设计上，如何做到条理清晰，吐字清晰，表现出自己的能力，这一点至关重要
- 尽量不要裸面了，这次多亏面试前碰巧看了相关内容，否则可能就挂了
- 菜鸡，不要膨胀！不要膨胀！不要膨胀！
本文链接：【面经】猿题库-2017年8月25日，散招实习生
作者：猴子007
出处：https://monkeysayhi.github.io
本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布，欢迎转载，演绎或用于商业目的，但是必须保留本文的署名及链接。
