---
# System prepended metadata

title: 2022q1 Homework1 (quiz1)

---

# 2022q1 Homework1 (quiz1)
contributed by < `Korin777` >

## Q1
### 延伸題目一
#### 函式功能:
1. map_init
用來建立 hash table `map_t` 的各個 `hlist_head` , `ht` 的數量為2的冪
```graphviz
digraph structs {
rankdir=LR
	node[shape=record]
	e1 [label=" <first> ht[0].first| <second> ht[1].first | <third> ht[2].first | <forth> ht[3].first"];
    
    node[shape=none];
    null_1[label = NULL]

    e1:first->null_1
    e1:second->null_1
    e1:third->null_1
    e1:forth->null_1
}
```
2. find_key
查詢 key 存在與否 , 透過 `hash function` 及 `key` 得到特定 `ht[i]` 並遍歷 `ht[i]` 找尋是否存在 `key` , 有的話回傳此 `hash_key` 指標 , 沒有則回傳 NULL
3. map_get
查詢 `key` 的 `data` , 透過 find_key 是否回傳 `hash_key` 指標來決定回傳對應的 `data` 指標或 `NULL`
5. map_add
增加 `ht[i]` 的節點 , 節點會增加在 `ht[i].first` , 先透過 `find_key` 查詢 key 是否存在 , 不存在再增加節點
```graphviz
digraph structs {
    rankdir=LR
	node[shape=record];
	e1 [label="<p> ht[i].first "];
    node[shape=record];
	e2 [label=" <h>hlist_node | {<p> pprev | <n>next }"];
    node[shape=record];
	e3 [label=" <h>hlist_node | {<p> pprev | <n>next }"];   
    node[shape=none];
    NULL [label="NULL"];
    
    e1:p->e2:h;
    e2:p->e1;
    e2:n->e3:h;
    e3:p->e2:n;
    e3:n->NULL;

    subgraph cluster_0 {
        style=filled;
        color="green";
        label="new node";
        e2;
    }
}
```
6. map_deinit
釋放 hash table 所配置過的記憶體 , 每個 `ht[i]` 的各個節點依照由頭到尾的順序釋放 `hash_key->data` 及 `hash_key` , 最後再釋放整個 `map_t`
## Q2

