概述#

所謂的「puzzles」（腦筋急轉彎）是面試中最具爭議的題型，許多公司已明文禁止。即便如此，你仍可能遇到。好消息是，這類題目幾乎都能透過數學或邏輯推導出答案，而非單純靠技巧或文字遊戲。

本章介紹解題所需的核心知識和思維方式。

Prime Numbers（質數）#

每個正整數都可以分解為質數的乘積。例如：

84 = 2^2 * 3^1 * 5^0 * 7^1 * 11^0 * 13^0 * 17^0 * ...

整除性（Divisibility）#

若 x 能整除 y（寫作 x\y 或 mod(y, x) = 0），則 x 的質因數分解中的每個質數，都必須出現在 y 的質因數分解中。

設：

x = 2^j0 * 3^j1 * 5^j2 * 7^j3 * ...
y = 2^k0 * 3^k1 * 5^k2 * 7^k3 * ...

若 x\y，則對所有 i，ji <= ki。

由此推導：

• gcd(x, y) = 2^min(j0,k0) * 3^min(j1,k1) * 5^min(j2,k2) * ...
• lcm(x, y) = 2^max(j0,k0) * 3^max(j1,k1) * 5^max(j2,k2) * ...
• gcd * lcm = x * y（可自行推導驗證）

質數檢查（Checking for Primality）#

樸素做法：從 2 遍歷到 n-1，逐一檢查整除性，時間複雜度 O(n)。

boolean primeNaive(int n) {
    if (n < 2) {
        return false;
    }
    for (int i = 2; i < n; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

改良做法：只需遍歷到 sqrt(n)。原因：若 a 整除 n，必有對應的 b 使 a * b = n。若 a > sqrt(n)，則 b < sqrt(n)，所以 b 早已被檢查過。

boolean primeSlightlyBetter(int n) {
    if (n < 2) {
        return false;
    }
    int sqrt = (int) Math.sqrt(n);
    for (int i = 2; i <= sqrt; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

產生質數列表：Sieve of Eratosthenes（埃拉托斯特尼篩法）#

篩法是高效率生成質數列表的方式，核心原理：所有非質數都可被某個質數整除。

演算法步驟：

1. 建立從 2 到 max 的數字列表，全部標記為 true
2. 從 2 開始，將 2 的所有倍數標記為 false
3. 找下一個未被劃掉的數（即下一個質數），重複步驟 2
4. 持續到 sqrt(max)

boolean[] sieveOfEratosthenes(int max) {
    boolean[] flags = new boolean[max + 1];
    int count = 0;

    init(flags); // 將 0 和 1 設為 false，其餘設為 true
    int prime = 2;

    while (prime <= Math.sqrt(max)) {
        /* 劃掉 prime 的所有倍數 */
        crossOff(flags, prime);

        /* 找下一個 true 的值 */
        prime = getNextPrime(flags, prime);
    }

    return flags;
}

void crossOff(boolean[] flags, int prime) {
    // 從 prime*prime 開始，因為更小的倍數在之前的迭代中已被劃掉
    for (int i = prime * prime; i < flags.length; i += prime) {
        flags[i] = false;
    }
}

int getNextPrime(boolean[] flags, int prime) {
    int next = prime + 1;
    while (next < flags.length && !flags[next]) {
        next++;
    }
    return next;
}

一個優化是只使用奇數陣列，可將空間減半。

Probability（機率）#

機率建立在幾個基本定律上，可用 Venn 圖來直覺理解。

P(A and B)#

P(A and B) = P(B given A) * P(A)

範例：從 1 到 10 挑一個數，同時為偶數且 <= 5 的機率：

P(x is even and x <= 5)
= P(x is even | x <= 5) * P(x <= 5)
= (2/5) * (1/2)
= 1/5

由此可推導 Bayes’ Theorem（貝氏定理）：

P(A given B) = P(B given A) * P(A) / P(B)

P(A or B)#

P(A or B) = P(A) + P(B) - P(A and B)

需要減去交集，避免重複計算。

範例：從 1 到 10 挑一個數，為偶數或 <= 5 的機率：

P(x is even or x <= 5)
= P(x is even) + P(x <= 5) - P(x is even and x <= 5)
= 1/2 + 1/2 - 1/5
= 4/5

Independence（獨立事件）#

若 A 和 B 獨立（A 發生與否不影響 B），則：

P(A and B) = P(A) * P(B)

因為 P(B given A) = P(B)。

Mutual Exclusivity（互斥事件）#

若 A 和 B 互斥（A 發生則 B 不可能發生），則：

P(A or B) = P(A) + P(B)

因為 P(A and B) = 0。

獨立與互斥是完全不同的概念！ 兩個機率皆大於 0 的事件，不可能同時既是獨立又是互斥的。互斥意味著一個發生則另一個不發生；獨立意味著一個的發生對另一個毫無影響。

Start Talking（開始說話）#

遇到腦筋急轉彎時，不要驚慌。面試官想看到的是你解題的過程，而不是你直接說出答案。開口說出你的思路，展示你如何接近問題。

Develop Rules and Patterns（歸納規則與模式）#

解題時，將你發現的「規則」寫下來是非常有用的方法。

範例題目：你有兩條繩子，各自燃燒完需要整整一小時。繩子密度不均，所以燒一半長度不代表花半小時。你如何用這兩條繩子計時剛好 15 分鐘？

解題過程 - 逐步歸納規則：

• Rule 1：若一條繩子燃燒需 x 分鐘，另一條需 y 分鐘，可以計時 x+y 分鐘。
• Rule 2：若從兩端同時點燃一條需要 x 分鐘的繩子，它會在 x/2 分鐘後燃盡。
• Rule 3：若繩 1 需 x 分鐘，繩 2 需 y 分鐘，可以將繩 2 縮減為需要 (y-x) 或 (y-x/2) 分鐘的繩子。

完整解法：

1. 同時從兩端點燃繩 1，從單端點燃繩 2
2. 繩 1 燃盡（30 分鐘後），繩 2 剩餘 30 分鐘的燃燒時間
3. 此時從另一端點燃繩 2
4. 繩 2 再過 15 分鐘燃盡

將規則逐條寫下，可以幫助你記住已發現的資訊，並在此基礎上繼續推導。

Worst Case Shifting（最壞情況平衡）#

許多腦筋急轉彎是最小化最壞情況的問題。有效的技巧是嘗試「平衡」最壞情況。

經典範例：九球問題

你有 9 顆球，8 顆重量相同，1 顆較重。只用天平（只能比較輕重，不能量重量），最少幾次能找出重球？

錯誤思路：分成兩組 4 顆，第 9 顆放旁邊。

• 問題：這不平衡。第 9 顆只需一次就能確定（若前 8 顆一樣重），其他球卻需三次。

最壞情況平衡：改為分成三組，每組 3 顆。

• 第一次秤：放兩組各 3 顆。若相等，重球在第三組；若不等，在較重的那組。
• 無論如何，一次秤完後縮減到 3 顆。
• 第二次秤：從 3 顆中秤 2 顆。若相等，第 3 顆就是重球；若不等，較重的就是。

規律：N 顆球（N 可被 3 整除），用一次天平可縮減到 N/3 顆含重球的集合。

Algorithm Approaches（演算法思維）#

卡住時，考慮套用解演算法題的方法（第 67 頁起）。腦筋急轉彎往往就是去掉技術細節的演算法題。特別是 Base Case and Build 和 Do It Yourself (DIY) 兩種方法尤為有用。

本章面試題列表#