写点什么

得物一面,都是非常经典的问题

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

    阅读完需:约 16 分钟

今天继续分享最新的面经。


投稿的是在得物的一面,得物的面经还是比较少见,内容的话我看了一下,整体来说挺简单的,但都是一些很经典的题目,值得一学:

面经详解

首先自我介绍,拿一个项目讲一下,你觉得这个项目对你有什么帮助。


(然后后面纯八股)

1. 线程,进程和协程的区别

这个问题前面的文章说过好几次了,还是有很多小伙伴表示记不住,这次我举一个特殊的例子来说明一下:

进程(Process)

想象一下你正在厨房里同时做几道菜。每个菜的准备过程就是一个独立的“小世界”,它们有自己的食材(资源)、厨具(内存空间)以及烹饪步骤(程序代码)。这些“小世界”就是进程。每个进程都是操作系统中一个独立运行的实体,拥有自己独立的内存空间。如果你在做饭的时候不小心把其中一个菜烧糊了,通常不会影响到其他菜。

线程(Thread)

现在假设你是一个超级厨师,能够同时处理多个菜肴的不同部分,比如一边切洋葱,一边炖汤。这里的“切洋葱”和“炖汤”就像是进程中的线程。线程是进程内部的一个执行单元,共享同一进程内的资源。这意味着如果一个线程遇到了问题(例如:切到了手指),可能会影响到同一个进程下的其他线程(比如,你需要停下来处理伤口,那么炖汤也得暂停)。但是,不同进程间的线程通常是相互隔离的,所以即使一个进程崩溃了,也不会直接导致另一个进程停止工作。

协程(Coroutine)

设想你是一位非常有条理的大厨,在处理多个任务时能自由地切换注意力。当你觉得需要等待某个操作完成(如等待水烧开)时,你可以先去做另一件事(比如洗菜),而不需要完全停止当前的工作。这就是协程的基本理念——轻量级的任务切换机制。协程是由程序员控制何时暂停和恢复执行的,而不是像线程那样由操作系统调度。这使得协程非常适合于编写异步非阻塞的应用程序,因为可以更高效地利用 CPU 时间。


简单来说:


  • 进程就像整个厨房,包含所有必要的东西来完成一项大的任务。

  • 线程是在厨房里同时进行的多个活动,但使用的是同样的厨具和材料。

  • 协程则是你在不同活动之间灵活切换的能力,让你可以在等待某些事情发生的同时继续做其他事情,从而提高效率。

2. make 和 new 的区别,能不能 new 一下 map

makenew 的区别

makenew 都是用来分配内存的内置函数,但它们的应用场景和返回值有所不同:


  • new(T):

  • new 函数用于分配零值并返回指向该类型的新分配的零值的指针。它适用于所有类型。

  • 返回的是一个指向新分配的零值的指针。

  • 例如:p := new(int) 会创建一个 int 类型的零值(即 0),并将它的地址赋给 p,此时 p 是一个 *int 类型的变量。

  • make(T, args...):

  • make 函数主要用于切片(slices)、映射(maps)和通道(channels)这些引用类型。

  • 它不仅分配内存,还会进行一些额外的初始化工作,比如设置切片的长度和容量,或者为 map 分配桶。

  • 返回的是一个具体类型的实例,而不是指针。

  • 例如:m := make(map[string]int) 会创建一个新的空的字符串到整数的映射,并将其赋给 m

能不能用 new 创建一个 map

不推荐使用 new 来创建 map。因为 new 只是分配了内存并且初始化为零值,对于 map 来说,零值是一个 nil 的指针,这样的 map 是不可用的,你不能对其进行任何操作(如插入或查找键值对),否则会导致运行时错误。


正确的做法是使用 make 来创建 map,这样可以确保 map 被正确地初始化,并且可以直接使用。

3. 讲一下 gc

这个问题可以从以下几个方面来回答:

基本概念

  • 定义:垃圾回收是一种自动内存管理机制,它负责识别和释放不再使用的内存,从而避免内存泄漏。

  • 重要性:在 Go 中,GC 是自动进行的,这减少了程序员手动管理内存的工作量,降低了出错的可能性。

Go 的 GC 特点

  • 三色标记算法:Go 使用三色标记法来进行垃圾收集。这个过程分为白色、灰色和黑色对象,通过追踪引用关系来确定哪些对象仍然活跃。

  • 并发执行:Go 的 GC 是并发的,意味着垃圾收集可以在程序运行时进行,尽量减少停顿时间(STW, Stop-The-World),提高应用程序的响应性。

  • 非分代收集:与 Java 等语言不同,Go 的 GC 不是基于分代的。所有对象都在同一个堆中处理,这样可以简化垃圾收集逻辑,但可能会增加一些开销。

  • 非紧缩:Go 的 GC 不会移动存活的对象,而是使用指针更新来清理死对象的空间。这种方法避免了因移动对象而导致的额外开销。

  • 混合写屏障:为了支持并发标记,Go 引入了混合写屏障技术,它可以追踪在标记过程中发生的指针更新,确保不会遗漏任何存活的对象。

