架构师训练营作业 -20200726
有两个单向链表(链表长度分别为m,n)这两个单向链表有可能在某个元素合并,也可能不合并。现在给定两个链表的头指针,在不修改链表的情况下如何快速的判断这两个链表是否合并?如果合并,找到合并的元素。
请用(伪)代码描述算法,并给出时间复杂度和空间复杂度。
两个链表合并的特征就是两个链表的某一个元素的下一个元素指针指向了同一个元素,符合此特征即可认为这两个链表存在此元素出现了合并的情况。考虑可用二重嵌套循环的方式对链表进行遍历,判断是否存在两个链表的后置元素指针相同的情况。伪代码如下:
//给定的m链表的头指针
Element mStart = mStart;
//给定的n链表的头指针
Element nStart = nStart;
//m链表当前元素指向的下个元素
Element mNext = null;
//保存合并节点的变量
Element combinElement = null;
//循环遍历链表m的所有元素
while(mStart.hasNext()) {
//获取m链表当前元素的后置元素
mNext = mStart.next();
//遍历n链表的每个元素
while(nStart.hasNext()) {
Element nNext = nStart.next();
//如果发现m链表和n链表的下个元素相同,则判断为在下个元素出现了合并的情况
if(mNext == nNext) {
combinElement = nNext;
break;
}
}
//如果发现了合并节点,则直接跳出循环
if(combinElement != null) {
break;
}
}
时间复杂度为O(n),空间复杂度为O(1)。
请画出DataNode服务器节点宕机的时候,HDFS的处理过程时序图
在正常状态下,NameNode通过心跳检测定时与实际保存文件片段的DataNode保持通讯。当心跳检测失败超过阈值的时候,NameNode判断目标DataNode失效。由于HDFS中数据会分多片保存,因此可以认为在其他服务器中存在宕机的DataNode的文件副本。NameNode在判断某个DataNode为失效状态后,会检索自身保存的数据,查找保存了宕机节点中的数据的备份的服务器,并向这些保存了备份的服务器发送指令,要求它们将受影响的文件复制到新的备份节点。其它DataNode收到指令后,将NameNode指令中包含的文件向备份节点进行复制,复制完成后系统即再次达到稳定状态。
评论