### 延伸題目一
* `new_head` 為移除重複節點後的 head
* `prev_node` 用來修正上個非重複節點的下個節點
```c
struct ListNode *deleteDuplicates(struct ListNode *head)
{
    if (!head)
        return NULL;
    struct ListNode *new_head = NULL, *prev_node = NULL;
    while(head) {
        while (head->next && head->val == head->next->val) // skip duplicate node 
            head = head->next;
        if(prev_node) { // fix previous non-duplicate node's next
            if(prev_node->next != head)
                prev_node->next = head;
            else
                prev_node = head;
        }
        if(!new_head && head->next && head->val != head->next->val) { // Init new head 
            new_head = head;
            prev_node = new_head;
        }
        head = head->next;
    }
    if(prev_node) { // fix previous non-duplicate node's next
        if(prev_node->next != head)
            prev_node->next = head;
    }
    return new_head;
}
```
### 延伸題目二
* 將 ListNode 結構改為作業的 circular doubly-linked list 結構
```c
struct list_head {
    struct list_head *prev;
    struct list_head *next;
};
typedef struct {
    int value;
    struct list_head list;
} element_t;
```
#### 迭代
* `tmp` 為整數指標 , 用來表示當前的重複數字
* `tmp` 為 NULL 或 `tmp` 和當前 `entry` 的數字不同 , 就看下個 `entry` 的數字是否與當前 `entry` 數字相同 , 來判斷是否該移除當前 節點及釋放對應的記憶體
* `tmp` 和當前 `entry` 的數字相同 , 直接移除當前節點及釋放對應的記憶體
* 若 `tmp` 最後不為 NULL 要釋放 `tmp` 記憶體
```c
void deleteDuplicates(struct list_head *head)
{
    if (!head)
        return;
    int *tmp = NULL;
    element_t *ele, *tmpele;
    list_for_each_entry_safe (ele, tmpele, head, list) {
        if (!tmp || tmp != ele->value) {
            if (ele->list.next && ele->list.next != head) {
                element_t *elen = list_entry(ele->list.next, element_t, list);
                if (elen->value == ele->value) {
                    if (!tmp)
                        tmp = malloc(sizeof(int));
                    tmp = ele->value;
                    list_del(&ele->list);
                    free(ele->value), free(ele);
                }
            }
        } else {
            list_del(&ele->list);
            free(ele->value), free(ele);
        }
    }
    if (tmp)
        free(tmp);
    return;
}
```
#### 遞迴
* `realhead` 傳進 circular doubly-linked list 的 head（不作為 `entry` 存放 `value` 的節點）, 用來判斷 list 是否以遍歷完
*  如果 `head` 與它之後的節點 `value` 重複則移除這段節點 , 並對下個非重複節點呼叫 `deleteDuplicates`
```c
void deleteDuplicates(struct list_head *head, struct list_head *realhead)
{
    if (!realhead || list_empty(realhead) || list_is_singular(realhead))
        return;
    element_t *ele, *elen;
    if(head != realhead && head->next != realhead) {
        ele = list_entry(head, element_t, list);
        elen = list_entry(head->next, element_t, list);
        if (ele->value == elen->value) {
            /* Remove all duplicate numbers */
            while (ele->value == elen->value) {
                head = head->next;
                list_del(&ele->list);
                free(ele->value), free(ele);
                if(head->next == realhead) { // finish list traversal
                    list_del(&elen->list);
                    free(elen->value), free(elen);
                    return;
                }
                ele = list_entry(head, element_t, list);
                elen = list_entry(head->next, element_t, list);
            }
            list_del(&ele->list);
            free(ele->value), free(ele);
            return deleteDuplicates(head->next, realhead);
        }
    }
    else // finish list traversal
        return;
    return deleteDuplicates(head->next, realhead);
}
```
## Q3
#### 資料結構
* LRUCache 結構如下 , `capacity=5` 為 `hheads` 數量及總共能存的 `LRUNode` 數量 , `count=5` 為目前 `LRUNode` 數量 , 能透過 `dhead` 或 `hheads[i]` 來取得 `LRUNode`
```graphviz
digraph structs {
    rankdir=LR
	node[shape=record]
	h1 [label=" <d>dhead  |<h0> hheads[0]| <h1> hheads[1] | <h2> hheads[2] | <h3> hheads[3] | <h4> hheads[4]"];
    node[shape=record];
	e1 [label="{key | value } |<h>hlink1 | {<p> prev | <n>next } | <d>dlink1 | {<p1> prev | <n2>next }"];
    node[shape=record];
	e2 [label="{key | value } |<h>hlink2 | {<p> prev | <n>next }  | <d>dlink2 | {<p1> prev | <n2>next }"];
    node[shape=record];
	e3 [label="{key | value } |<h>hlink1 | {<p> prev | <n>next }  | <d>dlink3 | {<p1> prev | <n2>next }"];
    node[shape=record];
	e4 [label="{key | value } |<h>hlink1 | {<p> prev | <n>next }  | <d>dlink4 | {<p1> prev | <n2>next }"];
    node[shape=record];
	e5 [label="{key | value } |<h>hlink2 | {<p> prev | <n>next }  | <d>dlink5 | {<p1> prev | <n2>next }"];

    h1:h0->e1:h
    e1:n->e2:h
    h1:h1->e3:h
    h1:h2->e4:h
    e4:n->e5:h
    h1:d->e1:d
    e1:n2->e2:d
    e2:n2->e3:d
    e3:n2->e4:d
    e4:n2->e5:d
}
```
* 透過 `hheads[i]` , 只能拿到屬於這個區塊的 `LRUNode`
```graphviz
digraph structs {
    rankdir=LR
	node[shape=record];
	e1 [label="<h> hheads[i] | {<p> prev | <n>next }"];
    node[shape=record];
	e2 [label="<h>hlink1 | {<p> prev | <n>next }"];
    node[shape=record];
	e3 [label="<h>hlink2 | {<p> prev | <n>next }"];
    node[shape=record];
    
    e1:n->e2:h;
    e2:p->e1:h;
    e2:n->e3:h;
    e3:p->e2:h;
    e3:n->hheads;
    e1:p->hlink2

    subgraph cluster_0 {
        style=filled;
        color="green";
        label="LRUNode";
        e2;
    }
    subgraph cluster_1 {
        style=filled;
        color="yellow";
        label="LRUCache";
        e1;
    }
    subgraph cluster_3 {
        style=filled;
        color="green";
        label="LRUNode";
        e3;
    }
}
```
* 透過 `dhead` 可以遍歷所有的 `LRUNode` , `LRUNode` 越後面表示越久沒用到
```graphviz
digraph structs {
    rankdir=LR
	node[shape=record];
	e1 [label="<d> dhead | {<p> prev | <n>next }"];
    node[shape=record];
	e2 [label="<h>dlink1 | {<p> prev | <n>next }"];
    node[shape=record];
	e3 [label="<h>dlink2 | {<p> prev | <n>next }"];
    node[shape=record];
    
    e1:p->dlink2
    e1:n->e2:h;
    e2:p->e1:d;
    e2:n->e3:h;
    e3:p->e2:h;
    e3:n->dhead
    
    

    subgraph cluster_0 {
        style=filled;
        color="green";
        label="LRUNode";
        e2;
    }
    subgraph cluster_1 {
        style=filled;
        color="yellow";
        label="LRUCache";
        e1;
    }
    subgraph cluster_3 {
        style=filled;
        color="green";
        label="LRUNode";
        e3;
    }
}

```
#### 函式功能
1. lRUCacheCreate
用來建立 `LRUCache` 及其中的 `hheads[]`
2. lRUCacheFree
用來釋放 `LRUCache` 及其所擁有的 `LRUNode`
3. lRUCacheGet
透過 `key` 來取得 `LRUCache` 對應的 `LRUNode->value` , 如果不存在則回傳 -1
4. lRUCachePut
* 新增或修改 `LRUNode` 
* 如果 `key` 存在會修改 `LRUNode->value` , 並將此 `LRUNode->dlink` 移到 `LRUCache->dhead` 最前面 , 表示最近用到
* 如果 `key` 不存在則會看 `LRUCache->count` 是否已達到 `LRUCache->capacity` , 是的話就移除 `LRUCache->dlink` 最後一個 `LRUNode(最久沒用到)` , 並新增新的 `key-value` 到該 `LRUNode` 並加到 `LRUCache->dlink` 及對應的 `LRUCache->hheads[]` , 反之則會配置一個新的 `LRUNode` 空間

