架构师训练营第八周作业

关注

发布于: 2020 年 07 月 29 日

作业 1 有两个单向链表（链表长度分别为m, n）,这两个单向链表有可能在某个元素合并，如图所示，也可能不合并。现在给定两个链表的头指针，在不修改链表的情况下，如何快读的判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的X元素。请用（伪）代码描述算法，并给出时间复杂度和空间复杂度。
时间复杂度为：O(m*n)
空间复杂度为：O(m+n)
代码描述链表节点
/**
 * Node
 *
 * @author Lee
 * @date 2020/7/28 9:35
 */
public class Node {
    /**
     * 数据信息
     */
    private String data;
    /**
     * 下一个节点的引用 （就是指针）
     */
    private Node next;
    public Node(String data) {
        this.data = data;
    }
    
    public String getData() {
        return data;
    }
    
    public Node getNext() {
        return next;
    }
    public void setNext(Node next) {
        this.next = next;
    }
}
﻿
判断链表合并
/**
 * Client
 *
 * @author Lee
 * @date 2020/7/28 9:47
 */
public class Client {
    public static void main(String[] args) {
        // 设置节点
        Node nodeA = new Node("a");
        Node nodeB = new Node("b");
        Node nodeX = new Node("x");
        Node nodeY = new Node("y");
        Node nodeZ = new Node("z");
        Node nodeD = new Node("d");
        Node nodeE = new Node("e");
        Node nodeF = new Node("f");
        // 链表A
        nodeA.setNext(nodeB);
        nodeB.setNext(nodeX);
        // 链表B
        nodeD.setNext(nodeE);
        nodeE.setNext(nodeF);
        nodeF.setNext(nodeX);
        nodeX.setNext(nodeY);
        nodeY.setNext(nodeZ);
        // 给定两个链表的长度
        int m = 5;
        int n = 6;
        
        boolean status = false;
        // 链表A的头指针
        Node nodeOne = nodeA;
        // 链表B的头指针
        Node temp = null;
        // 用短的链表循环遍历长链表的每个节点
        for (int i=0; i<m-1; i++) {
            if (status) {
                break;
            }
            nodeOne = nodeOne.getNext();
            // 从头遍历链表
            for (int j=0; j<n-1; j++) {
                if ( j == 0) {
                    temp = nodeD.getNext();
                }
                else{
                    temp = temp.getNext();
                }
                if (checkMerge(nodeOne, temp)) {
                    status = true;
                    System.out.println("两个链表在: " + nodeOne.getData() + "合并");
                    break;
                }
            }
        }
        if (!status) {
            System.out.println("链表并没有合并。");
        }
    }
    /**
     * 检测链表是否合并
     *
     * @param node1
     * @param node2
     * @return
     */
    public static boolean checkMerge(Node node1, Node node2) {
        boolean status = false;
        if (System.identityHashCode(node1) == System.identityHashCode(node2)) {
            status = true;
        }
        return status;
    }
}
﻿
结果
两个链表在: x合并
﻿
﻿
作业 2 请画出DataNode服务器节点宕机时候，HDFS的处理过程时序图。DataNode 会通过心跳和 NameNode 保持通信，如果 DataNode 超时未发送心跳，NameNode 就会认为这个 DataNode 已经宕机失效，立即查找这个 DataNode 上存储的数据块有哪些，以及这些数据块还存储在哪些服务器上，随后通知这些服务器再复制一份数据块到其他服务器上，保证 HDFS 存储的数据块备份数符合用户设置的数目，即使再出现服务器宕机，也不会丢失数据。
﻿
﻿