架构师训练营第八周 - 作业

1.有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，如下图所示的这样，也可能不合并。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。请用（伪）代码描述算法，并给出时间复杂度和空间复杂度。

依据题意，有两个链表，我们给名 A、B，A 链表长度 n，B 链表长度 m，假设 n>=m。

若两链表合并，则表示从合并点 x 往后，就是一条链表了。

合并点 x，A->x == B->x，且其为第一个相等点。

可以使用如下比较流程：

1. 先遍历 A 链表，n-m 个节点

2. 从 A 的 n-m+1 个节点和 B 的第一个节点开始，遍历比较相应节点是否相等

3. 不相等，接着比较两链接下来的节点

4. 因为 A 链先遍历了 n-m 个元素，所以两链会同时遍历到链尾

5. 若到链底，仍无相等元素，则说明两链未合并

6. 若找到相等元素，则说明两链合并

伪代码如下

List A = new NodeList("a", "b", "c");List B = new NodeList("c");int n = A.size();int m = B.size();int gap = n-m;NodeList* aPointer = A.header;NodeList* bPointer = B.header;while(gap-- > 0) {	aPointer = aPointer->next;}while(aPointer != null) {	if(aPointer == bPointer) {  	break;  }  aPointer = aPointer.next;  bPointer = bPointer.next;}if (aPointer != null) {	print("两链表合并")；  print("合并的元素x是"+ aPointer.value);} else {	print("两链表未合并")；}

上述算法的时间复杂度为 O(n)，空间复杂度为 O(1)。

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

DataNode 判定宕机流程如下：

1. DataNode 正常时，每隔一段时间（比如 30s）向 NameNode 发送心跳

2. 一段时间不上传（比如 10min），NameNode 判定 DataNode 掉线

3. NameNode 查询掉线的 DataNode 中存储的文件块信息

4. NameNode 查询丢失的文件块其余备份所在服务器信息

5. 每个丢失文件块选择一台服务器发送重新备份的命令信息

6. 备份服务器备份完成，NameNode 更新文件信息

7. 一台 DataNode 宕机，HDFS 确认及恢复流程完毕