写点什么

冲击美团!已成功 OC

作者:王中阳Go
  • 2024-10-21
    北京
  • 本文字数:6147 字

    阅读完需:约 20 分钟

冲击美团!已成功 OC

这是一位训练营学员的美团面经,目前已经 OC 。


在此之前他已经拿到了不少公司的 offer,但是都达不到他的预期,美团给的待遇就非常不错,大厂不愧是大厂,就是不知道工作强度如何。


他经历了一共三场面试,一面二面 HR 面,遇到的面试官都非常不错,有些问题没回答出来或者回答的不太好,面试官都会耐心的解答一下,而且脸上一直挂着笑容。


一面主要问的是一些八股,二面主要问的是项目,我总结了 Go 基础、MySQL、Redis 的一些问题,整理如下


go 基础

1. Go 中 Map 的数据结构?扩容机制?key 为什么是无序的?

很经典的题目,问到的概率比较高。


数据结构


主要就是 hmap 和 bmap


type hmap struct {    // 元素个数,调用 len(map) 时,直接返回此值  count     int  flags     uint8  // buckets 的对数 log_2  B         uint8  // overflow 的 bucket 近似数  noverflow uint16  // 计算 key 的哈希的时候会传入哈希函数  hash0     uint32    // 指向 buckets 数组,大小为 2^B    // 如果元素个数为0,就为 nil  buckets    unsafe.Pointer  // 等量扩容的时候,buckets 长度和 oldbuckets 相等  // 双倍扩容的时候,buckets 长度会是 oldbuckets 的两倍  oldbuckets unsafe.Pointer  // 指示扩容进度,小于此地址的 buckets 迁移完成  nevacuate  uintptr  extra *mapextra // optional fields}
type bmap struct { tophash [bucketCnt]uint8}
// 但这只是表面的结构,编译期间会给它加料,动态地创建一个新的结构:
type bmap struct { topbits [8]uint8 keys [8]keytype values [8]valuetype pad uintptr overflow uintptr}
复制代码


扩容机制


当满足某些条件时会自动触发:


  1. 装载因子:这是 map 中元素的数量与桶的数量之比。当装载因子超过某个阈值(通常是 6.5 或者更高)时,map 会触发扩容。这是因为随着元素数量的增加,哈希冲突的概率也会增加,这会导致查找和插入操作的效率下降。

  2. 哈希冲突过多:如果在某个桶中哈希冲突太多,即多个键被哈希到了同一个桶内,那么为了减少冲突并提高性能,map 也可能会触发扩容。

  3. 渐进式扩容:Go 的 map 扩容并不是一次性将所有元素搬迁到新的哈希表中,而是采用了一种称为“渐进式”的方式。这意味着在扩容过程中,原有的 key 不会被一次性全部搬迁到新表,而是在后续的读写操作中逐渐地、分批次地迁移。每次最多只会搬迁几个 bucket,这样可以分散扩容带来的性能开销。

  4. 等量扩容:在 Go 的 map 实现中,扩容通常会创建一个新的哈希表,其容量是原来的两倍或更多。然后旧表中的元素会被重新哈希到新表中。这种扩容策略有助于减少哈希冲突,提升 map 的访问速度。


key 为什么是无序的


当 map 发生扩容时,其中的键(key)可能会被重新分配到新的桶(bucket)中。在扩容之前位于同一个桶中的键,在扩容后可能因为桶的数量增加(通常是翻倍)而分散到不同的桶里,这意味着一些键会被移动到索引增加了 2^B 的新桶中(这里的 B 是扩容前桶的数量的幂次)。由于遍历 map 时是按照桶的顺序进行,并且在每个桶内也是按序遍历键,因此一旦发生键的搬迁,遍历的结果将不会保持原有的顺序。


即使我们有一个硬编码的 map 并且不对其进行任何插入或删除操作,遍历这个 map 应该会返回一个固定的 key/value 序列。但是 Go 语言的设计者为了避免给新手程序员造成误导——即认为这种固定顺序是可依赖的特性——采取了措施来防止这种情况。


而且 Go 做得更绝,当我们在遍历 map 时,并不是固定地从 0 号 bucket 开始遍历,每次都是从一个随机值序号的 bucket 开始遍历,并且是从这个 bucket 的一个随机序号的 cell 开始遍历。这样,即使你是一个写死的 map,仅仅只是遍历它,也不太可能会返回一个固定序列的 key/value 对了。

2. 简述一下 rune 类型

  • Unicode 字符rune 可以存储任何 Unicode 码点,支持全球多种语言的字符。

  • 字符串处理:在遍历字符串时,使用 rune 可以正确处理多字节的 Unicode 字符。

  • 类型转换:可以直接与 int32 相互转换。

  • 定义方式:可以用单引号 ' ' 定义一个 rune 值,例如 'A'

3. 什么是协程泄漏?

协程泄漏是指在 Go 语言中,启动的 goroutine 没有正确停止和释放,导致资源持续占用。这通常发生在 goroutine 无限期阻塞、死锁、未处理错误路径或忘记关闭通道等情况,最终可能导致程序性能下降甚至崩溃。

4. select 底层数据结构和一些特性?

select 语句用于处理多个通道(channel)的发送和接收操作。它类似于 switch 语句,但专门用于通道操作。select 语句会阻塞,直到其中一个 case 的通道可以进行通信为止。如果多个 case 都准备好,则随机选择一个执行。


底层数据结构


select 语句本身并不直接关联特定的数据结构,但它依赖于 Go 运行时对通道的操作。Go 语言中的通道是基于队列实现的,通常是一个环形缓冲区或无缓冲通道。select 语句通过运行时系统来监控所有涉及的通道的状态,并决定哪个通道已经准备好进行通信。


当使用 select 时,Go 运行时内部会为每个通道创建一个监视器,这些监视器会跟踪通道是否可以发送或接收数据。一旦某个通道就绪,select 语句就会解除阻塞并执行相应的 case 分支。


特性


  1. 多路复用select 允许你同时监听多个通道上的事件,这样可以有效地处理并发任务中的多种情况。

  2. 非阻塞性:如果没有任何 case 准备好,你可以提供一个 default 分支来避免 select 无限期地阻塞。default 分支会在没有其他 case 可以立即执行时被执行。

  3. 公平性:如果多个 case 同时准备好,select 会随机选择一个执行,这有助于避免饥饿问题,确保所有通道都有机会被选中。

  4. 超时控制:可以通过向 select 中添加一个带有时间限制的 case 来实现超时功能。例如,使用 time.After 函数创建一个计时器通道,当超过指定时间后,该通道会发送一个值,从而触发 select 语句退出等待状态。

5. 对已经关闭的的 chan 进行读写,会怎么样?为什么?

  • 从已关闭的空通道读取:如果尝试从一个已经关闭且没有剩余数据的通道读取数据,那么读取操作会立即返回,并且接收值将是对应类型的零值。同时,第二个返回值(通常是一个布尔值 ok)将为 false,表明通道已经关闭。

  • 从已关闭但有剩余数据的通道读取:如果通道已经关闭但仍有未被读取的数据,那么这些数据会被正常读取出来,直到通道中的所有数据都被读完。之后再读取就会像上述情况一样,返回类型零值和 false


ch := make(chan int, 1)ch <- 42close(ch)
v, ok := <-ch // 读取 42, ok 为 truefmt.Println(v, ok) // 输出: 42 true
v, ok = <-ch // 通道已关闭,读取零值 0 和 falsefmt.Println(v, ok) // 输出: 0 false
复制代码


  • 向已关闭的通道写入数据:如果尝试向一个已经关闭的通道发送数据,程序会抛出一个运行时 panic。这是因为关闭通道意味着不会再有新的数据被发送到这个通道,而再次尝试写入会导致错误。


ch := make(chan int, 1)ch <- 42close(ch)ch <- 50 // 这里会产生 panic: send on closed channel
复制代码


这种设计是为了确保通道的行为是可预测的,并且防止出现常见的并发编程错误。

6. 除了加 Mutex 锁以外还有哪些⽅式安全读写共享变量?

除了使用 Mutex 锁以外,还可以通过使用原子操作(如 sync/atomic 包提供的函数)、读写锁(RWMutex)、通道(channel)以及 sync 包中的其他同步原语(如 WaitGroupOnce 等)来安全地读写共享变量。

7. 互斥锁正常模式和饥饿模式的区别 ?

正常模式


  • 先来先服务:在正常模式下,当一个 goroutine 释放互斥锁时,它会直接将锁传递给等待队列中的下一个 goroutine,这通常是最近尝试获取锁的那个。


饥饿模式


  • 公平性:为了避免饥饿现象,互斥锁可以切换到饥饿模式。在这种模式下,锁会优先授予等待时间最长的 goroutine,确保每个等待的 goroutine 最终都能获得锁。

  • 触发条件:当一个 goroutine 等待锁的时间超过了某个阈值(通常是 1 毫秒),或者当 Mutex 发现已经有多个等待者时,它可能会自动切换到饥饿模式。

8. 原子操作和锁的区别 ?

  • 原子操作:通过硬件级别的指令保证对共享变量的操作是不可分割的,通常适用于简单的数值类型(如整数、指针)的读写。原子操作执行速度快,因为它不需要上下文切换或调度开销,但它功能有限,仅能处理一些基本的数据类型和操作。

  • :提供更广泛的同步控制,可以保护任意复杂度的数据结构。锁通过操作系统提供的互斥机制来确保同一时间只有一个 goroutine 可以访问受保护的资源。锁的使用可能会引入额外的性能开销,如上下文切换和可能的死锁风险。

MySQL

1. 一条 select 语句的执行流程?

简单总结为以下几个步骤:


  1. 连接管理:客户端与服务器建立连接并进行身份验证。

  2. 解析:服务器解析 SQL 语句,检查语法并生成解析树。

  3. 预处理:检查表和列的存在性,并进行权限验证。

  4. 查询优化:优化器生成并选择最优的执行计划。

  5. 执行:根据优化后的执行计划执行查询,读取数据。

  6. 结果返回:将查询结果返回给客户端。

2. CHAR 和 VARCHAR 的区别?

  1. 固定长度 vs 可变长度

  2. CHAR 是固定长度的字符类型。当你定义一个 CHAR(n) 字段时,无论实际存储的数据长度是多少,它都会占用 n 个字符的空间。不足 n 个字符的部分会被空格填充。

  3. VARCHAR 是可变长度的字符类型。VARCHAR(n) 字段只占用实际存储数据所需的字节数,外加一到两个字节来记录字符串的实际长度(具体取决于字符串的长度)。

  4. 存储空间

  5. CHAR 会使用固定的存储空间,即使存储的数据少于定义的长度。

  6. VARCHAR 仅使用实际需要的存储空间,因此在存储较短字符串时更加节省空间。

  7. 性能

  8. CHAR 由于是固定长度,处理速度通常比 VARCHAR 更快,尤其是在涉及大量数据读取和写入操作时。因为 CHAR 的长度是固定的,所以数据库引擎可以更快地定位到数据的位置。

  9. VARCHAR 在处理较长或长度变化较大的字符串时更灵活,但在处理时可能会稍微慢一些,因为它需要额外的步骤来确定每个字符串的实际长度。

  10. 适用场景

  11. CHAR 适合存储长度几乎相同的字符串,例如邮政编码、国家代码等。

  12. VARCHAR 适合存储长度可能差异很大的字符串,例如用户评论、文章内容等。

3. MYISAM 和 INNODB 的不同?

  1. InnoDB 支持事务,MyISAM 不支持,对于 InnoDB 每一条 SQL 语言都默认封装成事务,自动提交,这样会影响速度,所以最好把多条 SQL 语言放在 begin 和 commit 之间,组成一个事务;

  2. InnoDB 支持外键,而 MyISAM 不支持。对一个包含外键的 InnoDB 表转为 MYISAM 会失败;

  3. InnoDB 是聚集索引,使用 B+Tree 作为索引结构,数据文件是和(主键)索引绑在一起的(表数据文件本身就是按 B+Tree 组织的一个索引结构),必须要有主键,通过主键索引效率很高。但是辅助索引需要两次查询,先查询到主键,然后再通过主键查询到数据。因此,主键不应该过大,因为主键太大,其他索引也都会很大。

  4. InnoDB 不保存表的具体行数,执行 select count(*) from table 时需要全表扫描。而 MyISAM 用一个变量保存了整个表的行数,执行上述语句时只需要读出该变量即可,速度很快(注意不能加有任何 WHERE 条件);

  5. Innodb 不支持全文索引,而 MyISAM 支持全文索引,在涉及全文索引领域的查询效率上 MyISAM 速度更快高;PS:5.7 以后的 InnoDB 支持全文索引了

  6. MyISAM 表格可以被压缩后进行查询操作

  7. InnoDB 支持表、行(默认)级锁,而 MyISAM 支持表级锁

4. binlog 的工作模式有哪些?

1. Statement


这种方式是 MySQL5.6 版本中默认的方式;该日志格式中,每个事件记录的是引起数据变化的 SQL 语句;


  • 优势:暂用磁盘空间非常少速度快,对数据库的性能影响也会小很多

  • 缺点:对于非确定的 SQL 语句,在数据库服务主从复制或者数据备份的时候会产生结果的不一致性,譬如在 SQL 语句中使用了譬如NOW()或者UUID()内置函数,主服务器执行这些不确定函数的值与副本服务器执行时的值是为一致的。


2. Row


该日志格式中,每个事件记录的是变化(受到影响)的行记录被修改的形式


  • 优势:解决了 Statement 模式下非确定语句带来的数据不一致的问题

  • 缺点:暂用磁盘空间大,对数据库服务的影响稍大一些


3. Mixed


混合日志记录,它会自动根据执行语句是否安全(主要是备份、恢复的一致性安全)进行切换 Statement 与 Row 模式;服务器 Mixed 模式下,在如下场景会自动从Statement模式切换成Row模式。


  • 语句中包含UUID()

  • 当 AUTO_INCREMENT 更新一个或多个带有列的表 并调用触发器或存储函数时。

  • 如果语句按行记录并且执行该语句的会话有任何临时表,则所有后续语句(访问临时表的语句除外)都使用按行记录,直到删除该会话正在使用的所有临时表。

Redis

1. 持久化机制?各自的优缺点?

Redis 提供两种持久化机制 RDB 和 AOF 机制:


RDB 持久化⽅式:是指⽤数据集快照的⽅式半持久化模式,记录 redis 数据库的所有键值对,在某个时间点将数据写⼊⼀个临时⽂件。持久化结束后,⽤这个临时⽂件替换上次持久化的⽂件,达到数据恢复。


优点


1、只有⼀个⽂件 dump.rdb,⽅便持久化。


2、容灾性好,⼀个⽂件可以保存到安全的磁盘。


3、性能最⼤化,fork ⼦进程来完成写操作,让主进程继续处理命令,所以是 IO 最⼤化。使⽤单独⼦进程来进⾏持久化,主进程不会进⾏任何 IO 操作,保证了 redis 的⾼性能)


