写点什么

架构师训练营第 1 期 - 第 8 周课后练习

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

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


答:

  1. 代码实现如下:

单向链表类 SingleLinkedList,add 方法用来添加元素到链表中,getHead 方法用来返回头节点,size 方法用来返回链表的长度

package linkedlist;
public class SingleLinkedList {
private HeadNode head; private Node current; private int size;
public SingleLinkedList() { head = new HeadNode(); size = 0; }
public void add(Object value) { if (value == null) { throw new IllegalArgumentException("Value cannot be null"); } Node newNode = new Node(); newNode.value = value; if (head.next == null) { head.next = newNode; current = head.next; } else { current.next = newNode; current = current.next; } ++size; }
public HeadNode getHead() { return head; }
public int size() { return size; }
public static class HeadNode { private Node next;
public Node getNext() { return next; } }
public static class Node {
private Object value; private Node next;
public Object getValue() { return value; }
public Node getNext() { return next; } }}
复制代码

工具类 LinkedListUtils 的 findMergeNode 用来查找 2 个单向链表是否存在合并元素,里面包含 2 层循环,第 1 层循环迭代单向链表 m 中的每一个元素,把每一个元素去跟单向链表 n 中的每一个元素比较,如果符合合并元素的要求,则记录合并节点,并在方法最后返回合并节点。整个方法的时间复杂度是 O(m*n)

package linkedlist;
public class LinkedListUtils {
public static SingleLinkedList.Node findMergeNode(SingleLinkedList mList, SingleLinkedList nList) { SingleLinkedList.HeadNode mHead = mList.getHead(); SingleLinkedList.HeadNode nHead = nList.getHead();
if (mHead.getNext() == null || nHead.getNext() == null) { return null; }
SingleLinkedList.Node mergeNode = null; int m = mList.size(); int n = nList.size(); SingleLinkedList.Node mCurrent = mHead.getNext();
for (int i = 0; i < m; ++i) { SingleLinkedList.Node nCurrent = nHead.getNext();
for (int j = 0; j < n; ++j) { // 如果存在某个元素相等,剩下的元素也相等的话,那就是合并元素 if (isMergeable(mCurrent, nCurrent)) { mergeNode = mCurrent; break; } if (nCurrent.getNext() != null) { nCurrent = nCurrent.getNext(); } } if (mergeNode != null) { break; } if (mCurrent.getNext() != null) { mCurrent = mCurrent.getNext(); } }
return mergeNode; }
private static boolean isMergeable(SingleLinkedList.Node mCurrent, SingleLinkedList.Node nCurrent) { boolean isMergeable = false; if (mCurrent.getValue().equals(nCurrent.getValue())) { isMergeable = true;
SingleLinkedList.Node mNext = mCurrent.getNext(); SingleLinkedList.Node nNext = nCurrent.getNext();
while (true) { if (mNext != null && nNext == null) { isMergeable = false; break; } else if (mNext == null && nNext != null) { isMergeable = false; break; } else if (mNext != null && nNext != null) { if (!mNext.getValue().equals(nNext.getValue())) { isMergeable = false; break; } mNext = mNext.getNext(); nNext = nNext.getNext(); } else { break; } } } return isMergeable; }
public static SingleLinkedList toList(Object... eles) { SingleLinkedList mList = new SingleLinkedList(); for (Object ele : eles) { mList.add(ele); } return mList; }}
复制代码

单元测试类验证 findMergeNode 方法

package linkedlist;
import org.junit.Test;
public class TestLinkedListUtils {
@Test public void testFindMergeNode_2Lists_WithBeginMergeNode() { SingleLinkedList mList = LinkedListUtils.toList("a", "b", "c", "d", "f", "g", "h", "i"); SingleLinkedList nList = LinkedListUtils.toList("a", "b", "c", "d", "f", "g", "h", "i"); SingleLinkedList.Node mergeNode = LinkedListUtils.findMergeNode(mList, nList); assert mergeNode != null; assert mergeNode.getValue().equals("a"); }
@Test public void testFindMergeNode_2Lists_WithMiddleMergeNode() { SingleLinkedList mList = LinkedListUtils.toList("a", "b", "c", "d", "f2", "g", "h", "i"); SingleLinkedList nList = LinkedListUtils.toList("a", "b", "c", "d", "f", "g", "h", "i"); SingleLinkedList.Node mergeNode = LinkedListUtils.findMergeNode(mList, nList); assert mergeNode != null; assert mergeNode.getValue().equals("g"); }
@Test public void testFindMergeNode_2Lists_WithEndMergeNode() { SingleLinkedList mList = LinkedListUtils.toList("a", "b", "c", "d", "d", "g", "h2", "z"); SingleLinkedList nList = LinkedListUtils.toList("a", "b", "c", "d", "f", "g", "h", "z"); SingleLinkedList.Node mergeNode = LinkedListUtils.findMergeNode(mList, nList); assert mergeNode != null; assert mergeNode.getValue().equals("z"); }
@Test public void testFindMergeNode_2Lists_WithoutMergeNode() { SingleLinkedList mList = LinkedListUtils.toList("a", "b", "c", "d", "f", "g", "h", "h"); SingleLinkedList nList = LinkedListUtils.toList("a", "b", "c", "d", "f", "g", "h", "i"); SingleLinkedList.Node mergeNode = LinkedListUtils.findMergeNode(mList, nList); assert mergeNode == null; }}
复制代码
  1. 假设 HDFS 中有 4 个 DataNode 节点,DataNode 1 节点宕机了,那么处理过程的时序图如下:

  • 1. DataNode 1 宕机了,无法发送心跳给 NameNode

  • 2. NameNode 长时间内没有接收到 DataNode 1 的心跳,则认为节点已经宕机

  • 3. NameNode 在元数据中查找 DataNode 1 所有数据块的信息,比如有数据块 A、数据块 B、数据块 C

  • 4. NameNode 根据数据块查找到这些数据块所在的 DataNode 信息,比如数据块 A 的副本分别在 DataNode 1、DataNode 2、DataNode 3,数据块 B 的副本分别在 DataNode 1、DataNode 3、DataNode 4,数据块 C 的副本分别在 DataNode 1、DataNode 2、DataNode 4

  • 5. 发送指令复制 DataNode 2 上的数据块 A,复制新的副本到 DataNode 4

  • 6. 发送指令复制 DataNode 3 上的数据块 B,复制新的副本到 DataNode 2

  • 7. 发送指令复制 DataNode 4 上的数据块 C,复制新的副本到 DataNode 3


用户头像

Anyou Liu

关注

还未添加个人签名 2019.05.24 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营第 1 期 - 第 8 周课后练习