# 2022q1 Quiz1
###### tags: `linux2022`
contributed by <[ganoliz](https://github.com/ganoliz)>

## 測驗1

LeetCode編號1的題目 **Two Sum**，題意是給定一個陣列 nums 和一個目標值 target，求找到 nums 的 2 個元素相加會等於 target 的索引值。題目確保必為單一解，且回傳索引的順序沒差異。例如給定輸入 nums = [2, 7, 11, 15], target = 9，相加變成 9 的元素僅有 2 及 7，因此回傳這二個元素的索引值 [0, 1]。
以下是引入 hash table 的實作，學習 Linux 核心程式碼風格:

#include <stddef.h>
#include <stdlib.h>

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;

#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;
}

struct hash_key {
    int key;
    void *data;
    struct hlist_node node;
};

#define container_of(ptr, type, member)               \
    ({                                                \
        void *__mptr = (void *) (ptr);                \
        ((type *) (__mptr - offsetof(type, member))); \
    })

#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;
}

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;
}

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);
}

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;
}

請補完程式碼。
AAA=?

* (a) /* no operation */
* (b) n->pprev = first
* (*c*) n->next = first
* (d) n->pprev = n

BBB=?
* (a) n->pprev = &h->first
* (b) n->next = h
* (*c*) n->next = n
* (d) n->next = h->first
* (e) n->next = &h->first

:::success
延伸題目:

1.解釋上述程式碼運作原理
2.研讀 Linux 核心原始程式碼 [include/linux/hashtable.h](https://github.com/torvalds/linux/blob/master/include/linux/hashtable.h) 及對應的文件 [How does the kernel implements Hashtables?](https://kernelnewbies.org/FAQ/Hashtables)，解釋 hash table 的設計和實作手法，並留意到 [tools/include/linux/hash.h](https://github.com/torvalds/linux/blob/master/tools/include/linux/hash.h) 的 GOLDEN_RATIO_PRIME，探討其實作考量
:::

### 解題思路
首先我們先看看第一段程式碼:

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;
}

明顯地，我們初始化一個 map ， map 的大小以二的次方為單位， 使用 bits 做 bitwise 的位移，把我們 hash table 的第一個 list_head 的 first 指標設為 NULL 。 若 malloc 不成功就做一些必要的例外處置。

#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);
}

至於上面這段程式碼可以看到函數名稱是在做 hash 的動作。這個 GOLDEN_RATIO_32 我猜是一個比較不會發生碰撞的優良 hash 數值。 註解有提到，由於運算中高位元的數字變化通常比較隨機，因此 hash 出來的結果會從高位元位移，來產生出更好的 hash 數值。

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;
}

這段是透過我們的先透過 hash function 運算找出在 hash table 的位置，透過其 head 分別對每個鏈結的 Node 走訪(為一個雙向鏈結串列，有 *next 與 **pprev )。當我們找到就回傳該 element ，若否則回傳 NULL 表示未找到。

void *map_get(map_t *map, int key)
{
    struct hash_key *kn = find_key(map, key);
    return kn ? kn->data : NULL;
}

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;
}

digraph Hash{

node[shape=record];

Map[label="{Hash Value |<1>1|<2>2|<3>3|<4>4|<5>5|<6>6}" ]

Key[label="{Key|{data|hlist_node node} }"]
Hnode[label="{<1>hlist_node |{**pprev |*next } }"]
Hhead[label="{<1>hlist_head |{<2>hlist_node *first} }"]

Map:5->Hhead:2 [label="Access"]
Hhead:1->Hnode [label="Node Structure"]

Hnode:1->Key [label="is Part of Key"]

}

第一個函數就是將剛剛 *find_key 找出來的 Node 往外回傳值。
第二個則是若這個 key 不存在 ，就新增此 key 到這個 hash table 位置的鏈結串列。

因此， AAA 應為 (*c*) n->next = first ，(因為等等要將 h->first 設為自己，所以 first 節點要變成串列的 Node )
而 BBB 應為 (a) n->pprev = &h->first (指向 first 的位置，目前為自己)。

