架构师训练营第 8 周

作业一：

以下两题，至少完成一道

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

请用（伪）代码描述算法，并给出时间复杂度和空间复杂度。



class Solution(object):

    def getIntersectionNode(self, headA, headB):

        """

        :type head1, head1: ListNode

        :rtype: ListNode

        """

        lenA, lenB = 0, 0

        pA = headA

        pB = headB

        while pA:

            pA = pA.next

            lenA += 1

        while pB:

            pB = pB.next

            lenB += 1

        pA = headA

        pB = headB

        if lenA > lenB:

            for i in range(lenA-lenB):

                pA = pA.next

        else:

            for i in range(lenB-lenA):

                pB = pB.next

        while pA!=pB:

            pA = pA.next

            pB = pB.next

        return pA

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

• 一个数据块在datanode上以文件形式存储在磁盘上，包括两个文件，一个是数据本身，一个是元数据包括数据块的长度，块数据的校验和，以及时间戳。

• DataNode启动后向namenode注册，通过后，周期性（1小时）的向namenode上报所有的块信息。

• 心跳是每3秒一次，心跳返回结果带有namenode给该datanode的命令如复制块数据到另一台机器，或删除某个数据块。如果超过10分钟没有收到某个datanode的心跳，则认为该节点不可用。

• 集群运行中可以安全加入和退出一些机器

作业二：

1 数据结构与算法

复杂度、NP

2 网络与数据库

时间、空间复杂度

链捕

二叉树

栈

队列

hash表

红黑树

3 常用算法

穷举、递归、贪心

4 OSI 七层结构、TCP/IP四层

传输层TCP、应用层HTTP

网络数据包