架构师训练营 8 作业

用户头像
东哥
关注
发布于: 2020 年 07 月 29 日

一:

有两个单向链表(链表长度分别为m,n),这两个单项链表有可能在某个元素合并,如下图的这样,也可能不合并。现在给定两个链表的头指针,在不修改链表的情况下,如何快速的判断这两个链表是否合并?如果合并,找到合并的元素,也就是图中的 x 元素。

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

图:



/**
* 记忆法,同时遍历,并记录。时间复杂度为m n中最大的那个。但是因为引入了set,导致复杂度变高。并不是期待的O(m)
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
Set<ListNode> nodeSet = new HashSet<>();
int index = 0;
while (headA != null || headB!=null) {
if (headA != null) {
if (nodeSet.contains(headA)) {
return headA;
}
nodeSet.add(headA);
headA = headA.next;
}
if (headB == null) {
continue;
}
if (nodeSet.contains(headB)) {
return headB;
}
nodeSet.add(headB);
headB = headB.next;
}
return null;
}
}



/**
*双指针法,每个指针都跑公共长度 + 双方非公共的长度 ,最终会在距离相等时相遇。时间复杂度为O(m + n - 公共长度)
*/
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) return null;
ListNode pA = headA, pB = headB;
while (pA != pB) {
pA = pA == null ? headB : pA.next;
pB = pB == null ? headA : pB.next;
}
return pA;
}



二:DataNode故障恢复流程

1:DataNode和NameNode进行心跳

2:DataNode宕机

3:NameNode的根据策略进行心跳、询问等策略后,如果还是没有反馈,则将DataNode的剔除

4:找到对应数据备份,进行数据拷贝

但是重新上线后,怎么处理,暂时没有找到,在听一次课,或者等老师的回答吧。我觉得,其处理应该相当于新增一个。原先的数据会失效。

用户头像

东哥

关注

还未添加个人签名 2018.03.25 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营8作业