概述#

Part XI — Advanced Topics 收錄了在面試中偶爾出現、但並非常見的進階主題。作者在第 6 版加入這些內容，是為了給希望深入準備的讀者提供額外的學習材料。

本章主題大多超出一般面試的範疇，面試官不應因為你不熟悉這些內容而感到意外。若時間有限，這些主題的優先順序較低。但若你喜歡深入學習資料結構與演算法，或希望以最充分的準備應對面試，這些內容值得一讀。

Useful Math（實用數學）#

整數 1 到 N 的總和#

將低值與高值配對相加，可得：

  • n 為偶數時：總和 = n/2 * (n+1)
  • n 為奇數時：總和 = (n+1)/2 * n
  • 統一公式：n(n+1)/2

這個公式常用於分析巢狀迴圈的時間複雜度，例如：

for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        System.out.println(i + j);
    }
}

此程式碼總迭代次數為 n(n-1)/2，時間複雜度為 O(n²)。

2 的冪次總和#

2⁰ + 2¹ + 2² + … + 2ⁿ = 2ⁿ⁺¹ - 1

重要結論：2 的冪次序列的總和大約等於序列中下一個值。

對數換底#

log_b(k) 與 log_x(k) 之間只差一個常數因子：

log_10(p) = log_2(p) / log_2(10)

結論：在 Big O 分析中，對數的底數不影響複雜度級別（常數可忽略），因此通常直接寫 O(log n)。

排列數（Permutations）#

從 n 個獨特字元中排列所有字元：n! 種方式。

從 n 個字元中選出 k 個字元的排列：

n! / (n-k)! = n * (n-1) * (n-2) * ... * (n-k+1)

組合數（Combinations）#

從 n 個元素中選 k 個（不計順序）：

C(n,k) = n! / (k! * (n-k)!)

即 n-choose-k，又記作 (n k)。

數學歸納法（Proof by Induction）#

歸納法是遞迴思維的數學基礎：

  1. Base Case：證明 P(b) 為真
  2. 假設：假設 P(n) 為真
  3. 歸納步驟：證明若 P(n) 為真，則 P(n+1) 也為真

例如：用歸納法證明 n 元素集合有 2ⁿ 個子集。

Topological Sort（拓撲排序）#

拓撲排序是對有向圖的節點進行排序，使得若存在邊 (a, b)，則 a 在排序中出現在 b 之前。若圖有環或為無向圖，則不存在拓撲排序。

應用場景：組裝線的零件順序、課程先修關係等。

演算法步驟#

  1. 建立佇列 order（儲存最終排序結果）與 processNext（下一步處理的節點）
  2. 計算每個節點的 inbound（入度）
  3. 將所有入度為 0 的節點加入 processNext
  4. 迴圈處理 processNext：
    • 取出節點 n，加入 order
    • 對每條 n 的出邊 (n, x)，將 x 的 inbound 減 1；若 x.inbound == 0，加入 processNext
  5. 若 order 包含所有節點，排序成功；否則圖中有環

拓撲排序偶爾出現在面試題中。面試官不一定期望你能立即背出演算法，但能從基本原理推導出來是合理的期望。

Dijkstra’s Algorithm（最短路徑演算法）#

Dijkstra 演算法用於在加權有向圖（邊權重須為正值）中，從起始節點 s 找出到所有其他節點的最短路徑。

Dijkstra's Algorithm：加權有向圖範例

核心資料結構#

  • path_weight[node]：從 s 到各節點的當前最短路徑權重（初始化為無限大，path_weight[s] = 0）
  • previous[node]：記錄最短路徑中的前一個節點
  • remaining：優先佇列，依 path_weight 排序

演算法步驟#

  1. 從 remaining 中取出 path_weight 最小的節點 n
  2. 對每個相鄰節點 x：若 path_weight[n] + edge_weight(n,x) < path_weight[x]，則更新 path_weight[x] 與 previous[x]
  3. 從 remaining 移除 n
  4. 重複直到 remaining 為空

時間複雜度#

Priority Queue 實作時間複雜度
陣列O(V²)
Min HeapO((V + E) log V)

