大家好，我是皇子。

字节，在界内有个名称叫宇宙厂，是因为字节跳动主宰了宇宙内一切App，有点家大业大的意思。

今天分享一位字节后端开发的面经，问了很多Redis和Golang八股。

在Golang部分虽然问得很细，但是准备得比较好的，应该没有多大问题。

不过在redis部分，有很多一下子没想起来的，特别是谈到跳跃表时卡住了，有点慌...等待结果中。

下面我抽取一些罗列一下，也针对每个问题给出解析，方便大家查缺补漏。

算法题

数组中重复的数字

在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的，也不知道每个数字重复几次。请找出数组中任意一个重复的数字。

Input:
{2, 3, 1, 0, 2, 5}

Output:
2

要求时间复杂度 O(N)，空间复杂度 O(1)。因此不能使用排序的方法，也不能使用额外的标记数组。

对于这种数组元素在 [0, n-1] 范围内的问题，可以将值为 i 的元素调整到第 i 个位置上进行求解。在调整过程中，如果第 i 位置上已经有一个值为 i 的元素，就可以知道 i 值重复。

以 (2, 3, 1, 0, 2, 5) 为例，遍历到位置 4 时，该位置上的数为 2，但是第 2 个位置上已经有一个 2 的值了，因此可以知道 2 重复：

func duplicate(nums []int) int {
	for i := 0; i < len(nums); i++ {
		for nums[i] != i {
			if nums[i] == nums[nums[i]] {
				return nums[i]
			}
			swap(nums, i, nums[i])
		}
		swap(nums, i, nums[i])
	}
	return -1
}

func swap(nums []int, i int, j int) {
	t := nums[i]
	nums[i] = nums[j]
	nums[j] = t
}

Golang

GMP是什么

G（Goroutine）：我们所说的协程，为用户级的轻量级线程，每个 Goroutine 对象中的 sched 保存着其上下文信息。
M（Machine）：对内核级线程的封装，数量对应真实的 CPU 数（真正干活的对象）。
P（Processor）：即为 G 和 M 的调度对象，用来调度 G 和 M 之间的关联关系，其数量可通过 GOMAXPROCS()来设置，默认为核心数。

GMP 调度流程

GMP 中 work stealing 机制

M获取 P 本地队列，当M从绑定的 P 本地 runq 上找不到可执行的G，尝试从全局队列中拿，再拿不到从 netpoll 和事件池里拿，最后会从别的 P 里偷取一半G来执行，P此时去唤醒一个 M，P 继续执行其它的程序。

GMP 中 hand off 机制

当本线程 M 因为 G 进行的系统调用阻塞时，线程释放绑定的 P，把 P 转移给其他空闲的 M 执行。

细节：当发生上下文切换时，需要对执行现场进行保护，以便下次被调度执行时进行现场恢复。Go 调度器 M 的栈保存在 G 对象上，只需要将 M 所需要的寄存器（SP、PC 等）保存到 G 对象上就可以实现现场保护。当这些寄存器数据被保护起来，就随时可以做上下文切换了，在中断之前把现场保存起来。如果此时 G 任务还没有执行完，M 可以将任务重新丢到 P 的任务队列，等待下一次被调度执行。当再次被调度执行时，M 通过访问 G 的 vdsoSP、vdsoPC 寄存器进行现场恢复（从上次中断位置继续执行）。

GMP 调度过程中存在哪些阻塞

I/O(文件/网络)
block on syscall
select{}
channel
等待锁
runtime.Gosched()

介绍下 channel

Go 语言中，不要通过共享内存来通信，而要通过通信来实现内存共享。

Go 的CSP(Communicating Sequential Process)并发模型，中文可以叫做通信顺序进程，是通过 goroutine 和 channel 来实现的。

channel 收发遵循先进先出 FIFO 的原则。分为有缓冲区和无缓冲区。

在 Go 语言中，channel 的数据结构包含以下几个属性：

buffer：表示 channel 的缓冲区大小，即可以缓存的元素个数。如果 channel 是无缓冲的，则 buffer 为 0。

sendx：表示下一个可写入的位置的索引。

recvx：表示下一个可读取的位置的索引。

sendq：表示等待写入的 goroutine 队列。

recvq：表示等待读取的 goroutine 队列。

channel有什么特点

空(nil)channel：

发送和接收数据都会发生永久阻塞

已经关闭的 channel

发送会引起panic;
接收会返回一个零值

Channel 缓冲有什么特点？

无缓冲的 channel 是同步的，而有缓冲的 channel 是异步的。

定义结构体时需要注意

字段顺序：结构体中字段的类型大小从大到小的顺序排列可以最小化结构体的内存占用，并提高内存访问效率，因此，这种排列方式通常是比较合理的选择。但是，在一些特殊情况下，按照其他的排序方式也可能更加适合实际需求。

数据类型：结构体中字段的类型应该尽量使用基本类型，避免使用复杂类型，这样可以减少填充字节的数量，提高内存利用。

数据类型大小：结构体中的字段的大小应该尽量相同，这样可以减少填充字节的数量，提高内存利用率。

空结构体：空结构体（不含任何字段）在 Go 中不占用内存空间。但在某些情况下（如作为其他结构体的成员或数组元素），出于对齐目的，它可能会占用至少一个字节。

虽然上面都考虑到了内存对齐和节省空间，但实际情况不应牺牲代码可读性和维护性。过度调整字段顺序以追求微小的内存节省可能得不偿失。

Redis

描述下 ZSET（有序集合）

简介：已排序的字符串集合，同时元素不能重复

简单格式举例：zadd key score member [score member ...]，zrank key member

> zadd zset-key 728 member1
(integer) 1> zadd zset-key 982 member0
(integer) 1> zadd zset-key 982 member0
(integer) 0

> zrange zset-key 0 -1 withscores
1) "member1"
2) "728"
3) "member0"
4) "982"

> zrangebyscore zset-key 0 800 withscores
1) "member1"
2) "728"

> zrem zset-key member1
(integer) 1> zrem zset-key member1
(integer) 0

> zrange zset-key 0 -1 withscores
1) "member0"
2) "982"

**底层内部编码：ziplist（压缩列表）、skiplist（跳跃表）**应用场景：排行榜，社交需求（如用户点赞）

谈谈跳跃表

跳跃表是有序集合的底层实现之一
跳跃表实现由zskiplist和zskiplistNode两个结构组成，其中zskiplist用于保存跳跃表信息（如表头节点、表尾节点、长度），而zskiplistNode则用于表示跳跃表节点。
跳跃表是Redis特有的数据结构，跳跃表就是在链表的基础上，增加多级索引提升查找效率。
跳跃表支持平均 O（logN）,最坏 O（N）复杂度的节点查找，还可以通过顺序性操作批量处理节点。

在查找时，从上层指针开始查找，找到对应的区间之后再到下一层去查找。下图演示了查找 22 的过程。

跳跃表与红黑树等平衡树相比的优点

插入速度非常快速，因为不需要进行旋转等操作来维护平衡性；
更容易实现；
支持无锁操作。

推荐阅读：

详细、简单地学习这6种架构设计原则，再学设计模式也是 So Easy的事

被腾讯追着问，慌了

简历这样写，加分！保姆级教程

免费学习网站：https://itgogogo.cn

后台发送【简历】，领取简历摸板

ITPub博客

字节二面出来，有点慌...

算法题