contributed by < `jerry7961` >
## 第一周測驗題
### 測驗一
這是一個非遞迴的快速排序演算法，用來對鏈結串列進行排序：
1. 首先計算出原始鏈結串列的長度 n，並初始化一些必要的資料結構，將原始鏈結串列 push 進 stack 中。
2. 進入 while 迴圈，每次從stack頂端 pop 出一對節點指標( begin[i] 和 end[i] )，代表一個子鏈結串列。
3. 如果 begin[i] 和 end[i] 不同,代表子鏈結串列至少有兩個節點：
* 選擇 begin[i] 所指向的節點作為 pivot 。
* 走訪子鏈結串列，將小於 pivot 的節點插入 left 鏈結串列，大於 pivot 的節點插入 right 鏈結串列。
* 將 left 、 pivot 以及 right 三個部分的開始和結束節點指標依序 push 進 stack 中，等待進一步排序。
5. 如果 begin[i] 和 end[i] 相同，代表子鏈結串列只有一個節點或為空串列。使用 list_add 函數將 begin[i] 指向的節點(如果存在)插入result鏈結串列中。
6. 重複步驟 2 ，直到 stack 為空
7. 最終result鏈結串列就是排序後的結果，將其賦值給原始鏈結串列。

以包含五個節點 (4、2、5、10、1) 的鏈結串列為例：
未進入 while 迴圈前， stack 中只有原始鏈結串列(如下)。
在第一輪 while 結束後， stack 中會有三個子鏈結串列(如下)。

void quick_sort(node_t **list)
{
    int n = list_length(list);
    int value;
    int i = 0;
    int max_level = 2 * n;
    node_t *begin[max_level], *end[max_level];
    node_t *result = NULL, *left = NULL, *right = NULL;

    begin[0] = *list;
    end[0] = list_tail(list);

    while (i >= 0) {
        node_t *L = begin[i], *R = end[i];
        if (L != R) {
            node_t *pivot = L;
            value = pivot->value;
            node_t *p = pivot->next;
            pivot->next = NULL;

            while (p) {
                node_t *n = p;
                p = p->next; // CCCC
                list_add(n->value > value ? &right : &left, n);
            }

            begin[i] = left;
            end[i] = list_tail(&left); // DDDD
            begin[i + 1] = pivot;
            end[i + 1] = pivot;
            begin[i + 2] = right;
            end[i + 2] = list_tail(&right); // EEEE

            left = right = NULL;
            i += 2;
        } else {
            if (L)
                list_add(&result, L);
            i--;
        }
    }
    *list = result;
}

### 測驗二
Timsort 主要改進了 Merge Sort 的以下幾個方面：

* 降低 Cache miss 次數： Timsort 在尋找、分割和合併 runs (已排序的子序列)時，儘量讓要排序的節點剛才存取過，還在記憶體階層上層時，就進行合併，避免不必要的資料遷移，降低 cache miss 。
* 降低記憶體開銷：傳統 Merge Sort 在合併時需額外配置與待合併的二個 runs 相同大小的記憶體空間，而 Timsort 只需配置較短的 run 的空間大小。
* 降低比較次數：利用資料的部分有序性，減少比較操作。

主要函式：
* `merge()` ：合併兩個已排序的 runs 為一個新 run 。
- `AAAA`: 應該填入 `&head` ，初始化 `tail` 指向 `head` ，以建構新的鏈結串列。
- `BBBB` : 應該填入 `&a->next` ， 從 `a` 鏈結串列取出一個節點後，需要將 `tail` 指向該節點的下一個節點。
- `CCCC` : 應該填入 `&b->next`，從 `b` 鏈結串列取出一個節點後，需要將 `tail` 指向該節點的下一個節點。
* `build_prev_link()` ：將一個單向鏈結串列轉換為雙向環狀鏈結串列。
- `DDDD` ： 應該填入 `tail->next`，將最後一個節點的 `next` 指標設置為 `head`，這樣鏈結串列就形成了環，從尾部指向頭部。
- `EEEE` ： 應該填入 `head->prev`，將頭部節點的 `prev` 指標設置為 `tail`，這樣鏈結串列就完成了雙向鏈結，從頭部指向尾部。
* `timsort()` ：

    stk_size = 0;

    struct list_head *list = head->next, *tp = NULL;
    if (head == head->prev)
        return;

    /* Convert to a null-terminated singly-linked list. */
    head->prev->next = NULL;

