Golang面经总结

Golang语言相关

  1. go的channel 有缓存无缓存如何定义,区别 参考
    1. 注意点:如果一个通道被关闭了,我们就不能往这个通道里发送数据了,如果发送的话,会引起painc异常。但是,我们还可以接收通道里的数据,如果通道里没有数据的话,接收的数据是零值.
    2. 无缓冲的通道指的是通道的大小为0,也就是说,这种类型的通道在接收前没有能力保存任何值,它要求发送goroutine和接收goroutine同时准备好,才可以完成发送和接收操作。
    3. 从上面无缓冲的通道定义来看,发送goroutine和接收gouroutine必须是同步的,同时准备后,如果没有同时准备好的话,先执行的操作就会阻塞等待,直到另一个相对应的操作准备好为止。这种无缓冲的通道我们也称之为同步通道。
    4. 有缓冲通道内部有一个类似于队列机制的缓冲区,定义的时候通过make的第2个参数指定缓冲区大小,如果容量满了,接收将会阻塞,如果缓冲区空,发送将会阻塞。
    5. 如果给定了一个缓冲区容量,那么通道就是异步的,只要缓冲区有未使用空间用于发送数据,或还包含可以接收的数据,那么其通信就会无阻塞地进行
  2. goroutine内存泄漏场景 参考
    1. goroutine泄漏描述:如果你启动了一个 goroutine,但并没有符合预期的退出,直到程序结束,此goroutine才退出,这种情况就是 goroutine 泄露。
  3. go并发为什么快
  4. go垃圾回收
  5. go协程 java线程区别
  6. go数组和slice的区别
    1. 数组定长,定义的时候就需要确定。切片长度不定,append时会自动扩容
    2. 相同大小数组可以赋值,会拷贝全部内容。slice赋值和指针一样。数组和slice之间不能相互赋值。当然slice有自己的copy函数
    3. 数组也可以进行切片,返回值是一个slice,改变slice时会同步修改数组内容,相当于取得了这个数组的指针
  7. sync.Once的实现原理(上次哔哩哔哩面试问到了,幸亏我事后看了一眼是类似双重检验锁的实现方式哦),让我写出来,我写出了一大半,还让我运行一下,我运行不出来
  8. context包有没有用过,我说没用过
  9. 进程,线程,携程的区别
  10. go中导致内存泄漏的原因
  11. gin框架如何实现,我说用go内置的net http包实现的
  12. 逃逸分析讲一下
面试

(LeetCode系列)寻找旋转排序数组中的值

前言

在旋转数据中搜索值包括两个系列的题型:搜索旋转点(也就是最小值)以及搜索我们给定的目标值。关于旋转排序数组的定义这里就不再赘述

两个全排列的题目

第一道题

ZWdEW0

二叉树的序列化与反序列化

前言

序列化:二叉树被记录成文件的过程叫做序列化

反序列化:通过文件内容重建原来二叉树的过程叫做反序列化

Golang中刷题关于切片的一些坑

问题1

问题描述:递归的过程中,传递了一个切片作为参数,每次我们都需要对切片切取首元素,之后递归回来的时候发现切片中的元素还是没有切取首元素,是一个很严重的逻辑错误

问题解决:我们递归函数使用切片作为参数的时候,我们直接传入切片的地址。因为切片每次删除元素,地址也会改变。当切片增加元素引起扩容,地址也会发生改变,而如果只传入切片我们只是引用最开始的时候的切片的地址,因此会发现切片没有任何改变。

例如我们自己写的二叉树序列化和反序列化代码:在最开始只是传递一个切片,但是后来传递切片的地址进去发现代码逻辑正常运行。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
//方法一:使用先序遍历进行序列化和反序列化
//进行序列化
func PreorderSerialize(root *TreeNode) string {
if root == nil {
return "#!"
}

var ret string

ret += strconv.Itoa(root.Val) + "!"
ret += PreorderSerialize(root.Left)
ret += PreorderSerialize(root.Right)
return ret
}

