# 2024q1 Homework2 (quiz1+2)
contributed by < `yan112388` >
## 2024q1 第 1 週測驗題
[題目](https://hackmd.io/@sysprog/linux2024-quiz1)
### 測驗一
**基本結構**：考慮 struct __node 為節點結構，有一個 int 儲存資料，及一個 left pointer, right pointer 和 next pointer
```c
typedef struct __node {
struct __node *left, *right;
struct __node *next;
long value;
} node_
```
本題實作了一個非遞迴 (non-recursive iterative) 的快速排序演算法，其中：
在 `quicksort` 中，可見以下程式碼初始化 begin 和 end。
```c
begin[0] = *list;
end[0] = list_tail(list);
```
由此可知 `list_tail` 如其名，目的為找到鏈結串列的尾端節點
```c
node_t *list_tail(node_t **left)
{
while ((*left) && (*left)->next)
left = &(AAAA);
return *left;
}
````
AAAA 應填入 `(*left)->next` ，使 left持續往下個節點走訪，直到最後一個節點為止
```c
int list_length(node_t **left)
{
int n = 0;
while (*left) {
++n;
left = &(BBBB);
}
return n;
}
```
BBBB 應填入 `(*left)->next` ，與前者作用相似，直到無節點為止
**本題quicksort原理**
* 利用 begin 和 end 作為堆疊，以利將數值分成不同區段來做排序。
首先會選擇區段的第一個節點作為基準點 (pivot)，接著走訪此區段內的每個節點，
將小於基準點之值的節點串接到 left，大於基準點之值的節點串接 right。
在每次循環時， 如果從 begin 與 end 拿出的值相同，則表示此節點的排列位置正確，
可將此加入最終的鏈結串列 result 中。
```c
while (p) {
node_t *n = p;
p = CCCC;
list_add(n->value > value ? &right : &left, n);
}
```
CCCC 應填入 `p->next`，用來拜訪區段內的每個節點
```c
begin[i] = left;
end[i] = DDDD;
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = right;
end[i + 2] = EEEE;
```
DDDD 填入 `list_tail(&left)` ，取得 left 的尾節點
EEEE 填入 `list_tail(&right)` ，取得 right 的尾節點
**改進方案**
* `max_level` 不須開到 `2＊n` ? `n` 即可
### 測驗二
[Timsort](https://en.wikipedia.org/wiki/Timsort)：
該排序法考量現實世界中的資料大多為已排序的，首先將序列分成多個 runs，使用插入排序法做排序，再以合併排序法將 runs 合併，最後排序完成。
* `find_run()` ：找到每個 run ，如果該 run 為降序排列，則反轉為升序
* `merge_force_collapse()`：強制合併剩餘的 runs ，直到剩餘 runs 的數量小於 3 個，過程中呼叫 `merge_at()`
* `merge_collapse()`：根據剩餘的 runs 數量決定要合併哪兩個 runs，過程中呼叫 `merge_at()`
* `merge_at()`：合併位於 at 處的兩個相鄰 runs
* `merge_final()`：將最後兩個 runs 合併，並呼叫 `build_prev_link()`
* `build_prev_link()`：將單向鏈結串列轉換為雙向循環鏈結串列
## 2024q2 第 2 週測驗題
[題目](https://hackmd.io/@sysprog/linux2024-quiz2)
### 測驗一
**以 Linux 核心的 hash table 架構實作** [LeetCode 105 Construct Binary Tree from Preorder and Inorder Traversal](https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/)
* 前序會先拜訪每個子樹的根節點，中序則將每個子樹的左右子樹分開來，因此能建構出唯一二元樹
* hlist_node 架構示意圖
其中，next 指向相鄰的節點本身，而 pprev 宣告為指標的指標，指向指著自身節點的指標。
``` c
struct hlist_node {
struct hlist_node *next, **pprev;
};
```
**Q：為甚麼要使用 hash table**？
建構過程，需要根據前序，在中序中找到對應的索引來確定左右子樹的範圍。直接在中序內線性查找的時間複雜度為 O(n) ，對於大規模的數據會很費時。因此，使用 hash table 能加快尋找速度。
* `find`：計算 hash 值，在中序中查找指定元素的索引
* `node_add`：將新的節點加到 hash table 中，使用 Division method 作為 hash function
* `dfs`：
1. 找到根節點在中序中的索引 `idx`
2. 根據索引 `idx` 將中序分成左子樹和右子樹
3. 根據前序的順序，遞迴建構左子樹和右子樹
```c
static struct TreeNode *dfs(int *preorder,
int pre_low,
int pre_high,
int *inorder,
int in_low,
int in_high,
struct hlist_head *in_heads,
int size)
{
if (in_low > in_high || pre_low > pre_high)
return NULL;
struct TreeNode *tn = malloc(sizeof(*tn));
tn->val = preorder[pre_low];
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);
return tn;
}
```
參考資料：[Linux 核心的 hash table 實作](https://hackmd.io/@sysprog/linux-hashtable)、[内核基础设施——hlist_head/hlist_node结构解析](https://linux.laoqinren.net/kernel/hlist/)
**測試程式**
根據給予的前序和中序，建構出一顆根為 root 的二元樹
```c
struct TreeNode *root = buildTree(preorder, preorderSize, inorder, inorderSize);
```
以下兩個函式能根據傳入的根結點，印出二元樹的前序與中序
```c
void printPreorder(struct TreeNode *root) {
if (!root)
return;
printf("%d ", root->val);
printPreorder(root->left);
printPreorder(root->right);
}
```
```c
void printInorder(struct TreeNode *root) {
if (!root)
return;
printInorder(root->left);
printf("%d ", root->val);
printInorder(root->right);
}
```
### 測驗二
實作一個 LRU Cache
* `lRUCacheCreate` : 建立一個新的 LRU Cache，指定其容量大小為 capacity
* `lRUCacheFree` : 釋放 LRU Cache 所佔用的記憶體空間
* `lRUCacheGet` : 從快取中獲取特定 key 對應的值，如果該值存在，則將該節點移動到鏈結串列的頭部
* `lRUCachePut` : 將指定值依據 key 放進 Cache，如果 Cache 已滿，則移除最久未被存取的節點。如果 key 已存在，則更新其值並將該節點移動到鏈結串列的頭部
### 測驗三
在指定的記憶體空間找出第 N 個設定的位元
* 有三個參數會傳入 `find_nth_bit`
`*addr` ：指向要查找的記憶體區域起始位置的指標
`size` ：要查找的記憶體區域的位元大小
`n` ：要查找的是第幾個設定的位元（從 0 開始數）
```c
static inline unsigned long find_nth_bit(const unsigned long *addr,
unsigned long size,
unsigned long n)
{
if (n >= size)
return size;
if (small_const_nbits(size)) {
unsigned long val = *addr & GENMASK(size - 1, 0);
return val ? fns(val, n) : size;
}
return FIND_NTH_BIT(addr[idx], size, n);
}
```
* 如果 `n` 大於或等於 `size`，則直接回傳 `size`，因為 `n` 已經超出了給定的範圍
* 如果 `size` 是一個很小的常數值且小於等於 `BITS_PER_LONG(64)` 並大於0，則只需檢查第一個 `unsigned long` 值
* 如果以上皆非，則利用巨集 `FIND_NTH_BIT`
* `GENMASK`：依據給定的範圍，產生連續的 bitmask
* `h` 和 `l` 是需要設置為 1 的最高有效位和最低有效位的位置
* 例：`GENMASK(5, 0)` 會生成 00000000000000000000000000111111（二進位）
* `FIND_NTH_BIT`：逐一檢查每個 `unsigned long` 值中設定的位元數量。如果設定的位元數量大於` n` ，則進入 `found` 標籤，使用 `fns` 函數在該值中找到第 `n` 個設定的位元。
* `__ffs`：回傳該數值中最右邊值為1的位元的位置
>延伸問題皆待補充
Sign in with Wallet
Connect another wallet