博文精选 | 架构入门感悟之八

2021-11-15 14:02:43

F5小安

文章速览:

 

行业:互联网

 

关键字:架构、单向链表

 

摘要:架构入门学习感悟

 

阅读时长:5分钟

 

 

以下文章来源于InfoQ!作者:莫问

 

 

Questions

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

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


思路 1:

遍历链表 1,对于链表 1 中的每个元素,判断链表 2 中是否存在,如果存在,那么就认为这两个链表合并了,第一个在另一个链表中存在的元素就是合并的元素,否则,没有合并。

时间复杂度:O(n^2)

空间复杂度:O(1)

思路 2:

遍历两个链表,每个链表使用一个栈存放链表元素,再将元素从两个栈中弹出,当链表合并时,两个链表弹出的元素存在相同,而弹出不同元素的上一个元素就是合并的元素。

时间复杂度:O(n)

空间复杂度:O(m+n)

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


上图为 HDFS 的架构,当 DataNodes 节点宕机时,因为该节点的数据在其它节点上有副本,所以可以将该节点的数据复制一份到另一个节点上,保证系统高可用。副本的配置存储在 NameNode 上,所以 NameNode 需要控制迁移逻辑。

 

 

以上是针对架构入门学习感悟的分享,希望对大家有帮助!

 

 

 

阅读原文

 

声明:本文章版权归原作者及原出处所有 。凡本社区注明来源:XXX或转自:XXX”的作品均转载自其它媒体,转载目的在于传递分享更多知识,内容为作者个人观点,仅供参考,并不代表本社区赞同其观点和对其真实性负责。本社区转载的文章,我们已经尽可能的对作者和来源进行了注明,若因故疏忽,造成漏注,请及时联系我们,我们将根据著作权人的要求,立即更正或者删除有关内容。本社区拥有对此声明的最终解释权。

发布评论 加入社群

发布评论

相关文章

博文精选 | TCP 协议灵魂问题,巩固你的网路底层基础

F5小安

2022-01-14 09:11:08 50

博文精选 | 架构师入门感悟之十三

F5小安

2021-11-22 13:19:24 80

博文精选 | 架构入门感悟之十二

F5小安

2021-11-18 17:45:22 93

Login

手机号
验证码
© 2019 F5 Networks, Inc. 版权所有。京ICP备16013763号-1