4.相对于数据集⼤时,⽐ AOF 的启动效率更⾼。


缺点


1、数据安全性低。RDB 是间隔⼀段时间进⾏持久化,如果持久化之间 redis 发⽣故障,会发⽣数据丢失。所以这种⽅式更适合数据要求不严谨的时候)


AOFA 持久化⽅式:是指所有的命令⾏记录以 redis 命令请求协议的格式完全持久化存储,保存为 aof ⽂件。


优点


1、数据安全,aof 持久化可以配置 appendfsync 属性,有 always,每进⾏⼀次命令操作就记录到 aof ⽂件中⼀次。


2、通过 append 模式写⽂件,即使中途服务器宕机,可以通过 redis-check-aof ⼯具解决数据⼀致性问题。


3、AOF 机制的 rewrite 模式。AOF ⽂件没被 rewrite 之前(⽂件过⼤时会对命令进⾏合并重写),可以删除其中的某些命令(⽐如误操作的 flushall))


缺点


1、AOF ⽂件⽐ RDB ⽂件⼤,且恢复速度慢。


2、数据集⼤的时候,⽐ rdb 启动效率低

2. 怎么理解 Redis 事务?

Redis 的事务和 MySQL 的事务概念上是类似的,都是把一系列操作绑定成一组,让这一组能够批量执行。