## Q4
### 延伸問題一
#### 資料結構
題目結構如下 , `nums = [100,4,200,1,3,2]` 、 `n_size=6` , `heads` 數量即為 `n_size` 數 , 每個 `num` 對 `n_size` 取餘數放到對應的 `heads[num < 0 ? -num % size : num % size]`
```graphviz
digraph structs {
    rankdir=LR
	node[shape=record]
	h1 [label="<h0> heads[0]| <h1> heads[1] | <h2> heads[2] | <h3> heads[3] | <h4> heads[4] | <h5> heads[5]"];
	e1 [label="<num>num=100 |<l>link | {<p> prev | <n>next }"];
	e2 [label="<num>num=4 |<l>link | {<p> prev | <n>next }"];
	e3 [label="<num>num=200 |<l>link | {<p> prev | <n>next }"];
	e4 [label="<num>num=1 |<l>link | {<p> prev | <n>next }"];
	e5 [label="<num>num=3 |<l>link | {<p> prev | <n>next }"];
    e6 [label="<num>num=2 |<l>link | {<p> prev | <n>next }"];

    h1:h0->e3:l
    e3:n->e1:l
    h1:h1->e4:l
    h1:h2->e6:l
    h1:h3->e5:l
    h1:h4->e2:l
}
```
`heads[i]` 後面連結屬與此區塊的 `seq_node`
```graphviz
digraph structs {
    rankdir=LR
	node[shape=record];
	e1 [label="<h> heads | {<p> prev | <n>next }"];
    node[shape=record];
	e2 [label="num=200 | <h>link1 | {<p> prev | <n>next }"];
    node[shape=record];
	e3 [label="num=100 | <h>link2 | {<p> prev | <n>next }"];
    node[shape=record];
    
    e1:n->e2:h;
    e2:p->e1:h;
    e2:n->e3:h;
    e3:p->e2:h;
    e3:n->heads;
    e1:p->link2

    subgraph cluster_0 {
        style=filled;
        color="green";
        label="seq_node";
        e2;
    }
    subgraph cluster_1 {
        style=filled;
        color="yellow";
        label="list_head";
        e1;
    }
    subgraph cluster_3 {
        style=filled;
        color="green";
        label="seq_node";
        e3;
    }
}
```
#### 函式功能
1. find
用來尋找 `num` 是否存在對應 `heads[i]` 中 , 有就回傳此 `seq_node` , 沒有則回傳 NULL
2. longestConsecutive
* 用來找出最長連續整數長度
* 首先配置長度 `n_size` 的 `heads` 並將 `nums` 的數字依序以 `seq_node` 的型態插入對應的 `heads[i]`
* 遍歷 `nums` 中的數字 `num` , 如果 `num` 存在於對應 `heads[i]` 中 , 則繼續尋找與 `num` 相連的所有數字
    * `left` 及 `right` 初始為 `num`  ,`left` 表示比 `num` 小的相鄰數字 , `right` 則表示比 `num` 大的相鄰數字
    * 持續將 `left` 減1並查詢其是否存在與對應 `heads[i]` , 存在的話將 `heads[i]` 中的 `left` 移除 , 反之則表示已經沒有比 `num` 小的相鄰數字 , 再來持續將 `right` 加1並查詢 `right` 是否存在與對應 `heads[i]` , 存在的話將 `heads[i]` 中的 `right` 移除 , 反之則表示已經沒有比 `num` 大的相鄰數字
    * 更新最長相鄰數字的長度
