架构师训练营第八周命题作业

关注
发布于: 2020 年 11 月 15 日
作业一：
有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，也可能不合并，如下图所示的这样。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。
请用代码（或伪代码）描述算法，并给出时间复杂度。
﻿
这个题目给出了前提——已知两个链表的长度分别为 m 和 n。思路如下：
m = n，则对比两个头结点的值是否相等，若相等，则两个链表完全一致。若不等，则将两个结点分别后移，再次对比，直到链表末尾。
若 m != n，则将长链表的头指针向后移，直到等于另一个链表的长度。这样我们就可以用前面两个链表长度相同的情况也处理。
﻿
时间复杂度：O(m+n)
package main
import (
	"fmt"
	"log"
)
type Node struct {
	Value int
	Next  *Node
}
func (node *Node) Print() {
	head := node
	for head != nil {
		fmt.Printf("%d ", head.Value)
		head = head.Next
	}
	fmt.Println()
}
func main() {
	m := 50
	n := 10
	head1 := makeList(m)
	head1.Print()
	head2 := makeList(n)
	head2.Print()
	checkSameNode(head1, head2, m, n)
}
//head1 链表的长度为 m, head2 链表的长度为 n
func checkSameNode(head1, head2 *Node, m int, n int) {
	var node *Node
	if m == n {
		node = findSameNode(head1, head2)
	} else {
		h1, h2 := alignLists(head1, head2, m, n)
		node = findSameNode(h1, h2)
	}
	if node != nil {
		log.Printf("Find same node: %d", node.Value)
	} else {
		log.Println("No same node.")
	}
}
func alignLists(head1, head2 *Node, m int, n int) (h1, h2 *Node) {
	if m > n {
		for m > n {
			head1 = head1.Next
			m--
		}
	} else if m < n {
		for n > m {
			head2 = head2.Next
			n--
		}
	}
	return head1, head2
}
func findSameNode(head1, head2 *Node) *Node {
	if head1 == nil || head2 == nil {
		return nil
	}
	if head1.Value == head2.Value {
		return head1
	}
	head1 = head1.Next
	head2 = head2.Next
	return findSameNode(head1, head2)
}
func makeList(length int) *Node {
	if length == 0 {
		return nil
	}
	head := &Node{
		Value: length,
		Next:  nil,
	}
	length--
	next := head
	for length > 0 {
		next.Next = &Node{
			Value: length,
			Next:  nil,
		}
		next = next.Next
		length--
	}
	return head
}
﻿
作业二：
请画出 DataNode 服务器节点宕机的时候，HDFS 的处理过程时序图。
处理过程：
各个 DataNode 在正常情况下，定时向 NameNode 发送心跳。
若某个 DataNode 发生故障，长时间不发心跳，NameNode 判定其故障。
NameNode 从元数据中查找故障的 DataNode 保存了哪些数据分片，及还有哪些 DataNode 节点保存有这些数据的备份。
NameNode 通知那些保存有数据备份的正常的 DataNode，将数据复制到其他的 DataNode。
﻿
﻿