Golang面经总结

无法分类的问题 讲一下协程和线程的区别 3次 进程和线程的区别 1次 Epoll rpc框架序列化解决了什么问题 grpc框架 一致性hash是怎么做的 为什么 讲讲levelDB和RockesDB的区别 分布式锁改进和优化 怎么处理锁分段 缓存一致性问题怎么解决的优劣呢? hash的选型和一致性hash rpc框架解决了什么问题 grpc和jsonrpc的优劣 分布式框架的解决方案 路由网...
面试

面试问题之Top K系列

思路整理:

如图所示

  1. aLjufN
  2. b8s2H2

几种方法讲解

以剑指offer40题为例,求最小的k个数字

方法一:

思路:直接用最快的排序方法排好序后取前k个或者后k个元素即可

时间复杂度:O(n * logn)
空间复杂度:O(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
50
51
52
func getLeastNumbers(arr []int, k int) []int {
return QuickSort(arr)[:k]
}

func QuickSort(nums []int) []int {
quickSort(nums, 0, len(nums)-1)
return nums
}

func quickSort(nums []int, low int, high int) {
var pivotkey int
//优化1:尾递归优化
for low < high {
//pivotkey 为枢轴防止的最终下标
pivotkey = partition(nums, low, high)
quickSort(nums, low, pivotkey-1)
low = pivotkey + 1
}
}

func partition(nums []int, low int, high int) int {
//优化2:使用随机数选择划分枢轴
//设置随机数种子
rand.Seed(time.Now().UnixNano())
//选择[0,n)
//rand.Intn(n)
//选择划分元素
dummyIndex := rand.Intn(high-low+1) + low
//将随机选择的元素放置到low位置上,以后便于在高处找到比划分元素小的时候我们可以直接让high赋值给low
swap(nums, low, dummyIndex)
dummyVal := nums[low]
for low < high {
for low < high && dummyVal <= nums[high] {
high--
}
//优化3:我们使用替换而不是交换
//高处找到小的直接赋值给low
nums[low] = nums[high]
for low < high && dummyVal >= nums[low] {
low++
}
//低处找到大的直接赋值给high
nums[high] = nums[low]
}
//最后low == high
nums[low] = dummyVal
return low
}

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

方法二:

思路:冒泡排序每次都会将1个元素放置到最终位置上,我们可以冒泡k趟

时间复杂度:O(k * n)
空间复杂度:O(1)

代码

1
2
3
4
5
6
7
8
9
10
11
12
func getLeastNumbers(arr []int, k int) []int {
//需要冒泡k次
for i := 1; i <= k; i++ {
//每次从倒数第2个元素开始一直到前面的第i-1个元素,例如第1趟是到第0个(因为每次是和后面的元素进行比较)
for j := len(arr) - 2; j >= i-1; j-- {
if arr[j] > arr[j+1] {
arr[j+1], arr[j] = arr[j], arr[j+1]
}
}
}
return arr[:k]
}

固定长度的数组实现栈

题目描述

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

思路

思路:使用一个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

归并排序

应用场景

  1. 求小和
  2. 求逆序对的个数

几个注意点:

mid := l + (r-l)>>1 避免数组越界

for i <= mid { help[index] = nums[i] index++ i++ },这里是一个for循环,不是if,因为是要将后面剩下的数拷贝进来

for i <= mid { help[index] = nums[i] index++ i++ },这里是一个for循环,不是if,因为是要将后面剩下的数拷贝进来

go中的heap实现大根堆与小根堆

小根堆

几个注意点:

  1. 我们使用Less比较的时候决定了大根堆或小根堆
  2. push以及pop需要传入指针,因为涉及到改动。
  3. pop的时候需要删除最后一个,因为我们是append自己模拟进去的
  4. 我们自己用堆加入元素的时候需要使用heap中的方法来加入元素heap.push()和删除元素heap.pop()
  5. 如果我们自己想要查看堆顶,切片中索引为0对应的元素就是堆顶
1
2
3
4
5
minHeap := &MinHeap{}
heap.Init(minHeap)
heap.Push(minHeap, 123)
heap.Push(minHeap, 999)
num := heap.Pop(minHeap) //将会弹出堆顶

冒泡排序以及优化

冒泡排序

思路:从左向右每次两两比较相邻元素,如果前一个元素大于后一个元素,那么就交换这两个元素,一趟下来肯定有一个元素放到了最后的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func BubbleSort(nums []int) []int {
bubbleSort(nums)
return nums
}

func bubbleSort(nums []int) {
//从前往后进行交换,每次都会固定好后面的元素
for i := 0; i < len(nums)-1; i++ {
for j := 0; j < len(nums)-1-i; j++ {
//两两比较并交换
if nums[j] > nums[j+1] {
nums[j], nums[j+1] = nums[j+1], nums[j]
}
}
}
}

选择排序

选择排序

思路:每次选择一个当前未排序的最小元素放到当前未排序的第一个位置上

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func SelectSort(nums []int) []int {
selectSort(nums)
return nums
}

func selectSort(nums []int) {
//存储最小元素对应的下标
var min int
//进行多少趟
for i := 0; i < len(nums)-1; i++ {
min = i
//每趟从哪里开始
j := i + 1
for ; j < len(nums)-1; j++ {
if nums[min] > nums[j] {
min = j
}
}
if min != i {
nums[i], nums[min] = nums[min], nums[i]
}
}
}