写点什么

week8. 课后作业

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

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



遍历一遍M链表,使用TreeMap将节点HashCode做key,节点做value。时间复杂度O(M),空间复杂度O(M)

遍历N链表,每个节点在TreeMap中查找,时间复杂度O(NLogM),空间复杂度0.

整体时间复杂度O(M)+O(NLogM),空间复杂度O(M)

根据M和N的长度,选择那一条放入TreeMap,有更低的复杂度





package com.demo.linklistmeet;
import java.util.TreeMap;
/**
* @author niki-lauda
* @create 2020-07-26 10:28
*/
public class MeetTest {
public static void main(String[] args) {
Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
Node node4 = new Node(4);
Node node5 = new Node(5);
Node node6 = new Node(6);
Node node7 = new Node(7);
Node node8 = new Node(8);
Node node9 = new Node(9);
Node node10 = new Node(10);
// 1->2->3-->4->5
// 6->7->8-->4->5
// node1.setNext(node2).setNext(node3).setNext(node4).setNext(node5);
// node6.setNext(node7).setNext(node8).setNext(node4).setNext(node5);
// System.out.println(findMeetNode(node1, node1.getTotalSize(), node6, node6.getTotalSize()));//Node{val=4}
// 1->2-->3->4->5->3
// 6->7->8->9->10-->3->4->5->3
// node1.setNext(node2).setNext(node3).setNext(node4).setNext(node5).setNext(node3);
// node6.setNext(node7).setNext(node8).setNext(node9).setNext(node10).setNext(node3).setNext(node4).setNext(node5).setNext(node3);
// System.out.println(findMeetNode(node1, node1.getTotalSize(), node6, node6.getTotalSize()));//Node{val=3}
//
// 1->2->3-->4->5->3
// 6->7->8->9->10-->4->5->3->4
// node1.setNext(node2).setNext(node3).setNext(node4).setNext(node5).setNext(node3);
// node6.setNext(node7).setNext(node8).setNext(node9).setNext(node10).setNext(node4).setNext(node5).setNext(node3);
// System.out.println(findMeetNode(node1, node1.getTotalSize(), node6, node6.getTotalSize()));//Node{val=4}
// 1->2->3-->4->5->3
// 6->7->2->3->4->5->3
// node1.setNext(node2).setNext(node3).setNext(node4).setNext(node5).setNext(node3);
// node6.setNext(node7).setNext(node2).setNext(node3).setNext(node4).setNext(node5).setNext(node3);
// System.out.println(findMeetNode(node1, node1.getTotalSize(), node6, node6.getTotalSize()));//Node{val=2}
node1.setNext(node2).setNext(node3).setNext(node4).setNext(node5).setNext(node3);
node6.setNext(node7).setNext(node8).setNext(node9).setNext(node10);
System.out.println(findMeetNode(node1, node1.getTotalSize(), node6, node6.getTotalSize()));//null
}
public static Node findMeetNode(Node head1, int list1Size, Node head2, int list2Size) {
double rate0 = list1Size / list2Size;
double rate1 = (Math.log(list1Size) / Math.log(2) - 1) / (Math.log(list2Size) / Math.log(2) - 1);
TreeMap<Integer, Node> dataMap = new TreeMap<>();
if(rate0 > rate1) {
while (head2 != null) {
if(dataMap.containsKey(head2.hashCode())) {//有环情况
break;
}
dataMap.put(head2.hashCode(), head2);
head2 = head2.getNext();
}
while (head1 != null) {
Node nodeExist = dataMap.get(head1.hashCode());
if(nodeExist != null) {
return nodeExist;
}
head1 = head1.getNext();
}
} else {
while (head1 != null) {
if(dataMap.containsKey(head1.hashCode())) {//有环情况
break;
}
dataMap.put(head1.hashCode(), head1);
head1 = head1.getNext();
}
while (head2 != null) {
Node nodeExist = dataMap.get(head2.hashCode());
if(nodeExist != null) {
return nodeExist;
}
head2 = head2.getNext();
}
}
return null;
}
}
class Node {
private Integer val;
private Node next;
private int totalSize = 1;
public Node(Integer val) {
this.val = val;
}
public Node getNext() {
return next;
}
public Node setNext(Node next) {
this.next = next;
totalSize++;
return next;
}
public int getTotalSize() {
return totalSize;
}
@Override
public String toString() {
final StringBuffer sb = new StringBuffer("Node{");
sb.append("val=").append(val);
sb.append('}');
return sb.toString();
}
}



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

为了保证高可用,数据在Dataodes上面是3备份,有一份数据是跨机架备份。

文件在DataNodes上保存。文件名,副本数,备份信息都在NameNode上保存。DataNodes需要定期向NameNode发送心跳通知自己健康状况。

当DataNode节点宕机时,不能向NameNode发送心跳。NameNode会找出当前DataNode上所有数据块在其他DataNode上备份的数据,找到新的DataNode,通知其他机器将备份数据同步到新DataNode上。使数据恢复3备份。

NameNode应该有多个节点,数据定期同步,NameNode失效的时候,通过选举得到新的NameNode提供服务。

客户端上传文件的时候宕机,服务器起ServerSocket设置超时时间,超时未上传完成的文件,删除即可。

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

做一个真诚、坦诚的行人,追求自由。 2018.07.30 加入

还未添加个人简介

评论

发布
暂无评论
week8.课后作业