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

用户头像
zcj
关注
发布于: 11 小时前

一 第一题

有两个单向链表(链表长度分别为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节点宕机恢复过程时序图



用户头像

zcj

关注

还未添加个人签名 2019.10.12 加入

精神小伙

评论

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