极客大学 - 架构师训练营第八周作业

关注
发布于: 2020 年 11 月 09 日
﻿
作业一﻿
链表算法题要求: 有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，也可能不合并，如下图所示的这样。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。
请用代码（或伪代码）描述算法，并给出时间复杂度。
﻿
题解：
我们可以利用双指针的解法来解答此题，两个指针p1和p2，起始时p1指向headA, p2指向headB。headA是linked_list1的头指针，而headB是linked_list2的头指针。假设linked_list1和linked_list2有重合，那么每个node的访问顺序如下:
a -> b -> x -> y -> z -> null -> d -> e -> f -> x -> y -> z -> null
d -> e -> f -> x -> y -> z -> null -> a -> b -> x -> y -> z -> null
这样只需要循环遍历两个链表，每个链表各走一次，当两个指针都指向同一个节点的时候，退出循环即可。如果两个链表没有相交节点，那么当两个指针都为null的时候，循环结束。
时间复杂度: O(N), 因为只需要遍历每个链表各一次
空间复杂度: O(1), 只需要两个指针来保存当前节点 (两个链表的空间不算)
代码:
Python 3.7, virtual environment
ListNode.py: 定义节点
"""Linked List Node class"""
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
NodeIntersection.py: 定义查找intersection的方法类
"""Get linked list intersection node class"""
import ListNode
class NodeIntersection:
    def __init__(self):
        pass
    @staticmethod
    def get_node_intersection(head_a: ListNode, head_b: ListNode) -> ListNode:
        """Two pointers traverse two linked list
        
        :param head_a: Head pointer of linked list 1
        :param head_b: Head pointer of linked list 2
        :return: common node
        """
        pa, pb = head_a, head_b
        while pa != pb:
            pa = pa.next if pa else head_b
            pb = pb.next if pb else head_a
        return pa
    @staticmethod
    def create_linked_list(node_value_list):
        """Construct linked list from give list
        
        :param node_value_list: Python list with node values
        :return: Head node of the constructed list
        """
        temp = head = ListNode.ListNode(node_value_list[0])
        for v in node_value_list:
            node = ListNode.ListNode(v)
            temp.next = node
            temp = temp.next
        return head
def construct_two_linked_list_with_intersection(nt):
    # Construct linked list A
    # [4, 1, 8, 4, 5]
    head_a = nt.create_linked_list([4, 1, 8, 4, 5])
    temp, common_node = head_a, None
    while temp:
        if temp.val == 8:
            common_node = temp
        temp = temp.next
    # Construct linked list B
    # [5, 6, 1, 8, 4, 5]
    head_b = ListNode.ListNode(5)
    head_b.next = ListNode.ListNode(6)
    head_b.next.next = ListNode.ListNode(1)
    head_b.next.next.next = common_node
    return head_a, head_b
def main():
    nt = NodeIntersection()
    # Construct two linked list that has intersection
    head_a, head_b = construct_two_linked_list_with_intersection(nt)
    common_node = nt.get_node_intersection(head_a, head_b)
    print('Two linked list has intersection')
    print(f'     4 -> 1 \ ')
    print(f'             -> 8 -> 4 -> 5')
    print(f'5 -> 6 -> 1 /')
    print(f'Common node: {common_node.val if common_node else None}')
    # Construct two lists have no intersection
    # [1, 9, 1, 2, 4] and [3, 2, 4]
    head_a = nt.create_linked_list([1, 9, 1, 2, 4])
    head_b = ListNode.ListNode([3, 2, 4])
    common_node = nt.get_node_intersection(head_a, head_b)
    print('Two linked list has no intersection')
    print('1 -> 9 -> 1 -> 2 -> 4')
    print('3 -> 2 -> 4')
    print(f'Common node: {common_node.val if common_node else None}')
if __name__ == '__main__':
    main()
测试结果:
﻿
HDFS时序图要求：请画出 DataNode 服务器节点宕机的时候，HDFS 的处理过程时序图
﻿
首先我们来看看HDFS的架构图
HDFS的架构图
﻿
如何判断HDFS的DataNode失效:
DataNode会通过心跳和NameNode保持通信，如果DataNode超时未发送心跳（3秒），NameNode就会认为这个DataNode已经宕机失效，立即查找这个DataNode上存储的数据块有哪些，以及这些数据块还存储在哪些服务器上，随后通知这些服务器再复制一份数据块到其他服务器上，保证HDFS存储的数据块备份数符合用户设置的数目，同步完后，NameNode修改fsimage中的节点信息以便下一个block传输，即使再出现服务器宕机，也不会丢失数据。
HDFS - DataNode服务器节点宕机处理时序图
﻿