---
# System prepended metadata

title: 2022q1 Homework1 (quiz1)

---

# 2022q1 Homework1 (quiz1)
contributed by < [rickywu0421](https://github.com/rickywu0421) >

## 第一題 [LeetCode 1. Two Sum](https://leetcode.com/problems/two-sum/)

### Linux style hash table
```c
struct hlist_node {
    struct hlist_node *next;
    struct hlist_node **pprev;
};

struct hlist_head {
    struct hlist_node *first;
};
```
本題使用到 linux kernel 中 [include/linux/types.h](https://github.com/torvalds/linux/blob/master/include/linux/types.h) 內定義的  `hlist_node` 與 `hlist_head` 結構體。

`hlist_head` 為了節省 hash table 的空間之開銷,只包含一個成員 `first`, 指向第一個 `hlist_node`, `hlist_node` 則為雙向的 linked list, 其特別之處為： 不若另一個表示 linkd list 的結構體 `list_head` 的 `prev` 成員為指標, 其指向前一個 node 的成員 (精準的來說是指向前一個成員的 next field 的記憶體位址) 為指標的指標 `pprev`, 其目的在進行 delete 操作時不需要考慮前一個節點是否為 head。

以下為示意圖：

![](https://i.imgur.com/QYQLqvC.png)

以下 function 部分已由 [include/linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 中定義的操作改寫。
### map_init
根據 `bits` , 建立含有 $2^{bits}$ 個成員的 hash table。
```c
map_t *map_init(int bits)
{
    map_t *map = (map_t *) malloc(sizeof(map_t));
    if (!map)
        return NULL;

    map->bits = bits;
    map->ht = (struct hlist_head *) 
        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;
}
```
### find_key
首先, 透過 `hash()` 得到 `key` 對應的 hash value, 再從 hash table 中得到對應的 `hlist_head`, 接著走訪此 hlist, 找尋是否有值為 key 的 node。
```c
static struct hash_key *find_key(map_t *map, int key)
{
    struct hlist_head *h = &(map->ht)[hash(key, map->bits)];
    struct hash_key *kn;

    hlist_for_each_entry (kn, h, node) {
        if (kn->key == key)
            return kn;
    }

    return NULL;
}
```

### map_get
呼叫 `find_key()`, 若得到的回傳值不為 `NULL`, 則 return index 值。
```c
void *map_get(map_t *map, int key)
{
    struct hash_key *kn = find_key(map, key);
    return kn ? kn->data : NULL;
}
```
### map_add
新增一個 hash_key, 並根據 `key` 值將此 hash_key 的 list insert 到對應的 hash table 的 head。
```c
void map_add(map_t *map, int key, void *data)
{
    struct hash_key *kn = find_key(map, key);
    if (kn)
        return;

    kn = (struct hash_key *) 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;

    hlist_add_head(n, h);
}
```
### map_deinit
Deallocate hash_table。
```c
void map_deinit(map_t *map)
{
    if (!map)
        return;

    for (int i = 0; i < MAP_HASH_SIZE; i++) {
        struct hlist_head *h = &map->ht[i];
        struct hlist_node *n, *next;
        struct hash_key *kn, *safe;
        
        hlist_for_each_entry_safe (kn, safe, h, node) {
            free(kn->data);
            free(kn);
        }
    }

    free(map);
}
```

### two_sum
主要邏輯之處理。

根據 `nums[i]`, 找到對應的 `value = target - nums[i]`, 並從 hash table 中尋找是否有 `key == value` 的 node, 若有, 則呼叫 `map_get()` 得到該 key 的 index 值並 return; 否則透過 `map_add()` 將 `nums[i]` 與對應的 index `i` 加入到 hash table 中。
```c
int *two_sum(int *nums, int numsSize, int target, int *returnSize)
{
    map_t *map = map_init(10);
    *returnSize = 0;
    int *ret = (int *) 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) {
            *returnSize = 2;
            ret[0] = i;
            ret[1] = *p;
            break;
        }

        p = (int *) malloc(sizeof(int));
        *p = i;
        map_add(map, nums[i], p);
    }

bail:
    map_deinit(map);
    return ret;
}
```

## 第二題 [LeetCode 82. Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)

這題的目標是把 list 中擁有相同 val 的 node 從 list 中拿掉, 要注意的是首個 val 相同的 node 也必須拿掉, 示意圖如下：

![](https://i.imgur.com/5FIwrOX.png)

### 遞迴呼叫版
題目中第一個 `if` 為判斷節點是否為 NULL, 其作為遞迴呼叫時的終止條件之一。

第二個 `if` 則為判斷此節點與下一個節點的 `val` 是否相同, 若是, 則進入 `while` 迴圈 (這邊我覺得程式可以將 `if` 拿掉, 效果一樣且程式碼更為精簡), 逐次進行相同判斷, 直到條件為否時 即到達重複 `val` 之連續節點的最後一個 node, 傳入 `head->next` 進行遞迴呼叫。

若第二個 `if` 判斷為否, 則設定 `head->next` 為遞迴呼叫的回傳值, 並回傳 `head`。 
```c
#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;
}
```
### 迭代 + linux kernel style 版 
使用 `list_for_each_entry()` 走訪整個 linked list, 比較 `prev_value` 是否等於 `pos->value`, 若是, 則表示此 Node 為 duplicate node, 此時呼叫 `list_del()` 將該 Node 的 list unlink。除此之外, 因為第一個重複的 Node 也要被 unlink, 因此需要記錄其為 `start`, 並在造訪下一種 value 的節點或造訪到 head 時 unlink `start`。

此函式存在重複之程式碼, 還需要再想辦法精簡之。
```c
#include <stdbool.h>

bool q_delete_dup(struct list_head *head)
{
    element_t *pos, *start = NULL;
    char *prev_value = "";

    if (!head)
        return false;

    list_for_each_entry (pos, head, list) {
        if (!strcmp(pos->value, prev_value)) {
            /* Record the start queue element of the duplicate set,
               which will be delete later */
            if (!start)
                start = list_entry(pos->list.prev, element_t, list);

            list_del(&pos->list);
        } else {
            prev_value = pos->value;

            /* Defered deletion of the start of the duplicate set */
            if (start) {
                list_del(&start->list);
                start = NULL;
            }
        }
    }

    /* Defered deletion of the start of the duplicate set */
    if (start)
        list_del(&start->list);

    return true;
}
```

## 第三題 [LeetCode 146. LRU Cache](https://leetcode.com/problems/lru-cache/)
本題需實作資料結構, 使其能夠表現一個 LRU cache。所有的資料在 cache 中以 <key, value> pair 呈現, 以下以 "data" 作為 <key, value> pair 之簡稱。
### 結構體定義
#### LRUCache
```c
typedef struct {
    int capacity, count;
    struct list_head dhead, hheads[];
} LRUCache;
```
`LRUCache` 為 cache 之表示, 除了記錄 cache 容量與 
目前的資料數, 還包含使其成為 curcular doubly-linked list 的 `list_head` 結構體: `dhead` 與 `hheads`。

`dhead` maintain 了一個 LRU cache, 在 list 的成員從頭到尾依序表示新到舊的 data。

`hheads` 則作為一個 hash table , 優點是使 list 的搜尋效率增加, 缺點是 list node 在插入時增加了插入到 hash table 的成本。此成員亦為一個 zero-length array: `hheads`, 其存在使得此結構體成為 variable-length object。需注意的是此用法為 GNU C 的 extension, 參考資料: [Zero-Length](https://gcc.gnu.org/onlinedocs/gcc/Zero-Length.html)。

#### LRUNode
```c
typedef struct {
    int key, value;
    struct list_head dlink, hlink;
} LRUNode;
```
LRUNode 則為 list 中代表 data 的結構體, 其中 `dlink` 連接到 `LRUCache->dhead` 作為頭的 list, `hlink` 連接到 `hheads[hash]` 作為頭的 list (`hash` 由 `key` 值決定, 透過 hash function 產生, 本題使用最 naive 的手法, 即 `hash = key % capacity`, 此手法可能沒辦法有效的避免碰撞)

以下示意圖為 `capacity` 為 `100` 的情況下, 依序新增 `100`, `0`, `50` 三個節點時 dlink 與 hlink 的鏈結情況：

**dlink:**
![](https://i.imgur.com/d5oUqpk.png)


**hlink:**
![](https://i.imgur.com/OZ8N88v.png)

### lRUCacheCreate
配置 `LRUCache` 的記憶體空間, 要注意的是不能只是 `malloc(sizeof(LRUCache)`, 因為這樣沒有配置到最後一個成員 `hheads` (zero-lengh array), 要再加上 `sizeof(struct list_head) * capacity` 的長度。

最後透過 `INIT_LIST_HEAD()` 將 dlink, hlink 分別指向自身。
```c
LRUCache *lRUCacheCreate(int capacity)
{
    LRUCache *obj = (LRUCache *) 
        malloc(sizeof(LRUCache) + sizeof(struct list_head) * capacity);
    obj->count = 0;
    obj->capacity = capacity;
    INIT_LIST_HEAD(&obj->dhead);
    for (int i = 0; i < capacity; i++)
        INIT_LIST_HEAD(&obj->hheads[i]);
    return obj;
}
```
### lRUCacheFree
透過 `list_for_each_entry_safe()` 走訪 dlink, unlink 節點並 `free()` `LRUNode`。
```c
void lRUCacheFree(LRUCache *obj)
{
    LRUNode *lru, *n;
    list_for_each_entry_safe (lru, n, &obj->dhead, dlink) {
        list_del(lru);
        free(lru);
    }
    free(obj);
}
```
### lRUCacheGet
首先算出 key 的 hash 值, 再從對應 hash 值的 hlink 找尋是否存在 key 值, 若是, 則因為此節點是 least recently used 的節點, 需先將此節點透過 `list_move()` 移動到 dlink 的頭, 再回傳此節點的 value 值。
```c
int lRUCacheGet(LRUCache *obj, int key)
{
    LRUNode *lru;
    int hash = key % obj->capacity;
    list_for_each_entry (lru, &obj->hheads[hash], hlink) {
        if (lru->key == key) {
            list_move(&lru->dlink, &obj->deads);
            return lru->value;
        }
    }
    return -1;
}
```
### lRUCachePut
首先算出 key 的 hash 值, 再從對應 hash 值的 hlink 找尋是否已經存在 key 值, 若是, 則因為此節點是 least recently used 的節點, 需先將此節點透過 `list_move()` 移動到 dlink 的頭, 更新此節點的 value 並 return; 

若否, 則表示 link 中尚未存在 key 值的節點, 此時需先檢查 `cache->count` 是否已達到 `cache->capacity`, 若是, 則需要 remove 最久沒被用到的節點, 即 dlink 的最末端, 透過 `list_last_entry()` 可以得到 dlink 最末端的節點的 `LRUNode`, 替換其 `key` 與 `value`, 並將其插入至 dlink 的頭; 

若否, 則需 `malloc()` 一個 `LRUNode`, 並填入 `key` 與 `value`, 再將其插入至 dlink 的頭。 
```c
void lRUCachePut(LRUCache *obj, int key, int value)
{
    LRUNode *lru;
    int hash = key % obj->capacity;
    list_for_each_entry (lru, &obj->hheads[hash], hlink) {
        if (lru->key == key) {
            list_move(&lru->dlink, &obj->dhead);
            lru->value = value;
            return;
        }
    }

    if (obj->count == obj->capacity) {
        lru = list_last_entry(&obj->dhead, LRUNode, dlink);
        list_del(&lru->dlink);
        list_del(&lru->hlink);
    } else {
        lru = (LRUNode *) malloc(sizeof(LRUNode));
        obj->count++;
    }

    lru->key = key;
    lru->value = value;
    list_add(&lru->dlink, &obj->dhead);
    list_add(&lru->hlink, &obj->hheads[hash]);
}
```