---
# System prepended metadata

title: 2020q3 第 15 週測驗題
tags: [sysprog2020]

---

# [2020q3](http://wiki.csie.ncku.edu.tw/sysprog/schedule) 第 15 週測驗題
###### tags: `sysprog2020`

:::info
目的: 引導學員挑戰 LeetCode 和複習記憶體管理機制
:::

==[作答表單](https://docs.google.com/forms/d/e/1FAIpQLSdIhhVeIOLInSPt_1TFjc92TamE4ZuqP4vbQyG6YCBWHzBjQw/viewform)==

---

### 測驗 `1`

LeetCode [835. Image Overlap](https://leetcode.com/problems/image-overlap/) 給定二個影像 A 和 B，二者皆為大小相同的二維正方形矩陣，內部以二進位表示。我們轉換其中一個影像，向左、右、上，或下滑動任意數量的單位，並將其置於另一個影像之上，隨後，該轉換的重疊 (overlap) 指二個影像都有 1 的位置數量，注意：轉換不包含向任一方向旋轉。於是，最大可能的重疊為何？

範例 1:
![](https://i.imgur.com/OnF5wBs.png)
* 輸入
    $$
    A = \left(
    \begin{array}{ccc}
    1 & 1 & 0 \\
    0 & 1 & 0 \\
    0 & 1 & 0 \\
    \end{array}
    \right)
    $$
    $$
    B = \left(
    \begin{array}{ccc}
    0 & 0 & 0 \\
    0 & 1 & 1 \\
    0 & 0 & 1 \\
    \end{array}
    \right)
    $$
* 輸出:
    * `3`
* 解釋
    * 將 A 向右移動 1 個單位，然後向下移動 1 個單位
    ![](https://i.imgur.com/ONuIxjj.png)
    * 二張影像中都存在 `1` 的位置總數為 `3`，見下圖紅色標記
    ![](https://i.imgur.com/N00Zxg7.png)

思路：找出所有 1 的位置，對兩個矩陣的所有這些位置進行求差，再統計這些差出現最多的次數。兩個坐標的差表示什麼？即是將其中一個坐標移動到另一個坐標需要移動的向量。於是，在走訪個別單元的過程中，我們找出 `A` 中所有值為 `1` 的坐標，移動到 `B` 中所有值為 `1` 的坐標需要移動的向量。於是乎，在這些向量中出現次數最多的向量，就是我們要求的整個矩陣應該移動的向量。

以下程式碼針對 LeetCode [835. Image Overlap](https://leetcode.com/problems/image-overlap/)，提出可能的解法：

```cpp
#include <string.h>
#define max(a, b) (((a) > (b)) ? (a) : (b))

static inline int overlap_count(unsigned int *AA, unsigned int *BB, int size)
{
    int res = 0;
    for (int i = 0; i < size; ++i)
        res += __builtin_popcount(AA[i] & BB[i]);
    return res;
}

static void translate(unsigned int *v,
                      int vsize,
                      int i,
                      int j,
                      unsigned int *res)
{
    memcpy(res, v, sizeof(unsigned int) * vsize);
    int mask[32];
    for (int k = 0; k < 32; k++)
        mask[k] = (1U << k) - 1;
    int n = vsize;
    if (i >= 0) {
        for (int k = 0; k < n; k++)
            res[k] >>= i;
    } else {
        i = -i;
        for (int k = 0; k < n; k++)
            res[k] = ((res[k] << i) & mask[n]);
    }

    if (j >= 0) {
        ITER1;
        for (int k = 0; k < j; k++)
            res[k] = 0;
    } else {
        j = -j;
        ITER2;
        for (int k = n - j; k < n; k++)
            res[k] = 0;
    }
}

int largestOverlap(int **img1, int img1Size, int *img1ColSize,
                   int **img2, int img2Size, int *img2ColSize)
{
    int n = img1Size;
    unsigned int A[n], B[n];
    memset(A, 0, sizeof(unsigned int) * n);
    memset(B, 0, sizeof(unsigned int) * n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (img1[i][j] == 1)
                A[i] |= 1 << j;
            if (img2[i][j] == 1)
                B[i] |= 1 << j;
        }
    }

    int res = 0;
    for (int i = -(n - 1); i <= (n - 1); ++i) {
        for (int j = -(n - 1); j <= (n - 1); ++j) {
            unsigned int AA[n];
            translate(A, n, i, j, AA);
            res = max(res, overlap_count(AA, B, n));
        }
    }
    return res;
}
```

請補完程式碼，使其符合 LeetCode 題目要求。

參考資料:
* [LeetCode 835. Image Overlap](https://www.cnblogs.com/grandyang/p/10355589.html)

==作答區==

ITER1 = ?
* `(a)` `for (int k = 0; k < n - j; k++) res[k + j] = res[k]`
* `(b)` `for (int k = 0; k <= n - j; k++) res[k + j] = res[k]`
* `(c)` `for (int k = n - j - 1; k >= 0; k--) res[k + j] = res[k]`
* `(d)` `for (int k = n - j; k >= 0; k--) res[k + j] = res[k]`


ITER2 = ?
* `(a)` `for (int k = j; k < n; k++) res[k + j] = res[k]`
* `(b)` `for (int k = j; k < n; k++) res[k - j] = res[k]`
* `(c)` `for (int k = j - 1; k < n; k++) res[k + j] = res[k]`
* `(d)` `for (int k = j - 1; k < n; k++) res[k - j] = res[k]`


:::success
延伸題目:
1. 解釋上述程式碼運作原理
2. 提出效率更高，且空間佔用更少的 C 程式碼實作
:::

---

### 測驗 `2`

LeetCode [1569. Number of Ways to Reorder Array to Get Same BST](https://leetcode.com/problems/number-of-ways-to-reorder-array-to-get-same-bst/) 給定一個陣列 `nums` 表示 $1$ 到 $n$ 的排列，依據元素在 `nums` 中的順序，依次插入一個初始為空的二元搜尋樹 (BST)。請你統計將 `nums` 重新排序後，滿足以下條件的個數：
* 重排後得到的 BST 與 `nums` 原本數值順序得到的 BST 相同。

例如，給定 $nums = [2,1,3]$，我們得到一棵 `2` 為 root、`1` 為 left 及 `3` 為 right 的樹。
![](https://i.imgur.com/zp2bTKD.png)
陣列 $[2,3,1]$ 也能得到相同的 BST，但 $[3,2,1]$ 會得到一棵不同的 BST 。

由於答案可能會很大，請將結果對 $10^9 + 7$ 取餘數。
* 為何是 $10^9 + 7$ 呢？請見 [Modulo 10^9+7 (1000000007)](https://www.geeksforgeeks.org/modulo-1097-1000000007/)

範例 1
![](https://i.imgur.com/zp2bTKD.png)
* 輸入
    * $nums = [2,1,3]$
* 輸出
    * `1`
* 解釋
    * 我們將 `nums` 重排，$[2,3,1]$ 可得到相同的 BST
    * 沒有其他得到相同 BST 的方法

範例 2
![](https://i.imgur.com/EQRaUTp.png)
* 輸入
    * $nums = [3,4,5,1,2]$
* 輸出
    * `5`
* 解釋
    * 下面 5 個陣列可得到相同的 BST
    * $[3,1,2,4,5]$
    * $[3,1,4,2,5]$
    * $[3,1,4,5,2]$
    * $[3,4,1,2,5]$
    * $[3,4,1,5,2]$

範例 3
![](https://i.imgur.com/pHEpvcY.png)
* 輸入
    * $nums = [1,2,3]$
* 輸出
    * `0`
* 解釋
    * 沒有其他排列順序能得到相同的 BST

範例 4
![](https://i.imgur.com/KnFWUNa.png)
* 輸入
    * $nums = [3,1,2,5,4,6]$
* 輸出
    * `19`

範例 5
* 輸入
* $nums = [9,4,2,1,3,6,5,7,8,14,11,10,12,13,16,15,17,18]$
* 輸出
    * `216212978`
* 解釋
    * 得到相同 BST 的個數是 `3216212999`
    * 將其對 $10^9 + 7$ 取餘後得到 `216212978`

根節點是陣列第一個數，分為左右兩個子樹，左右子樹之間的順序若不變即可
假設左子樹 $L$ 長度 $nL$，右子樹 $R$ 長度 $nR$，則有效組合數為 $C_{nL+nR}^{nL} \times f(L) \times f(R)$

```cpp
#include <string.h>

static const int MOD = 1e9 + 7; /* prime */

static int recursive(int *nums, int nums_size, int N, DECL)
{
    if (nums_size <= 2)
        return 1;
    int left[N + 1], left_size = 0, right[N + 1], right_size = 0;
    for (int i = 1; i < nums_size; i++)
        nums[i] > nums[0] ? (right[right_size++] = nums[i])
                          : (left[left_size++] = nums[i]);
    int l = recursive(left, left_size, N, cache),
        r = recursive(right, right_size, N, cache);
    return (((long) cache[nums_size - 1][left_size] * l % MOD) * r) % MOD;
}

int numOfWays(int *nums, int N)
{
    int comb[N + 1][N + 1]; /* combination table */
    memset(comb, 0, sizeof(comb));

    comb[0][0] = 1;
    for (int i = 1; i <= N; i++) {
        comb[i][0] = 1;
        for (int j = 1; j <= N; j++)
            INIT;
    }
    return recursive(nums, N, N, comb) - 1;
}
```


參考資訊:
* [花花醬 LeetCode 1569](https://zxi.mytechroad.com/blog/recursion/leetcode-1569-number-of-ways-to-reorder-array-to-get-same-bst/)

注意：`DECL` 若是 `int **cache`，會在 [undefined behavior sanitizer](https://clang.llvm.org/docs/UndefinedBehaviorSanitizer.html) (UBsan) 的執行階段遇到 [Load of misaligned address](https://stackoverflow.com/questions/47619944/load-of-misaligned-address-and-ubsan-finding)

請補完程式碼，使其符合 LeetCode 題目要求。

==作答區==

DECL = ?
* `(a)` `int cache[N][N]`
* `(b)` `int cache[N - 1][N - 1]`
* `(c)` `int cache[N + 1][N]`
* `(d)` `int (*cache)[N + 1]`
* `(e)` `int (*cache)[N]`

INT = ?
* `(a)` `comb[i][j] = (comb[i - 1][j] + comb[i - 1][j - 1]) % MOD`
* `(b)` `comb[i][j] = (comb[i - 1][j] + comb[i - 1][j - 1])`
* `(c)` `comb[i][j] = (comb[i][j] + comb[i - 1][j - 1]) % MOD`
* `(d)` `comb[i][j] = (comb[i][j] + comb[i - 1][j - 1])`
* `(e)` `comb[i][j] = (comb[i][j - 1] + comb[i - 1][j - 1]) % MOD`
* `(f)` `comb[i][j] = (comb[i][j - 1] + comb[i - 1][j - 1])`

:::success
延伸題目:
1. 解釋上述程式碼運作原理
2. 提出效率更高，且空間佔用更少的 C 程式碼實作
:::

---

### 測驗 `3`

在 Ubuntu/Debian Linux 中，可執行 `sudo apt install dictionaries-common` 以安裝辭典套件，於是可得到 `/usr/share/dict/words` 檔案，後者包含超過 10 萬個單字/詞:
```shell
$ wc -l /usr/share/dict/words
```

考慮以下 C 程式 (`strsearch.c`) 可從給定的詞典中檢索:
```cpp
/*
 * Hash table is represented as `htable` array of size N (N = number of lines in
 * dict), where each element either points to the end of a singly-linked list or
 * is equal to zero. Lists are stored in pre-allocated array `clist` of size N.
 *
 * This implementation is memory-efficient and cache-friendly, requiring only
 * 12N + O(1) bytes of "real" memory which can be smaller than the size of
 * dict, sacrificing however for request processing speed, which is
 * O(req_size) in most cases, but may be up to O(dict_size) due to hash collision.
 */

#include <fcntl.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <unistd.h>

/* 2 additional bytes for '\n' and '\0' */
#define MAX_REQUEST_SIZE (128 * 1024 * 1024 + 2)

struct htable_entry {
    uint32_t ptr;
};

struct collision_list {
    uint32_t fpos;
    uint32_t len;
    uint32_t prev;
};

struct compr_collision_list {
    uint32_t fpos;
    uint32_t len;
};

typedef struct htable_entry htable_entry_t;
typedef struct collision_list collision_list_t;
typedef struct compr_collision_list compr_collision_list_t;

static char *dict;
static htable_entry_t *htable;
static collision_list_t *clist;
static compr_collision_list_t *cclist;
static size_t num_of_bytes, num_of_lines;
static size_t num_of_buckets;
static int clist_size = 1;

static uint32_t hash(char *s, size_t len)
{
    uint32_t hash = 5381;
    for (size_t i = 0; i < len; i++)
        hash = ((hash << 5) + hash) + (s[i] - 32);
    return hash % num_of_buckets;
}

static void htable_insert(size_t fpos, size_t len)
{
    uint32_t h = hash(dict + fpos, len);
    clist[clist_size].fpos = fpos;
    clist[clist_size].len = len;
    clist[clist_size].prev = htable[h].ptr;
    htable[h].ptr = clist_size;
    ++clist_size;
}

static bool htable_lookup(char *s, size_t len)
{
    uint32_t h = hash(s, len);
    uint32_t ptr = htable[h].ptr;
    uint32_t nextptr = htable[h + 1].ptr;
    for (; ptr < nextptr; ptr++) {
        if ((len == cclist[ptr].len) &&
            !memcmp(s, dict + cclist[ptr].fpos, len))
            return true;
    }
    return false;
}

int main(int argc, char **argv)
{
    if (argc != 2) {
        printf("usage: %s dictionary_file\n", argv[0]);
        return 2;
    }

    /* Map dictionary file directly to memory for easier access from program */
    int dictfd;
    if ((dictfd = open(argv[1], O_RDONLY)) < 0)
        return 1;

    struct stat st;
    fstat(dictfd, &st);
    num_of_bytes = st.st_size;
    if ((dict = mmap(0, num_of_bytes, PROT_READ, MAP_PRIVATE, dictfd, 0)) ==
        MAP_FAILED)
        return 1;

    /* Count number of lines in file */
    for (size_t i = 0; i < num_of_bytes; i++) {
        if (dict[i] == '\n')
            num_of_lines++;
    }
    num_of_lines++;

    num_of_buckets = num_of_lines;
    htable = calloc(num_of_buckets + 1, sizeof(htable_entry_t));
    clist = malloc((num_of_lines + 1) * sizeof(collision_list_t));

    size_t prev_start = 0;
    for (size_t i = 0; i < num_of_bytes; i++) {
        if (dict[i] == '\n') {
            htable_insert(prev_start, P1);
            prev_start = P2;
        }
    }

    /* Compress collision list and update ptrs in htable accordingly */
    htable[num_of_buckets].ptr = num_of_lines;
    cclist = malloc((num_of_lines + 1) * sizeof(compr_collision_list_t));
    size_t clines = 0;
    for (size_t i = 0; i < num_of_buckets; i++) {
        uint32_t ptr = htable[i].ptr;
        htable[i].ptr = clines;
        while (ptr) {
            cclist[clines].fpos = clist[ptr].fpos;
            cclist[clines].len = clist[ptr].len;
            ptr = clist[ptr].prev;
            clines++;
        }
    }
    free(clist);

    /* Ready to accept requests */
    char *req_buf = malloc(MAX_REQUEST_SIZE);

    while (!feof(stdin)) {
        fgets(req_buf, MAX_REQUEST_SIZE, stdin);
        size_t len = strlen(req_buf);
        /* Exit on "exit" command */
        if (!strncmp(req_buf, "exit\n", len))
            break;
        printf("%s: %s\n", req_buf, htable_lookup(req_buf, len) ? "YES" : "NO");
    }

    free(req_buf);
    free(htable);
    free(cclist);
    munmap(dict, num_of_bytes);
    close(dictfd);
    return 0;
}
```

給定測試輸入 (檔名: `inputs`) 如下:
```
gnu
linux
kernel
X
XX
exit
```

測試方式:
```shell
$ ./strsearch /usr/share/dict/words < inputs
```

預期執行結果:
```
gnu
: YES
linux
: NO
kernel
: YES
X
: YES
XX
: NO
```

請補完程式碼。

==作答區==

P1 = ?
* `(a)` `prev_start + i`
* `(b)` `prev_start + i + 1`
* `(c)` `i - prev_start`
* `(d)` `i - prev_start + 1`

P2 = ?
* `(a)` `i`
* `(b)` `i + 1`
* `(c)` `i - 1`

:::success
延伸題目:
1. 解釋上述程式碼運作原理
2. 提出效率更高，且空間佔用更少的 C 程式碼實作
:::

---