- 首先初始化 `stk_size` 為 0 ，用來記錄堆疊中 `run` 的數量。
- 然後將 `list` 指向鏈結串列的第一個節點， `tp` 初始化為 `NULL`。
- 如果鏈結串列為空，直接返回。
- 將原來的雙向環狀鏈結串列轉換為單向鏈結串列，方便後續操作。<br><br>

     do {
        /* Find next run */
        struct pair result = find_run(priv, list, cmp);
        result.head->prev = tp;
        tp = result.head;
        list = result.next;
        stk_size++;
        tp = merge_collapse(priv, cmp, tp);
      } while (list);

- 這個 loop 用於找出鏈結串列中的所有 run，並將它們暫存在一個堆疊中。
在每次循環中：
1. 調用 `find_run` 找出當前位置開始的一個 run ，並返回 run 的頭部和尾部節點。
2. 將新找到的這個 run 的頭部節點的 `prev` 指針指向前一個 run 的頭部節點 `tp`。
3. 將 `tp` 更新為新 run 的頭部節點。
4. 將 `list` 指向新 run 的下一個位置，準備下一次循環。
5. `stk_size` 累加 1，表示堆疊中 run 的數量增加了 1。
6. 調用 `merge_collapse` 嘗試將堆疊中的相鄰 run 進行合併，確保堆疊上的 run 長度保持平衡。

直到 `list` 指向 `NULL`，表示鏈結串列中的所有 run 都已經找出並加入堆疊中。<br><br>

        tp = merge_force_collapse(priv, cmp, tp);

- 合併所有 run 。<br><br>

     struct list_head *stk0 = tp, *stk1 = stk0->prev;
     while (stk1 && stk1->prev)
         stk0 = stk0->prev, stk1 = stk1->prev;
     if (stk_size <= 1) {
         build_prev_link(head, head, stk0);
         return;
     }

- 如果堆疊中只剩一個 run ，直接調用 `build_prev_link` 將這個 run 重建成雙向環狀鏈結串列。否則調用 `merge_final` 做最終的合併。

**延伸問題**

定義一個 minrun (最小運行長度)，用以表示每個 run 的最小長度，若長度太短，就用二分插入排序，將 run 後面的元素插入到前面的 run 裡面。
## 第二周測驗題
### 測驗ㄧ
這個程式根據 preorder 和 inorder 走訪的結果，利用 dfs 方法來重建二元樹。
* 利用 `find` 在 hash table 中找到值為 `preorder[pre_low]` 的節點在 `inorder` 陣列中的位置，並賦值給 `idx`。

int idx = find(preorder[pre_low], size, in_heads);`

* 遞迴建構左子樹

tn->left = dfs(preorder, pre_low + 1, pre_low + (idx - in_low), inorder,
               in_low, idx - 1, in_heads, size);

* 遞迴建構右子樹

tn->right = dfs(preorder, pre_high - (in_high - idx - 1), pre_high, inorder,
                    idx + 1, in_high, in_heads, size);

### 測驗二
`hlist_del` 用來刪除節點。

void hlist_del(struct hlist_node *n)
{
    struct hlist_node *next = n->next, **pprev = n->pprev;
    *pprev = next;
    if (next)
        next->pprev = pprev; // EEEE
}

`lRUCacheFree` 用來釋放整個 cache 佔用的空間。 它使用 `list_for_each_safe` 走訪鏈結串列中的所有節點，並利用 `list_del` 來刪除這些節點。

void lRUCacheFree(LRUCache *obj)
{
    struct list_head *pos, *n;
    list_for_each_safe (pos, n, &obj->dhead) {
        LRUNode *cache = list_entry(pos, LRUNode, link); // FFFF
        list_del(&cache->link); // GGGG
        free(cache);
    }
    free(obj);
}