# 2024q1 Homework2 (quiz1+2)

contributed by < [ollieni](https://github.com/ollieni) >
## 第一周測驗題
### 測驗一
這題是想透過非遞迴的方式實作 quick sort。
根據參考資料: [ Optimized QuickSort — C Implementation (Non-Recursive)](https://alienryderflex.com/quicksort/) ，作者提到想改進維基百科的做法，其中原因如下 :
1. 避免函式呼叫，因為進出函式是耗時的。
2. 不使用堆疊儲存資料，避免遞迴函數的性能慢且可能引起堆疊溢位。
3. 交換變數只在每輪中傳遞一個項目，降低效能成本。
4. 每輪中元素只移動到列表中的新位置一次，減少不必要的移動。
5. 當元素在 pivots 目的地正確一側，避免不必要的移動。
6. 避免在每輪中有50％的機會將列表中的元素與自身交換，降低性能成本。

這裡發現了一個問題，作者提到不使用堆疊儲存資料，但老師的測驗中提到"這份程式碼嘗試用堆疊模擬原本的遞迴呼叫"。
目前還沒想出這之間的關係。

本題的鏈結串列結構體如下:

typedef struct __node {
    struct __node *left, *right;
    struct __node *next;
    long value;
} node_t;

digraph structs {
        node[shape=record];
        struct0 [label="{<node>*left|<node>*right}|<node>*next|<data>value",color=black]
        rankdir=LR;
        node[shape=box];
}

## 重新回答題目
要我們填空的程式碼如下:
首先是`list_tail()`，依據函式名稱可以推論出此函式的功能是找到鍊結串列的尾端。

node_t *list_tail(node_t **left)
{
    while ((*left) && (*left)->next)
        left = &(AAAA);
    return *left;
}

可以看到 `while` 迴圈的停止條件是 `*left` 和 `(*left)->next`，其中之一為 `NULL` ，因此當 `*left` 指向尾端時，此迴圈就會停止，接著函式就會回傳 `*left` ，也就是尾端。
因此若是要找到尾端， `left = &(AAAA);` ，應為不斷往下一格移動。
所以 `AAAA` 的答案是 `(*left)->next`。

---

根據 `list_length()` 的函式名稱，我們可以得知此程式的目的是回傳鍊結串列的長度。

int list_length(node_t **left)
{
    int n = 0;
    while (*left) {
        ++n;
        left = &(BBBB);
    }
    return n;
}

依據現有的程式碼可以得知，此函式會在 `*left` 不為 `NULL` 時，持續將 `n` 加一，當 `*left` 為 `NULL` 時停止(也就達到尾端)。
因此可以推論出 `BBBB` 會讓 `*left` 持續往尾端移動。
答案為 `(*left)->next`。

---

以下程式碼為 quick sort 實作的一部份。

.
.
.
    while (p) {
        node_t *n = p;
        p = CCCC;
        list_add(n->value > value ? &right : &left, n);
    }
    begin[i] = left;
    end[i] = DDDD;
    begin[i + 1] = pivot;
    end[i + 1] = pivot;
    begin[i + 2] = right;
    end[i + 2] = EEEE;

    left = right = NULL;
    i += 2;
.
.
.

CCCC 在一個 `while` 迴圈中，這個迴圈會根據 n->value 是否大於 value，將節點 n 添加到名為 right 或 left 的鍊結串列中，此迴圈目的是在將鍊結串列依據大小分成 pivot 左右兩邊的串列。
因此需要走過每一個節點， CCCC 為 `p->next`。
begin 和 end 分別是在記錄左右兩邊串列的頭尾，因此 DDDD 應為 begin[i] 的尾端，我們可以用 `list_tail()` 來找尾端， DDDD 的答案就會是 `list_tail(left)`。
EEEE 會是 begin[i+2] 的尾端，答案會是 `list_tail(right)`。
### 測驗二
請補完 Timsort 程式碼，使其運作符合預期。
Timsort 為合併排序和插入排序的組合算法。
將數列分成數個 run (比較小的數列)以 insertion sort 將 run 裡的數字排序，再將所有 run 用 merge sort 的方式合併在一起。
分 run 時，有幾點需注意
1. run 的長度不宜超過 64，因為 insertion sort 的效果會變差
2. run 最好是二的次方， merge 合併效率才會比較好

## 第二周測驗題

### 測驗一
LeetCode [105 Construct Binary Tree from Preorder and Inorder Traversal](https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/)
用前序 (preorder) 和中序 (inorder) 重構二元樹。

**Preorder Traversal 前序遍歷**:
用Depth-first Search走訪整棵樹，順序是：根、左子樹、右子樹。根排在最前面。

**Inorder Traversal 中序遍歷**:
也是採用Depth-first Search，走訪順序是：左子樹、根、右子樹。根排在中間。

#### **Key point** :
preorder 和 inorder ，可以用根的位置，用 Divide-and-Conquer 的概念，建立唯一二元樹。

在 preorder 之中，最左端一定是根節點。 inorder 中，根的兩側是左子樹和右子樹。因為子樹也是樹，可以用相同方式遞迴下去，求出整棵樹的架構。

**hlist_node**

digraph structs {
        node[shape=record];
        struct0 [label="{<node1>*next|<node2>*pprev}",color=black]
        rankdir=LR;
        node[shape=box];
}

**Tree_Node 結構**:

digraph structs {
        node[shape=record];
        struct0 [label="{<node>*left|<node>*right}|<data>val",color=black]
        rankdir=LR;
        node[shape=box];
}

**order_node 結構**:

digraph structs {
        node[shape=record];
        struct0 [label="<node>*node|<data>val|<data>idx",color=black]
        rankdir=LR;
        node[shape=box];
}

這是一個經典的問題，接下來我會以我的理解，解釋這題的程式。

函式解釋:
**find**
找出 value = num 的節點。
這個函數的目的是在 hash 串列中查找特定數值 num 的索引。
使用 hash 值計算，確保索引落在 hash 表範圍內。
透過 `hlist_for_each` 循環遍歷 hash 鏈表，並使用 `container_of` 將節點轉換為 order_node 結構。
若找到相應的數值，則返回對應的索引；否則返回 -1。

**dfs**
使用遞迴的方式做深度優先搜尋。
用於構建二元樹。
接收前序和中序走訪的區間，以及相應的 hash 串列等參數。
透過遞迴方式，根據前序遍歷的順序，建立二元樹的每個節點。
利用 `find` 函數找到中序走訪中該節點的索引，並分別遞迴建立左右子樹。

**buildTree**
使用 inorder 和 preorder 來建立一個唯一的樹。
這個函數是用於建立二元樹。
一開始配置 hash 串列的內存，並初始化每個 hash 串列。
使用前序遍歷的數組建立 hash 串列，同時調用 `dfs` 遞迴函式構建整個二元樹。
返回指向根節點的指標。

### 測驗二
程式目的 : 實作 Least Recently Used (LRU) Cache
在清除快取中的資料時，將上一次使用時間離現在最遠的資料清除。

**LRUNode 結構**：

digraph G {
    rankdir = LR;
    node [shape=record]
    
    subgraph cluster_1 {
        node [shape=record];
        label="LRUNode";
        hn [label="{ **pprev | *next }"];
        lh [label="{ *prev | *next }"];
        node1[label="{ key | value }"];
    }
}

**LRUCache 結構**

digraph LRUCache {
    rankdir = LR;
    node [shape=record]
    
    subgraph cluster_1 {
        node [shape=record];
        label="LRUCache";
        node1[label="{ capacity | count }"];
        lh [label="{ *prev | *next }"];
        hn [label="{ hhead }"];
    }
    hln1 [label="{ **pprev | *next }"];
    hln2 [label="{ **pprev | *next }"];
    hn->hln1->hln2
}

函式解釋 :
**lRUCacheCreate**
創建一個空的 lRU cache ，並根據 `capacity` 配置記憶體。

**lRUCacheFree**
將 lRUCache 清空，並釋放記憶體。
使用 `list_for_each_safe` 走訪全部節點，並將結點記憶體釋放。

**lRUCacheGet**
根據 key ，從快取中取出相對應的值。
將 key 除餘 capacity ，得到 key 的 hash 值，再用 hlist_for_each走訪，若在LRUCache->hhead[hash] 的每個節點中，有找到 key 的值，將該節點放到 `obj->dhead`，也就是最前面。

**lRUCachePut**
將 key-value 放入快取中。
先查詢 key 是否存在，若存在就將其放到最前面的位置。若不存在，先檢查 cache 是否滿了，若沒滿則直接將 key-value 插入。若 cache 已滿，將最後的 key-value 刪除，並將要插入的 key-value 放到最前面。

### 測驗三
程式目的 : 找到第 n 個為1的 bit 。
**ffs** :
此函式功能為找出第一個是 1 的 bit。
其運作原理和 find_leading_zero 很相似。

...
///如果最低的16位都为0，将 num 加上16，然后将 word 右移16位
if ((word & 0xffff) == 0) {
        num += 16;
        word >>= 16;
    }
///如果最低的8位都为0，将 num 加上8，然后将 word 右移8位。
    if ((word & 0xff) == 0) {
        num += 8;
        word >>= 8;
    }
///如果最低的4位都为0，将 num 加上4，然后将 word 右移4位。
    if ((word & 0xf) == 0) {
        num += 4;
        word >>= 4;
    }
///如果最低的2位都为0，将 num 加上2，然后将 word 右移2位。
    if ((word & 0x3) == 0) {
        num += 2;
        word >>= 2;
    }
///如果最低的1位为0，将 num 加上1
    if ((word & 0x1) == 0)
        num += 1;
    return num;
...

**clear_bit** :
將特定區塊的 bits 刪除。
用 `BIT_MASK(nr)` 產生一個在 nr 位置是1，其他位置皆為0的 mask ，可用於清除特定 bit。
找到包含要刪除 bit 的 word 記憶體位置的 pointer。
對pointer 用 `~mask` 做 bit-wise and 將 bit 刪除。

**fns** :
用 __ffs 去找第一個是1的 bit，用 __clear_bit 刪除，重複 n 次，即可找到第 n 個是 1 的 bit。