「架构师训练营 4 期」 第八周 - 001&2

作业一

（至少完成一个）

有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，也可能不合并，如下图所示的这样。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。

请用代码（或伪代码）描述算法，并给出时间复杂度。

请画出 DataNode 服务器节点宕机的时候，HDFS 的处理过程时序图。



第一题

问题分析

从这道题来看，找到 x 就是要知道对于两个链表之间的数据差值。让我们把它转换成一个数学问题来思考。

假设链表长度分别是 n 和 m，且 n > m，合并点开始到结尾的长度是一致的，两个链表之间的数据差值是 x，那么 n - x = m，需要知道的值就是 x = n -m ，对于链表这种数据结构来看如何得到 n - m 这个数值查呢？大家就很容易想到，就是把 m 和 n 链表头尾相连。

答案说明

我们使用两个指针 node1，node2 分别指向两个链表 headA，headB 的头结点，然后同时分别逐结点遍历，当 node1 到达链表 headA 的末尾时，重新定位到链表 headB 的头结点；当 node2 到达链表 headB 的末尾时，重新定位到链表 headA 的头结点。

这样，当它们相遇时，所指向的结点就是第一个公共结点，时间复杂度 O(n)。

伪代码



-- coding:utf-8 --

class ListNode:

def _init_(self, x):

self.val = x

self.next = None

class Solution:

def FindFirstCommonNode(self, pHead1, pHead2):

# write code here

p1= pHead1

p2= pHead2

while p1 != p2:

p1 = p1.next if p1 else pHead2

p2 = p2.next if p2 else pHead1

return p1



第二题

作业二

红黑树原理与性能特性

二叉树

二叉树递归定义：左子树上所有的节点的值均小于他的根节点的值；右子树的根节点的值都大于等于他的根节点，左右子树也是二叉排序树。

时间复杂度的 O(log(N))，跟线性数据的查询时间复杂度一致，但是树结构的好处是增加和删除数据复杂度比较低。这样子的二叉树会有什么问题呢？我们看下面的一个树可以看出，这个数变成了一个链表，是不符合我们的预期的。对于这种链表我们出现了一种新的数据结构，叫做平衡二叉树。

平衡二叉树

从任何节点出发，左右子树的深度之差绝对不超过 1，左右子树也为平衡二叉树。



这种平衡二叉树的结构能看出来，我们的查询操作的时间复杂度降低很多，但是这个树插入新的数据不平衡怎么办呐？这样子有了树旋转的办法，插入是只需要两次就可以恢复平衡，但是删除节点需要维护整个链表的，整个复杂度较高，为 O(log(n))。



红黑树

为了解决这个问题，我们有了一种新的数据结构，就是红黑树。

每个节点只有两种颜色：红色和黑色。

• 根节点是黑色的

• 每个叶子节点都是黑色的空节点

• 从根节点到叶子节点不会连续出现两个红色

• 从任何一个节点触发，到叶子节点，这条路径上都有相同数量的黑色

删除的时候怎么操作的，还是通过染色和旋转的方式来做。

红色树的优势：

红黑树最多三次旋转就会达到平台，时间复杂度 O(1)，大量增加删除的工作效率更高

平衡性不如二叉树，效果相对差一点



跳表

我们看下面一张图



从这个图来看，可以通过基础的链表，然后多次跳表构建多个链表，然后在链表间进行转换操作（略相似于多级缓存和内存页的感觉），但是对于数据冗余很高，对于内存的占用会更高一点。

时间复杂度和空间复杂度的一个抉择。



常用算法

• 🔲【任务】还有哪些算法，进一步梳理和了解下，另外关于机器学习的线性回归，支持向量机，随机森林算法等。

穷举算法

递归算法

时间复杂度 n * log(n)

有序的情况下，会出现 n 平方的复杂度

贪心算法

在对于问题求解是，每次都作出当前最好的选择，不从整体而是局部最优解。

对于这个算法进行了改进，就是改进贪心算法（最快路径）

• 找出最短时间内节点

• 更新邻居节点的开销，查看是否有最短路径，如果有就更新开销

• 重复这个过程，直到对图中每个节点就进行更新

• 更新最终路径

注意：只关注路径，起点到当前节点的最快路径



动态规划算法

在合适的角度，把求解的目标值在某几个维度展开，变成了从小问题的最优解中选取大问题的最优解。

