架构师训练营第 8 周作业

用户头像
James-Pang
关注
发布于: 2020 年 07 月 29 日

作业一:

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

class LinkedNode {
value: string;
next: LinkedNode;

constructor(value: string, next: LinkedNode = null) {
this.value = value;
this.next = next;
}
}

function lengthOf(list: LinkedNode): number {
let len = 0;
let pointer: LinkedNode = list;

while( pointer ){
len++;
pointer = pointer.next;
}

return len;
}

function findTheMergedNode(list1: LinkedNode, list2: LinkedNode): LinkedNode {
const m: number = lengthOf(list1);
const n: number = lengthOf(list2);

let [longList, shortList] = m > n ? [list1, list2] : [list2, list1];

let delta: number = Math.abs(m - n);

while( delta-- ) {
longList = longList.next;
}
// Then the length of longList and shortList is the same

while( longList ) {
if( longList === shortList )
return longList;

longList = longList.next;
shortList = shortList.next;
}

return null;
}



作业二:

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



发布于: 2020 年 07 月 29 日 阅读数: 5
用户头像

James-Pang

关注

不忘初心 2018.11.08 加入

还未添加个人简介

评论

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