架构师训练营 第八周 作业

用户头像
李君
关注
发布于: 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 存储的数据块备份数符合用户设置的数目,即使再出现服务器宕机,也不会丢失数据。





发布于: 2020 年 07 月 29 日 阅读数: 5
用户头像

李君

关注

结硬寨,打呆仗。 2018.09.11 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营 第八周 作业