触发时机

  • 基于分配速度:GC 通常会在程序分配了一定量的新内存后触发。这个阈值会根据上一次 GC 后剩余的堆大小动态调整。

  • 显式调用:开发者也可以通过 runtime.GC() 显式地触发一次 GC,但这在大多数情况下并不推荐,因为自动 GC 已经很高效。

性能优化

  • 降低 STW 时间:Go 团队一直在努力减少 GC 的停顿时间,以提供更好的用户体验。

  • 可配置参数:可以通过设置 GOGC 环境变量或使用 debug.SetGCPercent 函数来调整 GC 的行为,比如设置堆增长的比例。

4. 说一下负载均衡有哪些算法

五种常见的负载均衡算法:

1. 轮询(Round Robin)

  • 描述:按照顺序将请求依次分配给每个服务器。

  • 优点

  • 简单易实现。

  • 在所有服务器性能相同时,可以均匀分配负载。

  • 缺点

  • 没有考虑服务器的实际处理能力和当前负载情况。

  • 如果服务器性能不一,可能会导致某些服务器过载。

2. 加权轮询(Weighted Round Robin)

  • 描述:为每个服务器分配一个权重值,权重高的服务器会获得更多的请求。

  • 优点

  • 可以更好地利用不同性能的服务器。

  • 适用于服务器处理能力不同的场景。

  • 缺点

  • 仍然不能实时反映服务器的实际负载状况。

  • 需要预先设置好每个服务器的权重。

3. 最少连接(Least Connections)

  • 描述:将请求发送到当前连接数最少的服务器。

  • 优点

  • 更公平地分配负载,特别是在服务器处理能力不同时。

  • 可以动态适应服务器的当前负载情况。

  • 缺点

  • 需要维护每个服务器的连接状态,可能会增加一些开销。

  • 实现相对复杂。

4. IP 哈希(IP Hash)

  • 描述:根据客户端 IP 地址的哈希值来决定转发到哪个服务器。

  • 优点

  • 确保来自同一个客户端的请求总是被发送到同一台服务器,有利于会话保持。

  • 适用于需要会话保持的应用。

  • 缺点

  • 如果某一台服务器出现问题,所有该服务器上的客户端都会受到影响。

  • 可能会导致负载不均。

5. 响应时间(Response Time)

  • 描述:根据服务器的响应时间来分配请求,响应时间越短的服务器获得更多的请求。

  • 优点

  • 可以动态调整负载,提高整体性能。

  • 适用于对响应时间敏感的应用。

  • 缺点

  • 需要持续监控服务器的响应时间,增加了管理复杂度。

  • 实现相对复杂,可能需要额外的监控机制。

5. 讲一下 MySQL 的 b+树

B+树是一种特殊的数据结构,主要用于数据库和文件系统中的索引。它可以帮助快速查找、插入和删除数据。B+树的特点是:


  1. 多层节点:有根节点、内部节点和叶子节点。

  2. 有序键值:每个节点中的键值都是有序的。

  3. 叶子节点链表:所有叶子节点通过指针连接成一个链表,方便范围查询。

  4. 数据存储在叶子节点:实际的数据记录(或指向数据的指针)只存储在叶子节点中。

B+树在 MySQL 中的作用

MySQL 使用 B+树来实现索引,特别是 InnoDB 存储引擎。主要有两种类型的索引:


  1. 主键索引(聚簇索引)

  2. 主键索引的叶子节点存储的是整行数据。

  3. 例如,如果你有一个 users 表,主键是 id,那么 B+树的叶子节点会存储每个用户的完整信息。

  4. 二级索引(非聚簇索引)

  5. 二级索引的叶子节点存储的是主键值。

  6. 例如,如果你有一个 name 索引,叶子节点会存储 name 和对应的 id 值,然后通过 id 再去主键索引中找到完整的用户信息。

6. 怎么解决哈希冲突

可以这么回答:


