字节还是那么喜欢考算法

今天分享的是训练营的朋友在字节跳动的面经，整个面试过程差不多一个小时，一半时间拷打八股，一半时间拷打算法，字节还是那么喜欢考算法。

内容如下：

面经详解

1 讲讲项目难易点

常考的问题，对于自己的项目可以提前准备好话术

2 kafka 处理消息丢失和消息重复

在分布式消息系统如 Apache Kafka 中，消息丢失和消息重复是两个常见的问题。为了解决这些问题，可以采取一系列的措施和技术手段。以下是一些处理 Kafka 消息丢失和消息重复的方法：

消息丢失

1. 确认机制：确保消费者在成功处理完消息后才提交偏移量（offset），这可以通过设置enable.auto.commit=false并手动管理偏移量来实现。

2. 持久化配置：设置适当的日志刷新策略，比如调整log.flush.interval.messages和log.flush.interval.ms参数，确保数据及时写入磁盘。

3. 副本因子：使用高副本因子（replication factor）来增强容错能力，即使一个节点失败，其他副本仍然可用。

4. ISR（In-Sync Replicas）配置：调整与 ISR 相关的参数，如min.insync.replicas，确保大多数副本保持同步，以减少因少数副本不同步导致的数据丢失风险。

5. 生产者可靠性：生产者端启用幂等性和事务支持，保证每条消息至少被发送一次且不超过一次。

消息重复

1. 幂等生产者：启用 Kafka 的幂等生产者特性，通过设置enable.idempotence=true，使得同一会话内的重复消息只记录一次。

2. 事务性消息传递：利用 Kafka 提供的事务 API，允许生产者在一个事务中执行多条消息的发送操作，确保这些消息要么全部成功要么全部失败，从而避免部分消息重复。

3. 消费端去重逻辑：在消费者端实现业务级别的去重机制，例如基于消息唯一 ID 或者时间戳进行过滤，防止重复消费。

4. 精确一次性语义：结合使用幂等生产和事务性消费，尽可能接近“恰好一次”语义，尽管完全消除所有场景下的重复消息是非常困难的。

3 你说消息重复可以去生成唯一 ID 你们 ID 是 kafka 自己生成的还是业务生成

以下是两种方式的说明：

业务系统生成唯一 ID

1. 业务逻辑保证：在某些情况下，业务逻辑本身可以确保每条消息都有一个唯一的标识符。例如订单号、交易 ID 等，这些通常由上游业务系统生成，并且是全局唯一的。

2. 去重机制：消费者端可以在接收到消息后检查该唯一 ID 是否已经存在（比如通过数据库记录或者缓存）。如果发现重复，则忽略这条消息；否则，进行正常处理并记录这个 ID 以防止未来的重复消费。

3. 优点与缺点：

4. 优点：这种方法能够很好地适应业务需求，特别是当业务本身就包含自然键时。

5. 缺点：需要额外的存储和查询开销，同时也增加了系统的复杂度。

Kafka 自动生成唯一 ID

1. 幂等生产者：当启用 Kafka 的幂等生产者功能(enable.idempotence=true)时，Kafka 会在内部为每条消息分配一个序列号，结合 Producer ID (PID) 和 Topic-Partition 形成一个全局唯一的标识符。这可以有效避免同一会话内的重复消息。

2. 事务性消息传递：使用 Kafka 的事务 API 时，虽然 Kafka 不会直接为每条消息生成唯一 ID，但可以通过事务边界来确保消息的一致性和完整性，从而间接减少重复消息的可能性。

3. 优点与缺点：

4. 优点：简化了应用层面对唯一性的处理，减少了业务代码中的复杂性。

5. 缺点：幂等性和事务的支持可能带来一定的性能损失，并且不能完全消除所有场景下的重复消息问题。

4 讲讲你对 redis 的了解

Redis 简介

• 类型：开源、高性能的键值存储系统。

• 用途：常作为数据库、缓存和消息中间件使用。

主要特点

1. 快速：所有数据存储在内存中，提供极高的读写速度。

2. 多种数据结构：支持字符串、列表、集合、哈希表等，适合不同场景。

3. 持久化：可以选择将数据保存到磁盘，防止数据丢失。

4. 复制与集群：支持主从复制和分布式部署，确保高可用性和扩展性。

5. 简单易用：命令行界面友好，易于集成到各种应用中。

使用场景

• 缓存：加速 Web 应用的数据访问。

• 会话管理：存储用户登录状态等临时信息。

• 实时分析：处理大量实时数据。

• 队列系统：实现任务队列或消息传递。

5 redis 的节点主从复制具体操作

Redis 的主从复制机制允许一个或多个 Redis 服务器（称为从节点）作为另一个 Redis 服务器（称为主节点）的副本运行。这种配置提供了数据冗余，并可以用于扩展读取操作。

具体操作步骤

1. 配置文件设置：在主节点和从节点上分别配置redis.conf文件。对于从节点，需要设置replicaof masterip masterport（旧版本可能是slaveof），其中masterip是主节点的 IP 地址，masterport是主节点的端口。

