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

用户头像
韩挺
关注
发布于: 2020 年 07 月 29 日

1、有两个单向链表(链表长度分别为 m,n),这两个单向链表有可能在某个元素合并,如下图所示的这样,也可能不合并。现在给定两个链表的头指针,在不修改链表的情况下,如何快速地判断这两个链表是否合并?如果合并,找到合并的元素,也就是图中的 x 元素。

请用(伪)代码描述算法,并给出时间复杂度和空间复杂度。

/**
* 两个单向链表是否在某个元素开始合并,找出该元素
* 将单向链表转成数组,利用数组的随机访问从最后一个元素开始比较,直至两边元素不想等
* 时间复杂度应该是O(min(m,n)+m+n),空间复杂度应该是O(m+n)
*/
public class TestApplication {
public static void main(String[] args) {
List<String> list1 = new LinkedList<>();
list1.add("a");
list1.add("b");
list1.add("x");
list1.add("y");
list1.add("z");

List<String> list2 = new LinkedList<>();
list2.add("d");
list2.add("e");
list2.add("f");
list2.add("x");
list2.add("y");
list2.add("z");

//假设m<n
int m=list1.size();
int n=list2.size();

//转数组
List<String> array1 = new ArrayList<>(m);
List<String> array2 = new ArrayList<>(n);
list1.forEach(p -> array1.add(p));
list2.forEach(p -> array2.add(p));


//从两个数组的最后一个元素开始比较
int idx;
boolean existFlag=false;
for(idx=m-1;idx>-1;idx--){
if(array1.get(idx).equals(array2.get(idx+n-m))){
existFlag=true;
}else{
break;
}
}

if(existFlag) {
System.out.println(array1.get(idx + 1));
}
}
}

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



用户头像

韩挺

关注

还未添加个人签名 2019.01.25 加入

还未添加个人简介

评论 (1 条评论)

发布
用户头像
作业请添加“极客大学架构师训练营”,便于分类
2020 年 07 月 29 日 17:44
回复
没有更多了
架构师训练营 - 第八周 - 作业