w8- 练习

用户头像
麻辣
关注
发布于: 15 小时前

链表合并监测



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

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





// 手写伪代码
func FindCross(l1 *Link, l2 *Link) interface{} {
stack1 := Stack{}
stack2 := Stack{}
for el := l1.Head(); el != nil; el = el.Next() {
stack1.Push(el.Value)
}
for el := l2.Head(); el != nil; el = el.Next() {
stack2.Push(el.Value)
}
var crossPoint interface{}
for {
e1 := stack1.Pop()
e2 := stack2.Pop()
if e1.Value != e2.Value {
break
}
crossPoint = e1.Value
}
return crossPoint
}



对于的以上代码的时间复杂度为link1 或 link2的长度,所以时间复杂度为O(N)

空间复杂度因为需要将所有的元素都放入Stack中,所以空间复杂度为N



HDFS datanode 失败处理

HDFS通过心跳的机制来确定data node的存活。

当data node失去心跳一段时间之后,name node判断该data node失败。

name node 搜索data node的文件块的编号及其他副本所在在的位置。

name node 向这些拥有失败data node锁包含数据块的其他data node发送copy相应的数据块到指定服务器。

新的数据块copy完成之后,通知name node, 给数据块新的副本已经ready.



用户头像

麻辣

关注

还未添加个人签名 2018.10.13 加入

还未添加个人简介

评论

发布
暂无评论
w8-练习