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

 关注

发布于: 2020 年 07 月 26 日

作业一有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，如下图所示的这样，也可能不合并。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。
请用（伪）代码描述算法，并给出时间复杂度和空间复杂度。
说明看了两篇文章，参考链接一给出了 7 种解题方法，参考链接二是其中的一种(Using difference of node counts)，不过并不是所有的方法都适用，有的需要修改链表结构，有的是用方程式。我这边参考的是 Using difference of node counts, 如下图：
思路遍历2个表，得到 lenA, lenB
计算遍历起始点，以较小长度的表为起点开始遍历
这样两个链表到终点的长度就相同了
从计算得到的起点开始遍历，如果合并(元素值相等)，返回合并元素值 
if ptrA->data == ptrB->data, 返回 ptrA->data。
如果遍历到队尾都找不到，那就说明两个链表不合并
伪代码
lenA = count(listA)
lenB = count(listB)
﻿
ptrA = listA
ptrB = listB
﻿
while (lenA > lenB) {
	ptrA = ptrA->next
  lenA--
}
while (lenB > lenA) {
	ptrB = ptrB->next
  lenB--
}
﻿
while (ptrA != NULL && ptrB != NULL) {
	if (ptrA->data == ptrB->data) {
  	return ptrA->data
  }
    
  ptrA = ptrA->next
  ptrB = ptrB->next
}
// Not found, no merge point
return NULL
﻿
时间复杂度：O(1)
空间复杂度：O(m+n) == O(n)
参考链接https://www.geeksforgeeks.org/write-a-function-to-get-the-intersection-point-of-two-linked-lists/
https://stackoverflow.com/questions/1594061/check-if-two-linked-lists-merge-if-so-where
作业二请画出 DataNode 服务器节点宕机的时候，HDFS 的处理过程时序图
DataNode 宕机时的处理过程DataNode 是真正存储数据的地方(一个数据块会有2个副本，加上自己本身，总共3个同样数据的数据块)，它是一个集群，分散在不同的机架上。
Name Node 类似与单机文件系统的文件控制块(FCB), 里面存放着文件信息、文件名、副本、存放位置等(存放在哪个DataNode 上)。
﻿
DataNode 启动时，它会先在 NameNode 中注册自己，DataNode 会定时发送心跳检测包给 NameNode, 当它超时未发送心跳检测包时，那么 NameNode 就判定它坏掉了，然后 NameNode 会检查该 DataNode 的元数据，损坏的 NameNode 上的数据块有哪些，其备份节点服务器是哪些，然后发送消息给备份节点服务器，让它们备份自己的数据块到另一个服务器上。
时序图
参考链接https://xie.infoq.cn/article/82c4b07e2de1d4a900b055317