第一轮面试

（由于当时在搬家记不太清了）

算法题

• 分析复杂度

  分析下面数据结构的插入的复杂度，A0-Ak 是一个数组，他们要么为空，要么分别存储 1，2，4，8 这么多个元素，如果当前数组满足不了插入，则将当前数组的元素和新插入的元素合并到下一层。每个数组内部都是有序的。新来一个元素先插入 A0，如果 A0 已经有 1 个元素，根据规则，则将两个元素归并插入 A1；如果 A1 有 2 个元素，则将 4 个归并到 A2，诸如此类。

  A0: [1] A1: A2: [4,5,8,10] A3: [2, 6, 9, 12, 13, 16, 20, 25]

• 给定\(n\)段原木和指定木材数量\(k\)，求满足数量要求的最长木材长度\(l\)（整数，二分法，拓展思考分数形式，这个没想出来，但是分数形式是必定有解的）。

  有一些原木，现在想把这些木头切割成一些长度相同的小段木头，需要得到的小段的数目至少为 k。当然，我们希望得到的小段越长越好，你需要计算能够得到的小段木头的最大长度。

  木头长度的单位是厘米。原木的长度都是正整数，我们要求切割得到的小段木头的长度也要求是整数。无法切出要求至少 k 段的,则返回 0 即可。

第二轮面试

面试问题有以下

• 问数据库中 ACID 的实现方式。
• 问进程上下文切换的原因，以及线程切换轻量一些的原因（同进程内共享地址空间？）
• 锁的种类，问了自旋锁
• 用户发起一次 I/O 操作（如 read、write）从用户空间到最底层的过程（操作系统内核）
• Raft 协议中，A、B、C 三个节点，若 A、C 之间出现网络隔离，是否会在 leader election 中出现问题

算法题

• 最长不重复子串（DP）

  标题：最长无重复子串

  无重复子串指：子串中每个字符都不相同

  例如：s = 'aaabcdddd' 最长的无重复子串为'abcd'长度为 4

• 任意两个节点求最近公共祖先

  假设 p/q 是二叉树上的两个 node，求离他们最近的公共的 parent

• 多线程 Hash Table（不会）

  写一个支持高并发访问的 hash table(int)

• 链表形式快排

  划分链表

  给出一个链表和一个值 \(x\) ，以 \(x\) 为参照将链表划分成两部分，使所有小于 \(x\) 的节点都位于大于或等于 \(x\) 的节点之前。两个部分之内的节点之间要保持的原始相对顺序。

  \(1→4→3→2→5→2\) 和 \(x=3\),

  返回

  \(1→2→2→4→3→5\).