综合面试题整理

排序

归并排序

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
def merge_sort(li):
# 当列表的长度为1时,不需要再拆分
if len(li) == 1:
return li
# 取一个中间位置,把数据拆分成左右两半
mid = len(li)//2
left = li[:mid]
right = li[mid:]

# 递归继续拆分
left_res = merge_sort(left)
right_res = merge_sort(right)
# 合并下层方法返回的结果,并且进行排序
res = merge(left_res,right_res)
return res
def merge(left,right):
"""把两个有序的序列组成有序序列"""
# 定义两个下标,分别指向两个序列的0位置
left_index = 0
right_index = 0
# 创建临时列表
res = []
while left_index < len(left) and right_index < len(right):
if left[left_index] <= right[right_index]:
res.append(left[left_index])
left_index += 1
else:
res.append(right[right_index])
right_index += 1
res = res + left[left_index:]
res = res + right[right_index:]
return res

快速排序

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
 def quick_sort(li,start,end):
# 当start=end时,证明只对一个数排序,不需要排序
# 当start>end时,证明没有需要排序的数据
if start >= end:
return
# 定义两个下标,一个是头,一个是尾
left = start
right = end
# 把第一个数当作中间值
mid = li[left]
# 不停的让右边下标往左移动,左边下标往右移动,直到左右下标相等
while left < right:
# 右边下标往左移动,找到一个小于mid的数据
while left < right and li[right] >= mid:
right -= 1
# 循环结束时,right指向的数据小于mid,把数据放到左边下标位置
li[left] = li[right]
# 左边下标往右移动,找到一个大于mid的数据
while left < right and li[left] <= mid:
left += 1
# 循环结束时,left指向的数据大于mid,把数据放到右边下标位置
li[right] = li[left]
# 循环结束时,left=right,把mid放到此位置
li[left] = mid
# 递归让左边的数据继续快排
quick_sort(li,start,left-1)
# 递归让右边的数据继续快排
quick_sort(li,left+1,end)
if __name__ == '__main__':
l = [7,6,5,4,3,2]
quick_sort(l,0,len(l)-1)
print(l)

Docker

docker 容器和虚拟机隔离级别的区别

  • 从两者的架构图上看,虚拟机是在硬件级别进行虚拟化,模拟硬件搭建操作系统;而Docker是在操作系统的层面虚拟化,复用操作系统,运行Docker容器。
  • Docker的速度很快,秒级,而虚拟机的速度通常要按分钟计算。
  • Docker所用的资源更少,性能更高。同样一个物理机器,Docker运行的镜像数量远多于虚拟机的数量。
  • 虚拟机实现了操作系统之间的隔离,Docker算是进程之间的隔离,虚拟机隔离级别更高、安全性方面也更强。
  • 虚拟机和Docker各有优势,不存在谁替代掉谁的问题,很多企业都采用物理机上做虚拟机,虚拟机中跑Docker的方式。

缓存

http缓存机制

http缓存分类

  • 数据库缓存
  • 服务器端缓存(代理服务器缓存、CDN 缓存)
  • 浏览器缓存 ( HTTP 缓存、indexDB、cookie、localstorage 等等)

缓存相关术语

  • 缓存命中率:从缓存中得到数据的请求数与所有请求数的比率。理想状态是越高越好。
  • 过期内容:超过设置的有效时间,被标记为“陈旧”的内容。通常过期内容不能用于回复客户端的请求,必须重新向源服务器请求新的内容或者验证缓存的内容是否仍然准备。
  • 验证:验证缓存中的过期内容是否仍然有效,验证通过的话刷新过期时间。
  • 失效:失效就是把内容从缓存中移除。当内容发生改变时就必须移除失效的内容。
  • 浏览器缓存: 是 HTTP 协议定义的缓存机制。HTML meta 标签,例如 Pragma: no-store; 含义是让浏览器不缓存当前页面。但是代理服务器不解析 HTML 内容,一般应用广泛的是用 HTTP 头信息控制缓存。

浏览器缓存分类

浏览器缓存主要有两类:缓存协商和彻底缓存,也有称之为协商缓存和强缓存。

