字节跳动 后台（基础架构）实习面经 （已收到Offer）

本来想投上海的实习，投简历的时候没留神投到深圳那去了，深圳面了两面转到上海，又面了两面，还好都是视频面试。

4.13白天投的简历，晚上就收到hr电话约了一面，字节效率还是很高的。

自我介绍，然后介绍实验室项目，包括核心技术，难点，遇到的问题等等。（20min）

海量数据，如何判断某一个数在不在里面？ 布隆过滤器 or 位图，详细过程

哈希表的实现？ 哈希函数，开链法，扩容机制

介绍一下平衡树和红黑树，说说区别？

介绍一下B树和B+树，说说区别？为什么数据库多使用B+树，而不是其他的数据结构？

跳表的原理和实现？

数据库事务ACID介绍一下，MySQL如何实现ACID？ 数据库我不太熟，就没多问

做个题，一个基因字符串，只由A、C、G、T构成，求该串中重复出现的、长度为10的子串。

这题没什么算法，就是哈希表的应用，思路即将所有长度为10的子串放入哈希表中。

优化：利用ACGT压缩字符串，即用2-bit表示一个char，同时可以由前一个子串进行位运算得到当前子串。

你有什么想问的吗？ 部门的工作内容（做数据库优化的），有多少转正的

面试官说你别走，等20分钟，还有一个同学来。。。。

自我介绍，介绍项目，同上。

代码的编译和执行过程？预处理、汇编器、编译器、静态链接器、可执行文件

动态链接什么过程？

Linux下查看符号表命令、查看端口占用命令、查看进程打开的文件命令：nm， netstat，lsof

找出占用80端口的进程？ netstat -nlp | grep 80

进程的通信方法？ FIFO、共享内存、socket。底层怎么实现的？

线程同步方法？ 信号量、锁

锁怎么实现？ 硬件锁机制，自旋锁CAS，mutex睡眠等待唤醒，rcu锁机制

容器有了解吗？CGroup是怎么实现的？

虚拟化和容器在资源隔离角度的理解？虚拟化有guest，要trap指令，页表隔离。容器只是限制资源使用，更加轻量。

LRU算法如何实现？双向链表保证有序，哈希表加快查找

TCP三次握手、四次挥手? 为什么不是三次而是四次？

数据库事务一致性了解吗？Raft协议了解过吗？ 数据库不熟。。

做题：LeetCode #53 Easy 最大子序和， 由于做过而且也不难，很快就写完了。

能实习的时间？ BASE？ 我说上海，他说要去上海得把简历forward给上海那边，面试可能得重来。。

自我介绍，介绍项目。

TCP可靠性怎么保证？ 超时重传、序列号、checksum

超时重传的timeout多大？你来设计会怎么实现？定时器如何设计？了解Linux内核中定时器的实现吗？

接收端发现序列号不对会有什么操作？如何保证数据有序？

Linux内存管理? 伙伴系统？为什么需要Slab？内存回收是什么过程？

访问一个虚拟内存地址可能会有多少次内存访问？Linux几级页表？TLB？

mmap机制了解吗？为什么mmap文件读写比read/write快？mmap的文件，写入中途断电会怎么样？

做题：二叉树的中序遍历（递归 + 非递归）。还好之前做过，非递归还想了一下，挺快就写出来了

还有点时间，继续做题：LeetCode #920 Hard 播放列表的数量： DP想了很久没想出来，跟他说了个DFS的思路，时间快到了

你有有什么要问我的吗？ 部门做的内容（Serverless, FaaS架构）

这一面难度就上来了，感觉发挥的不是很好。。

自我介绍，介绍项目。

上来聊会天，问问选择公司的基准啊，能来实习的时间啊，研三打算在公司还是实验室啊

然后问了几个问题，输入url之后到页面显示发生了什么？有哪些技术、机制等等？

我跟你能够视频通话、共享编辑器，里面又有哪些技术、机制？

HTTP GET POST有什么区别？ 我说我web不熟，他也笑了

做题：LeetCode 股票，题目刚打出来问我做没做过， 我说做过并讲了思路，他就换了一题= =

做题：有序矩阵中前K小的元素 （m * n, 每一行有序，求前K小）

一开始的思路是维护一个大小为K的最大堆，遍历所有元素过堆，时间O(m * n * log(K))，要求优化，并提示每一行是有序的。

在纸上画了有5到10分钟吧，终于想出来先把第一列加入最小堆，然后弹出最小，把这个最小数所在行的后面一个数加入堆，继续反复直到弹出了K个为止。时间O(K * log(m))。

你有什么要问我的吗？ 部门做的内容（视频分布式存储，容灾）

当天晚上问了HR说终面通过了，没有HR面，现在等OC中。。

4.30收到邮件offer了