看看上海的游戏公司面试强度

欢迎点击下方👇关注我，记得星标哟~

今天分享组织内部的朋友在上海叠纸游戏公司的面经。

当看到他分享的30多道题在微信聊天界面弹出，我心想这哪是面试，这分明是面试官给他设的关卡副本，问的也忒多了，但是有一半都是和他本人项目相关的，我整理的时候都去掉了:

面经详解

1. 切片的底层结构

切片的底层结构由三个部分组成：

1. 指针：指向底层数组的起始位置。
2. 长度（len）：表示切片中当前包含的元素个数。
3. 容量（cap）：表示从切片的起始位置到底层数组末尾的元素个数。

切片的底层结构可以理解为一个动态数组的封装。切片的指针指向底层数组的某个位置，而长度和容量决定了切片的边界。例如，如果底层数组是一个长度为5的数组，切片可以通过 arr[1:4] 创建一个长度为3、容量为4的切片。此时，切片的指针指向底层数组的第二个元素，长度为3，容量为4。

2. 切片的扩容过程

切片的扩容过程由 append 函数触发，规则如下：

1. 当容量不足时：如果切片的当前容量不足以容纳新元素，Go 会分配一个新的底层数组，并将旧数组的元素复制到新数组中。
2. 扩容规则：
   • 如果当前容量小于 256，则扩容后的容量是原来的两倍。
   • 如果当前容量大于等于 256，则扩容后的容量根据这个公式计算：newCap = oldCap + ( 3 * 256 + oldCap ) / 4 （根据源码简化，感兴趣的可以直接去看源码）。
3. 新切片：扩容后，切片的指针指向新的底层数组，长度和容量更新为新的值。

需要注意的是，扩容后，原切片和新切片的底层数组不再共享。因此，在并发场景中，扩容可能导致数据竞争问题。

3. 切片 append 过程是并发安全的吗？有没有可能并发的时候造成数据不一致？

切片的 append 操作本身不是并发安全的。原因如下：

1. 扩容时的竞争条件：当多个 goroutine 同时调用 append 时，如果其中一个 goroutine 触发了扩容，可能会导致其他 goroutine 的切片指针指向错误的底层数组。
2. 数据一致性问题：如果多个 goroutine 同时修改切片的底层数组，可能导致数据覆盖或丢失。

解决方案：

• 使用 sync.Mutex 或 sync.RWMutex 对切片的读写操作进行加锁。
• 使用 sync/atomic 包中的原子操作（仅适用于特定场景）。
• 使用并发安全的库，如 gRPC 中的 sync.Map。

4. 有缓存的 Channel 和无缓冲的 Channel 区别

无缓冲的 Channel：

• 同步通信：发送和接收操作必须同时准备好才能完成。发送者会阻塞直到接收者准备好接收数据。
• 用途：常用于 goroutine 之间的同步，例如在 WaitGroup 中协调多个 goroutine 的执行。

有缓冲的 Channel：

• 异步通信：发送操作只有在缓冲区为满时才会阻塞；接收操作只有在缓冲区为空时才会阻塞。
• 用途：适用于生产者-消费者模型，例如任务队列。

5. Map 的底层结构

Go 语言的 map 是一种哈希表（Hash Table）结构，其底层由以下组件组成：

1. hmap 结构体：表示整个 map，包含桶（bucket）数组、元素数量、哈希种子等字段。
2. bmap（桶）：每个桶存储 8 个键值对（在 Go 1.20 之前），并通过链表解决哈希冲突。
3. 哈希函数：通过键的哈希值计算其在桶中的位置。
4. 扩容机制：当元素数量超过负载因子（默认 6.5）时，map 会触发扩容，重新分配桶并迁移元素。

6. Map 存高 8 位的目的是什么？

在 Go 的 map 中，键的哈希值的高 8 位（tophash）用于快速判断键是否存在于当前桶中。其目的是：

1. 减少哈希碰撞的检查次数：通过比较 tophash 可以快速排除不在当前桶中的键。
2. 提高查找效率：在哈希冲突的情况下，tophash 可以帮助快速定位到正确的键。

7. 原子操作

原子操作是并发编程中保证操作不可中断的机制。Go 语言通过 sync/atomic 包提供以下原子操作：

