架构师 3 期 3 班 -week8- 作业

zbest

关注

发布于: 2021 年 01 月 18 日

作业

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

请用代码（或伪代码）描述算法，并给出时间复杂度。

!png

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

作业完成

作业 1

设计

通过迭代器模式设计链表类
将一个链表循环放入 map
迭代另一个链表从 map 总判断是否存在

时间复杂度

O(n) + O(m) = O(n)

注：n、m 都是常量，所以复杂度不表示为 O(n+m) 直接表示成 O(n)即可

类图

代码实现

代码地址

定义链表

type LinkTable struct {	sync.Mutex	name string	FirstNode *LinkNode	LastNode  *LinkNode	Count     int}func (link *LinkTable) String() string {	iterator:= link.GetIterator()	str := ""	for iterator.HasNext() {		if str == "" {			str += "link "			if link.name != "" {				str += link.name			}			str += ": "		}else {			str += " -> "		}		str += iterator.Next()	}	return str}func NewLinkTable(str string) LinkTable {	return LinkTable{name: str}}func (link *LinkTable) Add(str string) {	link.Lock()	defer link.Unlock()	node := NewLinkNode(str)	if link.LastNode != nil {		link.LastNode.next = &node	}	link.LastNode = &node	if link.FirstNode == nil {		link.FirstNode = &node	}	link.Count = link.Count +1}func (link *LinkTable) GetIterator() LinkIterator {	return NewLinkIterator(link)}type LinkNode struct {	value string	next *LinkNode}func NewLinkNode(value string) LinkNode {	return LinkNode{value: value}}type LinkIterator struct {	current LinkNode	link    LinkTable}func NewLinkIterator(link *LinkTable) LinkIterator {	return LinkIterator{link: *link}}func (iterator *LinkIterator) Next() string {	if iterator.current == (LinkNode{}) {		iterator.current = *(iterator.link.FirstNode)		if iterator.current != (LinkNode{}) {			return iterator.current.value		}	}	value := (*iterator.current.next).value	iterator.current = *iterator.current.next	return value}func (iterator *LinkIterator) HasNext() bool {	if iterator.current != (LinkNode{}) {		return iterator.current.next != nil	}else {		return iterator.link.FirstNode != nil	}}func (iterator *LinkIterator) CurrentItem() string {	return iterator.current.value}

复制代码

作业代码

func TestWeek8Job(t *testing.T) {	tableA := week8.NewLinkTable("A")	tableA.Add("a")	tableA.Add("b")	tableA.Add("x")	tableA.Add("y")	tableA.Add("z")	println(tableA.String())	tableB := week8.NewLinkTable("B")	tableB.Add("d")	tableB.Add("e")	tableB.Add("f")	tableB.Add("x")	tableB.Add("y")	tableB.Add("z")	println(tableB.String())	m := make(map[string]string, tableA.Count)	iteratorA := tableA.GetIterator()	//O(n)	for iteratorA.HasNext() {		item := iteratorA.Next()		m[item] = item	}	var target string	iteratorB := tableB.GetIterator()	//O(m)	for iteratorB.HasNext() {		item := iteratorB.Next()		if m[item] != ""  {			target = item			break		}	}	if target == "" {		println("链表A与链表B无合并")	}else {		println("链表A与链表B从元素[",target,"]开始合并")	}}

复制代码

运行结果

=== RUN   TestWeek8Joblink A: a -> b -> x -> y -> zlink B: d -> e -> f -> x -> y -> z链表A与链表B从元素[ x ]开始合并--- PASS: TestWeek8Job (0.00s)

复制代码

作业 2

假设 DataNode1 崩溃，NameNode 与 DataNode1 心跳检测无法连接到
NameNode 会先查找 DataNode1 中存储了哪些数据块，这些数据块的副本在在其他的 DataNode 的位置信息，假设分数据块副本在 node2 与 node3
NameNode 向 DataNode2 与 DataNode3 发送复制副本的请求，复制一份新的副本到 X 结点上，保证每个数据块的副本数量
复制完成后，NameNode 更新数据块的信息记录，完成恢复

发布于: 2021 年 01 月 18 日阅读数: 21

原文链接:【http://xie.infoq.cn/article/d3c42d2f4c6285ae066e9372c】。未经作者许可，禁止转载。

zbest

关注

一个胖子 2020.11.04 加入

一个不正经的java程序员，整天写着openresty和go的代码，努力从键摄向非职业摄影师迈进，快要溺死在内耗里的中年人，胖子。

发布

暂无评论

创作场景

架构师 3 期 3 班 -week8- 作业

作业

作业完成

作业 1

作业 2

zbest

评论