字节飞书面试总结

20 April, 2022

2022 年夏季在字节跳动飞书组实习的面试内容。

一面

• 自我介绍

  • 提到了从 C++ 转 Rust，简单讲一下 Rust 相比 C++ 的好处

    实现统一，不会出现不同平台不同行为的情况（其实还应该说一个不太容易碰到 UB）

    包管理好，C++ 依赖管理烦死人

    内存安全

    函数式风格，优雅、性能好

• 聊项目

  • 提到 Box<T>, Rc<T>, Arc<T>

    我估计他是准备问的，结果我提到了我开发的心路历程，顺便就把这个讲了

  • 提到多线程

    • 用的哪个运行时，Tokio 还是 Async-std？

      thread::spawn（笑）

    • 看过 Async 吗

      看过一点

    • 简单讲一下 Future

      记不太清了，应该是一个 enum，去 poll 的时候视里面有没有 Ready 来返回值或者通知还没好

  • 提到 KDTree

    • 提到父亲孩子相互引用

      推测是想问 Rc<T> 和 Weak<T>，我那个求交加速是不需要的，但我提了一句

    • 提到第一个切分维度的选择

      我的回答是选 max - min 最大的，也提了可以选方差最大，但我没实现

      • 问为什么选取方差大的维度

        一开始的嘴瓢了，回答是保证两边一样多，然后发现错了（因为必定是一样多的）

        正解是保证点与点之间距离不要太近

  • 提到其他智能指针如 Cell 和 RefCell

    RefCell 用过，Cell 没用过

    就是内部可变性

  • 提到 BTreeMap 的实现

    那段网特别差，我基本没听清楚

    我就说了下 B-Tree 是动态数目子节点，有分裂-合并操作的，对有 Cache 的现代 CPU 而言性能更好

    • 和什么比性能更好

      和传统二叉树，因为它一次性拿比较多的数据出来可以填到一个 Cache Line 里

  • 提到 Send, Sync

    分别提了一下语义（准备一下还是管用XD）

    提一下多线程的时候需要加上，编译器会自己推断一个结构是否 Send, 是否 Sync

    具体怎么推断我也不知道

  • 提到了 Mutex 和 RwLock

    • RwLock 在哪里比较好

      并发读很多的情况

    • Mutex 在哪里比较好

      一时间没反应过来，那边 hint 了 RwLock 怎么实现

      我说一个读标志位、一个写标志位

      然后意识到是因为写的时候 Mutex 只检查一个锁而 RwLock 要检查一个读锁一个写锁，开销很大

  • 提到了进程间通信的方式

    面试官说是八股文，我还真不知道，只说了共享内存和 mpsc

  • 一个比较具体的提问，一个 process 下两个 thread，一个 thread 是否可以访问另一个 thread 栈上的内容？

    我说拿到栈指针就行，但是这个东西不应该这么设计

    最后问面试官这题答案是啥，发现其实就是想考一个 process 下是一个单独的地址空间……所以就是如果拿到指针就可以，拿不到还是不可以

    那问题在于栈这东西就不应该共享啊……共享堆内存才是合理的

  • 算法题，01背包

    直接把输入省了，硬编码了输入去写

    用了 [Option<i32>; MAX_NUMBER] 来保存背包，然后用了一些 Rust 的语法特性比如 Option::map_or 之类的，反正是写对了