架构师训练营第八周 - 作业

用户头像
草原上的奔跑
关注
发布于: 2020 年 07 月 29 日
架构师训练营第八周-作业

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

依据题意,有两个链表,我们给名A、B,A链表长度n,B链表长度m,假设n>=m。

若两链表合并,则表示从合并点x往后,就是一条链表了。

合并点x,A->x == B->x,且其为第一个相等点。

可以使用如下比较流程:

  1. 先遍历A链表,n-m个节点

  2. 从A的n-m+1个节点和B的第一个节点开始,遍历比较相应节点是否相等

  3. 不相等,接着比较两链接下来的节点

  4. 因为A链先遍历了n-m个元素,所以两链会同时遍历到链尾

  5. 若到链底,仍无相等元素,则说明两链未合并

  6. 若找到相等元素,则说明两链合并

伪代码如下

List A = new NodeList("a", "b", "c");
List B = new NodeList("c");
int n = A.size();
int m = B.size();
int gap = n-m;
NodeList* aPointer = A.header;
NodeList* bPointer = B.header;
while(gap-- > 0) {
aPointer = aPointer->next;
}
while(aPointer != null) {
if(aPointer == bPointer) {
break;
}
aPointer = aPointer.next;
bPointer = bPointer.next;
}
if (aPointer != null) {
print("两链表合并");
print("合并的元素x是"+ aPointer.value);
} else {
print("两链表未合并");
}

上述算法的时间复杂度为O(n),空间复杂度为O(1)。



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

DataNode判定宕机流程如下:

  1. DataNode正常时,每隔一段时间(比如30s)向NameNode发送心跳

  2. 一段时间不上传(比如10min),NameNode判定DataNode掉线

  3. NameNode查询掉线的DataNode中存储的文件块信息

  4. NameNode查询丢失的文件块其余备份所在服务器信息

  5. 每个丢失文件块选择一台服务器发送重新备份的命令信息

  6. 备份服务器备份完成,NameNode更新文件信息

  7. 一台DataNode宕机,HDFS确认及恢复流程完毕



用户头像

草原上的奔跑

关注

还未添加个人签名 2018.05.04 加入

还未添加个人简介

评论

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