架构师训练营第 0 期第 8 周作业
1、链表合并问题
有两个单向链表(链表长度分别为 m,n),这两个单向链表有可能在某个元素合并,如下图所示的这样,也可能不合并。现在给定两个链表的头指针,在不修改链表的情况下,如何快速地判断这两个链表是否合并?如果合并,找到合并的元素,也就是图中的 x 元素。
请用(伪)代码描述算法,并给出时间复杂度和空间复杂度。
答:时间复杂度为 O(m + n),其中 m 和 n 为两个链表的长度,空间复杂度为O(1);
具体代码如下:
2、HDFS的DataNode宕机数据复制时序图
【DataNode】每3秒钟向【NameNode】发送心跳,【NameNode】记录【DataNode】的最新心跳时间;
如果【NameNode】在10分钟都没有接收到某个【DataNode】的心跳,开始数据复制流程;
首先查询宕机的【DataNode】上保存的数据块(block)有哪些;
根据数据块(block)信息查询对应的备份【DataNode】;
然后通知所有备份的【DataNode】将对应数据库复制到其他【DataNode】节点;
版权声明: 本文为 InfoQ 作者【Arthur】的原创文章。
原文链接:【http://xie.infoq.cn/article/24aa9b3147241372b2c7187df】。未经作者许可,禁止转载。
评论