2022 年「資訊科技產業專案設計」作業 1

貢獻者：達摩 - Daruma

模擬面試錄影(漢)
模擬面試錄影(英)

509. Fibonacci Number

題目敘述

現在有一個費氏數列

f

，定

f_{0} = 0

、

f_{1} = 1

。

現在題目給一個非負整數

n

，請算出

f_{n}

的值。

程式碼解說

使用 DP

用遞迴的方法來算答案的話重複的計算會算很多次，因此使用迭代的方式依序算出

f_{2}

f_{3}

一直到算出

f_{n}

來避免重複計算的問題。

int fib(int n) {
    if (n <= 1)
        return n;

    vector<int> f(n + 1, 0);
    f[1] = 1;
    for (int i = 2; i <= n; ++i)
        f[i] = f[i - 1] + f[i - 2];

    return f[n];
}

空間複雜度
$O (1)$

算

f_{i}

的時候只需要知道

f_{i - 1}, f_{i - 2}

，因此可以只用長度為

3

的陣列來記錄。

int fib(int n) {
    if (n <= 1)
        return n;

    array<int, 3> f{0, 0, 1};
    for (int i = 2; i <= n; ++i) {
        f[0] = f[1];
        f[1] = f[2];
        f[2] = f[0] + f[1];
    }

    return f[2];
}

時間複雜度
$O (\log n)$

如果將

f_{i}, f_{i + 1}

寫成

[\begin{matrix} f_{i} \\ f_{i + 1} \end{matrix}]

，那要得到

[\begin{matrix} f_{i + 1} \\ f_{i + 2} \end{matrix}]

的話，只需要乘上

[\begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix}]

即可。

可以推得

[\begin{matrix} f_{n - 1} \\ f_{n} \end{matrix}] = {[\begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix}]}^{n} [\begin{matrix} 1 \\ 0 \end{matrix}]

，而計算

{[\begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix}]}^{n}

的時間複雜度是

O (\log n)

。

Follow Up: 收納的智慧

給定一個

2 \times n

的收納盒，而你現在手邊有許多積木，積木的形狀都是長方形，並且有

1 \times 2

和

1 \times 1

兩種大小，請問要用積木把收納盒放滿有幾種可能的放法。

使用 DP

定義

d p_{i, 0}

為填滿

2 \times i

的盒子的方法數，而

d p_{i, 1}

為填滿

2 \times (i - 1)

，並且第

i

行「只」填其中一格的方法數。

要填滿第

i

行有四種方法：

使用一個
$2 \times 1$ 的積木
使用兩個
$1 \times 1$ 的積木
使用兩個
$1 \times 2$ 的積木
$1 \times 2$ 和
$1 \times 1$ 的積木各一個

從上面三種方法可以得知

d p_{i, 0} = d p_{i - 1, 0} + d p_{i - 1, 0} + d p_{i - 2, 0} + 2 d p_{i - 1, 1}

。

而第

i

行只填一格的方法則是用

1 \times 1

或是

1 \times 2

的積木，因此

d p_{i, 1} = d p_{i - 1, 0} + d p_{i - 1, 1}

。

Circular Permutation in Binary Representation

題目敘述

題目給兩個非負整數

n

和

s t a r t

，其中

n

代表現在有個長度為

2^{n}

的陣列

[0, 1, 2, \dots, 2^{n} - 1]

。

請你重新排列此陣列，使得陣列的第一項為

s t a r t

並且所有相鄰的數字在二進位表示中剛好只有一個位元不同。

注意第一項以及最後一項同樣視為相鄰。

程式碼解說

方法一：先找出第一項為
$0$ 的解

先找出第一項為

0

的解

a r r

之後，假設

s t a r t

在

a r r

中的索引值為

i

（索引值從

0

開始），則把

a r r

的

[i, 2^{n})

以及

[0, i)

對調之後就是題目要的答案。

假設現在有長度為

4

的解

[0, 1, 3, 2]

，如下圖，其中兩個數字中間有線代表這兩個數字只差一個位元。