## 測驗2
針對 LeetCode 82. Remove Duplicates from Sorted List II，以下是可能的合法 C 程式實作:

#include <stddef.h>

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode *deleteDuplicates(struct ListNode *head)
{
    if (!head)
        return NULL;

    if (COND1) {
        /* Remove all duplicate numbers */
        while (COND2)
            head = head->next;
        return deleteDuplicates(head->next);
    }

    head->next = deleteDuplicates(head->next);
    return head;
}

請補完程式碼，COND1=? COND2=?

:::success
延伸問題:

1.嘗試避免遞迴，寫出同樣作用的程式碼
2.以類似 Linux 核心的 circular doubly-linked list 改寫，撰寫遞迴和迭代 (iterative) 的程式碼
:::

### 解題思路
---

digraph test{



st[label="Start" shape=oval]
deletDuplicates1[label="deleteDuplicates(head)" shape=box ]
COND1[shape=diamond]
nxt[label="head->next" shape=box]
COND2[label="while(COND2) head=head->next" shape=box]

deletDuplicates2[label="deleteDuplicates(head->next)" shape=box ]

end[label="return head" shape=oval]

st->deletDuplicates1->COND1
COND1->nxt [label="No"]
COND1->COND2 [label="Yes"]

COND2->deletDuplicates1 [label="head=head->next"]
nxt->deletDuplicates1 [label="head=head->next"]

COND2->end [label="return"]
nxt->end [label="return"]
}

根據程式碼，我們可以知道假如 COND1 通過的話， head 就會往前移動，反之 COND1 沒有通過的話， head 就會保留，然後對下個節點做 deleteDuplicates 。
因此，我們可以推測透過 COND1 是對目前節點是否為重複節點的判斷，因此我們假設:

COND1=head->next != NULL && head->val == head->next->val

當此條件成立時，就會進入 while() 迴圈來越過數個重複 value 的 node ，因此我認為
COND2 跟 COND1 可以是一樣的：

COND2=head->next!=NULL && head->val == head->next->val

## 測驗3
針對 LeetCode 146. LRU Cache，以下是 Least Recently Used (LRU) 可能的合法 C 程式實作:

#include <stdio.h>
#include <stdlib.h>
#include "list.h"

typedef struct {
    int capacity, count;             
    struct list_head dhead, hheads[];
} LRUCache;
    
typedef struct {
    int key, value;
    struct list_head hlink, dlink;
} LRUNode;

LRUCache *lRUCacheCreate(int capacity)
{   
    LRUCache *obj = malloc(sizeof(*obj) + capacity * sizeof(struct list_head));
    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;
}
    
void lRUCacheFree(LRUCache *obj)
{       
    LRUNode *lru, *n;
    MMM1 (lru, n, &obj->dhead, dlink) {
        list_del(&lru->dlink);
        free(lru);
    }
    free(obj); 
}   

int lRUCacheGet(LRUCache *obj, int key)
{
    LRUNode *lru;
    int hash = key % obj->capacity;
    MMM2 (lru, &obj->hheads[hash], hlink) {
        if (lru->key == key) {
            list_move(&lru->dlink, &obj->dhead);
            return lru->value;
        }
    }
    return -1;
}

void lRUCachePut(LRUCache *obj, int key, int value)
{
    LRUNode *lru;
    int hash = key % obj->capacity;
    MMM3 (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 = MMM4(&obj->dhead, LRUNode, dlink);
        list_del(&lru->dlink);
        list_del(&lru->hlink);
    } else {
        lru = malloc(sizeof(LRUNode));
        obj->count++;
    }
    lru->key = key;
    list_add(&lru->dlink, &obj->dhead);
    list_add(&lru->hlink, &obj->hheads[hash]);
    lru->value = value;
}

請補完程式碼，注意作答規範:

* MMM1, MMM2, MMM3, MMM4 都是 Linux 核心風格的 list 巨集，以 list_ 開頭
* 不要出現空白
* 儘量寫出最精簡的程式碼，而且答案也只接受符合上述程式碼排版風格的最精簡形式

:::success
延伸問題:

1.解釋上述程式碼的運作，撰寫完整的測試程式，指出其中可改進之處並實作
2.在 Linux 核心找出 LRU 相關程式碼並探討
:::

### 解題思路：
MM1:

void lRUCacheFree(LRUCache *obj)
{       
    LRUNode *lru, *n;
    MMM1 (lru, n, &obj->dhead, dlink) {
        list_del(&lru->dlink);
        free(lru);
    }
    free(obj); 
}   

根據上面程式碼，我們可知 MM1 是走訪整個 LRUNode 的描述語句，因此我們回想一下 Linux Kernel API ，應該如此：

list_for_each_entry_safe​ (lru, n, &obj->dhead, dlink) {

MM2:

int lRUCacheGet(LRUCache *obj, int key)
{
    LRUNode *lru;
    int hash = key % obj->capacity;
    MMM2 (lru, &obj->hheads[hash], hlink) {
        if (lru->key == key) {
            list_move(&lru->dlink, &obj->dhead);
            return lru->value;
        }
    }
    return -1;
}

MM2應為

list_for_each_entry (lru, &obj->hheads[hash], hlink) {

MM3:

void lRUCachePut(LRUCache *obj, int key, int value)
{
    LRUNode *lru;
    int hash = key % obj->capacity;
    MMM3 (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 = MMM4(&obj->dhead, LRUNode, dlink);
        list_del(&lru->dlink);
        list_del(&lru->hlink);
    } else {
        lru = malloc(sizeof(LRUNode));
        obj->count++;
    }
    lru->key = key;
    list_add(&lru->dlink, &obj->dhead);
    list_add(&lru->hlink, &obj->hheads[hash]);
    lru->value = value;
}

與MM2相同的程式碼 ， MM3 與 MM2 的答案應該一致。

MM4:由程式碼判斷由 list_head dhead 找出 LRUNode 的位置，且根據前後程式碼說明空間已滿，所以我們踢出最後一個 LRUNode ，因此程式碼應為：

lru = list_last_entry(&obj->dhead, LRUNode, dlink);

## 測驗4

針對 LeetCode 128. Longest Consecutive Sequence，以下是可能的合法 C 程式實作:

#include <stdio.h>
#include <stdlib.h>
#include "list.h"

struct seq_node {
    int num;
    struct list_head link;
};                                                                                                                                                            
            
static struct seq_node *find(int num, int size, struct list_head *heads)
{   
    struct seq_node *node;
    int hash = num < 0 ? -num % size : num % size;
    list_for_each_entry (node, &heads[hash], link) {
        if (node->num == num)
            return node;
    }
    return NULL;
}

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);

            int left = num, right = num;
            while ((node = find(LLL, n_size, heads))) {
                len++;
                list_del(&node->link);
            }

            while ((node = find(RRR, n_size, heads))) {
                len++;
                list_del(&node->link);
            }

            length = len > length ? len : length;
        }
    }

    return length;
}

請補完程式碼：
LLL=?
* (a) left
* (b) left++
* (*c*) ++left
* (d) left--
* (e) --left

RRR=?
* (a) right
* (b) right++
* (*c*) ++right
* (d) right--
* (e) right--

### 解題思路
由於是找最長的數字串列(不用相鄰沒關係)，於是這段程式使用 hash table 來實作。根據 num % 陣列 size 的值填入我們的 hash table 。所以要找尋特定 Node 的值就可以用 Find 來看看是否有出現在陣列中。 若有，就繼續往上跟往下找，並判斷目前的長度與之前搜索的長度進行比較，若比較則取代該值。若沒有則根據 for 迴圈對陣列索引加一，直到到達陣列索引最大值後返回最大的 Length 長度。
因此 LLL = (e) --left RRR= (*c*) ++right

digraph long{

Start[shape=oval]

Array[label="Get Array[i] Value" shape=box]

function [label="Find val" shape=diamond]

end [label="Return length" shape=box]

Start->Array->function

function->function:left [label="Yes,++Val"]
function->function [label="    Yes,--Val"]

function->Array [label="   No, i++"]

function->end [label="No, i == Array_size"]

}