架构师训练营第 0 期第 8 周作业

用户头像
Arthur
关注
发布于: 2020 年 07 月 27 日

1、链表合并问题

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

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



答:时间复杂度为 O(m + n),其中 m 和 n 为两个链表的长度,空间复杂度为O(1);

具体代码如下:

/**
* 定义链表
*/
public class ListNode {
int val;
ListNode next;
ListNode(int x) {
this.val = x;
this.next = null;
}
}
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
ListNode l1 = headA;
ListNode l2 = headB;
while (l1 != l2) {
if (l1.next != null) {
l1 = l1.next;
} else {
l1 = headB;
}
if (l2.next != null) {
l2 = l2.next;
} else {
l2 = headA;
}
}
if (l1 == null) {
return null;
}
return l1;
}
}



2、HDFS的DataNode宕机数据复制时序图



  1. 【DataNode】每3秒钟向【NameNode】发送心跳,【NameNode】记录【DataNode】的最新心跳时间;

  2. 如果【NameNode】在10分钟都没有接收到某个【DataNode】的心跳,开始数据复制流程;

  3. 首先查询宕机的【DataNode】上保存的数据块(block)有哪些;

  4. 根据数据块(block)信息查询对应的备份【DataNode】;

  5. 然后通知所有备份的【DataNode】将对应数据库复制到其他【DataNode】节点;

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

Arthur

关注

还未添加个人签名 2018.08.31 加入

还未添加个人简介

评论

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