若圖為稠密圖（E ≈ V²），陣列實作較優；若為稀疏圖（E « V²），Min Heap 較優。

Dijkstra's Algorithm 逐步執行過程：path_weight 與 previous 的變化

Hash Table Collision Resolution（雜湊碰撞處理）#

任何雜湊表都可能發生碰撞，以下是常見的處理方法：

Chaining with Linked Lists（鏈結串列鏈接法）#

最常見的方法：每個陣列槽位對應一個鏈結串列，碰撞的元素加入同一串列。

  • 最差情況查找：O(n)（元素全部碰撞至同一槽位）
  • 適用於碰撞數量少的情況

Chaining with Binary Search Trees#

將碰撞元素存入 BST 而非鏈結串列，最差情況查找降至 O(log n)。僅在預期分布極不均勻時使用。

Open Addressing with Linear Probing（線性探測開放定址）#

發生碰撞時，移至陣列中下一個空位（或固定步距的位置，如 index + 5）。

  • 缺點：雜湊表總容量受陣列大小限制
  • 群聚問題（Clustering）：連續填滿的區間會讓後續碰撞更可能落在同一區域，惡化效能

Quadratic Probing & Double Hashing#

探測距離以二次函數增長，或使用第二個雜湊函數決定探測步距，以減少群聚問題。

Rabin-Karp Substring Search（子字串搜尋）#

暴力法在字串 B（長度 b）中搜尋子字串 S（長度 s）需要 O(s(b-s)) 時間。

Rabin-Karp 演算法利用雜湊加速：若兩個字串相同，其雜湊值必相同（反之不一定）。

核心思想#

預先計算 B 中每個長度為 s 的子字串的雜湊值，利用 rolling hash 技術在 O(b) 時間內完成所有雜湊計算：

hash('oe ') = (hash('doe') - code('d') * 128²) * 128 + code(' ')

Rabin 指紋函數將字串視為 base-128 的數字：

hash('doe') = code('d') * 128² + code('o') * 128¹ + code('e') * 128⁰
  • 期望時間複雜度：O(s + b)
  • 最差情況：O(sb)（雜湊碰撞過多）

Rabin-Karp：字元編碼與滑動視窗 hash 值計算

Rabin-Karp 演算法在面試中出現的頻率不低，值得熟悉其核心思路：用 rolling hash 避免每次從頭計算雜湊值。

AVL Trees（AVL 樹）#

AVL 樹是實作樹平衡的兩種常見方法之一，透過限制每個節點左右子樹高度差不超過 1 來防止樹過度傾斜。

平衡條件#

每個節點儲存其子樹的高度：

balance(n) = n.left.height - n.right.height
-1 <= balance(n) <= 1

插入後的旋轉修復#

插入後若某節點的平衡值變為 ±2，需透過旋轉修復。旋轉分為左旋與右旋，右旋為左旋的鏡像。

Case 1：balance == 2（左子樹過高）

  • LEFT LEFT SHAPE（左子樹的額外節點在左側）→ 直接右旋得到 BALANCED
  • LEFT RIGHT SHAPE（左子樹的額外節點在右側）→ 先對左子樹左旋（變成 LEFT LEFT SHAPE），再右旋得到 BALANCED

Case 2：balance == -2（右子樹過高）

為 Case 1 的鏡像，對應 RIGHT RIGHT SHAPE 與 RIGHT LEFT SHAPE。

遞迴向上修復，若某子樹的平衡值達到 0，代表該子樹高度未變，可提前終止。

AVL Tree：Right-Right Shape 經 Left Rotation 恢復平衡

Red-Black Trees（紅黑樹）#

紅黑樹是另一種自平衡 BST，不保證嚴格的 AVL 平衡，但能確保 O(log N) 的插入、刪除與查找。它使用較少記憶體且再平衡速度更快，適合頻繁修改的場景。

Red-Black Tree 範例：紅色節點（灰色標示）與黑色節點交替

