写点什么

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

用户头像
zbest
关注
发布于: 2021 年 01 月 18 日

作业


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

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

!png

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

作业完成

作业 1

设计

  1. 通过迭代器模式设计链表类

  2. 将一个链表循环放入 map

  3. 迭代另一个链表从 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


  1. 假设 DataNode1 崩溃,NameNode 与 DataNode1 心跳检测无法连接到

  2. NameNode 会先查找 DataNode1 中存储了哪些数据块,这些数据块的副本在在其他的 DataNode 的位置信息,假设分数据块副本在 node2 与 node3

  3. NameNode 向 DataNode2 与 DataNode3 发送复制副本的请求,复制一份新的副本到 X 结点上,保证每个数据块的副本数量

  4. 复制完成后,NameNode 更新数据块的信息记录,完成恢复


发布于: 2021 年 01 月 18 日阅读数: 21
用户头像

zbest

关注

一个胖子 2020.11.04 加入

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

评论

发布
暂无评论
架构师 3 期 3 班 -week8- 作业