0 - 1 - 3 - 2
|___________|

這時可以再複製一份長度為

4

的解，並且將複製後的每個元素都加

4

。

0 - 1 - 3 - 2
|___________|

4 - 5 - 7 - 6
|___________|

可以發現

0, 4

、

1, 5

、

3, 7

和

2, 6

中間會有邊，因為他們只差一個位元（就是

4

），如下圖。

0 - 1 - 3 - 2
|   |   |   |
4 - 5 - 7 - 6

因此就可以得到長度為

8

的解

[0, 1, 3, 2, 6, 7, 5, 4]

。

int* circularPermutation(int n, int start, int* returnSize){
    *returnSize = (1 << n);
    int *arr = malloc(sizeof(int) * (*returnSize));

    arr[0] = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = (1 << i); j < (2 << i); ++j)
            arr[j] = arr[(2 << i) - j - 1];

        for (int j = (1 << i); j < (2 << i); ++j)
            arr[j] |= (1 << i);
    }

    int i;
    for (i = 0; arr[i] != start; ++i)
        ;
    
    int *result = malloc(sizeof(int) * (*returnSize));
    for (int j = 0; j < (1 << n); ++j)
        result[j] = arr[(i + j) & ((1 << n) - 1)];
    
    free(arr);
    
    return result;
}

方法二：直接找出第一項為
$s t a r t$ 的解

在上個方法中，我們每次都是把陣列的後半的元素的

2^{i}

這個位元設為

1

，然而其實可以透過確認

s t a r t

中的

2^{i}

這個位元是否為

1

來決定要設為

1

的是前半還是後半的元素。

因為迴圈結束後第一項就會是

s t a r t

，所以也不需要額外的記憶體空間來重新排列。

int* circularPermutation(int n, int start, int* returnSize)
{
    *returnSize = (1 << n);
    int *arr = malloc(sizeof(int) * (*returnSize));

    arr[0] = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = (1 << i); j < (2 << i); ++j)
            arr[j] = arr[(2 << i) - j - 1];

        int begin = (~start) & (1 << i);
        for (int j = 0; j < (1 << i); ++j)
            arr[begin + j] |= (1 << i);
    }

    return arr;
}

Swap Nodes in Pairs

題目敘述

給定一個鏈結串列，請將鏈結串列中的元素兩兩交換。

例如：

[1, 2, 3, 4] -> [2, 1, 4, 3]
[1, 2, 3] -> [2, 1, 3]
[] -> []

不可直接改鏈結串列的節點的值。

程式碼解說

方法一：使用 Sentinel Node

為了方便操作，在 head 前面再多加一個節點，而 for 迴圈的指標就從多加的那個節點開始，如果此節點後面有兩個以上的節點，就交換那兩個節點，之後再將指標指向下下個節點，就可以重複一樣的過程，交換剩下的節點。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode *swapPairs(struct ListNode *head)
{
    struct ListNode sentinel = {.next = head};

    for (struct ListNode *p = &sentinel;
        p->next != NULL && p->next->next != NULL;
        p = p->next->next) {

        struct ListNode *nxt = p->next;
        p->next = nxt->next;
        nxt->next = p->next->next;
        p->next->next = nxt;
    }

    return sentinel.next;
}

方法二：使用指標的指標

使用指標的指標來節省上個方法的 sentinel 所使用的空間。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode *swapPairs(struct ListNode *head)
{
    for (struct ListNode **pp = &head;
        (*pp) != NULL && (*pp)->next != NULL;
        pp = &((*pp)->next->next)) {

        struct ListNode *nxt = (*pp)->next;
        (*pp)->next = nxt->next;
        nxt->next = (*pp);
        (*pp) = nxt;
    }

    return head;
}

Follow Up: Reverse Nodes in k-Group

題目敘述

給定一個鏈結串列，前一題是兩個為一組做反轉，這次變成

k

個為一組來反轉，若是最後剩下的元素不到

k

個，就不進行反轉。

解法

