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

关注

发布于: 2020 年 07 月 29 日

一 第一题有两个单向链表（链表长度分别为m，n），这两个单项链表有可能在某个元素合并，如下图的这样，也可能不合并。现在给定两个链表的头指针，在不修改链表的情况下，如何快速的判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。
请用（伪）代码描述算法，并给出时间复杂度和空间复杂度。
图：
﻿
思路：
单个链表元素不会重复，如果出现重复就说明在另个一链表中
遍历两个链表元素，并计算元素节点hash值，在hash表中查找有没有，没有则放入hash表。
如果查找到有表示找到相同的节点，单向链表节点不会重复，只能是另外一个链表中相同的节点。
至此找到合并的节点。
﻿
Java伪代码
 checkLinkHasCombine(单向链表 linkA,单向链表 linkB){
  Hash表 a；
    
  while( 链表A或链表B还有没遍历到的元素则继续循环 ){
    if( 如果链表A的还有下一个元素，则获取到下一个元素并计算hash值去Hash表查找 ）{
      if（ 如果Hash表查找Hash值有对应的元素，则找到合并的元素，返回当前遍历的元素 ）
      else (如果Hash表没有找到就把 Hash值和对应元素记录到Hash表 ）
    }
  	if( 如果链表B的还有下一个元素，则获取到下一个元素并计算hash值去Hash表查找 ）{
      if（ 如果Hash表查找Hash值有对应的元素，则找到合并的元素，返回当前遍历的元素 ）
      else (如果Hash表没有找到就把 Hash值和对应元素记录到Hash表 ）
    }
  }
    循环完毕后还没找到合并元素，表示量个链表没有合并
}
时间复杂度：最大循环最长链表的长度所以为 max(m,n)
空间复杂度：额外使用了 Hash表结构。最大存储两个链表所有元素。所以空间复杂度是m+n 
二 第二题请画出HDFS分布式文件系统中 DataNode服务器节点宕机的时候，HDFS的处理过程时序图。
﻿
﻿
HDFS 将数据更加广泛的分布到多个存储服务器，构成分布式文件系统。文件系统的每一存储服务器相当于一个大的磁盘块，分布式文件系统中由NameNode记录文件分布信息。读写数据时，客户端视分布式文件系统为一个整体，当做普通的存储磁盘的方式使用。分布式文件系统可以动态且方便的扩展存储服务器，理论上，单个文件大小不受限制（只需要增加分布式文件系统的存储服务器）。数据读写也由于多个服务器同时读写，也非常快。同时除了每个单个服务器上有数据备份，服务器节点之间也有备份，还有跨机架的备份。是真正达到了，数据的高存储量，高读写速度，数据高可用的特点。
﻿
DataNodes节点宕机恢复过程时序图
﻿