架构师训练营 - 第 8 周命题作业
题1：
1.1
有两个单向链表（链表长度分别为m，n），这两个单向链表有可能在某个元素合并，如下图所示的这样，也可能不合并。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。请用（伪）代码描述算法，并给出时间复杂度和空间复杂度。 解题：时间复杂度：O(m+n),空间复杂度O(m+n)
public static Integer findMergeNode(Node nodeOne, Node nodeTwo) {
1.2例如以下示例中 A 和 B 两个链表相交于 c1：
A: a1 → a2
B: b1 → b2 → b3但是不会出现以下相交的情况，因为每个节点只有一个 next 指针，也就只能有一个后继节点，而以下示例中节点 c 有两个后继节点。
A: a1 → a2 d1 → d2
B: b1 → b2 → b3 e1 → e2要求时间复杂度为 O(N)，空间复杂度为 O(1)。如果不存在交点则返回 null。
设 A 的长度为 a + c，B 的长度为 b + c，其中 c 为尾部公共部分长度，可知 a + c + b = b + c + a。
当访问 A 链表的指针访问到链表尾部时，令它从链表 B 的头部开始访问链表 B；同样地，当访问 B 链表的指针访问到链表尾部时，令它从链表 A 的头部开始访问链表 A。这样就能控制访问 A 和 B 两个链表的指针能同时访问到交点。
如果不存在交点，那么 a + b = b + a，以下实现代码中 l1 和 l2 会同时为 null，从而退出循环。
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
}
第二题
请画出DataNode服务器节点宕机的时候，HDFS的处理过程时序图。
版权声明: 本文为 InfoQ 作者【红了哟】的原创文章。
原文链接:【http://xie.infoq.cn/article/f2c95aaa205f6d2ac07f7b9f0】。文章转载请联系作者。
还未添加个人签名 2019.08.15 加入
还未添加个人简介
评论