1.强缓存:不会向服务器发送请求,直接从缓存中读取资源,在chrome控制台的network选项中可以看到该请求返回200的状态码;

2.协商缓存:向服务器发送请求,服务器会根据这个请求的request header的一些参数来判断是否命中协商缓存,如果命中,则返回304状态码并带上新的response header通知浏览器从缓存中读取资源;

两者的共同点是,都是从客户端缓存中读取资源;区别是强缓存不会发请求,协商缓存会发请求。

浏览器使用缓存加载页面流程

浏览器缓存分为强缓存和协商缓存,浏览器加载一个页面的简单流程如下:

  1. 浏览器先根据这个资源的http头信息来判断是否命中强缓存。如果命中则直接加在缓存中的资源,并不会将请求发送到服务器。
  2. 如果未命中强缓存,则浏览器会将资源加载请求发送到服务器。服务器来判断浏览器本地缓存是否失效。若可以使用,则服务器并不会返回资源信息,浏览器继续从缓存加载资源。
  3. 如果未命中协商缓存,则服务器会将完整的资源返回给浏览器,浏览器加载新资源,并更新缓存。

Zookeeper

Zookeeper 如何保证数据 一致性的

一致性实现方法

ZooKeeper是个集群,内部有多个server,每个server都可以连接多个client,每个client都可以修改server中的数据
ZooKeeper可以保证每个server内的数据完全一致,是如何实现的呢?

答:数据一致性是靠Paxos算法保证的,Paxos可以说是分布式一致性算法的鼻祖,是ZooKeeper的基础

paxos介绍

假设有一个社团,其中有团员、议员(决议小组成员)两个角色

团员可以向议员申请提案来修改社团制度

议员坐在一起,拿出自己收到的提案,对每个提案进行投票表决,超过半数通过即可生效
为了秩序,规定每个提案都有编号ID,按顺序自增

每个议员都有一个社团制度笔记本,上面记着所有社团制度,和最近处理的提案编号,初始为0
投票通过的规则:

新提案ID 是否大于 议员本中的ID,是议员举手赞同

如果举手人数大于议员人数的半数,即让新提案生效

例如:
刚开始,每个议员本子上的ID都为0,现在有一个议员拿出一个提案:

团费降为100元,这个提案的ID自增为1每个议员都和自己ID对比,一看 1>0,举手赞同,同时修改自己本中的ID为1发出提案的议员一看超过半数同意,就宣布:1号提案生效然后所有议员都修改自己笔记本中的团费为100元

以后任何一个团员咨询任何一个议员:”团费是多少?”,议员可以直接打开笔记本查看,并回答:团费为100元
可能会有极端的情况,就是多个议员一起发出了提案,就是并发的情况

例如
刚开始,每个议员本子上的编号都为0,现在有两个议员(A和B)同时发出了提案,那么根据自增规则,这两个提案的编号都为1,但只会有一个被先处理

假设A的提案在B的上面,议员们先处理A提案并通过了,这时,议员们的本子上的ID已经变为了1,接下来处理B的提案,由于它的ID是1,不大于议员本子上的ID,B提案就被拒绝了,B议员需要重新发起提案

大数据组件

Flume 如何保证数据不丢失不重复

  1. Flume采用基于Transactions的方式保证数据传输的可靠性,当数据从一个Agent流向另外一个Agent时,两个Transactions已经开始生效。发送Agent的Sink首先从Channel取出一条消息,并且将该消息发送给另外一个Agent。如果接受消息的Agent成功地接受并处理消息,那么发送Agent将会提交Transactions,标识一次数据传输成功可靠地完成。

  2. 当接收Agent接受到发送Agent发送的消息时,开始一个新的Transactions,当该数据被成功处理(写入Channel中),那么接收Agent提交该Transactions,并向发送Agent发送成功响应。

  3. 如果在某次提交(commit)之前,数据传输出现了失败,将会再次开始上一次Transcriptions,并将上次发送失败的数据重新传输。因为commit操作已经将Transcriptions写入了磁盘,那么在进程故障退出并恢复业务之后,仍然可以继续上次的Transcriptions。

刘小恺(Kyle) wechat
如有疑问可联系博主