架构师训练营 -week8- 作业
第一题:
判断是否合并的方法:
本文采取了将其中一个链首尾相连,通过快慢指针查另一个链中是否存在环的方式进行判断。
找到合并的元素:
在网上找了些资料,依据以下结论完成代码。
已知头节点d到连接点x需要a步,环长度为L,快指针的前进步数是慢指针的2倍,快指针与慢指针相遇的节点为y。慢指针进入环中时,即慢指针在连接点x,此时快指针在b点,快指针需要2m步才能追上慢指针。设慢指针走了s步到相遇节点,快指针走了2s步到相遇节点。
可知,s=a+m;2s = a+n*L+m。
可得a=n*L-m,即若在头节点前置节点与相遇节点各设一指针,同时单步前进,则最后一定相遇在连接点x。
由于头节点的前置节点是虚空,所以修正为若在头节点与相遇节点的下一节点各设一指针,同时单步前进,则最后一定相遇在连接点x。
代码
节点Node<T>
自定义链表接口IMyList<T>
自定义链表实现类MyList<T>
环工具类MyRing
测试类MyListTest
结果输出:
时间复杂度:O(nlog n),空间复杂度:O(1)。
更正:时间复杂度O(N)
第二题:
DataNode失效时的过程:
DataNode启动时,会到NameNode注册,此后会定时发送心跳包给NameNode。当NameNode超时没有收到心跳包,则判定该DataNode失效。此时NameNode就会通过检查元数据找到失效的DataNode上备份数据块在哪些DataNode上。检查完成后,通知所有的服务器将失效DataNode上的数据块的备份复制到指定机器上。
版权声明: 本文为 InfoQ 作者【晓-Michelle】的原创文章。
原文链接:【http://xie.infoq.cn/article/eb61adc1ad30f797f9164d939】。未经作者许可,禁止转载。
评论