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

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

一面

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

起手式

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

手撕代码

1. 写一个大数加法。

1

string add(string a, string b);

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

2. 利用上面的大数加法实现大数乘法

1

string mul(string a, string b);

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

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

1
2
3
4

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() 嘛？然后无了。具体右值引用的东西还得下来看看。