在哈希表中,哈希冲突是不可避免的,但有几种常用的方法可以有效地解决这个问题:


  1. 链地址法(Separate Chaining)

  2. 描述:每个哈希表的槽位存储一个链表。当发生冲突时,将新的元素添加到该槽位对应的链表中。

  3. 优点:实现简单,可以动态扩展,不受装载因子的影响。

  4. 缺点:如果链表过长,查找效率会下降,需要额外的内存来存储链表节点。

  5. 开放地址法(Open Addressing)

  6. 描述:当发生冲突时,寻找下一个可用的槽位来存放元素。常见的探测方法包括线性探测、二次探测和双重哈希。

  7. 线性探测:从冲突位置开始,依次检查下一个槽位,直到找到空闲的位置。

  8. 二次探测:从冲突位置开始,以平方数为步长进行探测,例如 1, 4, 9, 16 等。

  9. 双重哈希:使用第二个哈希函数来计算步长,从而避免聚集问题。

  10. 优点:不需要额外的指针或链表,节省内存。

  11. 缺点:当装载因子较高时,性能会显著下降,删除操作复杂。

  12. 再哈希法(Rehashing)

  13. 描述:当发生冲突时,使用另一个哈希函数重新计算哈希值,直到找到一个没有冲突的位置。

  14. 优点:可以减少冲突的概率。

  15. 缺点:需要多个哈希函数,实现较为复杂,在极端情况下可能仍然无法避免冲突。

  16. 布隆过滤器(Bloom Filter)

  17. 描述:布隆过滤器是一种空间效率高的概率型数据结构,用于判断一个元素是否在一个集合中。它可以用来减少哈希冲突的查询次数,但不能完全解决冲突。

  18. 优点:空间效率高,查询速度快。

  19. 缺点:存在误判率(假阳性),即可能会错误地认为一个元素在集合中,不能删除元素。

  20. 完美哈希(Perfect Hashing)

  21. 描述:构造一个哈希函数,使得所有键都不发生冲突。这通常需要两层哈希表,第一层用于分桶,第二层用于处理每个桶内的冲突。

  22. 优点:查找时间是常数 O(1)。

  23. 缺点:构造完美哈希函数比较复杂,且适用于静态集合(集合中的元素不会变化)。


根据具体的应用场景和需求,我会选择最合适的方法。

7. 说一下 slice 的扩容机制

切片的扩容机制是这样的:


  1. 初始分配:使用 make 函数创建一个切片时,可以指定长度和容量。如果没有指定容量,Go 会根据长度自动选择一个合适的容量。

  2. 容量不足时的处理:当使用 append 函数向切片追加元素时,如果当前容量不足以容纳新元素,Go 会创建一个新的更大的底层数组。扩容的具体规则如下:

  3. 如果旧容量小于 256:新容量 = 旧容量 * 2。

  4. 如果旧容量大于等于 256:新容量 = 旧容量 + (3 * 256 + 旧容量)/ 4。

  5. 数据迁移:将旧数组中的所有元素复制到新数组中,并更新切片的底层数组指针,使其指向新数组。

  6. 继续操作:在新数组上继续进行追加或其他操作。

8. map 是不是并发安全的,sync.map 的底层

标准库中的 map 类型并不是并发安全的。这意味着如果你有多个 goroutine 同时读写同一个 map,可能会导致数据竞争(data race)和未定义行为。为了在并发环境中安全地使用 map,Go 提供了 sync.Map 类型。

标准 map 的并发安全性

  • 非并发安全:标准 map 在多 goroutine 环境下不保证线程安全。如果需要在并发环境中使用 map,必须自己实现同步机制,例如使用 sync.Mutexsync.RWMutex 来保护 map 的访问。

sync.Map

sync.Map 是 Go 1.9 引入的一个并发安全的 map 实现。它提供了以下特性:


  • 并发安全:可以在多个 goroutine 中同时进行读写操作而不会发生数据竞争。

  • 高效读取:对于只读操作,sync.Map 不需要加锁,因此读取效率较高。

  • 动态扩容:内部会根据需要自动调整容量。

sync.Map 的底层实现

sync.Map 的底层实现比较复杂,但可以简要概括如下:


  1. 结构体定义

  2. sync.Map 内部包含两个主要部分:一个用于读取的 read 结构和一个用于写入的 dirty 结构。

  3. read 结构

  4. read 结构主要用于读取操作,它包含一个指针数组 m 和一个计数器 count

  5. m 数组存储键值对。

  6. count 记录当前 read 结构中的条目数量。

  7. 如果 count 为负数,表示正在进行写入操作或 read 结构已经被废弃。

  8. dirty 结构

  9. dirty 结构用于写入操作,它包含一个带锁的 map 和一个删除集合 misses

  10. map 存储实际的键值对。

  11. misses 用于记录那些在 read 结构中被删除但在 dirty 结构中还未删除的键。

  12. 读取操作

  13. 读取操作首先尝试从 read 结构中获取数据。

  14. 如果 read 结构中的 count 为负数或没有找到键,则会切换到 dirty 结构进行查找。

  15. 写入操作

  16. 写入操作总是通过 dirty 结构进行。

  17. 如果 dirty 结构不存在,则创建一个新的 dirty 结构,并将 read 结构标记为废弃。

  18. 写入完成后,如果满足某些条件(如 dirty 结构中的条目数量达到一定阈值),会将 dirty 结构的内容复制到新的 read 结构中,以提高后续读取操作的效率。

欢迎关注 ❤

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


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


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

用户头像

王中阳Go

关注

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

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

评论 (1 条评论)

发布
用户头像
欢迎大家向我投稿最新真实面经,有偿的哦
刚刚 · 北京
回复
没有更多了
得物一面,都是非常经典的问题_Go_王中阳Go_InfoQ写作社区