Try   HackMD

2022q1 Quiz1

tags: linux2022

contributed by <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

延伸題目:

1.解釋上述程式碼運作原理
2.研讀 Linux 核心原始程式碼 include/linux/hashtable.h 及對應的文件 How does the kernel implements Hashtables?，解釋 hash table 的設計和實作手法，並留意到 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;
}







Hash



Map

Hash Value

1

2

3

4

5

6



Hhead

hlist_head

hlist_node *first



Map:5->Hhead:2


Access



Key

Key

data

hlist_node node



Hnode

hlist_node

**pprev

*next



Hnode:1->Key


is Part of Key



Hhead:1->Hnode


Node Structure

第一個函數就是將剛剛 *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=?

延伸問題:

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

解題思路







test



st

Start



deletDuplicates1

deleteDuplicates(head)



st->deletDuplicates1





COND1

COND1



deletDuplicates1->COND1





nxt

head->next



COND1->nxt


No



COND2

while(COND2) head=head->next



COND1->COND2


Yes



nxt->deletDuplicates1


head=head->next



end

return head



nxt->end


return



COND2->deletDuplicates1


head=head->next



COND2->end


return



deletDuplicates2

deleteDuplicates(head->next)

根據程式碼，我們可以知道假如 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_ 開頭
  • 不要出現空白
  • 儘量寫出最精簡的程式碼，而且答案也只接受符合上述程式碼排版風格的最精簡形式

延伸問題:

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







long



Start

Start



Array

Get Array[i] Value



Start->Array





function

Find val



Array->function





function->Array


   No, i++



function->function:left


Yes,++Val



function->function


    Yes,--Val



end

Return length



function->end


No, i == Array_size
Last changed by 
 
ganoliz
嗨我是畢業於成大資工所的品品，現在是隻知識倉鼠，儘量把目前要學的東西做成筆記或是直接快速地謄寫起來方便查看複習。
0
285

Read more

C語言複習

偵測是否為 0

Mar 31, 2025
Django 框架

以上內容參考自 MDN

Mar 4, 2025
RAG and Query analysis

假如使用者想跟 RAG LLM 互動，其中的上下文內容會牽涉到特別的關鍵字或是查詢方法。如何透過使用者的原始輸入與模型的最佳輸出，Query analysis 作為橋梁，目前主要有兩種方法:

Feb 27, 2025
捷克布拉格理工大學交換報告

教育部赴捷克短期進修獎學金，係為捷克教育部頒發之獎學金，可申請獎學金之人士可以是正職學生、交換學生、短期研習之受高等教育人士或是訪問研習教授，分別可選五個月或是十個月，該獎學金可以每年重複提交申請審查。本人於 2023年參與教育部委辦的書面徵選及面試，於 2023 年六月初得到捷克教育部的回函，得到捷克布拉格理工大學資訊工程系所的獎學金資格，因此於 2023/9-2024/6 前往捷克進行研習交換。 任何交換有想問問題的學弟妹或同學都可以 Email 給我: willy123301@gmail.com 。或是參考我們這期交換生開始編寫的 捷克交換學生生存手冊(感謝蔡秀吉同學主編)。

Oct 30, 2024
Read more from ganoliz
Published on HackMD