# 2024q1 Homework2 (quiz1+2)

contributed by < [ChengChaoChun](https://github.com/ChengChaoChun) >

## 2024q1 第 1 週測驗題

## 第一題
### 分析 [Optimized QuickSort — C Implementation (Non-Recursive)](https://alienryderflex.com/quicksort/)
以升序排序來說，Quicksort 的關鍵是把 pivot key 放到陣列的正確位置，也就是在 pivot key 的左側都是小於等於 pivot key，右側都是大於等於pivot key。在 Non-Recursive 版本中，新增了兩個陣列，beg 和 end。把 pivot key 放置到正確的位置後， beg 陣列會分別記錄 pivot key 左測的陣列的第一個元素的索引和 pivot key 右測陣列的第一個元素索引，而 end 陣列會分別記錄 pivot key 左測的陣列的最後一個元素的索引和 pivot key 右測的陣列的最後一個元素的索引。這個步驟取代了原本 Wikipedia 版本的函式遞迴，因為遞迴式需要時間成本的。
### 測驗
題目將原本陣列資料結構換成 linked list，來實作 Non-Recursive Quicksort。

* 原本的 beg 和 end 紀錄索引的陣列替換成了 beg 指標陣列和 end 的陣列

node_t *begin[max_level], *end[max_level];
node_t *result = NULL, *left = NULL, *right = NULL;
    
begin[0] = *list;  
end[0] = list_tail(list);

* 建立三個指標，result，right，left。如果當前節點 n 的 value 大於 pivot 的 value 就把 n 鏈接到 right ， 否則鏈接到 left 。

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

* 把每個 node 都放到對應的 right 或 left 之後，依序將 left ， pivot ， right 分別加入到 begin 和 end 指標陣列，因為最後 result 是以這個順序來鏈接節點的。最後把 right 和 left 設置為 null ，然後接著下一輪的排序。

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;


## 2024q1 第 2 週測驗題

### 第一題
* 建立 hash table

struct hlist_head *in_heads = malloc(inorderSize * sizeof(*in_heads));
for (int i = 0; i < inorderSize; i++)
    INIT_HLIST_HEAD(&in_heads[i]);

* 以 inorder 順序依序將 node 添加到 hash table。
* 參考 [Linux 核心的 hash table 實作](https://hackmd.io/@sysprog/linux-hashtable) 可以清楚了解 Linux 核心的 hash table 資料結構

for (int i = 0; i < inorderSize; i++)
    node_add(inorder[i], i, inorderSize, in_heads);

* 在 node_add 函式中根據 hash 的值來添加到對應的 hash table 索引

static inline void node_add(int val,
                            int idx,
                            int size,
                            struct hlist_head *heads)
{
    struct order_node *on = malloc(sizeof(*on));
    on->val = val;
    on->idx = idx;
    int hash = (val < 0 ? -val : val) % size;
    hlist_add_head(&on->node, DDDD);
}

* 以 DFS 的方式來建立 Binary tree，這裡的關鍵是以 preorder 的順序依次找到 tree(subtree) 的 root 在 inorder 中的位置
* 參考[C++ | Recursive & Using Map Approaches](https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solutions/2279613/c-recursive-using-map-approaches/) 以相同方法建立 Binary tree

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);

### 第二題
`cashe` 紀錄容量，當前已使用的空間，還有維護兩個資料結構，分別是 linked list 和 hash table
#### lRUCacheCreate
`cashe` 建立後如下圖

#### lRUCacheFree
首先 traverse cashe 的 linked list，把每個 LRUNode 從 linked list 中移除並釋放記憶體空間，接著把 cashe 配置的空間回收。

#### lRUCacheGet
計算 key 的 hash 值，然後搜索 hash table 的那個 bucket。如果找到了需要把該 LRUNode 的 list_head 移動到第一個位置。 linked list 的順序表示訪問 LRUNode 順序，越晚訪問到節點放在越前面。

#### lRUCachePut
* 這個函式的前半部分與 `lRUCacheGet` 相同，如果 LRUNode 已經存在就只要更新 value
* 如果 cashe 已經滿了，把 linked list 最後一個節點移除， hash table 中的紀錄也要移除。把新加入節點鏈接在 linked list 的第一個位置，並放入 hash table 對應的 bucket 。 否則配置一個 LRUNode 空間，然後同樣把節點鏈接在 linked list 的第一個位置和放入 hash table 對應的 bucket
* 如果 cashe 已經滿了，新加入的資料使用的記憶體空間是 linked list 最後一個節點的 LRUNode 空間，也就是 Least Recently Used LRUNode 原本的空間，所以不需要 malloc 新的空間
* 如果 cashe 已經滿了，因為使用的是原本 Least Recently Used LRUNode 的空間，所以 count 不需要+1 ; 如果 cashe 還有空間，會配置一個新的 LRUNode 空間，所以 count 要+1

if (!cache) {
    if (obj->count == obj->capacity) {
        cache = list_last_entry(&obj->dhead, LRUNode, link);
        list_move(&cache->link, &obj->dhead);
        hlist_del(&cache->node);
        hlist_add_head(&cache->node, &obj->hhead[hash]);
    } else {
        cache = malloc(sizeof(LRUNode));
        hlist_add_head(&cache->node, &obj->hhead[hash]);
        list_add(&cache->link, &obj->dhead);
        obj->count++;
    }
    cache->key = key;
}