对于这个问题来说，我们可以理解为了每个商品都有一个，这种情况下我们只需要知道 1 / 2 /3 /4 的情况下，有一/二/三个产品的情况下，

然后分别比较 1 + 3 =4 ，2 + 2 =4，0 + 4 =



遗传算法

通过摸底达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模式，通过模拟自然进化过程搜索最优解的方法。

遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索，其中，选择、交叉和变异构成了遗传算法的遗传操作；参数编码、初始化群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素构成了遗传算法的核心内容。

网络通信的基本原理和性能优化

基础介绍

从正常的架构来看，客户端通过域名的单词请求来说，整个后端服务的处理流程如下。



第一步：域名解析，单次解析结果缓存，直到失效之后重新解析

第二步：cdn 进行缓存，不缓存直接到负载均衡或者反向代理服务

第三步：反向代理服务器可以进行缓存处理

第四步：网关服务集群进行 rpc 调用和处理

第五步：机房内服务端调

基础的 osi 七层模型和 tcpip 四层模型

物理层：双角线、同轴电缆、光纤上协议一致性

数据链路层：物理层转分段分块层位传输的帧信息，然后根据 mac 地址传输到对应的服务器地址

链路层协议：mac 地址

ip 协议：服务器地址

tcp 协议：端口通信

http 协议：post 方法和请求路径、参数

tips 建议查看：图解 tcpip 协议~



tcp 协议

ip 是不可靠的通信协议，为了保障可靠性使用了 tcp 协议。有哪些机制？

使用序号：对收到的 tcp 报文段进行排序和检测重复的数据

无错传输 ：使用校验和检测报文段的错误

使用确认和计时器来检测和纠正丢包和延时

流量控制，避免主机分组发送过缓是的接收方来不及完全接收

拥塞避免，发送方根据网络的承载情况来控制分组的发送量，已获得高性能的同时避免拥塞本丢包重传。



补充知识点

• 🔲【任务】tcp 的超时重传的机制，避免用塞和快速重传算法

• 🔲【任务】滑动窗口

• 🔲【任务】懒启动

http 协议

示例



http 请求的七种方法

• get：读，不应该产生变更操作

• head：同 get，需返回响应头

• post：提交请求，数据变更

• put：上传请求

• delete：删除

• trace：回显服务器收到请求，多用于诊断

• options：返回 http 支持的方法，复杂跨域方法使用。

五种响应

• 1xx - 接受，继续处理

• 2xx - 成功，常见 2xx

• 3xx - 重定向，常见 301 302

• 4xx - 请求的词法错误或者无法被执行，但是 404 请求无资源可能是客户端问题，也可能是服务端或者路由层问题

• 5xx - 服务器错误



http1.0

基本淘汰，每次请求响应都要一个 tcp 链接，开销极大。

http1.1

广泛使用，使用连接的概念，需要进行连接池的控制

http2.0

grpc 基于 http2.0 实现

http3.0

没有广泛使用，应用难度较大，依赖于 udp 封装的 quic 协议来实现。

非阻塞网络 IO

网络通讯

socket：依赖于 socket 接口进行网络编程，这个是 linux 操作系统给进程提供的编程接口。

多线程：关于进程和线程之间的关系不做赘述，对于进程来说，多线程在网络层面就是每个线程开一个 socket 来进行处理。但是多线程数量是有限的，那就限制了程序并发处理的方式。

线程池：使用线程池来优化，但是仍然会出现堵塞的情况，无法彻底解决。



socket 接受数据之后的处理过程。

1. 收到挽留过包到网卡，进行解析，解析成功

2. 执行中断到 cpu 优先调度，开始执行程序

3. 拷贝数据到 socket 接受缓存区

4. 完成拷贝后，唤醒等待队列中的线程进行处理，这里面如果涉及到一些资源操作(大概率是 io 的读写)，那么线程就会出现阻塞的情况。

那么我们改怎么办才能够避免线程阻塞的情况？

非阻塞/IO 复用的网络模型

非阻塞 IO，以 java NIO 为例



1. 每个客户端建立一个 channel 通道

2. selector 监听 channel 的情况

3. 根据情况对 buffer 中进行操作



selector 的实现方式是怎么样的吗？采用多路复用 io 的方式，有 select、poll 和 epoll 这几种方式，epoll 是目前使用比较多的方式，redis、nginx 的高并发和非阻塞也是通过 epoll 来实现的。

• 🔲【任务】epoll 的具体的实现原理是怎么样的？