八股文 - 字节备考全整理

以下是一篇围绕“字节跳动面试八股文”主题的完整博客文章,整合并扩展了你提供的内容,保留了核心知识点并进行适当补充:


八股文 - 字节备考全整理

字节跳动作为国内一线互联网公司,对技术能力的考察非常全面,既涉及底层原理,也关注算法细节。本文整理了在字节跳动技术面试中高频出现的基础知识点与算法题,并给出思路与实现,帮助大家高效备考。

一、基础数据结构与算法题

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
2
3
a ^= b;
b ^= a;
a ^= b;

2. 查找第 K 大数

快排改进的 快速选择 或最小堆(TopK)

3. 查找最长连续递增子序列 Top 2

记录起止位置即可,面试常考。


八、附加挑战题 & 实战题

  • 100W 字符频率统计:哈希表 + 堆
  • 100W 个手机号最省空间存储:用 trie 或 bitset 压缩存储
  • 实现 DNS 查询包:构造符合协议的请求与响应
  • 10T 单词文件统计 Top K:哈希 + 外部排序

总结

字节跳动的面试不光看算法实现,更考查你对系统原理、语言细节、网络协议和实际项目能力的理解。刷题是基础,理解是核心,项目是亮点,准备过程中要注意:

  • 八股文不要死背,要真正理解
  • 算法要会优化,不只是能写出
  • 底层知识要储备,如内存管理、锁机制等
  • 系统设计需积累,尤其分布式、缓存、容灾相关

面试准备没有捷径,但可以系统化。祝大家字节上岸!