7.11 一面

1.实现双向链表，并实现插入、删除和查找功能

因为面试官是 C++ 的不太懂 Java，一上来就让做道题考察下语言掌握情况。就从 LRU 那道题中把 DeLinkedList 抽出来即可。

2.MySQL 为什么要用 B+ 树作为索引的存储结构

写完链表题就问我数据库、网络、数据结构和操作系统我最熟悉哪一块，我说最熟悉 MySQL 数据库。
回答了 B+ 树的三点优势（减少 IO 次数，查询时间稳定，便于范围查询）
然后追问我为什么不用 BST，回答说 BST 可能退化为 O(n) 的时间复杂度，并且与 B+ 树相比深度会很大。
追问我为什么深度大了不好，回答说会增加 IO 次数，他说不对。空气安静了好久，我说暂时想不到比较合理的答案，他解释说要从磁盘 IO考虑，同一层树是顺序 IO，不同层是随机 IO，B+ 树的度更大也更矮，随机 IO 次数是有限的，大多数 IO 都是顺序 IO。

3.MySQL 是如何实现 ACID 的

我觉得这个问题想答好需要非常长的篇幅，我只回答了使用 redo log 保证持久性，四种隔离级别以及 RR 级别的实现来保证隔离性，
追问为什么 redo log 不直接刷盘，还需要弄一个缓冲，我说为了保证速度，还讲了一下 redo log buffer 的刷盘策略。
追问哪些 SQL 语句使用当前读，这个比较容易。

4.说一下熟悉哪些排序算法（O(n^2)复杂度的就不要说了）

我说最熟悉快速排序，堆排序和归并排序也了解，大致说了一下快排思路，他说你说得太笼统了，细说一下。我说我给你写一下吧，他很开心说好。
写完问我知道为什么快速排序那么快吗？我愣了半天没想好怎么回答，这里想请教各位快排和堆排序时间复杂度是同一级别的，为什么快呢？
追问堆排序时间复杂度，如何实现，调整堆的时间复杂度，比较容易。

5.虚拟内存讲一下

先说了为什么需要虚拟内存，然后讲了物理地址和逻辑地址映射和 MMU（内存管理单元），每个进程都有页表来记录这个映射，还问了他需要深入讲解一下页表如何优化吗？到这里想炫技快表和多级页表的，他说到这就够了，不用再说了。

6.反问

问在北京的主要业务是做什么的，他说不太清楚，他是深圳这边的。
问我的知识还有哪方面比较欠缺，他说没啥特别欠缺的，就是代码抽象度再高一些就好了。

7.23 二面

1.项目

全程都在撕项目

2.八股文

在撕项目的时候问到一句 Redis 的 zset 的底层实现。

3.算法

一道没见过的题目，让设计一个类，里面有 addNumber(int num) 和 getMedian() 两个方法，每次通过 addNum 方法接受一个数字，让我能在 O(logn) 复杂度实现求中位数 getMedian
思路是使用两个优先队列，一个是大根堆另一个是小根堆，通过这两个堆的堆顶元素来计算中位数。

4.反问

在北京的主要业务是做什么的，回答说有基础架构部门和业务部门，他对业务部门不太了解。
还有哪些知识需要进一步学习提高，说项目准备得挺好的，题目是 hard 也做出来了。
问还有技术面吗，回答说下一轮是 HR 面。

二面结束10分钟就收到 HR 面邮件啦！有兄弟知道虾皮 HR 面会不会刷人呢？