八股文 - 字节备考全整理
以下是一篇围绕“字节跳动面试八股文”主题的完整博客文章,整合并扩展了你提供的内容,保留了核心知识点并进行适当补充:
八股文 - 字节备考全整理
字节跳动作为国内一线互联网公司,对技术能力的考察非常全面,既涉及底层原理,也关注算法细节。本文整理了在字节跳动技术面试中高频出现的基础知识点与算法题,并给出思路与实现,帮助大家高效备考。
一、基础数据结构与算法题
1. 倒置二叉树
递归交换左右子树即可,经典面试题。
2. 二叉树遍历
前序、中序、后序、层序遍历必须掌握,递归和迭代两种实现都要熟悉。
3. 实现一个线程安全的单例类
推荐使用 C++11 的 std::call_once
实现懒汉式线程安全单例。
4. 二叉排序树插入算法
通过比较插入值和当前节点值决定向左还是向右递归插入。
5. 手写线程安全智能指针
关键点在于引用计数的原子操作,推荐使用 std::atomic<int>
实现 shared_ptr
的线程安全计数。
6. 最小覆盖子串
双指针 + 哈希表实现,滑动窗口问题的经典代表。
7. 抽取唯一子数组
给定一个长度为 n 的数组,从中抽取 m 个唯一元素:常见方法有 hash 去重 + 随机采样。若追求 O(n) 时间复杂度可使用 蓄水池抽样(Reservoir Sampling)。
8. 剔除一个元素后的最大乘积
枚举删除每个元素后的最大乘积,同时注意正负数个数。使用前后缀积优化时间复杂度。
9. 一对数中找最大值与最小值
成对比较法减少比较次数,平均比较次数为 1.5n。
10. 字符串字典序最小重排
从两端依次选择较小字符构造新串,称为 最小字典序重排,双指针贪心。
11. 找到数组中左右都满足条件的元素
1 | // 参考 Go 实现,构造 leftMax 和 rightMin 数组,遍历查找 |
12. 在排序数组中找最接近目标值的下标
1 | // 二分查找基础 + 判断最接近的下标 |
13. 燃烧两根香测15分钟
经典脑筋急转弯,理解不同速度与燃尽时间的关系。
二、基础知识问答(八股文)
1. 链表 VS 数组
- 链表:插入删除快、访问慢
- 数组:随机访问快、插入删除慢
2. 常见排序算法
排序 | 时间复杂度 | 空间复杂度 | 稳定性 |
---|---|---|---|
快排 | O(nlogn) | O(logn) | 不稳定 |
堆排 | O(nlogn) | O(1) | 不稳定 |
归并 | O(nlogn) | O(n) | 稳定 |
冒泡 | O(n²) | O(1) | 稳定 |
3. 常见查找算法
顺序查找、二分查找、哈希查找、B+树查找等。
4. 快排 & 堆排实现过程
- 快排:选择 pivot,左右指针交换
- 堆排:构建最大堆,不断交换堆顶与末尾元素
5. 二分查找三种实现
- 普通二分
- 左边界查找
- 右边界查找
注意:边界条件处理是重点,建议面试前写 3 次!
6. 哈希表原理与冲突处理
哈希函数 + 冲突解决(链表法、开放地址法)。底层常见使用链地址法。
三、高频面试算法
1. 二叉树右视图
层序遍历取每层最后一个节点。
2. 0-1 背包
动态规划经典,状态转移方程:dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i])
3. 字符串判断相等
可选:字符逐位比较或使用 hash 比较。
4. 打乱数组
Fisher-Yates 洗牌算法。
5. 矩阵最小路径和
动态规划,dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
6. 二叉树深度
递归实现,左右子树深度取最大值。
7. 十进制转十六进制
位运算 + 字符映射,注意负数处理。
8. 用栈实现队列 & 反之
两个栈或两个队列交替使用。
四、链表专题
- 判断链表有环:快慢指针法
- 翻转链表:双指针或递归实现
- 合并两个升序链表:双指针归并
- 删除值为0的节点:遍历重建链表
- 查询倒数第k个节点:快慢指针
五、项目实战与系统设计
1. LRU 实现
使用哈希表 + 双向链表,支持 O(1) 查询与更新。
2. 内存池/智能指针实现原理
shared_ptr
: 引用计数、线程安全需配合atomic
- 内存池:分块分配,提高内存分配效率,避免频繁 malloc/free
3. Redis相关
- RDB 与 AOF 持久化机制
- 主从复制、高可用、哨兵模式
- 数据结构:跳表、字典、压缩列表、整数集合等
4. MySQL 引擎
- InnoDB(支持事务)
- MyISAM(读多写少)
- Memory(高速、断电即丢)
六、网络协议与操作系统基础
- TCP 三次握手、四次挥手过程与状态图
- TCP/UDP区别,HTTP/HTTPS区别
- 粘包问题及解决(定长、分隔符、长度头部)
- epoll VS select,边缘触发与水平触发
- TCP 滑动窗口、拥塞控制、RTT测量
- 虚函数表位置,迭代器失效场景
七、实用技巧与边界问题
1. swap 两变量不使用第三变量
1 | a ^= b; |
2. 查找第 K 大数
快排改进的 快速选择 或最小堆(TopK)
3. 查找最长连续递增子序列 Top 2
记录起止位置即可,面试常考。
八、附加挑战题 & 实战题
- 100W 字符频率统计:哈希表 + 堆
- 100W 个手机号最省空间存储:用 trie 或 bitset 压缩存储
- 实现 DNS 查询包:构造符合协议的请求与响应
- 10T 单词文件统计 Top K:哈希 + 外部排序
总结
字节跳动的面试不光看算法实现,更考查你对系统原理、语言细节、网络协议和实际项目能力的理解。刷题是基础,理解是核心,项目是亮点,准备过程中要注意:
- 八股文不要死背,要真正理解
- 算法要会优化,不只是能写出
- 底层知识要储备,如内存管理、锁机制等
- 系统设计需积累,尤其分布式、缓存、容灾相关
面试准备没有捷径,但可以系统化。祝大家字节上岸!