写点什么

架构师训练营第八周命题作业

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

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

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

1 判断链表合并算法

设给出的两个链表为 A 和 B,长度分别为 m 和 n。

将链表 A 的尾节点与链表 B 的头节点相连,将链表 B 的尾节点与链表 A 的头节点相连。

从链表 A 和链表 B 的头结点开始遍历,设当前遍历到的结点分别为 p 和 q。

如果 p 和 q 为同一节点,则两链表合并且该结点为合并的元素。

如果遍历 m+n 次后未找到,则两链表不合并。

ListNode* GetIntersectionNode(ListNode* headA, ListNode* headB)
{
ListNode* p = headA;
ListNode* q = headB;
while (p != q)
{
p = p ? p->next : headB;
q = q ? q->next : headA;
}
return p;
}

在具体实现中,不需要真正将两个链表头和尾连接起来,只需要判断当迭代变量为空时将另一个链表的头赋过去就可以了。如果两个链表合并则该函数返回合并处结点的指针。当进行了 m+n 次迭代后,此时 p 与 q 都为空指针,循环退出,返回空指针。因此,当两个链表不合并时,该函数返回空指针。

该算法的时间复杂度为O(m+n),因为每个链表最多会被遍历两次。

该算法的空间复杂度为O(1),因为只申请了两个迭代变量。

2 HDFS 失效时序图

当 HDFS 中有数据节点失效时,以数据节点 F 失效为例,名称节点会由于没有收到数据节点 F 发送的心跳检查而检测到数据节点 F 失效。接着名称节点会检查数据节点 F 中包含的数据块,以数据块 i 为例,查看其他包含数据块 i 的数据节点。若数据节点 X 包含数据块 i ,再寻找另一个不包含该数据库的数据节点 Y,将数据块 i 复制到数据节点 Y 上。

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

whiter

关注

还未添加个人签名 2020.05.29 加入

还未添加个人简介

评论

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