//进行反序列化
func PreorderDeserialize(ret string) *TreeNode {
strs := strings.Split(ret, "!")

//注意点:由于切片在执行过程中有可能会因为增加和删除元素而造成切片不是原来那个切片,但是我们递归回去的时候还是指向原来的切片,因此会有问题
//所以这里我们传递的是切片的地址
//因为切片扩容可能会生成一个新的底层数组,并且由于切片移除了元素,因此对应的头部地址一定会改变,所以会造成地址的改变
root := ReconstructTreeFromPreorder(&strs)
return root
}

//根据我们分割后的字符串建立二叉树
func ReconstructTreeFromPreorder(strs *[]string) *TreeNode {
if (*strs)[0] == "#" {
(*strs) = (*strs)[1:]
return nil
}

//首先将该值对应的字符串转换为int
val, _ := strconv.Atoi((*strs)[0])
//建立一个针对于该值的节点
node := &TreeNode{
Val: val,
}

//去掉我们建立过的节点的值
(*strs) = (*strs)[1:]
//之后进行递归建立左右子树
node.Left = ReconstructTreeFromPreorder(strs)
node.Right = ReconstructTreeFromPreorder(strs)

return node
}

布隆过滤器总结

了解布隆过滤器

什么是布隆过滤器?

一个布隆过滤器精确地代表了一个集合。并不像哈希表那样存储原始信息,而是存储原始信息的压缩信息以节省空间,但牺牲了一定的准确度。

布隆过滤器的作用

可以精确地判断一个元素是否在这个集合中。注意只是精确代表和精确判断,到底有多精确,取决于我们自己的设计。想做到完全正确是不可能的,布隆过滤器的优势在于使用很少的空间就可以将准确率做到很高的程度。

固定长度的数组实现栈

题目描述

使用一个固定长度大小的数组实现栈

思路

思路:使用一个index进行指向当前可以插入元素的位置

  1. 使用一个index指向下次栈中加入元素的位置
  2. 如果要弹出元素,需要判断index是否大于1,如果大于弹出index-1位置的元素,index减去1,否则不可以弹出。
  3. 如果要加入元素,直接加入到index指向的位置,之后index++

固定长度的数组实现队列

题目描述

使用一个固定长度大小的数组实现队列

思路

思路:使用start指向队头,end指向队尾的下一个位置

  1. 我们加了一个标志位empty区分start等于end的两种情况,一种是队列中没有元素,另外一种是队列元素满。
  2. 如果要弹出元素,需要判断end是否等于start,如果empty为真且start等于end,说明不可以弹出,否则可以弹出元素。
  3. 如果要加入元素,直接加入到end指向的位置,之后end需要判断是否处于最后一个位置,如果是则跳转到数组第1个位置,否则end++。同时判断是否满元素来更新empty

不基于比较的排序找到数组排序后的最大差值

题目描述

给定一个数组,求如果排序之后,相邻两数的最大差值,要求时 间复杂度O(N),且要求不能用非基于比较的排序

注意不基于比较哦

思路

思路:桶排序

  1. 假设数组长度为n,准备n+1个桶
  2. 遍历该数组,将最小值放入到第1个位置,将最大值放入到最后一个位置
  3. 将剩下的数等分成等分成n-1份依次放入剩下对应范围的桶中,
  4. 最后这n+1个桶中至少有一个空桶,说明桶内的数值差不是最大差值,我们去桶间找最大差值
  5. 对于每个桶,我们都保存了每个桶的最小值和最大值,从第2个桶开始,每次计算当前桶的最小值与前一个桶(要有元素)的最大值的差,过程中我们动态更新最大差值

堆排序

堆排序基本知识

基本介绍

堆是一个完全二叉树,因此我们可以利用节点的特性去使用一个数组模拟一颗完全二叉树:

  1. 下标为i的节点的左子节点的下标为i*2+1, 右子节点的下标为i*2+2
  2. 下标为i的节点的父节点的下标为(i-1)/2

建立堆的时间复杂度:O(log1) + O(log2) + … + O(logN) 近似于 O(N),因此建立堆的时间复杂度为O(N)

堆有大根堆以及小根堆,没有规定堆中左子树的根必须大于(或小于)右子树的根。

堆排序的两个基本步骤:(具体说明看代码注释)

  1. 建堆,循环将数组中的每个数加入堆中(每次都需要heapInsert)
  2. 不断从堆的最后一个元素交换到堆的头部,然后将堆的长度减小1,再调整堆,每次都需要heapify