写点什么

架构师训练营第二期 Week 8 作业

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

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


class Node  attr_accessor :val, :next
def initialize(val = nil) @val = val endend
def merged_linked_list(l1, l1_length, l2, l2_length) shorter_list, longer_list = l1, l2 shorter_list, longer_list = l2, l1 if l1_length > l2_length # 用Hash缓存短链表的节点以节省内存空间 shorter_list_nodes = {}
while shorter_list shorter_list_nodes[shorter_list] = true shorter_list = shorter_list.next end
while longer_list return longer_list if shorter_list_nodes[longer_list] longer_list = longer_list.next end
nilend
l1 = Node.newn2 = Node.new('Hello World!')l1.next = n2n3 = Node.newn2.next = n3n4 = Node.newn3.next = n4
l2 = Node.newn5 = Node.newl2.next = n5n5.next = n2
# 这个会输出Hello World!puts merged_linked_list(l1, 4, l2, 3).val
l2 = Node.newn5 = Node.newl2.next = n5
# 这个会输出空puts merged_linked_list(l1, 4, l2, 2)
复制代码


时间复杂度是 O(m+n)。


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

也不知道理解的对不对。。。

用户头像

bigxiang

关注

还未添加个人签名 2018.03.21 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营第二期 Week 8 作业