Redis 事务与 MySQL 事务的区别:


  • 弱化的原子性:Redis 事务不支持回滚机制。在 Redis 中,事务中的所有命令会被批量执行,但如果其中某个命令执行失败,其他命令仍然会继续执行,而不会回滚到事务开始前的状态。相比之下,MySQL 事务如果有一个操作失败,则整个事务可以回滚,恢复到事务开始前的状态。

  • 不保证一致性:Redis 事务不涉及数据约束(如外键、唯一性等),也没有回滚机制。因此,如果事务中的某个修改操作失败,可能会导致数据处于不一致的状态。而在 MySQL 中,事务的一致性确保了事务执行前后数据都是合理有效的,不会出现中间的非法状态。

  • 不需要隔离性:Redis 不支持隔离级别,因为它是单线程处理请求的,不会并发执行事务。这与 MySQL 不同,MySQL 通过不同的隔离级别来控制并发事务之间的可见性和影响。

  • 不需要持久性:Redis 的数据默认保存在内存中,是否开启持久化(如 RDB 或 AOF)是 Redis 服务器自身的配置选项,与事务无关。Redis 在集群模式下不支持事务,因为集群模式下的多节点操作无法保证事务的原子性。

欢迎关注 ❤

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


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


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

用户头像

王中阳Go

关注

靠敲代码在北京买房的程序员 2022-10-09 加入

【微信】wangzhongyang1993【公众号】程序员升职加薪之旅【成就】InfoQ专家博主👍掘金签约作者👍B站&掘金&CSDN&思否等全平台账号:王中阳Go

评论

发布
暂无评论
冲击美团!已成功 OC_Go_王中阳Go_InfoQ写作社区