| title | shortTitle | description | tag | category | head | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
字节跳动后端面经：一面+二面+三面+HR 面 |
字节跳动后端面经 |
字节跳动后端面经：一面+二面+三面+HR 面 |
|
|
|
球友们好，今天给大家分享一份牛客上的优质面经，收录在《Java 面试指南》的优质面经模块下，包括一面+二面+三面+HR 面，同时，把答案贴出来供大家参考，目标是大厂的球友们注意了，知道重心在哪里。
- 自我介绍
- select、poll、epoll？
- epoll的两种触发模式？
- TCP三次握手过程，有什么状态，状态机如何变化？
- TCP握手的目的有哪些？
- 什么是 TIME_WAIT 状态，为什么需要 TIME_WAIT 状态？时间是多久，为什么？
- TCP 和 UDP 的区别？
- TCP 拥塞控制？慢启动的时候窗口在什么情况下会增长？为什么会呈指数增长？
- Linux 中一个进程的虚拟内存分布长什么样？内核空间+用户空间（6 种不同的内存段）。
- 为什么要用虚拟内存？
- 虚拟地址映射为物理地址的过程？
- 进程和线程的区别？哪些资源是线程共享的，哪些是线程独占的？
- 使用线程有哪些好处？
- 使用线程有哪些坏处？
- 进程有哪些同步的机制？
- 协程的实现原理？无栈协程和有栈协程？独立栈和共享栈？
- 什么是稳定排序？
- 聊项目，难点，怎么解决？
- 手撕：189.数组循环右移。将一个长度为 n 的数组，循环右移 k 位，要求时间复杂度为 O(n) 空间复杂度为 O(1) 。
思路：三次reverse，reverse 前 k 位，reverse 后 n - k 位，reverse 整个数组
小插曲： 一开始使用的是库中的 reverse 函数，写完后面试官要求自己实现这个 reverse。由于当时时间不多了又加上紧张，写完后答案一直有错，也没找到错在哪。面试结束之后，没有马上退出会议，想把这个错找出来。结果过了两分钟，面试官又回来了，说是下一个面试的还没到，就回来看看我。然后在他眼下把代码改对了。也算是有惊无险吧。
- 自我介绍
- 进程有哪些状态？
- 进程的调度算法？
- 进程间的通信方式？
- 进程上下文切换做了哪些事？流程是怎么样的？
- 进程在哪些场景会进行上下文切换？
- 上下文切换为什么资源消耗会比较高？消耗在什么地方？
虚拟内存、栈、全局变量等用户空间的资源，还包括了内核堆栈、寄存器等内核空间的资源。
- 上面哪个资源的切换效率更低？
- 为什么虚拟内存的切换效率更低？
因为切换后 TLB 无法被命中
- 常见的排序算法？
- 堆排序原理？
- 归并排序原理？
- LRU缓存？为什么要链表？为什么要用哈希表？为什么要用双向链表？既然哈希表中已经存了 key，为什么链表中还要存 key 和 val 呢，只存 val 不就行吗？
- linux 命令，如何查看主机 CPU 核数？如何查看内存还剩多少？
- 如何查看哪个进程正在监听 80 端口？
- netstat -n 是什么意思？-a 是什么意思？-p 是什么意思？
- TCP 为什么要三次握手和四次挥手？
- 为什么 TCP 第二次握手的 SYN 和 ACK 要合并成一次？
- SYN Flood 的原理？有哪些防范的方法？
上面三个问题问了十多分钟。看起来简单，但面试官会顺着你的思路一直往下问，问得特别深，差点给问崩了。
下面问了几个 C++ 的问题。字节不是用 go 吗？
- 智能指针有哪些？主要解决什么问题？
- 指针和引用的区别？为什么要引入引用？好处有哪些？
- 重写和重载的区别？
- 手撕：236.二叉树的最近公共祖先（最后只剩十分钟，要求十分钟之内写出来）。
- 自我介绍
- 聊项目
- 问了一会儿八股，具体问题忘了。
- 如果让你设计一个视频网站，所有用户都可以上传自己的视频，也可以观看别人的视频。你作为后端要怎么设计？用户目录怎么设计？
这个问题聊了20分钟。因为没做过相关的东西，感觉答得一般。刚开始答了很多个方面，感觉面试官都不太满意。但是面试官会一直引导你回答。最后反问的时候面试官也说这个问题没有固定的答案，这个问题涉及的方面非常多，从接入到怎么去存储以及怎么去实现一些具体的逻辑功能，这些方面很难一下子就能想出一个很全面方案。问这个问题主要还是想看看我的一个思考的过程。
- 手撕：234.回文链表
- 自我介绍
- 家在哪？
- 为什么选择这个专业？
- 有没有校外实习的经历？
- 研究生期间的成绩？
- 参加过什么计算机相关的比赛？在团队中担任什么角色？
- 为什么选择我们这个部门？
- 对我们的部门有没有什么了解？
大概说了一下，然后 HR 给我介绍了一下这个部门。
- 想去什么城市？
- 有没有考公的想法？
- 职业规划是怎么样的？
- 有没有在面其他的公司？BAT 都有投吗？
- 能不能提前来实习？
- 反问：后续流程是什么？
内部讨论后，过几天会给答复。如果没过就等其他的部门来捞，过了的话会先发意向书，十月份左右谈薪资。有可能还有加面的情况（忘记问这个加面是好还是不好了，网上有的说会刷人，有的说是看看你能不能拿更高的等级）。
以下是某网友针对这些问题的个人解答，二哥做了简单的整理和归纳，有问题可以交流。
这三个都是多路复用方面的技术，而多路复用指的是多个 socket 复用同一个线程。
- level 模式：该模式就是只要还有没有处理的事件就会一直通知
- edge 模式：该模式是当状态发生变化时才会通知
客户端主动向服务端握手：
一开始客户端为 CLOSED 状态，服务端为 LISTEN 状态
首先客户端发送 SYN 报文，将 seq 置为 x，此时客户端状态转为 SYN_SENT
服务端收到后 SYN 抱文后返回 SYN+ACK 报文，将 seq 置为 y，ack 置为 x+1，此时服务器状态转为 SYN_RCVD
客户端收到 SYN+ACK报文，此时客户端已经知道双方的收发都没有问题，但为了让服务端知道故返回 ACK 报文，将 ack 置为 y+1，此时客户端状态为 ESTABLISHED，并可以发送数据
服务端收到 ACK报文，此时服务端已经知道双方的收发都没有问题，此时服务端状态为 ESTABLISHED
至此连接建立成功
确认双方的收发能力都没有问题，初始化序列号，确认窗口大小即 MSS 等信息
四次挥手客户端接受到服务端 FIN 报文后返回 ACK 报文的状态
可以防止 ACK 报文丢失，服务器没有收到会重复发 FIN 报文
而 TIME_WAIT 的长度为 2*MSL 这样 ACK 丢失了，FIN 再次发送，在这时间里客户端还能收到 FIN 报文
| --- | TCP | UDP |
|---|---|---|
| 连接 | 面向连接 | 无连接 |
| 可靠性 | 可靠 | 不可靠 |
| 数据流方式 | 字节流 | 报文流 |
| 速度 | 慢 | 快 |
TCP 拥塞控制由三部分组成
- 慢启动：每次收到一个 ACK 报文将拥塞窗口（cwnd）加上一个 MSS，从 1 开始成指数级增长
- 拥塞避免：当 cwnd ≥ 慢启动阈值（sstresh）时，窗口按线性增长，当收到三个连续的冗余 ACK 后，进入快重启
- 快重启：sstresh=cwnd, cwnd = sstresh + 3*MSS（三次冗余的）并发送丢失的报文，每次收到冗余的就指数级增长直到收到新的 ACK，进入拥塞避免或者超时进入慢重启
.init：程序初始化的引导
.text：已编译的机器代码
.rodata：只读数据，存放字符串字面量，全局常量，虚函数表（C++）以及 switch 跳转表之类
.data：存放已经初始化的全局和静态变量
.bss：存放未初始化或初始化为 0 的全局和静态变量，仅仅是占位符，不占空间，名称可以理解为 Better Save Space（实际起源并不是这个）
- 将主存当作辅存的高速缓存，经常活动的东西放在主存中，就像 GTA5 几十 GB 大的东西都放主存中是放不下的，因此可以高效利用主存
- 每个进程地址空间都一样，方便管理
- 避免进程破坏其他进程的地址空间
ps：思考虚拟内存和交换空间的区别？
❶ 直接映射
❷ 使用页表缓存映射
❸ 使用 TLB 映射
| 名称 | 进程 | 线程 |
|---|---|---|
| 资源分配的最小单位 | 系统调度的最小单位 | |
| 切换开销 | 大 | 小 |
| 通信 | IPC[https://imageslr.com/2020/02/26/ipc.html] | 共享内存 |
线程共享全局变量，独占局部变量
上下文切换代价小，通信方便
资源同步麻烦，容易出错
临界区、互斥、信号量、事件
协程本质是一个用户态的线程，通过跳转来实现
有栈协程把局部变量放在新开的空间上，无栈协程直接使用系统栈使得CPU cache局部性更好，同时也使得无栈协程的中断和函数返回几乎没有区别
通过独立栈实现的协程库中的每一个协程都有自己独立的栈空间，协程栈大小固定且互不干扰
通过共享栈实现的协程库中的每一个协程在运行时都使用一个公共的栈空间，当协程挂起时将自己的数据从共享栈拷贝到自己的独立栈，协程运行时又将数据从独立栈拷贝到共享栈运行
利用关键词排序后，关键词相同的元素之间的相互顺序不变的排序算法
思路：三次reverse，reverse 后 k 位，reverse 前 n - k 位，reverse 整个数组
小插曲： 一开始使用的是 库中的 reverse 函数，写完后面试官要求自己实现这个 reverse。由于当时时间不多了又加上紧张，写完后答案一直有错，也没找到错在哪。面试结束之后，没有马上退出会议，想把这个错找出来。结果过了两分钟，面试官又回来了，说是下一个面试的还没到，就回来看看我。然后在他眼下把代码改对了。也算是有惊无险吧。
ps: LZ 这里写反了，已订正
就绪（Ready）：程序等待执行
运行（Running）：程序正在执行
堵塞（Blocked）：进程执行了某些操作需要等待其运行，如：IO 操作
还有两种特殊的状态
初始（Initial）：进程在创建时的状态
最终（Final）：退出但没有清理，使得其他进程可以得取返回值
最短任务优先（SJF）
先来先出（FIFO）
高响应比优先（HRRN）
最短完成时间优先（STCF）
轮转（RR）
多级反馈队列（MLFQ）
管道，信号量，共享内存，消息队列，套接字通信
保存虚拟内存，栈，寄存器，程序计数器等
时间片到了，IO 堵塞
虚拟内存、栈、全局变量等用户空间的资源，还包括了内核堆栈、寄存器等内核空间的资源。
虚拟内存
因为切换后 TLB 无法被命中
将数组看成一个完全二叉树，先进行初始化，使得子节点都比跟节点小，每次取堆顶（0）放在最后，同时将数组大小减 1
使用分治算法，将排序好的两边用归并的思想合并到 tmp 数组中，最后原地修改原数组
链表插入时间复杂度为 O ( 1 ) ，哈希表查找复杂度为 O ( 1 ) ，双向链表删除复杂度为 O ( 1 ) ，要删除节点时没有 key 就无法删除哈希表中的值
cat /proc/cpuinfo
cat /proc/meminfo
lsof -i:80
netstat -tunlp | grep 80
- a (all)显示所有选项，默认不显示LISTEN相关
- p 显示建立相关链接的程序名
- n 拒绝显示别名，能显示数字的全部转化成数字。
三次握手是为了确认双方的收发能力都没有问题，四次挥手是确保数据都发送完了才结束
分开两次发送，浪费资源
客户端发送三次握手的第一个 SYN 报文后收到服务器的报文却不回应，从而导致服务器的半开资源浪费直到超时释放
可以使用 SYN Cookie，即通过将源目地址及 IP 地址和端口号哈希为序列号，将返回的 ACK-1 得到原来的序列号判断是否正确，直到连接建立才分配资源
上面三个问题问了十多分钟。看起来简单，但面试官会顺着你的思路一直往下问，问得特别深，差点给问崩了。
下面问了几个 C++ 的问题。字节不是用 go 吗？
shared_ptr：解决资源忘记释放的内存泄漏问题，及悬空指针问题
unique_ptr：对象对其有唯一所有权
weak_ptr：和 shared_ptr 搭配，不会增加引用计数，用于避免循环引用（比如 a 对象持有 b 对象，b 对象持有 a 对象），这样必然会导致内存泄露
auto_ptr：时代的眼泪
引用即指针常量，指向后不能修改指向的是哪个对象，想较于指针用法更简单，不需要担心内存泄漏，也更安全不会有野指针哪些乱七八糟的问题
重写是动态多态中，子类重写父类的方法，
重载是静态多态中，同名函数通过不同的形参列表调用不同的实现
4. 手撕：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/solution/er-cha-shu-de-gong-gong-zu-xian-by-pedan-00fs/（最后只剩十分钟，要求十分钟之内写出来）。
忘记录音了，凭回忆写个大概
这个问题聊了20分钟。因为没做过相关的东西，感觉答得一般。刚开始答了很多个方面，感觉面试官都不太满意。但是面试官会一直引导你回答。最后反问的时候面试官也说这个问题没有固定的答案，这个问题涉及的方面非常多，从接入到怎么去存储以及怎么去实现一些具体的逻辑功能，这些方面很难一下子就能想出一个很全面方案。问这个问题主要还是想看看我的一个思考的过程。
大概说了一下，然后 HR 给我介绍了一下这个部门。
内部讨论后，过几天会给答复。如果没过就等其他的部门来捞，过了的话会先发意向书，十月份左右谈薪资。有可能还有加面的情况（忘记问这个加面是好还是不好了，网上有的说会刷人，有的说是看看你能不能拿更高的等级）。
淘宝二面，面试官居然把TCP三次握手问的这么详细-面包板社区
CSAPP / CSE 351 学习笔记（虚拟内存 Virtual Memory)
进程/线程同步的方式和机制，进程间通信 - Icnblog_Wan - 博客园
参考链接：https://leetcode.cn/circle/discuss/MDq50z/view/dgDwBC/，整理：沉默王二