## 第一周測驗題
### 測驗 `1`
先閱讀教材 [a pointer to a pointer](https://hackmd.io/@sysprog/c-linked-list) 了解指標的指標是什麼?
```clike
#include <stdio.h>
int main() {
int val = 10;
int *pointer_1 = &val;
int **pointer_2 = &pointer_1;
printf("val 存的值: %d\n", val);
printf("val 記憶體位址: %p\n", &val);
printf("pointer_1 指向的位址儲存的值: %d\n", *pointer_1);
printf("pointer_1 指向的位址: %p\n", pointer_1);
printf("pointer_1 記憶體位址: %p\n", &pointer_1);
printf("pointer_2 指向的位址所儲存的值(位址): %p\n", *pointer_2);
printf("pointer_2 指向的位址所指向的位址儲存的值: %d\n", **pointer_2);
printf("pointer_2 指向的位址: %p\n", pointer_2);
printf("pointer_2 記憶體位址: %p\n", &pointer_2);
return 0;
}
```
```
val 存的值: 10
val 所在的記憶體位址: 0x7fffffffd534
pointer_1 指向的位址儲存的值: 10
pointer_1 指向的位址: 0x7fffffffd534
pointer_1 所在的記憶體位址: 0x7fffffffd538
pointer_2 指向的位址所儲存的值(位址): 0x7fffffffd534
pointer_2 指向的位址所指向的位址儲存的值: 10
pointer_2 指向的位址: 0x7fffffffd538
pointer_2 所在的記憶體位址: 0x7fffffffd540
```
`lsit_inster_before` 函式的功能為: 負責在鏈結串列 (list_t) 中，在指定的節點 (before) 之前插入新節點 (item)。
AAAA : 是一個指向鏈結串列開頭的變數所以為 &l->head。p 就變成 指向 head 指標的指標 `list_item_t **`，因此 *p 就是 head 本身。
BBBB : 遍歷節點直到找到需要的點 before ， *p 代表當前節點，因此 *p != BBBB 代表還沒找到 before。
CCCC : 讓 p 指向下一個 next 指標的位置。
DDDD : *p 是 before 前一個節點的 next，讓 item 成為 before 前一個節點的 next。 最後讓 item->next 連接到 before，確保 item 插入後仍然連接到 before。
```clike
static inline void list_insert_before(list_t *l, list_item_t *before, list_item_t *item)
{
list_item_t **p;
for (p = &l->head; *p != before; p = &(*p)->next);
*p = item;
item->next = before;
}
```
` static char *test_list(void) ` 功能為: 測試在各個位置插入元素的情況
正確執行:
#### 在現有的程式碼基礎上，撰寫合併排序操作
在將節點使用 `list_move_tail` 的方法改成使用 `list_insert_before` 替代 ，透過 pointer to pointer 操作 插入正確位置。
```clike
void q_sort(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *slow = head;
struct list_head *fast = head->next;
while (fast != head && fast->next != head) {
slow = slow->next;
fast = fast->next->next;
}
struct list_head first;
list_cut_position(&first, head, slow);
q_sort(&first);
q_sort(head);
q_merge_list(head, &first);
}
```
```clike
void q_merge_list(struct list_head *left_list, struct list_head *right_list)
{
if (!left_list || !right_list)
return;
struct list_head temp;
INIT_LIST_HEAD(&temp);
while (!list_empty(left_list) && !list_empty(right_list)) {
element_t *first_node = list_first_entry(left_list, element_t, list);
element_t *second_node = list_first_entry(right_list, element_t, list);
bool tag = strcmp(first_node->value, second_node->value) < 0;
element_t *add_first = tag ? first_node : second_node;
list_insert_before(&temp, temp.next, &add_first->list);
}
list_splice_tail_init(left_list, &temp);
list_splice_tail_init(right_list, &temp);
list_splice(&temp, left_list);
}
```
### 測驗 `2`
擁有兩個子節點的情況
* 找到 target 的 predecessor，就是左子樹中最大（最右邊）的節點：
透過 while (EEEE) pred_ptr = FFFF; 來遍歷 target 左子樹中的最右點。
在尋找 target->l 中最右的節點：
`EEEE` 表示迴圈繼續的條件，應該是還有右子樹 `*pred_ptr->r`。
`FFFF` 表示更新指標，應該移動到右子數 `&(*pred_ptr)->r`。
* 用這一點來取代 target：
若 pred_ptr 直接是 target->l，直接把 target->r 連接到新節點。
若 pred_ptr 不在 target->l，則將其從原來的位置移除，然後插入 target 的位置。
使用 `find_free_tree(root, target)` 找到 target 的位置。
```clike
block_t **find_free_tree(block_t **root, block_t *target) {
while (*root && *root != target) {
if (target->size < (*root)->size)
root = &(*root)->l;
else
root = &(*root)->r;
}
return root;
}
```
使用 `find_predecessor_free_tree(block_t **root, block_t *node)` 找 predecessor
```clike
block_t *find_predecessor_free_tree(block_t **root, block_t *node) {
block_t *pred = NULL;
if (node->l) {
pred = node->l;
while (pred->r) pred = pred->r;
}
return pred;
}
```
### 測驗 `3`
`HHHH` : 取得 pivot 的值，使用 `list.h` 中的 `list_entry(pivot, node_t, list)->value` 找到 pivot 的值
`IIII` : 取得 n 的值，一樣使用 `list.h` 中的 `list_entry(n, node_t, list)->value` 找到 n 的值
`JJJJ` : pivot
`KKKK` : right
`GGGG` : list->prev = result
## 第二周測驗題
### 測驗 `1`
使用快速排序，並且保持 stable sorting
先找到 Pivot
* 透過 `list_first_entry` 取得 head 中的第一個元素當作 pivot。
將節點依次分配到 list_less 和 list_greater
* `list_less` 儲存小於 Pivot 的元素
* `list_greater` 儲存大於或等於 Pivot 的元素
* 使用 `list_move_tail` 來確認排序是 stable
遞迴處理 `list_less` 和 `list_greater`
* 透過 `list_quicksort` 遞迴對 `list_less` 和 `list_greater` 進行排序。
合併結果回 head
* 先把 pivot 插入 head `list_add_tail`
* 再將 `list_less`、`list_greater` 依序合併回 head `list_splice_tail`
`AAAA` : `list_first_entry` ，取得 head 第一個元素作為 pivot。
`BBBB` : `list_del` ，將 pivot 從 head 移除，避免影響 `list_for_each_entry_safe` 。
`CCCC` : `list_move_tail`，確保排序 stable，若 item >= pivot，則將 item 維持原順序放入 `list_greater`。
`DDDD` : `list_add_tail`，把 pivot 放回 head。
`EEEE` : `list_splice_tail`，合併 list_less 到 head，維持順序。
`FFFF` : `list_splice_tail`，合併 list_greater 到 head，維持順序。
`list_move_tail` 會保留原來的相對順序：相同數值的節點不會被重新排序，而是維持它們原始的先後順序。
若改成`list_move` 順序被改變
`list_move(&item->list, &list_less)` 會將 item 插入 `list_less` 的頭部，導致原來的相對順序被顛倒。
`list_move(&item->list, &list_greater)` 會將 item 插入 `list_greater` 的頭部，同樣導致順序改變。
變成 unstable
e.g. [3, 2, 2*, 3*]
使用 `list_move_tail`： 2, 2*, 3, 3* (stable)
使用 `list_move`： 2*, 2, 3*, 3 (unstable)
### 測驗 `2`
透過位元運算來實作快速的開平方根運算
clz2 (count leading zeros)：計算數值 x 的前導 0 個數 (clz)，並藉由遞迴加速。每次遞迴將 x 切成高低兩半：
upper = (x >> (16 >> c)) 取得 x 的高位部分
lower = (x & (0xFFFF >> mask[c])) 取得 x 的低位部分
如果 upper 不為 0，則繼續對 upper 遞迴計算
如果 upper 為 0，就對 lower recursive，並加上相應的位數補償
當 c == 3（剩 2 位元）時，直接查表 (magic) 來獲取 clz 值
這樣可以透過少量遞迴快速計算 clz(x)，比逐位數檢查快很多。
clz64 (64-bit clz)：擴展 clz32 以支援 64 位元運算。
sqrti (integer square root)：透過二進位搜尋法計算 sqrt(x)。
`GGGG` : 14，決定 mask 的位移量，用於 mask 陣列，使 lower 取得 4-bit mask。
`HHHH` : 2，magic 陣列的第一個元素，用來在 base case 直接回傳 clz 值。
`IIII` : 3，magic 陣列的最後一個索引。
`JJJJ` : 3，進入 magic 陣列查表的條件，當 c == 3 時表示只剩 2 位元需要處理，可直接查 magic。
`KKKK` : 2，計算 lower 時的 offset，lower 位移調整。
`LLLL` : 1，當 upper == 0 時，clz2 需要對 lower 遞迴並調整 bit-shift，控制 clz2 遞迴深度。
`MMMM` : -2，確保 shift 為偶數，使 m 為 4 的次方。
`NNNN` : 1，y >>= 1，確保二進位運算正確，讓 y 每次右移 1 位。
`PPPP` : 2，m >>= 2，讓 m 每次右移 2 位 (除 4)
目前的 `sqrti(x)` 計算的是 floor(√x)，如果 x 不是完全平方數，則 ⌈√x⌉ = floor(√x) + 1。
我們可以判斷 y * y < x 來決定是否要加 1
若 y * y < x，則 y 必須加 1
使用 x >= y * (y + 1) 來避免乘法
當 y * y < x 時，x 可能為y * y ~ (y+1) * (y+1) 之間
若 x >= y * (y + 1)，表示 ⌈√x⌉ = y + 1
這樣可以 避免直接計算 y * y （因為 y * (y + 1) 可透過 bit-shift 快速計算）
```clike
uint64_t sqrti_ceil(uint64_t x)
{
uint64_t m, y = 0;
if (x <= 1)
return x;
int total_bits = 64;
int shift = (total_bits - 1 - clz64(x)) & -2;
m = 1ULL << shift;
while (m) {
uint64_t b = y + m;
y >>= 1;
if (x >= b) {
x -= b;
y += m;
}
m >>= 2;
}
if (x > 0 && x >= y * (y + 1))
y++;
return y;
}
```
### 測驗 `3`
TwoSum 運作流程
建立 hash table (map_t)
遍歷 nums 陣列，對於每個 nums[i]：
* 檢查 target - nums[i] 是否已經存在於 map
* 若找到匹配值，返回索引
* 若找不到，將 nums[i] 及其索引加入 map
free hash table
return
Time complexity : O(n)
`map_get()` : 根據 key 計算 hash value，查找對應的 hlist_head 鏈結。遍歷桶內鏈結串列：若 kn->key == key，return kn->data。若找不到，return NULL。
`map_add()`：插入 Key，避免重複插入 key（若已存在則直接 return）。
插入時，維護 hlist_node 雙向鏈結：
* 插入 first 之前
* 更新 first->pprev
* 更新 h->first
`AAAA` : map->bits ，hash() 需要 bits 來決定 hash table 的大小
`BBBB` : map->bits ，hash() 需要 bits 來尋找 bucket
`CCCC` : first->pprev ， 將 n->next->pprev 指向 n，維護 hlist 雙向鏈結
`DDDD` : n->pprev ， 將 h->first 的前驅指標設為 n->pprev，確保 hlist 正確運作
`EEEE` : &p->pprev， 在 map_deinit 中找到 pprev，並將其指向 next，確保刪除元素時不會破壞鏈結
確保 hash() 的 bits 正確計算
* hash(key, map->bits) 保持一致。
維護 hlist 雙向鏈結
* CCCC = first->pprev，確保 next 指向 n 時，first->pprev 也正確更新。
* DDDD = n->pprev，確保 h->first 被插入 n 後，n->pprev 設為 h->first。
* EEEE = &p->pprev，確保 pprev 連結正確，防止 NULL 存取錯誤。
確保 map_deinit() 正確釋放記憶體
* if (!n->pprev) goto bail; 確保未連結的節點被跳過。
* bail: 確保 kn->data 及 kn 被正確釋放。
Sign in with Wallet
Connect another wallet