2. 启动服务：使用各自的配置文件启动主节点和从节点的服务。

3. 连接建立：从节点会尝试与主节点建立 TCP 连接，并发送命令以开始同步过程。

4. 权限验证（如果有设置）：如果主节点设置了密码保护，从节点必须通过身份验证才能进行复制。

5. 全量同步：首次同步时，主节点执行BGSAVE创建 RDB 快照，并将此快照发送给从节点。同时，所有新的写入命令都会被记录到主节点的复制缓冲区中。

6. 增量同步：一旦全量同步完成，主节点继续向从节点发送其接收到的所有写入命令，以保持数据一致性。如果网络中断导致同步失败，当连接恢复时，主节点可以根据情况选择是否进行部分重传（基于偏移量 offset）。

6 增量复制那步，怎么把数据给到主节点，或者说怎么保证数据一致性

可以通过下面几种方式：

• 复制积压缓冲区：主节点维护了一个固定大小的循环缓冲区，称为复制积压缓冲区（Replication Backlog）。它保存了最近一段时间内执行过的写命令，以便在网络断开后重新连接时能够补发这些命令给从节点。

• 偏移量跟踪：每个写命令都有一个唯一的偏移量，主节点和从节点都记录下自己处理的最后一个命令的偏移量。当从节点重新连接时，它会告知主节点自己最后接收到的偏移量，主节点据此决定应该从哪个位置开始补发命令。

• PSYNC 命令：从 Redis 2.8 起，引入了PSYNC命令来支持部分重同步（即增量同步）。该命令使得从节点能够在断线重连时请求特定范围内的命令，而不是每次都触发全量同步。

7 数据库 4 个隔离级别讲讲

数据库的四个隔离级别是 SQL 标准定义的，用来控制事务并发执行时的行为。每个隔离级别解决了不同程度的读取问题，并提供了不同级别的数据一致性保证。以下是这四个隔离级别的详细介绍：

1. Read Uncommitted（读未提交）

2. 这是最宽松的隔离级别，在这种模式下，一个事务可以读取另一个事务尚未提交的数据更改。

3. 它允许脏读（Dirty Read），即读取到了其他事务还未提交的数据，如果该事务之后回滚，则这些数据将不存在。

4. 此级别很少被使用，因为它无法提供有效的数据一致性保护。

5. Read Committed（读已提交）

6. 在此级别上，一个事务只能读取到已经被其他事务提交的数据。

7. 它防止了脏读的发生，但仍然可能发生不可重复读（Non-repeatable Read），即同一查询在同一个事务中多次执行可能返回不同的结果集。

8. 大多数主流数据库系统默认采用这个隔离级别，因为它在性能和数据一致性之间取得了较好的平衡。

9. Repeatable Read（可重复读）

10. 在这个级别，一个事务在整个生命周期内对同一行数据进行的所有读操作都将获得相同的结果，即使其他事务在这期间对该行进行了修改并提交。

11. 它不仅避免了脏读，还阻止了不可重复读，但是它不能防止幻读（Phantom Read）。幻读是指当一个事务在同一条件下两次查询得到的结果集数量不同。

12. MySQL 的 InnoDB 存储引擎默认使用这一隔离级别。

13. Serializable（串行化）

14. 这是最严格的隔离级别，它要求所有事务依次顺序执行，不允许任何并发操作。

15. 它完全消除了脏读、不可重复读以及幻读的问题，提供了最高的数据一致性。

16. 不过，由于其严格性，通常会导致较高的锁竞争和较低的并发性能，因此只有在确实需要最高级别的一致性时才会选择此级别。

随着隔离级别的升高，虽然数据一致性得到了更好的保障，但也伴随着更多的资源锁定，从而影响了系统的并发性能。

8 MVCC 实现原理

多版本并发控制（MVCC）是一种用于数据库管理系统和事务内存的并发控制机制，其核心目标是提高并发性能，解决并发读写操作中的数据一致性问题。MVCC 通过保存数据的历史版本来实现非阻塞读取，允许读写操作并行执行而不互相干扰。

1. 隐藏列

在 MySQL 的 InnoDB 存储引擎中，每一行记录都会隐式地包含以下几个字段：

• DB_TRX_ID：最近修改这条记录的事务 ID。

• DB_ROLL_PTR：指向 undo 日志中的位置，用于回滚指针，可以找到该行之前的版本。

• DB_ROW_ID：隐藏的主键，当表没有显式的主键时使用。

2. Undo Log（回滚日志）

• 当一个事务对某一行进行更新或删除时，并不会直接修改原始数据，而是创建一个新的版本并将旧版本的信息保存到 undo 日志中。

• 这样做不仅支持了事务的回滚功能，还为 MVCC 提供了读取历史版本的能力。

3. Read View（读视图）

• 每个事务在开始时会生成一个 Read View，它包含了当前系统中所有活跃事务的快照。

• Read View 主要用于确定哪些版本的数据是可以被当前事务看到的，哪些是不可见的。

4. 可见性判断规则

