架構師訓練營第 1 期 - 第 08 周作業

关注

发布于: 2020 年 11 月 13 日

作業一有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，也可能不合并，如下图所示的这样。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。请用代码（或伪代码）描述算法，并给出时间复杂度。
Code
class Node:
  def __init__(self, data):
    self.data = data
    self.next = None
﻿
def _create_list(items):
  head = current = None
  for index, item in enumerate(items):
    node = Node(item)
    if index == 0:
      head = current = node
    else:
      current.next = node
      current = node
  return head
﻿
def _find_node(head, item):
  current = head
  while current != None:
    if current.data == item:
      break
    else:
      current = current.next
  return current
﻿
def _print_list(head):
  current = head
  while (current != None):
    print(f'{current.data}',end='-')
    current = current.next
  print()
﻿
def _print_stack(stack):
  for item in stack:
    print(f"{item.data}", end=" ")
  print()
﻿
def _push_to_stack(list_head):
  stack = []
  current = list_head
  while (current != None):
    stack.append(current)
    current = current.next
  return stack
﻿
def _find_merge_node_alg1(head1, head2):
  current1 = head1
  current2 = head2
  same_node = None
  while current1 != None:
    while current2 != None:
      if current1 is current2:
        same_node = current1
        break
      current2 = current2.next
    if same_node != None:
      break
    current1 = current1.next
    current2 = head2
  return same_node
﻿
def _find_merge_node_alg2(head1, head2):
  stack1 = _push_to_stack(head1)
  stack2 = _push_to_stack(head2)
  same_node = None
  try:
    while True:
      node1 = stack1.pop()
      node2 = stack2.pop()
      if node1 is node2:
        same_node = node1
      else:
        break
  except IndexError:
    pass
  return same_node
﻿
if __name__ == '__main__':
﻿
  #list1 = ['a', 'b', 'x', 'y', 'z']
  list1 = ['a','b','x','y', 'z']
  list2 = ['d', 'e', 'f']
﻿
  head1 = _create_list(list1)
﻿
  # make merge list
  head2 = _create_list(list2)
  f_pos = _find_node(head2, 'f')
  x_pos = _find_node(head1, 'x')
  f_pos.next = x_pos
﻿
  _print_list(head1)
  _print_list(head2)
﻿
  node1 = _find_merge_node_alg1(head1, head2)
  node2 = _find_merge_node_alg2(head1, head2)
﻿
  if node1 != None:
    print(f"alg1: {node1.data}")
  else:
    print("alg1 not found")
﻿
  if node2 != None:
    print(f"alg2: {node2.data}")
  else:
    print("alg2 not found")
Output
a-b-x-y-z-
d-e-f-x-y-z-
alg1: x
alg2: x
說明
利用 python 模擬
演算法一
_find_merge_node_alg1(...)
暴力法:
遍尋兩個單向鏈表
最差時間複雜度 O( M x N)
空間複雜度: 沒有多使用其他空間
為 O(1)
演算法二
_find_merge_node_alg2(...)
利用 stack 反向查找
先將兩個鏈表分別推入兩個 stack 中
同時 pop 兩個 stack，直到第一個不同點
則前一個 pop 的點，即為合併點
最差時間複雜度 O ( N + 2 M)
假設 M < N
推入兩個 stack 需遍尋兩個鏈表，所以為 O(N + M)
此為一定要做的，屬於固定開銷
同時 pop，最差為找不到，短鏈表已經查完，所以為 O(M)
結合兩者 O (N + 2M)
空間複雜度，需增加兩個與鏈表同長之 stack
為 O (N + M)
分析
當鏈表較短且有合併時，演算法一會比較有利
因為演算法二有固定開銷，就是推入 stack 
當鏈表很長時且兩者沒有合併，演算法二會比較有利
N x M 會遠大於 N + 2M
作業二请画出 DataNode 服务器节点宕机的时候，HDFS 的处理过程时序图。時序圖
說明
每一個 DataNode 均會定期的向 NameNode 作 Heartbeat 回報狀況
當某一 DataNode (例如 DataNode 1) 超過一定時間段 (例如 10 次應回報時間)時，NameNode 會發起 recheck 的要求
當 DataNode 沒有回應兩次的 recheck 要求，NameNode會進入 Fail recover 階段
整理在 faile DataNode 上所有的 data block 有哪些
確定那些 data block 沒有達到系統規定的副本個數要求，並決定那些 DataNode 需要執行複製
當正常 DataNode 作 Heartbeat 回報時，分配需要複製的 data blocks 並下命令給 DataNode進行複製
收到命令的 DataNode會進行 data blocks 的複製
接收 data block 的 DataNode 會利用定期的 Heartbeat 進行回報
﻿