白板程式設計 (Whiteboard Coding)：斐波那契數列實戰#

以斐波那契數列為例，展示如何在面試中從暴力解逐步最佳化到最優解。

解法演進#

暴力遞迴 O(2ⁿ)#

最直觀的解法，直接定義 $f(n) = f(n-1) + f(n-2)$：

fun fib(n: Int): Long {
    if (n <= 1) return n.toLong()
    return fib(n - 1) + fib(n - 2)
}

存在大量重複計算。例如計算 $f(5)$ 需要計算 $f(4)$ 和 $f(3)$，而計算 $f(4)$ 時又要計算一次 $f(3)$。當 $n=40$ 時，程式執行速度將變得極慢。（回傳型別用 Long：斐波那契數成長極快，Int 在 $n=47$ 附近就會溢位。）

記憶化遞迴 O(n)#

加上快取，避免重複計算：

fun fib(n: Int, memo: HashMap<Int, Long> = HashMap()): Long {
    if (n <= 1) return n.toLong()
    // getOrPut：不存在時才計算並存入，等同 Python 的 memo 檢查
    return memo.getOrPut(n) { fib(n - 1, memo) + fib(n - 2, memo) }
}

動態規劃 O(n)#

正推方式，只保留前兩個狀態：

fun fib(n: Int): Long {
    if (n <= 1) return n.toLong()
    var prev = 0L
    var curr = 1L
    for (i in 2..n) {
        val next = prev + curr   // Kotlin 無多重賦值，用臨時變數推進
        prev = curr
        curr = next
    }
    return curr
}

矩陣快速冪 O(log n)#

斐波那契數列求第 $n$ 項的最優解法是矩陣快速冪，時間複雜度為 O(log n)。

矩陣快速冪原理#

構造狀態矩陣#

找到常數矩陣 $M$，使得：

$$ \begin{bmatrix} F_n \ F_{n-1} \end{bmatrix} = M \times \begin{bmatrix} F_{n-1} \ F_{n-2} \end{bmatrix} $$

根據斐波那契定義：

• $F_n = 1 \cdot F_{n-1} + 1 \cdot F_{n-2}$
• $F_{n-1} = 1 \cdot F_{n-1} + 0 \cdot F_{n-2}$

得到常數矩陣：

$$ M = \begin{bmatrix} 1 & 1 \ 1 & 0 \end{bmatrix} $$

轉化為冪運算#

展開遞推：

$$ \begin{bmatrix} F_n \ F_{n-1} \end{bmatrix} = M^{n-1} \times \begin{bmatrix} F_1 \ F_0 \end{bmatrix} $$

求解 $F_n$ 轉化為求解 $M^{n-1}$，套用快速冪演算法即可達到 O(log n)。

升維思想：在一維遞推中只能達到 O(n)。引入矩陣後，利用數學結構「摺疊」計算過程，實作指數級加速。

快速冪演算法#

核心思想#

利用 $x^n = x^{n/2} \times x^{n/2}$ 的性質，將規模減半。

二進位迭代法（推薦）#

將 $n$ 視為二進位串。例如 $x^{10}$，$10$ 的二進位是 1010，即 $x^8 \times x^2$。

fun myPow(x: Double, n: Int): Double {
    var base = x
    var exp = n.toLong()   // 轉 Long：避免 n = Int.MIN_VALUE 時 -n 溢位

    if (exp < 0) {
        base = 1 / base
        exp = -exp
    }

    var result = 1.0
    var currentProduct = base
    while (exp > 0) {
        if (exp and 1L == 1L) {              // 當前位元是 1
            result *= currentProduct
        }
        currentProduct *= currentProduct     // 權重翻倍
        exp = exp shr 1                       // 處理下一位
    }
    return result
}

這裡刻意把指數轉成 Long。Python 整數任意精度，n = -n 永遠安全；但 Kotlin 的 Int 是 32 位，若 n == Int.MIN_VALUE，-n 會溢位（正好對應下方 Clarification 提醒的邊界）。先擴成 Long 再取負就萬無一失。

