大家好，我是皇子。

从开始寻找面试机会开始，写好简历是一个特别重要的环节，不管你是有经验的大佬，还是技术小白，简历写得好不好，与你能否有机会参与面试有关。

而一旦我们到简历中的技术点，都需要好好准备下，因为你写上去的之后，面试官都会重点关注，还会追着问，看你是否真正掌握了，所以大家对于写上去的知识点，一定要深度学习恶补好。

今天分享一份腾讯Golang后端面经，上来的算法题还是比较顺利的，20分钟就写完了，不过在被追着问到具体技术点时，慌了，结果还是等待中，不过大概率凉了。

算法

堆排序

手写一个大根堆排序

思路：堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。而大根堆是每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列。

大根堆排序，Golang 代码

func HeapSort() {
	arr := []int{5, 3, 2, 1, 4}
	HeapSort(arr)
}

func heapSort(arr []int) []int {
	l := len(arr)
	// 获取节点，在从下往上每个节点上构建大根堆，最终得到完整的大根堆
	for i := l / 2; i >= 0; i-- {
		heapMaxRoot(arr, i, l)
	}

	for i := l - 1; i >= 0; i-- {
		// 把堆首（最大值）和堆尾互换
		pkg.SwapInt(arr, 0, i)

		// 重新构建大根堆
		l--
		heapMaxRoot(arr, 0, l)
	}

	return arr
}

// 构建大根堆
func heapMaxRoot(arr []int, i, l int) {
	// i为父节点，确定左右节点索引
	left := i*2 + 1
	right := i*2 + 2
	// 最大值的索引，初始值为i
	maxNumIndex := i
	// 确定存在最大值的索引是否在左右节点
	if left < l && arr[left] > arr[maxNumIndex] {
		maxNumIndex = left
	}
	if right < l && arr[right] > arr[maxNumIndex] {
		maxNumIndex = right
	}
	// 不为当前根节点时，交换数据，并在当时最大值的节点上继续构建大根堆
	if maxNumIndex != i {
		pkg.SwapInt(arr, i, maxNumIndex)
		heapMaxRoot(arr, maxNumIndex, l)
	}
}

追着问Golang部分

介绍协程

是Golang 在语言级别支持的一种轻量级线程，称之为 Goroutine,。Golang 标准库提供的所有系统调用操作(包括所有的同步 I/O 操作)，都会出让 CPU 给其他Goroutine。这让 Goroutine 的切换管理不依赖于系统的线程和进程，也不依赖于 CPU 的核心数量，而是交给 Golang 的运行时统一调度。

Go1.19

Go运行时将根据goroutine的历史平均栈使用率来分配初始goroutine栈，避免了一些goroutine的最多2倍的goroutine栈空间浪费。

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()

是否可以无限开辟协程？

不可以。

我们知道goroutine具备轻量、高效GPM调度的特点，如果无限开辟goroutine，短时间内会占用大量的占用操作系统的资源（文件描述符、CPU、内存等）：

CPU浮动上涨；
内存占用持续身高；
主进程被操作系统杀死；

这些资源实际上是用户态程序共享的资源，所以大批的goroutine最终引发灾难不仅仅是自身，还会关联其他运行的程序。

控制协程数量有哪些方式

1）只用有buffer的channel

例如使用一个有缓冲的channel。当channel满了的时候，其会发生阻塞，避免一直不断的开辟goroutine。完整代码如下：

package main

import (
  "fmt"
  "math"
  "runtime"
)

func MyWork(c chan bool,i int){
  fmt.Println("go func ",i," goroutine count=",runtime.NumGoroutine())
  <- c
}

func main(){
  // 模式业务需要开辟的数量
  task_cnt := math.MaxInt64
  // 创建一个带缓冲的channel
  myChan := make(chan bool,3)

  // 测试是否可以无限go
  // 循环创建业务
  for i := 0 ; i< task_cnt;i++ {
	      myChan <- true
	      go  MyWork(myChan,i)
  }
}

