# 2024q1 Homework2 (quiz1+2)
contributed by < [tintinjian12999](https://github.com/tintinjian12999) >
## 第 1 週測驗題
[2024q1 第 1 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz1)
### 測驗 `1`
#### 解釋程式碼運行
在
```c
void quick_sort(node_t **list)
```
中會將比 `pivot` 大的數存入 right 中，比 `pivot` 小或相等的數則存入 left 中
```c
while (p) {
node_t *n = p;
p = n->next;
list_add(n->value > value ? &right : &left, n);
}
```
而 begin 與 end 則用
```c
//left, pivot, right
begin[i], begin[i + 1], begin[i + 2]
end[i], end[i + 1], end[i + 2]
```
來儲存 left, pivot, right 節點的開頭與結尾
```c
begin[i] = left;
end[i] = list_tail(left);
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = right;
end[i + 2] = list_tail(right);
```
程式的執行過程如下
假設需排序的序列如下
```graphviz
digraph structs {
node[shape=plaintext];
node[shape=box];
struct0 [label= "4"];
struct1 [label= "1"];
struct2 [label= "3"];
struct3 [label= "5"];
struct4 [label= "2"];
struct5 [label= "7"];
{
rank="same";
struct0 -> struct1
struct1 -> struct2
struct2 -> struct3
struct3 -> struct4
struct4 -> struct5
}
}
```
則迭代過程為
```graphviz
digraph structs {
node[shape=plaintext];
iter [label = "i = 0\l"];
pivot
left
right
node[shape=box];
struct0 [label= "4"];
struct1 [label= "1"];
struct2 [label= "3"];
struct3 [label= "5"];
struct4 [label= "2"];
struct5 [label= "7"];
{
rank="same";
pivot -> struct0
}
{
rank="same";
left -> struct4 -> struct2 -> struct1
}
{
rank="same";
right -> struct3 -> struct5
}
}
```
```graphviz
digraph structs {
node[shape=plaintext];
iter [label = "i = 2\l"];
pivot
left
right
node[shape=box];
struct3 [label= "5"];
struct5 [label= "7"];
NULL [label = "NULL"];
{
rank="same";
pivot -> struct3
}
{
rank="same";
left -> NULL
}
{
rank="same";
right -> struct5
}
}
```
```graphviz
digraph structs {
node[shape=plaintext];
iter [label = "i = 4\l"];
result [fontcolor="blue"];
node[shape=box];
struct5 [label= "7"] [fontcolor="blue"];
{
rank="same";
result -> struct5
}
}
```
```graphviz
digraph structs {
node[shape=plaintext];
iter [label = "i = 3\l"];
result [fontcolor="blue"];
node[shape=box];
struct3 [label= "5"][fontcolor="blue"];
struct5 [label= "7"][fontcolor="blue"];
{
rank="same";
result -> struct3 -> struct5
}
}
```
```graphviz
digraph structs {
node[shape=plaintext];
iter [label = "i = 2\l"];
LNULL [label="L = NULL"];
i [label="i--"][fontcolor = "red"];
{
rank="same";
LNULL -> i
}
}
```
```graphviz
digraph structs {
node[shape=plaintext];
iter [label = "i = 1\l"];
result [fontcolor="blue"];
node[shape=box];
struct3 [label= "5"][fontcolor="blue"];
struct4 [label= "4"][fontcolor="blue"];
struct5 [label= "7"][fontcolor="blue"];
{
rank="same";
result -> struct4 -> struct3 -> struct5
}
}
```
```graphviz
digraph structs {
node[shape=plaintext];
iter [label = "i = 0\l"];
pivot
left
right
node[shape=box];
struct1 [label= "1"];
struct2 [label= "3"];
struct4 [label= "2"];
{
rank="same";
pivot -> struct4
}
{
rank="same";
left -> struct1
}
{
rank="same";
right -> struct2
}
}
```
```graphviz
digraph structs {
node[shape=plaintext];
iter [label = "i = 2\l"];
result [fontcolor="blue"];
node[shape=box];
struct2 [label= "3"][fontcolor="blue"];
struct3 [label= "5"][fontcolor="blue"];
struct4 [label= "4"][fontcolor="blue"];
struct5 [label= "7"][fontcolor="blue"];
{
rank="same";
result -> struct2 -> struct4 -> struct3 -> struct5
}
}
```
```graphviz
digraph structs {
node[shape=plaintext];
iter [label = "i = 1\l"];
result [fontcolor="blue"];
node[shape=box];
struct1 [label= "2"][fontcolor="blue"];
struct2 [label= "3"][fontcolor="blue"];
struct3 [label= "5"][fontcolor="blue"];
struct4 [label= "4"][fontcolor="blue"];
struct5 [label= "7"][fontcolor="blue"];
{
rank="same";
result -> struct1 -> struct2 -> struct4 -> struct3 -> struct5
}
}
```
```graphviz
digraph structs {
node[shape=plaintext];
iter [label = "i = 0\l"];
result [fontcolor="blue"];
node[shape=box];
struct0 [label= "1"][fontcolor="blue"];
struct1 [label= "2"][fontcolor="blue"];
struct2 [label= "3"][fontcolor="blue"];
struct3 [label= "5"][fontcolor="blue"];
struct4 [label= "4"][fontcolor="blue"];
struct5 [label= "7"][fontcolor="blue"];
{
rank="same";
result -> struct0 -> struct1 -> struct2 -> struct4 -> struct3 -> struct5
}
}
```
#### 使用 Linux 核心風格的 List API 改寫上述程式碼
### 測驗 `2`
## 第 2 週測驗題
[2024q1 第 2 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz2)
### 測驗 `1`
這裡最重要的實作是使用 hash table 來實現在 inorder 裡尋找對應元素的過程。
在 `find` 裡有以下實作
```c
int hash = (num < 0 ? -num : num) % size;
hlist_for_each (p, &heads[hash]) {
struct order_node *on = container_of(p, struct order_node, node);
if (num == on->val)
return on->idx;
}
```
透過 `hlist_for_each` 走訪 hash table 上的 linked list，如此比起直接走訪整個 inorder 的元素來得更有效率。
接著 `dfs` 透過遞迴的方式將左節點與右節點依序接上，如下圖所示
```graphviz
digraph BST {
node [];
root1 [ label = "3" ];
left1 [ label = "9" ];
right1 [ label = "20,15,7" ];
root1 -> { left1 right1 };
l3 [ label = "3" ];
l4 [ label = "9" ];
l5 [ label = "20" ];
l6 [ label = "7" ];
l7 [ label = "15" ];
l3 -> { l4 l5 };
l5->{ l6 l7};
}
```
### 測驗 `2`
### 測驗 `3`
Sign in with Wallet
Connect another wallet