2022年1月21日 Singularity Data 存储引擎工程师（实习）面经

2022年1月21日 Singularity Data 存储引擎工程师（实习）面经

提前总结

由于是第一次面试这种基础软件的岗位，一开始有点小紧张，面对面试官的问题想尽快一股脑把想说的说出来，自己的思维及其跳跃，面试官问这个我直接延伸到另一个地方去了，导致在语言的组织上变得十分混乱，把面试官都给整蒙了，后面才渐渐稳定下来。

两次面试的面试官都很好，整个面试过程更像是一次技术交流，这也是我后面渐渐放开的原因。

简历上的一个败笔是带上了 MiniOB 这个项目。在面试中问到这个项目的时候，我才意识到，这个项目值得说的东西太少了，这整个项目也是个玩具级的软件，和真实的工业产品的设计理念大相径庭。在介绍项目的时候我就觉得很尴尬，面试过程中甚至产生了抵触情绪，我觉得面试官肯定也被我整尬了。

一面

项目介绍

首先就是 MiniOB。一开始大概介绍了整个项目的背景和整体的功能分布，然后由于我一开始的迷惑操作，导致在面试时直接开始了现场优化当时实现的功能。

• 首先是优化 NULL 类型的实现，我引入了一个叫 NULLMAP 的 BITMAP 来表示每一个记录中某一个字段是否是 NULL。这里由于我的思维有点跳跃导致面试官一开始没 get 到我的意思，便扯了一会儿皮。
• 然后介绍了下 TEXT 类型的实现，这里也由于我的思维混乱，被面试官指出了几个我实际上是实现了的但是没有说出来的要点。
• 最后又问了下我多表查询的实现。虽然当时这一部分是我实现的，但是我确实有点忘了。几经想打开源码复习一波，但是被面试官制止了。看了代码才想起来，是先把两张表查出来再做笛卡尔积，这里实现的大头是怎么实现笛卡尔积，但我面试时的时候直接忘了。

然后就是 TiDB Hackthon 的项目 MVCC 时光机。得益于头一天 TiDB Hackthon 获奖选手的采访，我对这个项目不管是我自己的部分还是其他人做的部分都比较熟悉，所以这一部分倒是信手拈来。我就一五一十地告诉面试官我负责的 MVCC Query 是如何实现地。

算法题

Leetcode 230.二叉搜索树中第K小的元素，一开始没看到二叉搜索树所以想用搜索+最小堆来做。后来发现这不是二叉搜索树嘛，那直接中序遍历到第 k 个节点不就行了。比较简单，没什么好说的。

分布式哈希表的设计

这里面试官想要的设计是，客户端直接请求到存储节点，而不是通过一个统一的 master 来请求。我 get 到面试官的意思后就想到的是一致性哈希，但是为了不让面试官认为我是个背题家，就没有提到一致性哈希。后来一想，面试官可能就是想听到一致性哈希，这么一来我还挺蠢的。

一些设计：

• client 首先从 master 获取到所有存储节点的分布等元信息，并维持在 client 的 cache 中。
• client 中缓存了各个节点的地址信息与哈希算法。
• 当请求某个节点失败时向 master 请求更新节点信息。如果使用一致性哈希算法怎么不需要这么做。

提问

问了一些流式数据库的设计与实现，它们与传统数据库的区别。

二面

自我介绍

二面一开始进行了一些自我介绍，我的学历，专业，并介绍了在分布式与数据库领域中我的一些学习和工作。

实习经历介绍

一开始介绍了在字节的实习经历。面试官问了云游戏平台的一些具体实现。

然后介绍了在腾讯实习的工作。QQ 频道消息通知的开发经历，以及 QQ 频道机器人的一些实现，最后是 QQ 频道机器人平台的介绍。

面试官也和我交流了他认为应该怎么设计这些系统。

项目介绍

又将 MiniOB 与 MVCC 时光机介绍了一遍。不过这次 MVCC 时光机讲的更多，把 FLASHBACK 和 GC 相关的功能也讲了。

LSM-Tree 相关

感觉应该是从 TiKV 延伸到 RocksDB 再延伸过来的，主要问了这些问题：

• LSM-Tree 的整体结构，以及各个部分的结构。
• LSM-Tree 操作的 workflow。
• LSM-Tree 的一个 SST 中是否会有重复的 key。不同的 SST 中会有吗。对于前者，显然是不会；对于后者，面试官说得看具体实现，不含重复 key 的实现是有的。
• 存储系统宕机之后怎么办。

算法题

给两个等长的 01 数组，找出它们拥有相同 01 个数的最大公共下标区间的长度。比如 101 与 010，它们的相同 01 个数的最大公共下标区间为 [0, 1]，长度为 2（10 与 01）。要求时间复杂度为 O(n)。

利用前缀和可以轻松找到 O(n^2) 的算法。但是要求 O(n)，所以需要继续优化。

经面试官的提示，得出以下算法（以 A = [0,0,1,1] 与 B = [1,1,0,1] 为例）：

• C = A - B = [-1,-1,1,0]。问题转换为 C 的最长的和为 0 的子数组。
• 求得 C 数组的前缀和数组 p = [-1,-2,-1,-1]，向 p 最前面增加一个 0 得到 P = [0,-1,-2,-1,-1]。问题转换为在 P 中找到两个下标 i, j (i <= j) 使得 P[i] == P[j]，怎么答案 ans = max(j - i + 1)（此例子中为 3）。一些细节：
  • 正确性：前缀和数组两个元素相同代表它们之间的所有元素的和为 0。
  • 为什么要填一个 0：处理前缀和数组中有元素为 0 的情况。
  • 具体实现可以依靠哈希表，前缀和数组也不用真正的创建，迭代一个变量即可。

Python 实现：

1
2
3
4
5
6
7
8
9
10
11
12

def func(A: List[int], B: List[int]) -> int:
    C = [A[i] - B[i] for i in range(len(A))]
    presum = 0
    hashmap = {0: -1}
    ans = 0
    for i in range(len(C)):
        presum += C[i]
        if presum not in hashmap:
            hashmap[presum] = i
        else:
            ans = max(ans, i - hashmap[presum] + 1)
    return ans

最后

面试官问我想做存储还是计算，我说存储。然后他又问了下可以做计算吗，了解过计算吗？看来是想让我做计算相关的。我说了解的不多，他说没关系。

最后问我会不会 Rust，答曰”会“。

结束。