#### 改進與實作
在 `longestConsecutive` 新增釋放記憶體的 code 避免 memory leak
```c
int longestConsecutive(int *nums, int n_size)
{
    int hash, length = 0;
    struct seq_node *node;
    struct list_head *heads = malloc(n_size * sizeof(*heads));
    for (int i = 0; i < n_size; i++)
        INIT_LIST_HEAD(&heads[i]);
    for (int i = 0; i < n_size; i++) {
        if (!find(nums[i], n_size, heads)) {
            hash = nums[i] < 0 ? -nums[i] % n_size : nums[i] % n_size;
            node = malloc(sizeof(*node));
            node->num = nums[i];
            list_add(&node->link, &heads[hash]);
        }
    }
    for (int i = 0; i < n_size; i++) {
        int len = 0;
        int num;
        node = find(nums[i], n_size, heads);
        while (node) {
            len++;
            num = node->num;
            list_del(&node->link);
            free(node);

            int left = num, right = num;
            while ((node = find(--left, n_size, heads))) {
                len++;
                list_del(&node->link);
                free(node);
            }
            while ((node = find(++right, n_size, heads))) {
                len++;
                list_del(&node->link);
                free(node);
            }
            length = len > length ? len : length;
        }
    }
    struct seq_node *seq, *tmp;
    for (int i = 0; i < n_size; i++)
        list_for_each_entry_safe(seq,tmp,&heads[i],link)
            list_del(&seq->link), free(seq);
    free(heads);
    return length;
}
```
### 延伸問題二
參考 Q1 的 hash table 實作 , 結構改為如下
```c
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;
};
```
沿用 Q1 程式碼 , 並參考 [linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) `__hlist_del` 函式實作 `map_del` 用來移除 hash table 節點 `hlist_node`
```c
void map_del(struct hlist_node *n)
{
    struct hlist_node *next = n->next;
	struct hlist_node **pprev = n->pprev;
    *pprev = next;
    if(next)
        next->pprev = pprev;
}
```
修改 `longestConsecutive` , 以 `map_t` 來尋找最長連續整數長度
```c
int longestConsecutive(int *nums, int n_size)
{
    map_t *map = map_init(10);
    int length = 0;
    for (int i = 0; i < n_size; i++) {
        int *p = map_get(map,nums[i]);
        if(!p) {
            p = malloc(sizeof(int));
            *p = nums[i];
            map_add(map,nums[i],p);
        }
    }
    for (int i = 0; i < n_size; i++) {
        int len = 0;
        int *num;
        struct hash_key *hk = find_key(map, i);
        while (hk) {
            len++;
            num = hk->data;
            int left = *num, right = *num;
            map_del(&hk->node);
            free(hk->data);
            free(hk);
            while ((hk = find_key(map,--left))) {
                len++;
                map_del(&hk->node);
                free(hk->data);
                free(hk);
            }
            while ((hk = find_key(map,++right))) {
                len++;
                map_del(&hk->node);
                free(hk->data);
                free(hk);
            }
            length = len > length ? len : length;
        }
    }
    map_deinit(map);
    return length;
}
```
[題目連結](https://hackmd.io/@sysprog/linux2022-quiz1)