面試經驗反思

To 十分感謝點進來的您

Q1: Merge Sort

思路整理

1. 在每次遞迴呼叫中，我們會將原始的 list 拆分為兩個子問題：一個是從索引 1 到 m，另一個是從 m+1 到 n，也就是將整個問題劃分為左右兩個子區間。
2. 接著針對這兩個子問題分別遞迴處理，並在每一層遞迴結束後，對兩個已排序的子序列進行一次合併（merge）操作，以合併成一個整體有序的序列。
3. 此演算法的整體時間複雜度為 O(n log n)，其中 log n 表示將問題遞迴劃分為兩半所需的層數，而每一層的合併操作都會對整個序列進行線性掃描，因此每層的合併操作是 O(n)，總體複雜度即為 O(n log n) 且空間複雜度會是 O (1) （考慮遞迴的 stack 會是 O(log n)。

面試中的問題

1. 有考量到拆分子問題的解法，並且針對兩個子問題遞迴處理的想法也是對的，但在遞迴式子的建立上出現了問題，面試官也有提示在最小的子問題會是有序的，並且從 bottom up merge 上來的答案也會是有序的，這部分完全是我算法實作程度的問題，沒有將面試官好意的提示撰寫出來。
2. 有想到可以將各個 node 轉換為陣列裡的元素，並直接進行 sort() 排序後在使用 iteration 建立整個鏈結串列，但這個解法首先空間複雜度會來到 O(n) ，並且這題的出發點就是想要我去實作出算法，但這個方法是選擇用現成的解法，雖然都是同樣的時間複雜度，但就失去題目的意義。
3. 在面試中太緊張，導致還沒定義好 function 就想著要 return 什麼結果，並且像是獲取中間點這種操作是可以將他寫成獨立 function的，而不是直接撰寫，這樣代碼的可讀性跟可維護性也會比較高。
4. 在與面試官的溝通中，因為過於緊張而沒有讓面試官有感受到雙向溝通，我應該要把我腦中癥結的點與面試官確認，並尋求指引，而非自己埋頭苦惱。
5. 太緊張了。

演算法實作

應該要先將會用到的 function 定義出來，而不是直接開始撰寫代碼

getMid

面試過程中的想法與實作是沒問題的，可利用快慢指標去獲取中間點

// 使用快慢指標去獲取中間的點
Node* getMid(Node* node) {
    int slow = node;
    int fast = node->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next-next;
    }
    return slow;
}

merge

對「有序」的兩個鏈結串列可以進行排列，並且善用指標的指標去指定剩餘串列

// 合併兩個有序的鏈結串列
Node* merge(Node* l1, Node* l2) {
    Node* dummy(0);
    Node* curr = dummy;
    while (l1 && l2) {
        
        if (l1->val <= l2->val) {
            curr->next = l1;
            l1 = l1->next;
        } else {
            curr->next = l2;
            l2 = l2->next;
        }
        curr = curr->next;
    }
    if (l1) {
        curr->next = l1;
    }
    
    if (l2) {
        curr->next = l2;
    }
    
    return dummy->next;
}

mergeSort

在這主程式要進行 divide and conquer 的操作，利用先前定義的兩個函式去進行整個鏈結串列的排序

Node* mergeSort(Node* node) {
    if (!node || !node->next) return node;
    
    Node* mid = getMid(node);
    Node* right = mid->next;
    mid->next = nullptr;
    
    Node* left = merge_sort(head);
    Node* right = merge_sort(right);
    
    return merge(left, right);
}

Q2: KMP（Knuth–Morris–Pratt）演算法

思路整理

1. 題目給定兩個字串，分別為長度為 n 的 s 以及長度為 m 的 t ，希望能找出所有 s 的子字串中等於 t 的起始點。
2. 這題當下直觀的想法是做一個暴力搜尋，透過一整個 iteration 對 s 的每個字元當作起始點去確認是否與 t 相同，若相同則加進答案列裡。
3. 這樣情況下的時間複雜度會來到 O(n * m) ，因為在最糟的情境會需要對每一個字元做長度為 m 的檢查，並且空間複雜度會來到 O(n) <–答案陣列的空間。
4. 以題目敘述來說有更好的解法，但當下沒想出來，只有想到可能與 prefix 有相關。

面試中的問題

