首先感谢热心助人的崔同学，耐心给我讲解猿题库的面试风格，让我能安心只准备了算法和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分钟思考+代码。

知道归并排序吧？归并排序一般用递归实现，如果不用递归怎么实现呢？

跟面试官确定的信息：

• 返回值

对，才开始刷题的我也没见过这道题。但是过了一会也想通了，就是用循环模拟递归版归并排序的执行过程，算法描述如下：

1. 申请数组B，大小为A.length
2. 设segLen为1，定义长度为segLen的子数组为1个seg
3. 每两个seg为一组，分别做2路归并
4. 将数组B拷贝回A
5. segLen = segLen * 2
6. 如果segLen小于A.length，则回到步骤3；否则继续
7. 返回数组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。

题目概括起来有四个要求：

1. 所有查询都是实时的
2. 学生能查看自己的排名
3. 维护排名前100的排行榜
4. 作业量每天清零，从新计算

第4点没什么意思，分库分表，甚至每天清空一次数据库都可以，可以不考虑。对于高并发的系统而言，可概括为两个需求：

1. 学生能实时查询自己的排名
2. 排行榜能实时更新

我设计的方案以一个桶为核心——之所以想到桶，多半是因为面试前还在复习ConcurrentHashMap的源码。ConcurrentHashMap是java.util.concurrent包中的一个神器，也算是面试常考点，你知道它的size()方法是怎么实现的吗？我忘记了，不过我在书里的笔记讨论了三种方案：

1. 维护size变量；每次有段更新时，同步修改size变量。并发瓶颈在于size变量上的锁，相当于退化回了串行更新。
2. 不维护size变量，但维护每段的segSize；每次有段更新时，仅修改segSize；每次调用size()方法，把所有segSize加起来。可根据一致性要求选择不同的segSize加和策略：要求完全一致性就在计算时所处所有seg，那么调用size()方法时产生了并发瓶颈；要求弱一致性，可直接加和。
3. 维护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. 现在的服务都是单点的，如何解决单点故障？
2. 你的桶要保存在内存里，发生了单点故障怎么办？

对于问题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 国际许可协议发布，欢迎转载，演绎或用于商业目的，但是必须保留本文的署名及链接。