字节还是那么喜欢考算法

今天分享的是[训练营](https://mp.weixin.qq.com/s/tKbBrdwOzLCvQv_FqkVvQg?token=1020328508&lang=zh_CN)的朋友在**字节跳动**的面经，整个面试过程差不多一个小时，**一半时间拷打八股，一半时间拷打算法**，字节还是那么喜欢考算法。 ## 内容如下：  ## 面经详解 ### 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. **优点与缺点**： - 优点：这种方法能够很好地适应业务需求，特别是当业务本身就包含自然键时。 - 缺点：需要额外的存储和查询开销，同时也增加了系统的复杂度。 #### Kafka自动生成唯一ID 1. **幂等生产者**： 当启用Kafka的幂等生产者功能(`enable.idempotence=true`)时，Kafka会在内部为每条消息分配一个序列号，结合Producer ID (PID) 和 Topic-Partition 形成一个全局唯一的标识符。这可以有效避免同一会话内的重复消息。 2. **事务性消息传递**： 使用Kafka的事务API时，虽然Kafka不会直接为每条消息生成唯一ID，但可以通过事务边界来确保消息的一致性和完整性，从而间接减少重复消息的可能性。 3. **优点与缺点**： - 优点：简化了应用层面对唯一性的处理，减少了业务代码中的复杂性。 - 缺点：幂等性和事务的支持可能带来一定的性能损失，并且不能完全消除所有场景下的重复消息问题。 ### 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（读未提交）** - 这是最宽松的隔离级别，在这种模式下，一个事务可以读取另一个事务尚未提交的数据更改。 - 它允许脏读（Dirty Read），即读取到了其他事务还未提交的数据，如果该事务之后回滚，则这些数据将不存在。 - 此级别很少被使用，因为它无法提供有效的数据一致性保护。 2. **Read Committed（读已提交）** - 在此级别上，一个事务只能读取到已经被其他事务提交的数据。 - 它防止了脏读的发生，但仍然可能发生不可重复读（Non-repeatable Read），即同一查询在同一个事务中多次执行可能返回不同的结果集。 - 大多数主流数据库系统默认采用这个隔离级别，因为它在性能和数据一致性之间取得了较好的平衡。 3. **Repeatable Read（可重复读）** - 在这个级别，一个事务在整个生命周期内对同一行数据进行的所有读操作都将获得相同的结果，即使其他事务在这期间对该行进行了修改并提交。 - 它不仅避免了脏读，还阻止了不可重复读，但是它不能防止幻读（Phantom Read）。幻读是指当一个事务在同一条件下两次查询得到的结果集数量不同。 - MySQL的InnoDB存储引擎默认使用这一隔离级别。 4. **Serializable（串行化）** - 这是最严格的隔离级别，它要求所有事务依次顺序执行，不允许任何并发操作。 - 它完全消除了脏读、不可重复读以及幻读的问题，提供了最高的数据一致性。 - 不过，由于其严格性，通常会导致较高的锁竞争和较低的并发性能，因此只有在确实需要最高级别的一致性时才会选择此级别。 随着隔离级别的升高，虽然数据一致性得到了更好的保障，但也伴随着更多的资源锁定，从而影响了系统的并发性能。 ### 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`，我们也应该将它计入该层的宽度。 ```go 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`是否存在于这个矩阵中，可以利用这些特性来设计一种高效的搜索算法。一种有效的方法是从矩阵的右上角开始查找（也可以选择左下角），因为这样的起点能让我们根据当前值与目标值之间的关系决定是向上/向下还是向左/向右移动，从而逐步缩小搜索范围。 ```go 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**，备注：面试群。