链表交集
题目：
有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，也可能不合并，如下图所示的这样。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。
请用代码（或伪代码）描述算法，并给出时间复杂度。
实现：
蛮力计算： 逐个获取链表 1 的节点，遍历链表 2 判断是否存在相同的节点，存在则返回， 不存在返回空。
时间复杂度 O(m*n)
空间复杂度 O(1)
public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if (headA == null || headB == null) return null; ListNode pa = headA; ListNode pb ; while (pa != null){ pb = headB; while (pb != null){ if (pa == pb){ return pa; } pb = pb.next; } pa = pa.next; } return null; }}
复制代码
通过 hash 值判断 将链表 1 中数据 hash 值计算出来存放到集合中， 同时顺序计算链表 2 的 hash 值如果存在标识存在交叉节点。
时间复杂度 O(m+n)
空间复杂度 O(max(m,n))
public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if (headA == null || headB == null) return null; ListNode pa = headA; HashSet<ListNode> hashA= new HashSet<ListNode>(); while (pa != null) { hashA.add(pa); pa = pa.next; } ListNode pb = headB; while (pb != null){ if (hashA.contains(pb)){ return pb; } pb = pb.next; } return null; }}
复制代码
对接链表 如果两个链表中存在相交的节点， 当链表遍历结束时，将指针一定到另外一个链表遍历， 如果存在相同节点，必在相同节点相遇， 没有的话在链表结尾处相遇。
public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if (headA == null || headB == null) return null; ListNode pa = headA; ListNode pb = headB; while (pa != pb) { if (pa == null) { pa = headB; } else { pa = pa.next; } if (pb == null){ pb = headA; } else { pb = pb.next; } } return pa; }}
复制代码
DataNode 宕机 HDFS 处理时序
HDFS 架构
DataNode 宕机处理时序
假设文件涉及文件块 BlockA， BlockB， 分别存放在 DataNode1，DataNode2， DataNode3 上
当 DadaNode3 节点出现故障， NameNode 查找 DataNode3 存储的 Block， 通知从其他拥有这些块的节进行复制。 这样保证其备份副本数量（这里是三个），不会因为节点宕机而减少。
参考及引用
架构师训练营作业-李智慧老师相关讲义
Photo by Tatiana Syrikova from Pexels
评论