面试问题之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]
}

计算机网络面试题整理

操作系统协程,线程,进程,以及区别 操作系统为了跟踪每个进程的活动状态,维护了一个进程表。进程表的内部列出了每个进程的状态以及每个进程使用的资源等。 进程:正在执行程序的一个实例,是资源分配的基本单位。(进程控制块(process control block)描述进程的基本信息和运行状态,所谓的创建和撤销进程,都是指对PCB的操作)线程:进程中的单条流向,是程序独立调度的基本单位。 区别:...

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) //将会弹出堆顶

内存泄漏与内存溢出

内存泄漏与内存溢出:

前缀树

前缀树的结构: 结点的话本身不存储任何单词,它只存它要去到下一个路径上面这个路径代表的字符。 基本性质 结点本身不存储完整的单词。 从根节点到某一结点,路径上经过的字符连接起来,为该节点对应的字符串。 每个节点的所有子节点路径代表的字符都不相同。 走过的边就形成了单词 前缀树中的单词可以存储额外的信息,例如频次,后续的话我们就可以给用户做相应的推荐, 因为每个节点后面都有26个可能的字...

单工通信,半双工通信,双工通信

1. 单工通信(simplex)只有一个信道不可改变方向 单工通信只支持信号在一个方向上传输(正向或反向),任何时候不能改变信号的传输方向。为保证正确传送数据信号,接收端要对接收的数据进行校验,若校验出错,则通过监控信道发送请求重发的信号。 应用:此种方式适用于数据收集系统,如气象数据的收集、电话费的集中计算等。例如计算机和打印机之间的通信是单工模式,因为只有计算机向打印机传输数据,而没有相...

描述输入url到页面呈现的整个过程

大致过程客户端获取URL - > DNS解析 - > TCP连接 - >发送HTTP请求 - >服务器处理请求 - >返回报文 - >浏览器解析渲染页面 - > TCP断开连接 详细文字讲解客户端: (应用层开始)获取URL,通过负责域名解析的DNS服务获取网址的IP地址,根据HTT协议生成HTTP请求报文(应用层结束) (传输层开始)根据TCP协...

https面试题

https中ssl的握手过程,为什么不一致用非对称加密?https中ssl的握手过程为什么不一直用非对称加密? 使用非对称密钥用于传入对称密钥来保证传输过程的安全性,之后使用对称密钥加密进行通信来保证通信过程的效率 非对称加密加密解密算法效率较低,不适合客户端和服务器端这样高频率的通信过程,在某些极端情况下,甚至能比非对称加密慢上1000倍。 非对称加密的优势在于它可以很好帮助完成秘钥的交换...

TCP面试整理

第1题:请详细介绍一下TCP的三次握手机制,为什么需要三次握手?2个点: 为什么需要握手? 为什么是3次握手?(建连接需要3次握手,关闭连接需要4次握手) TCP一个重要特性便是可靠性,必须对方告诉说收到消息才算收到消息,不然就会一直重发,互相发的时候如何确定消息发过去呢?给消息进行一个编号叫序列号,序列号不能从0开始,相对随机,需要通过握手同步序列号确定双方都收到消息。 正常是4次,但...

并发,并行,异步,同步,长连接,短连接,阻塞,非阻塞

同步和异步区别同步和异步最大的区别就是被调用方的执行方式和返回时机。同步指的是被调用方做完事情之后再返回,异步指的是被调用方先返回,然后再做事情,做完之后再想办法通知调用方。 阻塞和非阻塞阻塞请求,A调用B,A一直等着B的返回,别的事情什么也不干。 非阻塞请求,A调用B,A不用一直等着B的返回,先去忙别的事情了。 区别阻塞和非阻最大的区别就是在被调用方返回结果之前的这段时间内,调用方是否一直...
面试