架构师课程第八周 作业

一、有两个单向链表（长度分别为m，n），这两个链表有可能在某个元素合并，如下图所示，也可能不合并。现在给定两个链表的头指针，在不修改链表的情况下，如何快速判断这两个链表是否合并？如果合并，找到合并的元素。请用（伪）代码描述算法，并给出时间复杂度。



linked m = [a, b, x ,y, z]
linked n=[d, e, f, x ,y, z]
hash sinal[m] = []
l = m.head
for i=0;i<m+n;i++ {
  if i < m { 
    singal[i] = &l 
  } else { 
    if &l in sinal {
      return &l 
    }
    if l.next == null { return null }
  }
  if i == m-1 { 
    l = n.head
    continue
  }
  l = l.next
}

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

三、总结

本周已经是第八周了，可以说是赛程过半，不知道每个人的进度如何。我感觉课程的主要内容集中在基础知识的了解方面，很多东西如果要弄清楚还是需要查看更多的资料以及更多的实践，毕竟大部分技术都是人们通过实践得来的，还是要从实践中理解。有一些东西可能真的是实验室出来的东西，理解起来比较晦涩，不符合人的习惯，但是大部分的东西理解应该是没有问题的。那我们是否需要立刻马上就是花大量时间在这些方面的，我觉得像老师说不需要什么东西都马上去理解，主要还是要掌握学习方法以及积累大量基础知识，这样在泳道的时候，再去学习了解就可以更轻松，而且不容易忘记。没有人能记住几年都不会使用的一门技术的具体实现。我们只要做一个基本的了解，知道这个东西是解决什么问题的，这样当我们碰到这方面的问题的时候我们能想到这个技术可以解决就行了。当我们掌握了大量基础知识之后，也可以像老师一样试着去推理出这种问题的最佳方案然后去对比着学习，这样也可以达到事半功倍的效果。所以，学习有的时候不求深但求广。

本周主要内容有：数据结构与算法、网络通信协议、数据库实现逻辑。

数据结构主要有线性、树形、图的组织方式。其中数组、链表、hash表、栈、队列、跳表可以用线性方式，树、二叉树用树形。数组是内存中一连串的地址空间，每个数组的大小相同，它的优势是随机访问的时间复杂度是O(1)，但是插入、删除数组元素的代价是O(n)。为了改善数组的随机访问时间，人们设计了链表，插入、删除元素的时间复杂度可以达到O(1)，但是却失去了数组可以随机访问的优势，但是链表中每个元素的大小就可以不同的。因此什么时候使用数组什么时候使用链表需要程序员根据自己的业务特点进行选择。为了想要同时拥有数组和链表的优点，人们又设计了hash表这种数据结构，hash表本质上还是数组，通过某一个hash函数将key/value数据中的key映射成数组的下标，由于hash表空间的大小以及hash函数的原因，hash冲突时有发生，所以可以将hash表中的每个元素设计成一个链表，来存储hash冲突的元素。hash表拥有随机访问的时间复杂度O(1)以及插入删除元素的时间复杂度O(1)，不过在极端情况下，hash表可能会退化为一个链表。一致性hash则是分布式缓冲中使用的一种改成hash表。栈与队列则是操作受限的线性表，栈表现为元素只能后进先出，队列表现为先进先出。树则是另一种类型的数据结构了，树有根节点以及它的子树组成，二叉树则是限定每个节点至多只能有2个子树的树，其中平衡二叉排序树使用的比较多，因为它的查询时间复杂度可以到O(logn)，插入删除元素可以达到O(logn)，当然由于元素的插入删除，平衡二叉排序树可能会失去它的平衡性，所以需要移动一些节点保持它的平衡。B+树、红黑树都是对树在特定场景下的改进。红黑树最多只需3次旋转就会重新达成红黑树的平衡，时间复杂度为O(1)，在有大量元素增删的场景汇总，红黑树比平衡二叉树效率更高，红黑树的平衡性不如平衡二叉树，查询效率稍低。跳表则是一种以空间换时间的多个链表组成。为了更快速查找到元素，跳表将链表中的元素经过不同步长提取到另一个链表中。

常见算法可以归类为以下几个大类：穷举、递归、贪心、动态规划。

在互联网的基础中，网络协议是必不可少的。ISO模型以及TCP/IP协议则是描述网络协议的分层架构。ISO模型中将网络通信分为应用层、会话层、表示层、传输层、网络层、数据链路层、物理层7层结构。上层对下层有感，下层对上层无感。分层的好处自然是为了简化通信的结构，每层只需关注一部分内容，是网络更加容易理解、更加容易使用。实际中互联网大部分使用TCP/IP协议族，简化了ISO的7层结构，将网络协议分成4层：应用层、传输层、网络层、网络访问层。