# 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 核心程式碼風格:
```c
#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，探討其實作考量
:::
### 解題思路
首先我們先看看第一段程式碼:
```c
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 不成功就做一些必要的例外處置。
```c
#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 數值。
```c
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 表示未找到。
```c
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;
}
```
```graphviz
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 程式實作:
```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) 的程式碼
:::
### 解題思路
---
```graphviz
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 是對目前節點是否為重複節點的判斷，因此我們假設:
```c
COND1=head->next != NULL && head->val == head->next->val
```
當此條件成立時，就會進入 while() 迴圈來越過數個重複 value 的 node ，因此我認為
COND2 跟 COND1 可以是一樣的：
```c
COND2=head->next!=NULL && head->val == head->next->val
```
## 測驗3
針對 LeetCode 146. LRU Cache，以下是 Least Recently Used (LRU) 可能的合法 C 程式實作:
```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:
```c=
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 ，應該如此：
```c=4
list_for_each_entry_safe (lru, n, &obj->dhead, dlink) {
```
MM2:
```c=
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應為
```c=5
list_for_each_entry (lru, &obj->hheads[hash], hlink) {
```
MM3:
```c
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 ，因此程式碼應為：
```c
lru = list_last_entry(&obj->dhead, LRUNode, dlink);
```
## 測驗4
針對 LeetCode 128. Longest Consecutive Sequence，以下是可能的合法 C 程式實作:
```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
```graphviz
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"]
}
```
Sign in with Wallet
Connect another wallet