五大性質#

  1. 每個節點為紅色或黑色
  2. 根節點為黑色
  3. 葉節點（NULL）視為黑色
  4. 每個紅色節點的子節點必須為黑色（即路徑上不能出現連續紅色節點）
  5. 從任一節點到其後代葉節點的所有路徑，黑色節點數量相同

為何能保持平衡#

設某路徑有 b 個黑色節點：

  • 最短路徑（全黑）：b 個節點
  • 最長路徑（紅黑交替）：2b 個節點

因此任意兩條路徑長度之比不超過 2 倍，足以保證 O(log N) 的操作。

插入操作#

新節點插入為紅色葉節點，附帶兩個黑色 NULL 葉節點，再修復可能的違規：

  • 紅色違規（Red Violation）：紅色節點的子節點也是紅色
  • 黑色違規（Black Violation）：某路徑的黑色節點數多於另一路徑

修復邏輯依叔父節點（U）的顏色與相對位置分為兩大情況：

Case 1：U 為紅色

將 P（父）、U（叔）從紅色翻轉為黑色，G（祖父）從黑色翻轉為紅色，再遞迴處理 G 可能引發的新違規。

Case 2：U 為黑色

依 N 與 P 的左右子關係分為 4 種子情況（A、B、C、D），透過旋轉與換色解決違規，同時保持 BST 的中序性質與各路徑黑色節點數一致。

Case 2A（修復前）：N 和 P 都是左子節點

Case 2A（修復後）：旋轉並重新著色後恢復平衡

MapReduce#

MapReduce 是廣泛用於大規模資料處理的分散式計算框架。程式設計師只需撰寫 Map 與 Reduce 兩個步驟，其餘由系統處理。

執行流程#

  1. 系統將資料分散到多台機器
  2. 每台機器執行使用者提供的 Map 程式
  3. Map 程式讀取資料，輸出 <key, value> 配對
  4. 系統的 Shuffle 流程將相同 key 的配對路由到同一台機器
  5. Reduce 程式接收一個 key 與對應的所有 value，將它們「歸納」成新的 <key, value> 輸出

範例：統計詞頻#

void map(String name, String document) {
    for each word w in document:
        emit(w, 1)
}

void reduce(String word, Iterator partialCounts) {
    int sum = 0
    for each count in partialCounts:
        sum += count
    emit(word, sum)
}

範例：計算各城市每年平均氣溫#

  • Map：輸出 (City_Year, (Temperature, 1))
  • Reduce：接收特定城市年份的所有氣溫資料，計算加權平均

由於 Reduce 可能分批接收部分資料，必須追蹤溫度總和與資料點數量（加權平均），避免直接對中間結果取平均。

MapReduce 詞頻統計流程：Input → Split → Map → Shuffle → Reduce → Final

設計 MapReduce 方案時，建議先思考 Reduce 步驟需要什麼資料，再反向設計 Map 步驟的輸出格式。

Additional Studying（延伸學習）#

以下主題值得進一步探索，但超出本書範疇：

  • Bellman-Ford Algorithm：單源最短路徑，支援負權重邊
  • Floyd-Warshall Algorithm：所有節點對之間的最短路徑，支援負權重邊（但不能有負環）
  • Minimum Spanning Trees：連通加權無向圖中，總權重最小的生成樹
  • B-Trees：磁碟或儲存裝置上常用的自平衡搜尋樹，比 BST 減少 I/O 操作
  • A*：結合 Dijkstra 與啟發式函數的最短路徑演算法
  • Interval Trees：儲存區間（低-高範圍）的平衡 BST，支援高效區間查詢
  • Graph Coloring：對圖的節點著色，使相鄰節點顏色不同
  • P, NP, NP-Complete：計算複雜度類別的理論基礎
  • Combinatorics & Probability：隨機變數、期望值、n-choose-k
  • Bipartite Graph：節點可分為兩個集合、每條邊跨越兩集合的圖
  • Regular Expressions：正規表達式的語法與匹配演算法

若要深入學習演算法，作者推薦 Introduction to Algorithms（Cormen, Leiserson, Rivest & Stein，即「CLRS」）或 The Algorithm Design Manual（Steven Skiena）。

Backward X. Solutions XII. Code Library Forward