# 2022q1 Homework1 (quiz1)
contributed by < `Wallmountain` >
## Q1
Leetcode 題目 : [TwoSum](https://leetcode.com/problems/two-sum/)
### Structure
```cpp
struct hlist_node { struct hlist_node *next, **pprev; };
struct hlist_head { struct hlist_node *first; };
typedef struct { int bits; struct hlist_head *ht; } map_t;
struct hash_key {
int key;
void *data;
struct hlist_node node;
};
```
:::danger
`pprev` 的存在不是為了讓程式碼「更簡潔」，有其他更關鍵的作用。
:notes: jserv
:::
- ~~利用指標的指標實作 ```pprev```，讓程式碼更簡潔~~
- 在 hlist_head 中不需要指標指向前一個 node, 所以將hash table 的 structure 分成 ```hlist_node``` 和 ```hlist_head```, 若 ```hlist_node``` 中使用指標 ```struct hlist_node *prev``` , 則在刪除 node 時， 需要使用 branch 去判斷 ```prev``` 是否有指向前一個 node, 故選擇使用指標的指標消除 branch
- ```data``` 的 type 為 ```void *``` 能夠讓 hash table 去 fit 不同 type 的資料
### container_of
```cpp
#define container_of(ptr, type, member) \
({ \
void *__mptr = (void *) (ptr); \
((type *) (__mptr - offsetof(type, member))); \
})
```
- 使用 ```container_of``` 從指標取得 ```struct hash_key``` 的 ```data``` 和 ```key```
- ```offsetof``` 用來取得子物件在物件中的 offset (in bytes)
### map_init
```cpp
#define MAP_HASH_SIZE(bits) (1 << bits)
map_t *map_init(int bits) {
map_t *map = malloc(sizeof(map_t));
if (!map)
return NULL;
map->bits = bits;
map->ht = malloc(sizeof(struct hlist_head) * MAP_HASH_SIZE(map->bits));
if (map->ht) {
for (int i = 0; i < MAP_HASH_SIZE(map->bits); i++)
(map->ht)[i].first = NULL;
} else {
free(map);
map = NULL;
}
return map;
}
```
- hash table 大小 : 2^bit^
### map_deinit
```cpp
void map_deinit(map_t *map)
{
if (!map)
return;
for (int i = 0; i < MAP_HASH_SIZE(map->bits); i++) {
struct hlist_head *head = &map->ht[i];
for (struct hlist_node *p = head->first; p;) {
struct hash_key *kn = container_of(p, struct hash_key, node);
struct hlist_node *n = p;
p = p->next;
if (!n->pprev) /* unhashed */
goto bail;
struct hlist_node *next = n->next, **pprev = n->pprev;
*pprev = next;
if (next)
next->pprev = pprev;
n->next = NULL, n->pprev = NULL;
bail:
free(kn->data);
free(kn);
}
}
free(map);
}
```
- 走訪 map 中所有的 ```hlist_head``` 和 ```hlist_node```
- 每走訪到一個 node, 若 ```n->next``` 存在， 便將 ```n->next->pprev``` 指向 next node 本身
- 每走訪到一個 node, free 當前的節點
```graphviz
digraph {
rankdir = LR;
node [shape=record];
subgraph cluster {
first;
label = "heads[i]";
}
a [label="<body>hlist_node a|{<p>pprev|<n>next}"];
b [label="<body>hlist_node b|{<p>pprev|<n>next}"];
c [label="<body>hlist_node c|{<p>pprev|<n>next}"];
node [shape=none];
none [label=""];
edge [style="invis"];
first -> a -> b -> c;
edge [style=""];
first -> a:body;
a:n -> b:body;
b:n -> c:body;
c:n -> none;
edge [color="blue"];
a:p -> first;
b:p -> a:n;
c:p -> b:n;
}
```
```graphviz
digraph {
rankdir = LR;
node [shape=record];
subgraph cluster {
first;
label = "heads[i]";
}
a [label="<body>hlist_node a|{<p>pprev|<n>next}"];
b [label="<body>hlist_node b|{<p>pprev|<n>next}"];
c [label="<body>hlist_node c|{<p>pprev|<n>next}"];
node [shape=none];
none [label=""];
edge [style="invis"];
first -> a -> b -> c;
edge [style=""];
first -> a
a:n -> NULL
b:n -> c:body;
c:n -> none;
edge [color="blue"];
a:p -> NULL
b:p -> b:body;
c:p -> b:n;
}
```
```graphviz
digraph {
rankdir = LR;
node [shape=record];
subgraph cluster {
first;
label = "heads[i]";
}
b [label="<body>hlist_node b|{<p>pprev|<n>next}"];
c [label="<body>hlist_node c|{<p>pprev|<n>next}"];
node [shape=none];
none [label=""];
edge [style="invis"];
b -> c;
edge [style=""];
first -> NULL
b:n -> c:body;
c:n -> none;
edge [color="blue"];
b:p -> b:body;
c:p -> b:n;
}
```
### map_get
```cpp
#define GOLDEN_RATIO_32 0x61C88647
static inline unsigned int hash(unsigned int val, unsigned int bits) {
/* High bits are more random, so use them. */
return (val * GOLDEN_RATIO_32) >> (32 - bits);
}
static struct hash_key *find_key(map_t *map, int key) {
struct hlist_head *head = &(map->ht)[hash(key, map->bits)];
for (struct hlist_node *p = head->first; p; p = p->next) {
struct hash_key *kn = container_of(p, struct hash_key, node);
if (kn->key == key)
return kn;
}
return NULL;
}
void *map_get(map_t *map, int key)
{
struct hash_key *kn = find_key(map, key);
return kn ? kn->data : NULL;
}
```
- ```hash``` 為 hash function
### map_add
```cpp
void map_add(map_t *map, int key, void *data)
{
struct hash_key *kn = find_key(map, key);
if (kn)
return;
kn = malloc(sizeof(struct hash_key));
kn->key = key, kn->data = data;
struct hlist_head *h = &map->ht[hash(key, map->bits)];
struct hlist_node *n = &kn->node, *first = h->first;
AAA;
if (first)
first->pprev = &n->next;
h->first = n;
BBB;
}
```
- 若 data 不在 hash table 中, 則新增 node 加入 hash table
```cpp
struct hlist_head *h = &map->ht[hash(key, map->bits)];
struct hlist_node *n = &kn->node, *first = h->first;
AAA;
if (first)
first->pprev = &n->next;
h->first = n;
BBB;
```
- h 為data對應要存入的hash table bucket
- 當要在 hash table 中加入 node 時，因為只有指向頭的指標， 故這邊為 insert node into head
```graphviz
digraph {
rankdir = LR;
node [shape=record];
subgraph cluster {
first;
label = "heads[i]";
}
a [label="<body>hlist_node a|{<p>pprev|<n>next}"];
b [label="<body>hlist_node b|{<p>pprev|<n>next}"];
c [label="<body>hlist_node c|{<p>pprev|<n>next}"];
node [shape=none];
none [label=""];
edge [style="invis"];
first -> a -> b;
edge [style=""];
first -> c:body;
a:n -> b:body;
b:n -> none;
edge [color="blue"];
a:p -> c:n;
b:p -> a:n;
}
```
- 以上程式碼分別還少以下兩個操作
將 ```node->next``` 指向 ```head->next```
```graphviz
digraph {
rankdir = LR;
node [shape=record];
subgraph cluster {
first;
label = "heads[i]";
}
a [label="<body>hlist_node a|{<p>pprev|<n>next}"];
b [label="<body>hlist_node b|{<p>pprev|<n>next}"];
c [label="<body>hlist_node c|{<p>pprev|<n>next}"];
node [shape=none];
none [label=""];
edge [style="invis"];
first -> c -> a -> b;
edge [style=""];
first -> c:body;
a:n -> b:body;
b:n -> none;
c:n -> a:body;
edge [color="blue"];
a:p -> c:n;
b:p -> a:n;
}
```
將```node->pprev``` 指向 ```head->first```
```graphviz
digraph {
rankdir = LR;
node [shape=record];
subgraph cluster {
first;
label = "heads[i]";
}
a [label="<body>hlist_node a|{<p>pprev|<n>next}"];
b [label="<body>hlist_node b|{<p>pprev|<n>next}"];
c [label="<body>hlist_node c|{<p>pprev|<n>next}"];
node [shape=none];
none [label=""];
edge [style="invis"];
first -> c -> a -> b;
edge [style=""];
first -> c:body;
a:n -> b:body;
b:n -> none;
c:n -> a:body;
edge [color="blue"];
a:p -> c:n;
b:p -> a:n;
c:p -> first
}
```
- AAA = ```n->next = first```, BBB = ```n->pprev = &h->first```
### twoSum
```cpp
int *twoSum(int *nums, int numsSize, int target, int *returnSize)
{
map_t *map = map_init(10);
*returnSize = 0;
int *ret = malloc(sizeof(int) * 2);
if (!ret)
goto bail;
for (int i = 0; i < numsSize; i++) {
int *p = map_get(map, target - nums[i]);
if (p) { /* found */
ret[0] = i, ret[1] = *p;
*returnSize = 2;
break;
}
p = malloc(sizeof(int));
*p = i;
map_add(map, nums[i], p);
}
bail:
map_deinit(map);
return ret;
}
```
若 ```target - nums[i]``` 存在 map 中, 則代表找到解
```cpp
int *p = map_get(map, target - nums[i]);
if (p) { /* found */
ret[0] = i, ret[1] = *p;
*returnSize = 2;
break;
}
```
否則, 將 ```nums[i]``` 加入 map 中
```cpp
p = malloc(sizeof(int));
*p = i;
map_add(map, nums[i], p);
```
### 延伸題目 2
:::info
研讀 Linux 核心原始程式碼 include/linux/hashtable.h 及對應的文件 How does the kernel implements Hashtables?，解釋 hash table 的設計和實作手法，並留意到 tools/include/linux/hash.h 的 GOLDEN_RATIO_PRIME，探討其實作考量
:::
:::success
TODO : 持續更新
:::
## Q2
Leetcode 題目 : [Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)
- 原程式碼
```cpp
#include <stddef.h>
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode *deleteDuplicates(struct ListNode *head)
{
if (!head)
return NULL;
if (head->next && head->val == head->next->val) {
/* Remove all duplicate numbers */
while (head->next && head->val == head->next->val)
head = head->next;
return deleteDuplicates(head->next);
}
head->next = deleteDuplicates(head->next);
return head;
}
```
### 延伸問題 1
:::info
嘗試避免遞迴，寫出同樣作用的程式碼
:::
- 使用指標的指標, 讓 remove node 不需要 prev node, 也不需要在一開始判斷是否 ```head==NULL```,讓程式碼更簡潔
- 用外層的while 迴圈代替遞迴
```cpp
struct ListNode *deleteDuplicates(struct ListNode *head)
{
struct ListNode **node = &head;
while (*node) {
/* Remove all duplicate numbers */
if ((*node)->next && (*node)->val == (*node)->next->val) {
while((*node)->next && (*node)->val == (*node)->next->val) {
*node = (*node)->next;
}
*node = (*node)->next;
}
else
node = &((*node)->next);
}
return head;
}
```
> 思考如何寫出更精簡的程式碼，一樣是 indirect pointer 的應用
> :notes: jserv
### 延伸問題 2
:::info
以類似 Linux 核心的 circular doubly-linked list 改寫，撰寫遞迴和迭代 (iterative) 的程式碼
:::
#### 遞迴
```cpp
```
#### 迭代
```cpp
```
## Q3
Leetcode 題目 : [LRU Cache](https://leetcode.com/problems/lru-cache/)
Sign in with Wallet
Connect another wallet