按照上面的方式使得能够一直运行。其实实际上，执行的只有3个（还有一个main goroutine）。上面代码的本质就是在myChan <- true处会阻塞，直到之前三个中有一个完成了任务，阻塞结束，才开辟一个新的goroutine。

2）channel与sync同步组合方式

如果我们只使用sync的WaitGroup会怎么样？

package main
import (
	"fmt"
	"math"
	"runtime"
	"sync"
)

// 创建一个全局的wait_group{}
var wg = sync.WaitGroup{}
func MyWork(i int){
	fmt.Println("go func ",i," goroutine count=",runtime.NumGoroutine())
	wg.Done()
}

// 测试是否可以无限go
func main(){
	// 模式业务需要开辟的数量
	task_cnt := math.MaxInt64
	// 循环创建业务
	for i := 0 ; i< task_cnt;i++ {
	wg.Add(1)
	go  MyWork(i)
	}
	// 阻塞等待
	wg.Wait()
}

结果是仍然无法大量开辟，主线程会被操作系统杀死。

channel与sync同步组合方式,是没问题

package main

import (
  "fmt"
  "math"
  "runtime"
  "sync"
)

// 创建一个sync.WaitGroup{}变量
var wg = sync.WaitGroup{}

func MyWork(c chan bool,i int){
  fmt.Println("go func ",i," goroutine count=",runtime.NumGoroutine())
  wg.Done()
  <- c
}

// 测试是否可以无限go
func main(){
  // 模式业务需要开辟的数量
  task_cnt := math.MaxInt64
  // 创建一个带缓冲的channel
  myChan := make(chan bool,3)

  // 循环创建业务
  for i := 0 ; i< task_cnt;i++ {
	      wg.Add(1)
	      myChan <- true
	      go  MyWork(myChan,i)
  }
  wg.Wait()
}

3）利用无缓冲channel与任务发送/执行分离方式

package main

import (
  "fmt"
  "math"
  "runtime"
  "sync"
)

// 定义一个WaitGroup类型的变量，保证所有的任务都能执行完毕
var wg = sync.WaitGroup{}

// 任务执行函数
func MyWork(c chan int){
  // 表示业务执行完毕
  defer wg.Done()
  for t := range c {
	    // 模拟业务处理逻辑
	    fmt.Println(t)
  }

}

// 发送业务的函数
func SendTask(c chan int,task int){
  // 保证所有的任务都能执行完毕
  wg.Add(1)
  c <- task
}

func main(){
  // 创建一个无缓冲的通道
  myChan := make(chan int)
  // 开辟固定数量的协程
  for i := 0; i < 3 ; i++ {
	    go MyWork(myChan) // 他们都会各自内部阻塞，等待任务发送过来
  }
  // 最大任务数量
  task_cnt := math.MaxInt64
  // 开始发送任务
  for i := 0 ; i < task_cnt ; i++ {
	    SendTask(myChan,i)
  }
  // 等待
  wg.Wait()
}

这里实际上是将任务的发送和执行做了业务上的分离。使得输入SendTask的频率可设置、执行Goroutine的数量也可设置。也就是既控制输入(生产)，又控制输出(消费)。使得可控更加灵活。这也是很多Go框架的Worker工作池的最初设计思想理念。

如何并发访问Map

在 Go 语言中，如果多个 goroutine 并发访问同一个 map，可能会出现竞态条件（race condition）的问题，导致程序崩溃或者出现不可预期的结果。

具体来说，如果一个 goroutine 正在对 map 进行写操作，而另一个 goroutine 正在对同一个 map 进行读或写操作，就可能会出现竞态条件。这因为 map 不是并发安全的数据结构，它的内部实现可能会在多个 goroutine 同时访问时出现问题。

为了避免这种问题，可以使用 Go 语言提供的 sync 包中的 Map 类型，或者使用互斥锁（Mutex）来保证 map 的访问是串行化的，从而避免竞态条件的出现。

ITPub博客

被腾讯追着问，慌了

算法

堆排序