【字节】暑假实习面经，三轮详解+归纳

体验了和美国公司不一样的面试，考察内容很全。写的比较详细，也当复习巩固了。答案不一定完全正确，欢迎指教，另求大米~

字节一面

-算法
给定一棵二叉树，求其中的最长路径。所谓路径是指，联通两个结点的最小边数。
E.g. 经过一个根节点的最长路径=左子树高度+右子树高度+2
> 我用的递归，遍历节点求高度，得路长

Follow up问速度优化；遍历树不用递归怎么写
> 我答的dp，memo结构用树，存高度（不是存路长），顺序用后序
> 遍历借助栈可以代替递归。递归/非递归遍历可以看下蠡口 94


-基础：
1. 说一下内存段页式管理
> 段页式管理是结合分段式管理、分页式管理的内存管理机制。
>> 分段式管理：计算机按程序逻辑结构划分内存区域，比如主程序、库函数会分得各自的内存区域，优点是有利于段共享。
>> 分页式管理：页（page）是由虚拟内存引出来的。虚拟内存映射到物理内存时是按page（页）-frame（帧）的对应关系，目的是通过加一层indirection来减少页表本身所需的空间，且可以提高内存分配、管理效率。

p.s. 我之前没听过段式管理，只答上来页式管理。
关于分段式管理，从linux进程内存layout的分布来看，text、data、heap、stack等区域划分可不可以理解成是段式管理？因为其中的mapped area、text、data区域是有共享机制的。这里我不太确定，有待指教。

. 1point 3acres 附：虚拟内存的作用：
1）安全：不同进程虽然有相同的虚拟地址(eg. 0x0~0xffff ffff)，但操作系统会将虚拟地址映射到不同的物理地址，保证了进程之间内存的隔离，从而保证了各自数据的安全性。
2）规模：对于一个32位的系统，进程寻址范围仅为0x0~0xffff ffff -- 也就是2^32byte，4GB的空间。如果一个进程需要8GB内存怎么办？通过虚拟内存的映射，进程可以访问超过4GB的内存。
3）效率：更灵活地管理内存。比如除了1)中隔离两个进程的内存，也能使两个进程共享同一块内存用于共同读/写，实现高速的进程间通信，mmap就是这样实现的。

^^ 个人理解，供参考。

2. LRU、FIFO是什么？
> 当缓存空间已满，需要为新来的数据腾出内存空间，采取的不同内存管理机制，
>> LRU（Least Recently Used）总是保留最近访问的数据。按数据最后一次访问时间排序 淘汰最小的；
>> FIFO（First In First Out）淘汰最先进入缓存的数据

3. 进程间通信的方式
> signal、pipe、mmap

3.1. ^哪种最快？
> mmap -- 因为内存共享，相当于直接读写，速度最快

3.2. mmap需要注意什么？
> 竞争(race condition)，需要mutex加锁

3.3. mmap用户态还是内核态？
.. > 内核态

4. 什么是文件描述符？
> 对文件的抽象

4.1. 文件描述符和进程有什么联系?
> 每一个进程有自己的文件描述符表

4.2. 一个进程打开第一个文件时的描述符是多少
> 3
>> 进程初始会有三个默认已分配的descriptor，0-standard input，1-standard output，2-error output，文件描述符在未分配的数字中从小往大分配

5. 说一下内存颠簸
> 页式管理下频繁换页带来的消耗

5.1. 怎么解决？
> SIMD, 优化代码时考虑spacial locality, time locality

5.2. 硬件层面怎么解决 -- 面试官问的时候憋着笑，说这是个脑筋急转弯。。
这个时候感觉气氛就比较轻松了。我实在不知就瞎说把CPU换成GPU
面试官说这也算，最直接的是：
> 加内存 =_ =


-系统设计：
设计一个缓存池/内存池
> 按大小类size划分
>> 数组存大小类的size，每一个size entry对应一个链表，链表每个节点就是一个内存块
> 分割合并机制
>> 内存块的大小随着划分会变化，经分割/合并之后的新区块插入到新的size entry下

-项目：
聊天室项目，掉线之后再登录，怎么收之前的消息。

--------------------------------------------
字节二面

自我介绍。比较意外地被问到刷题情况，听我说20左右面试官笑出了声。。
coding是共享屏幕，我临时找的线上编辑器debuger不太友好

-算法:
给一个链表排序，时间要求 O(n log(n))
> 我用的MergeSort， divide + merge
>> divide：找链表中点，用快慢指针。记得递归之前把返回的中点节点的next设为null
可以看下蠡口 148 Sort List

-基础：
数据库原理、底层实现
> 不会 =_ =
系统问的和一面差不多

--------------------------------------------
HR面

问了简历上的经历，未来的打算。当然还有雷打不动的送命题：还面了哪几个公司，如果都给offer选哪家
感觉不妙。。
面国内公司得准备下这个套路

--------------------------------------------

总结
技术面除了算法，还挺注重基础知识的，系统、数据库原理需要准备一下。系统的不少问题在《深入理解计算机系统》这本书里看过。
还有一个感受就是基础知识与实际操作的联系，比如加内存那个问题，感觉非常practical。
系统这块虽然内容很多，很多知识偏底层，但是从国内面试来看，实际问的最多的还是围绕内存。学习/复习系统基础的话着重看内存应该效率比较高。当然这只是我个人面试dp，仅供参考。
另外，问题偶尔也会先给场景，很多场景我都一脸懵，就厚着脸请面试官多解释一点，然后往相关的基础知识方向靠。

-------------------end---------------------

again，借写面经复习巩固一下。答案不一定完全正确，欢迎指教，

正在写其他几家的面经稍后发出来，希望有帮助。另，

新人求赏大米~

MackeyZheng 发表于 2020-5-23 14:56
送命题是啥意思，如何回答？

他们offer发出来不希望被candidate拒。一般就夸这个公司如何如何好，但注意不要拍到马腿上了，比如一个常规操作996的公司就不能说“我想去贵公司因为wlb非常非常好”。。。应该说“有拼劲，很充实，可以学到很多东西！”

为什么实习要考系统设计，要求这么高吗

lz写的很用心，赞一个

楼主的timeline是什么样子的呀

Constance12 发表于 2020-5-20 10:49
楼主的timeline是什么样子的呀

4月底投
5.4   一面
5.11 二面
5.14 hr面

想请问楼主面的哪个部门哪个组呢

楼主写得很棒，先赞一个！但我觉得Inter Process Communication是不是可以再加一个Socket, 这样答案比较完善～

看来国内实习坑还没满啊。

酸了...为什么lz只有两轮技术面呜呜呜
上周第三面被刷了，所有题都实现了只不过最后一题没有达到optimal...而且前两轮所有题都是秒解...
我真的醉了

我在hr面也遇到了你说的那个送命题，答得非常差，就挂了。
我已经打算好，以后面国内的公司，一定要准备好一套合情合理的彩虹屁！

不错，马一个