2021年4月20日 TEG 云架构部门面经


一面

这次面试我觉得算是我所有面试中(虽然也没面过几次)体验最好的,没有问一道八股,感觉问的全是和部门工作内容紧紧相关的问题。面试官人也很好,虽然问的问题一开始我都答不上来,但是他会一层一层地引导我。结束之后再来看,其实一共也没问几个问题,但是因为我太菜了,足足面了1个半小时。

起手式

  1. 按照常规首先做了个自我介绍。
  2. 问了问我之前在字节的工作内容。
  3. 看到我简历里写了自己动手实现过 raft,然后问了一下我的具体实现,以及我是如何利用 raft 做一个存储系统的。针对我的数据持久化又问了一些问题。最后得知我的 raft 并不支持动态添加节点,遂作罢。
  4. 我旁敲侧击了一下说自己最近在实现一个存储引擎(指 CMU 15-445 的 project),自己手写了 b+ tree 和 query executor 啥的。不过面试官得知了这个存储引擎是单机的之后便不感兴趣了。

手撕代码

  1. 写一个大数加法。
string add(string a, string b);

这个直接从最低位一次向前加就行,保留一个进位变量。这个就是要注意一下不等长的情况,以及最低位是从 string 尾开始。只要没不想我被前进方向绕昏了还是能很快写出来的。

  1. 利用上面的大数加法实现大数乘法
string mul(string a, string b);

一开始我本来想直接按照人类的思维硬怼的,但面试官说你这么写没啥意义,还是用分治法吧。

具体思路就是利用递归写分治法,每次将较长的那个数分割成两半,分别求乘积,再组合起来即可。

string part1 = mul(longer.substr(0, longer.size() / 2), shorter); // 高位
string part2 = mul(longer.substr(longer.size(), longer.size() - longer.size() / 2), shorter); // 低位
add_zero(part1, longer.size() / 2); // 给 part1 补 longer.size() / 2 个 0
ans = add(part1, part2); // 利用上面的 add 函数

这里要注意的仍然是方向的问题,不然会像我一样直接丢人。还有就是 string 的 substr 方法第二个参数是指定个数,不是结尾位置。某些语言的切片写多了就容易下意识地以为是结尾位置,如果是 C++ 的话那一般会让你传迭代器。

分布式 ID 生成器

设计一个分布式 ID 生成器,每次请求系统生成器会返回一个 ID,每次请求得到的是唯一且递增的。要求尽量做到高并发高可用。

  1. 一开始我的想法和 raft 类似,采用主从结构,每次都从 leader 请求 ID,请求之后 ID 递增,leader 再同步到每个 follower 上。然后面试官说这样 leader 就成为了瓶颈,如何优化一下。
  2. 在面试官的提示下得出了第二个方案。还是主从结构,但是 leader 向 follower 的同步变为了批量方式,就是让 leader 每次攒够一波网络热门生物视频 n 次递增 ID 之后再向 follower 同步。然后如果遇到了 leader 挂了需要更换 leader 时,新 leader 直接在现有 ID 基础上 +n+1 即可保证后续的正确性。不过这个方案在每个节点上还是存在很大的性能瓶颈,能不能再优化。
  3. 于是得到了第三个方案,那就是采用无主结构。现在想起来我自己的给的方案是错的,但是面试官并没有发现。晚上经室友提醒,这不就是雪花算法(snowflake)嘛(参考:某篇知乎),不过面试官貌似想让我答的不是雪花这种方法。

随机数产生器

这里用 rand(a, b) 表示生成一个在闭区间 [a, b] 之间的整数。

  1. 首先来了个简单的,问如何用 rand(0, 2^16-1) 构造 rand(0, 2^64-1)。这个还算简单,就是 rand(0, 2^16-1) 四次,然后在按位组合起来。(也就是进制转换的思想)。
  2. 然后问如何用 rand(0,6) 构造 rand(0,9),然后果不其然我答不上来,然后面试官进行了下一步铺垫,如何用 rand(0,6) 构造 rand(0,48),这个其实和上面的类似。rand(0,6) 产生一个数的概率是 1/7,rand(0,48) 产生一个数的概率是 1/49,这不刚好是平方关系嘛。和 1 类似,按照进制转换结合两个数即可(若第一个产生的数是 a,第二个是 b,那结果就是 7a+b,符合概率和数字分布)。
  3. 得到 rand(0,48) 之后,怎么用它构造 rand(0,9) 呢?不会,好,下一个铺垫,如何构造 rand(0,47)?那使用 rand(0,48) 生成一个随机数,如果产生的数是 48,那再来一遍,直到满足为止。
  4. 那么接下来怎么用 rand(0,48) 构造 rand(0,9) 呢?抛弃掉所有大于 9 的?不太现实。那就利用除法,抛弃掉大于 39 的就是了,然后再除以 4 就可以了(为什么是 39,因为 0-39 的概率是 1/40,0-9 的概率是 1/10,刚好是 4 对 1 的转换)。
  5. 以上过程就能用 rand(0,6) 构造一个 rand(0,9) 了。
  6. 然后接下来问了如何设计一个筛选器,按概率选择对象 A 和 B呢(A 出现的概率为 x,B 出现的概率是 y,x+y=1)。我说,就直接用上面的方法构造一个宽度很大的随机数产生器,随机出一个数看在哪个区域里即可。
  7. 然后将上面的两个对象扩展为 n 个数。遇上同理,每一个对象对应一个随机数区间,然后用一个哈希表之类的维护一下就行。

其他

有没有用过 C++11、C++17 啥的。写 C++ 的时候有啥使用右值引用的场景。然后我当时卡壳了没想起来,然后结束之后一想,这不就是 std::move() 嘛?然后无了。具体右值引用的东西还得下来看看。


文章作者: RinChanNOW
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 RinChanNOW !
 上一篇
C++ 类型萃取 C++ 类型萃取
背景最近在网上冲浪的时候注意到了 <cmath> 中 sqrt 这个求平方根的函数。与 C 语言中的不同,C++ 将它重定义为了模板函数。在使用过程中我发现,这个函数的模板特化只能用整数类型,如果是其他类型,则会编译报错。 #i
2021-07-31
下一篇 
用 Windows 开发遇到的各种问题 用 Windows 开发遇到的各种问题
自从之前那段实习结束之后,我的日常开发就转变成了 Windows 10 + WSL2 的方式。刚开始的时候还觉得特爽,等新鲜感过去,这种模式成为常态之后, Windows 以及 WSL2 的各种毛病都逐渐涌现了出来。为了防止我之后再次遇到又
2021-04-01
  目录