写点什么

架构师训练营第八周课后作业

用户头像
Gosling
关注
发布于: 2020 年 11 月 15 日
1.有两个单向链表(链表长度分别为 m,n),这两个单向链表有可能在某个元素合并,也可能不合并,如下图所示的这样。现在给定两个链表的头指针,在不修改链表的情况下,如何快速地判断这两个链表是否合并?如果合并,找到合并的元素,也就是图中的 x 元素。

请用代码(或伪代码)描述算法,并给出时间复杂度。





ListNode类

public class ListNode {
//为了方便这里不设置为私有成员
public String val;
public ListNode next;
ListNode(String val) {
this.val = val;
}
public ListNode next() {
return this.next;
}
}

ListNodeUtil类

public class ListNodeUtil {
public ListNode isMerge(ListNode list1, ListNode list2) {
Map<ListNode,String> map = new HashMap<>();
//合并点
ListNode mergePoint = null;
ListNode ln1 = list1;
ListNode ln2 = list2;
while(ln1 != null) {
map.put(ln1,ln1.val);
ln1 = ln1.next();
}
while(ln2 != null) {
if(mergePoint == null) {
//找到合并点
if(map.get(ln2) != null) {
mergePoint = ln2;
}
}else {
//出现不合并点,退出循环,设置结果为Null
if(map.get(ln2) == null) {
mergePoint = null;
break;
}
}
ln2 = ln2.next();
}
return mergePoint;
}
}

判断两个链表是否合并,通过遍历两个链表,结合散列表来辅助判断是否存在合并点。其时间复杂度是O(m+n),因为需要额外准备一个散列存储,其空间复杂度是O(n)。

2.请画出 DataNode 服务器节点宕机的时候,HDFS 的处理过程时序图。

HDFS一般遵循三副本原则,一个副本在同一机架上的节点,一个副本放在另一个机架上的节点。

当DataNode发生宕机时,NameNode通过心跳检测发现问题,通知副本往其他节点进行数据复制,时刻保证数据保有三副本。



用户头像

Gosling

关注

这个家伙很懒,只留下这一句话 2017.10.28 加入

还未添加个人简介

评论

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