這邊使用遞迴來解這題，revK(pp, k) 會反轉以 *pp 為開頭的

k

個元素，並且遞迴的處理剩下的元素，直到剩下的元素小於

k

個。

void revK(struct ListNode **pp, int k)
{
    struct ListNode *end = *pp;

    for (int i = 0; i < k; ++i) {
        if (end == NULL)
            return;

        end = end->next;
    }

    struct ListNode *p, *nxt;
    for (p = *pp; (*pp)->next != end;) {
        nxt = (*pp)->next;
        (*pp)->next = nxt->next;
        nxt->next = p;
        p = nxt;
    }

    revK(&(*pp)->next, k);

    *pp = p;
}

struct ListNode *reverseKGroup(struct ListNode *head, int k)
{
    revK(&head, k);
    return head;
}

自我檢討

英語口說需加強，常常講到一半就會停下來想接下來要說的內容
程式碼撰寫時可以加一些註解方便理解
常因為打字太急而出現錯字，也因此需要多花時間修改
在解費氏數列的題目時，應該要先解釋自己的做法，之後再撰寫程式碼

同學互評

Fibonacci Number

06:22
interviewee

可分析為何此陣列運算可達到
$O (l g (n))$

其他
interviewer

在時間允許情況下，可請面試者推導費波那契數一般式
$F_{n}$

同學互評 02

Fibonacci Number

00:33：建議可以在給範例的時候列出前 5~10 個費氏數列，原因是可能不是每個人都了解，列出能讓 interviewee 更清楚
00:57：可能題目確實比較經典，所以沒有做 react，不過建議還是在實作前進行 approach，像是可以說一開始最 naive 的 recusive 解法，並說明該解法重複運算太多次，因此 dp 的方式存儲運算過的部分，進而降低複雜度
02:33：這部分是原本用大小為 n 的陣列處理，由於每次運算只會用到前兩個，因此改為大小為 const 的陣列，這邊會讓我覺得你已經知道了這個方法比較好，但在演給我看，比較不自然的感覺，因此建議可以在這邊停一下如果 interviewer 要問優化時再進一步說明，或者在 approach 的部分直接講明思考過程，並直接實作較佳的解法
07:05：interviewer 有詢問如何計算出時間複雜度，這點我覺得挺好，可以知道 interviewee 是不是確實了解
07:11：這部分應該是 interviewee 而非 interviewer
有講述到 O(logn) 的解法，或許也能時做出來，為以下 (參考資料)




















int F[2][2] = {{1, 1}, {1, 0}}, M[2][2] = {{1, 1}, {1, 0}};
int fib(int n) {
	if(n <= 1) return n;          
	power(F, n - 1);
	return F[0][0];
}
void power(int F[2][2], int n){
	if(n <= 1) return;
	power(F, n / 2);
	matrixMul(F, F);
	if(n & 1) 
		matrixMul(F, M);   
}
void matrixMul(int F[2][2], int M[2][2]){
	int m00 = F[0][0] * M[0][0] + F[0][1] * M[1][0];
	int m01 = F[0][0] * M[0][1] + F[0][1] * M[1][1];
	int m10 = F[1][0] * M[0][0] + F[1][1] * M[1][0];
	int m11 = F[1][0] * M[0][1] + F[1][1] * M[1][1];
	F[0][0] = m00, F[0][1] = m01, F[1][0] = m10, F[1][1] = m11;
}

同學互評 03

Interviewer

0:00 可以再跟面試者閒聊一下，讓彼此更多互動

Interviewee

8:15 沒有解釋為甚麼%2的n次方

程式碼的部分會讓人看得很亂，因為把次方都寫成1>>n跟2>>n

我覺得可以在for迴圈中間宣告像是

unsigned int len = 1 << i; //2 << i 就是 2*len

會讓程式碼可讀性更高，加上for迴圈變成兩半，看得不太舒服

