「架构师训练营」作业：第 8 周

 关注
发布于: 2020 年 07 月 28 日
有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，如下图所示的这样，也可能不合并。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。
﻿
请用（伪）代码描述算法，并给出时间福再度和空间复杂度。
双指针法
时间复杂度：O(n)
空间复杂度：O(1)
﻿
伪代码
# pseudo-code of GetIntersectionNode 
class ListNode{
   AnyType data;
   Node next;
}
// 如果返回值是 null，表示没有相交
function GetIntersectionNode(headA:ListNode,headB:ListNode)
{
  if(headA == null or headB == null)
      return null;
      
  var node1=headA, node2=headB;
  
  while(node1!=node2){
      if(node1 != null)
          node1 = node1.next;
      else 
          node1 = headB;
          
      if(node2 != null)
          node2 = node2.next;
      else
          node2 = headA;
  }
  
  return node1; 
}
﻿
C#
public class ListNode
{
    public string val;
    public ListNode next;
    public ListNode(string x) { val = x; }
}
创建链表：
/// <summary>
/// 创建链表
/// </summary>
/// <param name="arry"></param>
/// <returns></returns>
private ListNode CreateListNode(string[] arry)
{
    if (arry == null || arry.Length == 0)
        return null;
     var head = new ListNode(arry[0]);
     var currentNode = head;
     for(int i = 1; i < arry.Length; i++)
     {
         currentNode.next = new ListNode(arry[i]);
         currentNode = currentNode.next;
     }
     return head;
 }
双指针法：
/// <summary>
/// 双指针法
/// </summary>
/// <param name="headA"></param>
/// <param name="headB"></param>
/// <returns></returns>
public ListNode GetIntersectionNode(ListNode headA, ListNode headB)
{
     if (headA == null || headB == null)
         return null;
      ListNode node1 = headA, node2 = headB;
      while (node1 != node2)
      {
          if (node1 != null && node2 != null && node1.val == node2.val)
              break;
           node1 = node1 != null ? node1.next : headB;
           node2 = node2 != null ? node2.next : headA;
       }
    return node1;
}
展示结果：
/// <summary>
/// 展示结果
/// </summary>
/// <param name="node"></param>
private void ShowResult(ListNode node)
{
    if(node==null)
        Console.WriteLine("没有相交");
    else
        Console.WriteLine("相交点：{0}",node.val);
    Console.WriteLine("---------------------------------------");
}
测试：
class Program
{
    static void Main(string[] args)
    {
        var pro = new Program();
        try
        {
            // 测试1：[a,b,x,y,z],[d,e,f,x,y,z]，预期结果：x
            {
                var headA = pro.CreateListNode(new string[]{ "a","b","x","y","z"});
                var headB = pro.CreateListNode(new string[] { "d", "e", "f", "x","y", "z" });
                 var result = pro.GetIntersectionNode(headA, headB);                    
                 pro.ShowResult(result);
             }
             // 测试2：[a,b,x], [d,2]， 预期结果：没有相交
             {
                 var headA = pro.CreateListNode(new string[] { "a", "b", "x" });
                 var headB = pro.CreateListNode(new string[] { "d", "e"});
                 var result = pro.GetIntersectionNode(headA, headB);
                 pro.ShowResult(result);
             }
        }
        catch (Exception ex)
        {
             Console.WriteLine(ex.ToString());
        }
        Console.ReadLine();
    }
}
结果：
﻿
请画出 DataNode 服务器节点宕机的时候， HDFS的处理过程时序图
DataNode 启动时，向 NameNode 进行注册。
DataNode 定时向 NameNode 发送心跳，一般 3 分钟一次。
当某个 DataNode 超时没有向 NameNode 发送心跳，NameNode 就会判定这个 DataNode 坏掉了。
NameNode 会去检查这个坏掉的 DataNode 上记录的数据块有哪些，以及这些数据块的备份节点在哪些服务器上
检查完后，会通知其他有备份节点的服务器，把数据块复制一份到某个指定的服务器上
﻿
发布于: 2020 年 07 月 28 日阅读数: 38
Amy

 关注
还未添加个人签名 2018.06.10 加入
还未添加个人简介
发布
暂无评论