位元運算技巧：

• n & 1 判斷奇偶（等價於 n % 2 == 1）
• n >> 1 右移一位（等價於 n / 2）

面試中的 Clarification#

遇到 pow(x, n) ^↗ 這類題目，務必先確認邊界條件：

• $n$ 可以是負數嗎？
• $x$ 可以是 $0$ 嗎？（$0$ 的負數次方會導致除以零）
• 需要處理整數溢位嗎？（如 $n = \text{INT_MIN}$ 時，$-n$ 會溢位）

Clarification 比直接寫出程式碼更重要。這展示了你的工程思維與嚴謹性。

遞迴模板#

面試中使用遞迴時，遵循以下四步驟：

1. Terminator：終止條件
2. Process：處理當前層邏輯
3. Drill Down：下探到下一層
4. Clear Status：清理當前層狀態（若需要）

能夠看出程式碼的「壞味道」並進行重構，是工程師進階的必經之路。例如將 n % 2 最佳化為 n & 1，不僅是效能提升，更是對底層邏輯理解的展現。

探索設計空間：別跳進第一個解法#

面試真正的加分點，不是「快速寫出第一個想到的解」，而是提出多個方案並比較取捨。埋頭就寫，等於放棄了展示判斷力的機會。

正確節奏是：先用虛擬碼勾勒兩三種思路，講清楚每種的時間／空間取捨，再選定一個動手實作。

把「先講方案、再比較、最後挑一個」說出口，面試官就能看見你的思考過程，而不只是結果。如何系統化地產生與比較這些方案，可參考 面試準備 中的 BUD（找 Bottlenecks／Unnecessary work／Duplicated work）與 BCR（Best Conceivable Runtime）方法。

即使最終實作的是最樸素的解，「我先評估過更快的做法、權衡後選這個」這句話本身就有價值。沉默地寫出唯一一版程式碼，反而看不出你會不會權衡。

好程式碼的五個特性#

寫完不是只要「能跑」，面試官真正在評估的是程式碼品質。一段好程式碼同時具備五個特性：

把這五點落地，常見的具體做法有：

• 善用資料結構：選對結構（如用雜湊表做 O(1) 查找）往往比硬寫邏輯更乾淨也更快。
• 適當複用：重複出現的邏輯抽成函式，別到處複製貼上。
• 模組化：把大函式拆成各司其職的小函式，可讀也可測。
• 別 hardcode：魔術數字與寫死的值改成具名常數或參數。
• 檢查輸入：別假設輸入一定合法——對 null、空集合、越界先做防禦。

這五個特性常常彼此拉扯（例如極致的高效可能犧牲簡潔）。面試時把取捨講出來，比硬要五項全滿更能展現成熟度。

寫完後的「聰明測試」#

寫完程式碼後別急著從頭隨便代數字——那樣既慢又容易漏掉真正的問題。按以下順序檢查，效率最高：

1. Conceptual（概念檢查）：像做 code review 一樣逐行讀過，每一行都問「這行為什麼是對的」。先在腦中確認邏輯成立，再談跑數字。
2. 看起來怪的程式碼：盯住容易出錯的寫法——x - 2 這類偏移、從 1 開始（而非 0）的迴圈、< 與 <= 的邊界。這些地方往往就是 bug 藏身處。
3. Hot spots（熱點）：聚焦最容易爆的位置——遞迴的 base case、整數除法（截斷與除以零）、null 節點、鏈結串列的頭與尾。
4. 小型測試案例：用 3 ～ 4 個元素就好，別用一大串。小到能心算、又大到能涵蓋一般情況，最划算。
5. 特殊案例：最後才補上 null、單一元素、極值、空輸入這些邊界。

找到 bug 後，先停下來分析「為什麼會錯」，別急著套上第一個想到的修補。倉促的修補常常只壓掉表面症狀，甚至引入新 bug；理解根因後的修正才會一次到位。