9:47 在講解直接找到開頭就是start的解的部分，我第一次聽的時候沒聽懂，可能是我理解力差，但是我覺得跳過太多東西了，包括怎麼會有這個想法，以及透過檢查start的2^i的bit去決定前半後半，來讓開頭是start，兩個聽起來就會很跳，沒有解釋為甚麼這樣做，start就會是開頭，只是把解法講出來而已

Swap Nodes in Pairs

聲音很炸

Interviewer

14:13 問的問題我覺得有點怪，因為p不管指向哪個我覺得差異只是實作方式，即使用兩個指標去操作我覺得問題也不大

17:57 我覺得問題有點沒有必要，因為說node更改會增加記憶體空間，但整個code也只有用到2個node，如果要改進的話，挑這個地方我覺得有更好的選擇，但在看完後面後，才了解到因為是遞迴會用到很大量的空間，這時候我覺得才會是合理的修改

Interviewee

在Follow up的部分，我是聽了下面的YT連結才了解

https://youtu.be/1UOPsfP85V4

我覺得解釋部分可以再加強，包括畫圖的部分，在解釋想法時，圖上已經有之前畫過的線，變成你講的跟圖上的不一樣，看的就不是很明白，以及為甚麼要用遞迴，遞迴的作用是甚麼，我覺得都沒有很清楚的解釋到

同學互評 04

( 509. Fibonacci Number )

02:54 “dp i minus 1” 為 dpi-1, 若要表示 dpi_1 的話能夠說 “dp i underscore 1” 或是為變數命名表示
04:40 函式回傳值為 int 在長度為 32 位元的情況下只能算到大約 Fib(47)，64 位元能夠到大約 Fib(93)。直接說效率不足不太好，這部分可能可以當作延伸問題
06:23
${(\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix})}^{(n - 1)}$ 的時間複雜度為
$O (n)$
解釋平方求冪之前假定時間複雜度為
$O (\lg n)$ 會讓 interviewer 誤會你不知道自己在說什麼，當作interviewee 在背答案。這裡可以先說時間複雜度為
$O (n)$ 再提出最佳化至
$O (\lg n)$ 的方案
06:51 這裡開始應該是 interviewee 回答，不過畫面顯示 interviewer
08:04 沒有完整解釋為什麼能夠最佳化時間複雜度至
$O (\lg n)$
這裡能夠手寫數學式解或是直接畫 recurrence tree 解出時間複雜度

數學式：

$x^{n} = {\begin{cases} 1 & if n = 0. \\ ⌊ x^{n / 2} ⌋^{2} & if n > 0, n is even . \\ ⌊ x^{n / 2} ⌋^{2} \cdot x & if n > 0, n is odd . \end{cases}$
可以看到每一步都會將 n 次式減半
假設時間複雜度為
$O (k)$

$\begin{aligned} \frac{n}{2^{k}} & \leq & 1 \\ n & \geq & 2^{k} \\ \lg n & \geq & k \end{aligned}$
時間複雜度
$O (k) = O (\lg n)$

Recurrence Tree :

時間複雜度為二元樹的高度
$O (\lg n)$

2022 年「資訊科技產業專案設計」作業 1

509. Fibonacci Number

題目敘述

程式碼解說

使用 DP

空間複雜度 O(1)

時間複雜度 O(log⁡n)

Follow Up: 收納的智慧

使用 DP

Circular Permutation in Binary Representation

題目敘述

程式碼解說

方法一：先找出第一項為 0 的解

方法二：直接找出第一項為 start 的解

Swap Nodes in Pairs

題目敘述

程式碼解說

方法一：使用 Sentinel Node

方法二：使用指標的指標

Follow Up: Reverse Nodes in k-Group

題目敘述

解法

自我檢討

同學互評

Fibonacci Number

同學互評 02

Fibonacci Number

同學互評 03

Interviewer

Interviewee

Swap Nodes in Pairs

Interviewer

Interviewee

同學互評 04

空間複雜度
$O (1)$

時間複雜度
$O (\log n)$

方法一：先找出第一項為
$0$ 的解

方法二：直接找出第一項為
$s t a r t$ 的解