发布于 

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,答曰”会“。

结束。


本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议,转载请注明出处。

本站由 @RinChanNOW 创建,使用 Stellar 作为主题。