2024q1 Homework2 (quiz1+2)

contributed by < yan112388 >

2024q1 第 1 週測驗題

題目

測驗一

基本結構：考慮 struct __node 為節點結構，有一個 int 儲存資料，及一個 left pointer, right pointer 和 next pointer

typedef struct __node {
    struct __node *left, *right;
    struct __node *next;
    long value;
} node_

本題實作了一個非遞迴 (non-recursive iterative) 的快速排序演算法，其中：

在 quicksort 中，可見以下程式碼初始化 begin 和 end。

begin[0] = *list;
end[0] = list_tail(list);

由此可知 list_tail 如其名，目的為找到鏈結串列的尾端節點

node_t *list_tail(node_t **left)
{
    while ((*left) && (*left)->next)
        left = &(AAAA);
    return *left;
}

AAAA 應填入 (*left)->next ，使 left持續往下個節點走訪，直到最後一個節點為止

int list_length(node_t **left)
{
    int n = 0;
    while (*left) {
        ++n;
        left = &(BBBB);
    }
    return n;
}

BBBB 應填入 (*left)->next ，與前者作用相似，直到無節點為止

本題quicksort原理

• 利用 begin 和 end 作為堆疊，以利將數值分成不同區段來做排序。
  首先會選擇區段的第一個節點作為基準點 (pivot)，接著走訪此區段內的每個節點，
  將小於基準點之值的節點串接到 left，大於基準點之值的節點串接 right。
  在每次循環時， 如果從 begin 與 end 拿出的值相同，則表示此節點的排列位置正確，
  可將此加入最終的鏈結串列 result 中。

while (p) {
    node_t *n = p;
    p = CCCC;
    list_add(n->value > value ? &right : &left, n);
}

CCCC 應填入 p->next，用來拜訪區段內的每個節點

begin[i] = left;
end[i] = DDDD; 
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = right;
end[i + 2] = EEEE; 

DDDD 填入 list_tail(&left) ，取得 left 的尾節點
EEEE 填入 list_tail(&right) ，取得 right 的尾節點

改進方案

• max_level 不須開到 2＊n ? n 即可

測驗二

Timsort：
該排序法考量現實世界中的資料大多為已排序的，首先將序列分成多個 runs，使用插入排序法做排序，再以合併排序法將 runs 合併，最後排序完成。

• find_run() ：找到每個 run ，如果該 run 為降序排列，則反轉為升序

• merge_force_collapse()：強制合併剩餘的 runs ，直到剩餘 runs 的數量小於 3 個，過程中呼叫 merge_at()

• merge_collapse()：根據剩餘的 runs 數量決定要合併哪兩個 runs，過程中呼叫 merge_at()

• merge_at()：合併位於 at 處的兩個相鄰 runs

• merge_final()：將最後兩個 runs 合併，並呼叫 build_prev_link()

• build_prev_link()：將單向鏈結串列轉換為雙向循環鏈結串列

2024q2 第 2 週測驗題

題目

測驗一

以 Linux 核心的 hash table 架構實作 LeetCode 105 Construct Binary Tree from Preorder and Inorder Traversal

• 前序會先拜訪每個子樹的根節點，中序則將每個子樹的左右子樹分開來，因此能建構出唯一二元樹
• hlist_node 架構示意圖
  

其中，next 指向相鄰的節點本身，而 pprev 宣告為指標的指標，指向指著自身節點的指標。

struct hlist_node {
    struct hlist_node *next, **pprev;
};

Q：為甚麼要使用 hash table？
建構過程，需要根據前序，在中序中找到對應的索引來確定左右子樹的範圍。直接在中序內線性查找的時間複雜度為 O(n) ，對於大規模的數據會很費時。因此，使用 hash table 能加快尋找速度。

• find：計算 hash 值，在中序中查找指定元素的索引

• node_add：將新的節點加到 hash table 中，使用 Division method 作為 hash function

• dfs：

1. 找到根節點在中序中的索引 idx
2. 根據索引 idx 將中序分成左子樹和右子樹
3. 根據前序的順序，遞迴建構左子樹和右子樹

static struct TreeNode *dfs(int *preorder,
                            int pre_low,
                            int pre_high,
                            int *inorder,
                            int in_low,
                            int in_high,
                            struct hlist_head *in_heads,
                            int size)
{
    if (in_low > in_high || pre_low > pre_high)
        return NULL;

    struct TreeNode *tn = malloc(sizeof(*tn));
    tn->val = preorder[pre_low];
    int idx = find(preorder[pre_low], size, in_heads);
    tn->left = dfs(preorder, pre_low + 1, pre_low + (idx - in_low), inorder,
                   in_low, idx - 1, in_heads, size);
    tn->right = dfs(preorder, pre_high - (in_high - idx - 1), pre_high, inorder,
                    idx + 1, in_high, in_heads, size);
    return tn;
}

參考資料：Linux 核心的 hash table 實作、内核基础设施——hlist_head/hlist_node结构解析

測試程式

根據給予的前序和中序，建構出一顆根為 root 的二元樹

struct TreeNode *root = buildTree(preorder, preorderSize, inorder, inorderSize);

以下兩個函式能根據傳入的根結點，印出二元樹的前序與中序

void printPreorder(struct TreeNode *root) {
    if (!root)
        return;
    printf("%d ", root->val);
    printPreorder(root->left);
    printPreorder(root->right);
}

void printInorder(struct TreeNode *root) {
    if (!root)
        return;
    printInorder(root->left);
    printf("%d ", root->val);
    printInorder(root->right);
}

測驗二

實作一個 LRU Cache

• lRUCacheCreate : 建立一個新的 LRU Cache，指定其容量大小為 capacity

• lRUCacheFree : 釋放 LRU Cache 所佔用的記憶體空間

• lRUCacheGet : 從快取中獲取特定 key 對應的值，如果該值存在，則將該節點移動到鏈結串列的頭部

• lRUCachePut : 將指定值依據 key 放進 Cache，如果 Cache 已滿，則移除最久未被存取的節點。如果 key 已存在，則更新其值並將該節點移動到鏈結串列的頭部

測驗三

在指定的記憶體空間找出第 N 個設定的位元

• 有三個參數會傳入 find_nth_bit
*addr ：指向要查找的記憶體區域起始位置的指標
  size ：要查找的記憶體區域的位元大小
  n ：要查找的是第幾個設定的位元（從 0 開始數）

static inline unsigned long find_nth_bit(const unsigned long *addr,
                                           unsigned long size,
                                           unsigned long n)
{
    if (n >= size)
        return size;

    if (small_const_nbits(size)) {
        unsigned long val = *addr & GENMASK(size - 1, 0);

        return val ? fns(val, n) : size;
    }

    return FIND_NTH_BIT(addr[idx], size, n);
}

• 如果 n 大於或等於 size，則直接回傳 size，因為 n 已經超出了給定的範圍

• 如果 size 是一個很小的常數值且小於等於 BITS_PER_LONG(64) 並大於0，則只需檢查第一個 unsigned long 值

• 如果以上皆非，則利用巨集 FIND_NTH_BIT

• GENMASK：依據給定的範圍，產生連續的 bitmask

  • h 和 l 是需要設置為 1 的最高有效位和最低有效位的位置
  • 例：GENMASK(5, 0) 會生成 00000000000000000000000000111111（二進位）

• FIND_NTH_BIT：逐一檢查每個 unsigned long 值中設定的位元數量。如果設定的位元數量大於 n ，則進入 found 標籤，使用 fns 函數在該值中找到第 n 個設定的位元。

• __ffs：回傳該數值中最右邊值為1的位元的位置

延伸問題皆待補充