1. 沒有將更好的算法名稱主動說出來，也沒有與面試官討論更好的解法的思路，像是我有想到可能與 prefix 相關但沒提出進行討論。
2. 不知道最優解的完整思路，也沒將最優解代碼撰寫出來

學習演算法

TODO: 先閱讀 Knuth-Morris-Pratt Algorithm Visually Explained 的圖解，理解算法，並且 trace 算法的每一步驟。

拆解演算法

核心思路是不希望在找到當下兩個字串的字元不 match 的情況下從頭來過，那這個算法希望利用 當下字串與字串本身最長的相等的前綴與後綴長度，當 s[i] != t[j] 發生時，我們不需要讓 j = 0 重頭比對，可以跳回 j = lps[j - 1]（前一個字元的最長前後綴的長度），這樣能避免多餘比較，這樣就能降低整體的時間複雜度，可以將搜尋特定字串的時間複雜度從 O(n * m) 優化至 O(n + m)，並且在空間複雜度的部分會是 O(max(n, m))。
首先 KMP 會去針對每個字元與此字串做最長前後綴的陣列
像是對於字串 "ABABCDEAB" 來舉例：
lps[0] = 0（"A" -> 只有一個字元）
lps[1] = 0（"AB" -> 沒有前後綴）
lps[2] = 1（"ABA" -> 擁有相同前後綴 "A"）
lps[3] = 2（"ABAB" -> 擁有相同前後綴 "AB")
…

string t = {'A', 'B', 'A', 'B', 'C', 'D', 'E', 'A', 'B'};
// A B A B C D E A B
// 0 0 1 2 0 0 0 1 2

那這個前後綴陣列在字串的比較中，是為什麼可以讓當下兩個字元不匹配時，跳回他前一項的最長前後綴的長度呢？

那是因為前面的所有字元都「已經確定」與 s 中的某一段是匹配的，所以我們可以保留這些資訊，不需要重比，總結的話就，我們跳回的 lps[j - 1]，就是「在前一段已知匹配的子字串中，能保留最長、且仍可能匹配的部分」，因此能跳過無效比對，提高效率。

舉個例子：

t = ABABCDEAB
s = ABABAFEABDD

若進行到s index 為 4 的地方此時是
ABABC
ABABA
並且 'C' != 'A' 那在這種情況下暴力解會讓 t 開始匹配的 index 歸 0 
s 移動至下一個 index 開始匹配
但若使用前後綴的概念，我們在雙方的前一個點 index = 3 （"ABAB"）時是已經確定 t 與 s 是匹配的
此時我們的最長前後綴是 "AB" 那我們就可以讓 t 的 index 移動至 2 這個點
代表 s[2:4] = t[0:2]
因此可以跳過這些，從 t[2] 開始比對，提升效率

理解完演算法來實現代碼：

演算法實現

createLPSArray

1. 首先定義前一個 LPS 的長度 prev 以及下一個要計算的 LPS 位置 i
2. 如果匹配成功便代表在 cur 這個 index 的 LPS 應該為 prev + 1，並且prev 以及 cur 都繼續往前匹配。
3. 若匹配失敗且前一個位置 prev 已經為 0，則 lps[cur] 為 0，cur 繼續往前匹配。
4. 若匹配失敗，且前一個位置 prev 不為 0，則代表可以透過 LPS (最長相等前後綴)來回到應該重新匹配的位置。

vector<int> createLPSArray(const string& t) {
    int m = t.length();
    vector<int> lps(m, 0);
    int prev = 0, i = 1;

    while (i < m) {
        if (t[i] == t[prev]) {
            lps[i] = prev + 1;
            i++;
            prev++;
        } else if (prev == 0) {
            lps[i] = 0;
            i++;
        } else {
            prev = lps[prev - 1];
        }
    }

    return lps;
}

KMP

當我們匹配失敗的時候，都要先透過 LPS 陣列找到可以重新嘗試的地方先匹配看看，以避免每一次都從頭開始匹配的時間浪費。

vector<int> KMP(string s, string t) {
  vector<int> lps = createLPSArray(t);
  vector<int> ans;
  int i = 0, j = 0;
  while (i < s.length()) {
    if (s[i] === t[j]) {
        i++;
        j++;
    } else {
        if (j === 0) {
            i++;
        } else {
            j = lps[j - 1];
        }
    }
    if (j === t.length()) {
        ans.push_back(i - j); // 找到一組完整匹配
        j = lps[j - 1];       // 接著找下一個
    }
  }
  return ans;
}