1. CAS（Compare and Swap）：比较并交换，用于实现无锁的数据结构。
2. Add：原子加法，用于计数器等场景。
3. Load/Store：原子读取和写入，用于共享状态的同步。

8. Gin 的中间件如何实现的？

Gin 的中间件是基于 HandlerFunc 的链式调用实现的。每个中间件是一个 HandlerFunc，它会在请求到达路由处理器之前执行，并通过 c.Next() 调用后续的中间件或路由处理器。

实现原理：

1. 中间件链：Gin 将所有中间件按注册顺序组织成一个链表。
2. 执行顺序：请求进入时，从第一个中间件开始执行，直到所有中间件和路由处理器完成。
3. 响应处理：中间件可以在 c.Next() 之前或之后修改请求或响应。

示例：

func Logger() gin.HandlerFunc {
    return func(c *gin.Context) {
        fmt.Println("Before request")
        c.Next()
        fmt.Println("After request")
    }
}

r.Use(Logger())

9. MySQL 当中如何判断一个 SQL 语句是否命中索引？

判断 SQL 是否命中索引的方法：

1. 使用 EXPLAIN 语句：

   EXPLAIN SELECT * FROM table WHERE id = 1;

• key 字段显示使用的索引。
• rows 字段显示扫描的行数。
• type 字段显示访问类型（如 const、ref、range）。

1. 查看索引使用情况：

   SHOW INDEX FROM table;

1. 性能分析：
   • 如果 Extra 列显示 Using index，表示使用了覆盖索引。
   • 如果 Extra 列显示 Using filesort，表示进行了文件排序。

10. MySQL 主从同步是什么原理？

MySQL 主从同步的原理基于 二进制日志（Binlog），其核心流程如下：

1. 主库写入 Binlog：主库将所有 DML/DCL 操作记录到 Binlog 文件中。
2. 从库 I/O 线程：从库的 I/O 线程连接到主库，拉取 Binlog 数据并存储到中继日志（Relay Log）中。
3. 从库 SQL 线程：从库的 SQL 线程解析中继日志，将操作应用到从库的数据中。

同步模式：

• 异步复制：主库不等待从库确认。
• 半同步复制：主库等待至少一个从库确认接收。
• 全同步复制：主库等待所有从库确认（性能较低）。

11. Redis 中 ZSet 底层原理

Redis 的 ZSet（有序集合） 是一种结合了 Set（无重复成员） 和 Sorted（按分数排序） 特性的数据结构，其底层实现根据数据量的不同分为两种形式：

1. 小数据量时的实现：压缩列表（ZipList）

• 适用条件：
  • 元素数量小于 zset_max_ziplist_entries（默认 128）。
  • 每个成员的长度小于 zset_max_ziplist_value（默认 64 字节）。
• 结构特点：
  • 压缩列表是一种连续内存块的紧凑结构，适合存储小规模数据。
  • 元素按顺序存储，成员和分数交替排列。
  • 优点：节省内存，适合内存敏感的场景。
  • 缺点：插入、查找和范围查询的性能较低（需遍历）。

2. 大数据量时的实现：跳表（SkipList） + 哈希表（Hash Table）

• 适用条件：
  • 数据量超过上述阈值时，Redis 自动切换为跳表 + 哈希表的组合。
• 结构特点：
  • 跳表负责排序和范围查询。
  • 哈希表负责快速定位成员的分数，避免全表扫描。
  • 用于快速查询成员对应的分数（ZSCORE 操作）。
  • Key 是成员名（Member），Value 是分数（Score）。
  • 提供 O(1) 级别的查找效率。
  • 用于维护成员的有序性，支持高效的范围查询（如 ZRANGE、ZRANGEBYSCORE）。
  • 跳表是多层链表结构，每一层是下一层的子集，通过随机生成层级（最大 32 层）加速查找。
  • 每个节点包含：
  • 时间复杂度：
  • 成员（Member）：存储实际数据（如字符串）。
  • 分数（Score）：用于排序的数值。
  • 后退指针（Backward）：指向前一个节点，方便倒序查询。
  • 层级指针（Level）：每层包含一个前进指针（Forward）和跨度（Span）。
  • 插入、删除、查找：O(log N)。
  • 范围查询：O(log N + M)（M 为返回元素数量）。
  • 跳表（SkipList）：
  • 哈希表（Hash Table）：
  • 协同工作：