根据 Read View 中的信息，结合每行记录的 DB_TRX_ID 以及 undo 日志中的历史版本，按照如下规则判断某一版本是否对当前事务可见：

• 如果记录的事务 ID 小于 Read View 中的最小活跃事务 ID，则认为此版本是在当前事务之前提交的，因此是可见的。

• 如果记录的事务 ID 大于等于 Read View 中的最大已分配事务 ID，则认为此版本是在当前事务之后创建的，所以是不可见的。

• 如果记录的事务 ID 位于上述两个范围之间，则需要检查该事务 ID 是否存在于 Read View 中的活跃事务列表中。如果存在，则表示这个版本是由尚未提交的事务产生的，因而不可见；否则就是已经提交的版本，可以看见。

5. 版本链

每当有新的更改发生时，都会产生新的版本，并通过 DB_ROLL_PTR 链接起来形成版本链。查询时，会从最新的版本开始沿链向下查找，直到找到满足可见性条件的第一个版本为止。

代码题

给定一个二叉树，编写一个函数，获取这个树的最大宽度。树的宽度是所有层中的最大宽度（每一层的节点可能为空）

要计算二叉树的最大宽度，可以使用广度优先搜索（BFS）的方法进行层序遍历。在这个过程中，我们会记录每一层的节点数量，并更新最大宽度。需要注意的是，题目中提到“每一层的节点可能为空”，这意味着即使某个节点是nil，我们也应该将它计入该层的宽度。

package main
import "fmt"
// TreeNode 定义二叉树的节点结构type TreeNode struct {  Val   int  Left  *TreeNode  Right *TreeNode}
// getMaxWidth 计算二叉树的最大宽度func getMaxWidth(root *TreeNode) int {  if root == nil {    return 0  }
  maxWidth := 0  var queue []*TreeNode  queue = append(queue, root)
  for len(queue) > 0 {    levelLength := len(queue)    if levelLength > maxWidth {      maxWidth = levelLength    }
    for i := 0; i < levelLength; i++ {      node := queue[0]      queue = queue[1:]
      if node != nil {        // Add child nodes to the queue.        // Even if they are nil, we add them to maintain the width.        queue = append(queue, node.Left)        queue = append(queue, node.Right)      }    }
    // Remove all nil nodes at the end of the queue for next level processing.    for len(queue) > 0 && queue[len(queue)-1] == nil {      queue = queue[:len(queue)-1]    }  }
  return maxWidth}
func main() {  // 构建一个测试用的二叉树  root := &TreeNode{Val: 1}  root.Left = &TreeNode{Val: 3}  root.Right = &TreeNode{Val: 2}  root.Left.Left = &TreeNode{Val: 5}  root.Left.Right = &TreeNode{Val: 3}  root.Right.Right = &TreeNode{Val: 9}
  fmt.Println("The maximum width of the tree is:", getMaxWidth(root))}

给定二维数据 m*n 矩阵 matrix，满足一定特性：a 每行从左到右递增，b 每列从上到下递增.给定目标元素 num，判断 Num 是否存在

给定一个满足以下条件的二维矩阵matrix：

• 每行从左到右递增。

• 每列从上到下递增。

要判断一个目标元素num是否存在于这个矩阵中，可以利用这些特性来设计一种高效的搜索算法。一种有效的方法是从矩阵的右上角开始查找（也可以选择左下角），因为这样的起点能让我们根据当前值与目标值之间的关系决定是向上/向下还是向左/向右移动，从而逐步缩小搜索范围。

package main
import "fmt"
// searchMatrix 判断num是否存在于matrix中func searchMatrix(matrix [][]int, num int) bool {  if len(matrix) == 0 || len(matrix[0]) == 0 {    return false  }
  row := 0  col := len(matrix[0]) - 1 // 从右上角开始
  for row < len(matrix) && col >= 0 {    if matrix[row][col] == num {      return true    } else if matrix[row][col] > num {      col-- // 向左移动    } else {      row++ // 向下移动    }  }
  return false}
func main() {  matrix := [][]int{    {1, 4, 7, 11, 15},    {2, 5, 8, 12, 19},    {3, 6, 9, 16, 22},    {10, 13, 14, 17, 24},    {18, 21, 23, 26, 30},  }  num := 5  fmt.Println("Does the number exist in the matrix?", searchMatrix(matrix, num))}

解释：

• 从右上角开始：这是因为当你在右上角时，你有明确的方向选择：如果当前值大于目标值，则可以确定目标值不会出现在当前列的下方，因此你可以向左移动；如果当前值小于目标值，则可以确定目标值不会出现在当前行的左侧，因此你可以向下移动。

• 时间复杂度：这种方法的时间复杂度为 O(m + n)，其中 m 是矩阵的行数，n 是矩阵的列数。因为在最坏的情况下，我们可能需要遍历一行和一列的所有元素。

欢迎关注 ❤

我们搞了一个免费的面试真题共享群，互通有无，一起刷题进步。

没准能让你能刷到自己意向公司的最新面试题呢。

感兴趣的朋友们可以加我微信：wangzhongyang1993，备注：infoq 面试群。