12. 跳表的底层的数据结构，跳表有这么多层级的目的是什么，查找顺序是什么？

跳表的底层数据结构： 跳表由多层链表组成，每一层的节点是下一层节点的子集。顶部层级的节点较少，用于快速跳过大量元素。

层级的目的：

• 加速查找：通过层级跳过不必要的节点，减少比较次数。
• 平衡性能：跳表的平均查找复杂度为 O(log n)，接近二分查找。

查找顺序：

1. 从最高层级的头节点开始查找。
2. 如果当前节点的下一个节点的值小于目标值，则跳转到下一个节点。
3. 如果当前层级无法继续前进，则降级到下一层级。
4. 重复上述步骤，直到找到目标节点或到达链表末尾。

13. 登录接口有个黑名单大概有 2 亿左右，每天都去查这个用户是否在黑名单内，有没有高效的方式？

高效方案：

1. 布隆过滤器（Bloom Filter）：
   • 使用多个哈希函数将用户 ID 映射到布隆过滤器的位数组中。
   • 查询时，如果所有哈希位都为 1，则认为用户可能在黑名单中（存在误判）。
   • 优点：内存占用小，查询速度快。
   • 缺点：存在误判率，无法删除元素。
2. Redis 集合：
   • 使用 SET 或 ZSET 存储黑名单用户 ID。
   • 查询时通过 SISMEMBER 快速判断是否存在。
   • 优点：支持精确查询和动态更新。
   • 缺点：内存占用较高。
3. 分布式哈希表（DHT）：
   • 将黑名单分片存储到多个节点，通过一致性哈希算法快速定位用户 ID 所属的节点。
   • 优点：支持大规模数据。
   • 缺点：实现复杂。

14. 布隆过滤器的原理

原理： 布隆过滤器是一个概率型数据结构，使用 位数组 和 多个哈希函数 实现：

1. 初始化：创建一个长度为 m 的位数组，所有位初始化为 0。
2. 插入元素：对元素通过 k 个哈希函数计算出 k 个位置，将这些位置的位设置为 1。
3. 查询元素：对元素通过相同的 k 个哈希函数计算出 k 个位置，如果所有位都为 1，则认为元素可能存在；如果有任意一位为 0，则元素一定不存在。

特点：

• 优点：空间效率高，查询速度快。
• 缺点：存在误判率（False Positive），无法删除元素。

15. 微服务里是怎么做服务发现的？

微服务中的服务发现通常通过 注册中心（Service Registry） 实现，常见方案包括：

1. Eureka（Netflix）：
   • 服务启动时向 Eureka 注册，包含元数据（IP、端口、健康状态）。
   • 客户端通过 Eureka 获取服务实例列表，并进行负载均衡。
2. etcd：
   • 服务将自身信息写入 etcd，客户端通过 etcd 查询服务实例。
   • 支持 Watch 机制，实时监听服务变化。
3. Consul：
   • 提供服务注册、健康检查、配置管理等功能。
   • 客户端通过 Consul 的 API 获取服务实例列表。
4. ZooKeeper：
   • 通过临时节点实现服务注册和发现。
   • 客户端监听节点变化，动态更新服务列表。

16. etcd 租约概念有什么作用？

租约（Lease） 是 etcd 中用于管理临时键值对生命周期的机制，其作用包括：

1. 自动续租：客户端可以通过续租保持键值对的有效性。
2. 租约到期：如果客户端未及时续租，键值对会自动过期并被删除。
3. 分布式锁：租约可用于实现分布式锁，确保锁的持有者在超时后自动释放锁。

17. etcd client 端是怎么发现这个集群增加还是减少了？

etcd 客户端通过 Watch 机制 监听集群的变化：

1. Watch 键值对：客户端可以监听某个键值对的变化，当键值对被修改或删除时，客户端会收到通知。
2. Watch 集群事件：客户端可以监听 etcd 集群的成员变更事件（如节点加入或离开）。
3. 健康检查：客户端定期向 etcd 服务器发送健康检查请求，检测服务器的可用性。

早日上岸！