資深 PHP 後端工程師面試指南：演算法與時間複雜度

作為資深 PHP 後端工程師，面試中除了系統設計與框架知識外，演算法與時間複雜度分析是展現技術深度的重要部分。本文針對 PHP 後端開發場景，整理出七大類常見演算法問題，涵蓋模擬問答、PHP 程式碼範例、演算法分析、時間與空間複雜度，以及實戰建議。內容不僅幫助你在面試中脫穎而出，也適合技術創作者轉化為影片或部落格教學。

1. 陣列與資料處理

問題：如何在 PHP 中實現一個函數，找出陣列中出現次數最多的元素（眾數）？

回答要點：

使用哈希表（關聯陣列）記錄每個元素的出現次數。
遍歷哈希表，找出出現次數最多的元素。
討論邊界情況，如多個眾數或空陣列。

模擬答案：

演算法：使用哈希表統計元素頻次，然後線性掃描找出最大頻次。
邊界處理：檢查陣列是否為空，若多個元素頻次相同，返回其中之一。
優化：若需返回所有眾數，可修改為記錄所有最大頻次元素。

範例程式碼：

function findMode(array $arr): ?int {
    if (empty($arr)) return null;
    
    $freq = [];
    // 統計頻次
    foreach ($arr as $num) {
        $freq[$num] = ($freq[$num] ?? 0) + 1;
    }
    
    $maxCount = 0;
    $mode = null;
    // 找出最大頻次
    foreach ($freq as $num => $count) {
        if ($count > $maxCount) {
            $maxCount = $count;
            $mode = $num;
        }
    }
    
    return $mode;
}

// 測試
$arr = [1, 2, 2, 3, 3, 3, 4];
echo findMode($arr); // 輸出：3

時間與空間複雜度：

時間複雜度：O(n)，其中 n 是陣列長度。第一次遍歷統計頻次 O(n)，第二次遍歷找出最大頻次 O(k)，其中 k ≤ n。
空間複雜度：O(k)，其中 k 是不同元素的數量，用於儲存哈希表。

實戰建議：面試時可補充如何處理多眾數情況（返回陣列），或討論若資料流式輸入（無法一次載入記憶體）如何使用線上演算法（如 Boyer-Moore 投票演算法的變形）。

2. 字串處理

問題：如何檢查兩個字串是否為字母異位詞（anagram）？

回答要點：

字母異位詞指字元組成相同但順序不同的字串。
使用哈希表或排序法解決。
討論大小寫敏感與非字母字元的處理。

模擬答案：

演算法：將兩個字串轉為字元陣列，排序後比較是否相等。
替代方案：使用哈希表記錄字元頻次，比較兩個字串的頻次表。
邊界處理：檢查字串長度是否相等，處理空字串或無效輸入。

範例程式碼（排序法）：

function isAnagram(string $s, string $t): bool {
    if (strlen($s) !== strlen($t)) return false;
    
    $sArr = str_split(strtolower($s));
    $tArr = str_split(strtolower($t));
    sort($sArr);
    sort($tArr);
    
    return $sArr === $tArr;
}

// 測試
echo isAnagram("listen", "silent") ? "True" : "False"; // 輸出：True

時間與空間複雜度：

時間複雜度：O(n log n)，其中 n 是字串長度，來自排序操作。
空間複雜度：O(n)，用於儲存字元陣列。
替代方案（哈希表法）：
- 時間複雜度：O(n)，遍歷字串統計頻次。
- 空間複雜度：O(1)，因為字母表大小固定（如 26 個小寫字母）。

實戰建議：面試時可比較排序法與哈希表法的優缺點（排序法簡單但較慢，哈希表法更快但需額外空間），並提到如何處理 Unicode 字元。

3. 搜尋與排序

問題：如何在已排序的陣列中實現二分搜尋？

回答要點：

二分搜尋適用於已排序陣列，時間複雜度為 O(log n)。
說明遞迴與迭代實現的差異。
討論邊界情況，如目標值不存在或陣列為空。

模擬答案：

演算法：使用迭代二分搜尋，通過比較中間元素與目標值，縮小搜尋範圍。
邊界處理：若目標值不存在，返回 -1；檢查陣列是否為空。
優化：若需要查找第一個或最後一個出現的位置，可調整邏輯。

範例程式碼：

function binarySearch(array $arr, int $target): int {
    $left = 0;
    $right = count($arr) - 1;
    
    while ($left <= $right) {
        $mid = (int)(($left + $right) / 2);
        if ($arr[$mid] === $target) {
            return $mid;
        } elseif ($arr[$mid] < $target) {
            $left = $mid + 1;
        } else {
            $right = $mid - 1;
        }
    }
    
    return -1;
}

// 測試
$arr = [1, 3, 5, 7, 9];
echo binarySearch($arr, 5); // 輸出：2

時間與空間複雜度：

時間複雜度：O(log n)，每次迭代將搜尋範圍減半。
空間複雜度：O(1)，僅使用常數級變數。

實戰建議：面試時可補充如何處理「查找第一個出現位置」的情況，並提到二分搜尋在資料庫索引查詢中的應用（如 MySQL B+樹）。

4. 樹與圖結構

問題：如何遍歷一棵二元樹（例如前序遍歷）？

回答要點：

說明二元樹遍歷的三種方式：前序（根-左-右）、中序（左-根-右）、後序（左-右-根）。
使用遞迴或迭代（堆疊）實現。
討論在後端場景中的應用，如解析 JSON 樹狀結構。

模擬答案：

演算法：使用遞迴實現前序遍歷，先訪問根節點，再遍歷左子樹與右子樹。
邊界處理：檢查根節點是否為空。
替代方案：使用堆疊實現迭代版本，適合同等邏輯但記憶體受限的情況。

範例程式碼：

class TreeNode {
    public $val;
    public $left;
    public $right;
    public function __construct($val = 0) {
        $this->val = $val;
        $this->left = null;
        $this->right = null;
    }
}

function preorderTraversal(TreeNode $root): array {
    $result = [];
    if ($root === null) return $result;
    
    $result[] = $root->val;
    $result = array_merge($result, preorderTraversal($root->left));
    $result = array_merge($result, preorderTraversal($root->right));
    
    return $result;
}

// 測試
$root = new TreeNode(1);
$root->left = new TreeNode(2);
$root->right = new TreeNode(3);
print_r(preorderTraversal($root)); // 輸出：[1, 2, 3]

時間與空間複雜度：

時間複雜度：O(n)，其中 n 是樹的節點數，每個節點訪問一次。
空間複雜度：O(h)，其中 h 是樹的高度，用於遞迴調用堆疊（平均 O(log n)，最差 O(n)）。

實戰建議：面試時可提到樹結構在後端的應用，如解析 XML/JSON 或資料庫查詢計畫，並比較遞迴與迭代實現的記憶體使用。

5. 動態規劃

問題：如何計算費氏數列（Fibonacci）第 n 項，優化記憶體與效能？

回答要點：

費氏數列定義：F(n) = F(n-1) + F(n-2)，F(0) = 0，F(1) = 1。
比較遞迴、記憶化遞迴與迭代實現。
討論在後端場景中的應用，如快取計算或分頁查詢優化。

模擬答案：

演算法：使用迭代法計算費氏數列，避免遞迴的冗餘計算。
邊界處理：檢查 n 是否為負數或非整數。
優化：僅儲存前兩個數，減少空間使用。

範例程式碼：

function fibonacci(int $n): int {
    if ($n < 0) return 0;
    if ($n <= 1) return $n;
    
    $prev = 0;
    $curr = 1;
    for ($i = 2; $i <= $n; $i++) {
        $next = $prev + $curr;
        $prev = $curr;
        $curr = $next;
    }
    
    return $curr;
}

// 測試
echo fibonacci(10); // 輸出：55

時間與空間複雜度：

時間複雜度：O(n)，迭代 n 次。
空間複雜度：O(1)，僅使用兩個變數。
替代方案（記憶化遞迴）：
- 時間複雜度：O(n)，每個子問題計算一次。
- 空間複雜度：O(n)，用於儲存記憶化表。

實戰建議：面試時可補充如何將動態規劃應用於後端問題，如計算分頁資料的總和或快取查詢結果，並提到如何用 Redis 實現記憶化。

6. 快取與資料結構優化

問題：如何設計一個 LRU 快取（最近最少使用）？

回答要點：

LRU 快取需快速存取與淘汰最近最少使用的元素。
使用雙向鏈結串列（快速插入/刪除）與哈希表（快速查找）實現。
討論在後端場景中的應用，如快取資料庫查詢結果。

模擬答案：

演算法：使用哈希表儲存鍵值對，雙向鏈結串列維護訪問順序。
操作：
- get(key)：若鍵存在，返回值並將節點移到鏈結串列頭部。
- put(key, value)：插入或更新鍵值，若超出容量，移除鏈結串列尾部節點。
邊界處理：檢查快取容量與無效鍵。

範例程式碼：

class LRUCache {
    private $capacity;
    private $cache = [];
    private $head;
    private $tail;
    
    public function __construct(int $capacity) {
        $this->capacity = $capacity;
        $this->head = new stdClass();
        $this->tail = new stdClass();
        $this->head->next = $this->tail;
        $this->tail->prev = $this->head;
    }
    
    public function get(int $key): int {
        if (!isset($this->cache[$key])) return -1;
        
        $node = $this->cache[$key];
        $this->moveToHead($node);
        return $node->value;
    }
    
    public function put(int $key, int $value): void {
        if (isset($this->cache[$key])) {
            $node = $this->cache[$key];
            $node->value = $value;
            $this->moveToHead($node);
        } else {
            $node = new stdClass();
            $node->key = $key;
            $node->value = $value;
            $this->cache[$key] = $node;
            $this->addToHead($node);
            
            if (count($this->cache) > $this->capacity) {
                $last = $this->tail->prev;
                $this->removeNode($last);
                unset($this->cache[$last->key]);
            }
        }
    }
    
    private function addToHead($node): void {
        $node->next = $this->head->next;
        $node->prev = $this->head;
        $this->head->next->prev = $node;
        $this->head->next = $node;
    }
    
    private function removeNode($node): void {
        $node->prev->next = $node->next;
        $node->next->prev = $node->prev;
    }
    
    private function moveToHead($node): void {
        $this->removeNode($node);
        $this->addToHead($node);
    }
}

// 測試
$cache = new LRUCache(2);
$cache->put(1, 1);
$cache->put(2, 2);
echo $cache->get(1); // 輸出：1
$cache->put(3, 3);
echo $cache->get(2); // 輸出：-1

時間與空間複雜度：

時間複雜度：O(1)，get 和 put 操作均為常數時間（哈希表查找與鏈結串列操作）。
空間複雜度：O(capacity)，儲存哈希表與雙向鏈結串列。

實戰建議：面試時可提到 LRU 快取在後端的應用，如 Redis 或 Memcached 的快取策略，並討論如何處理高併發下的鎖機制。

7. 資料庫查詢優化

問題：如何優化一個查詢頻繁的資料表，找出前 k 個最活躍使用者？

回答要點：

使用索引與聚合查詢優化資料庫性能。
結合演算法（如 Top-K 堆積演算法）處理大量資料。
討論快取與分頁查詢的應用。

模擬答案：

演算法：
- 資料庫層：使用 SQL 查詢統計使用者活躍次數，加入索引加速查詢。
- 程式層：若資料量大，使用最小堆找出前 k 個活躍使用者。
邊界處理：檢查 k 是否有效，處理無資料情況。
優化：使用快取（如 Redis）儲存查詢結果，減少資料庫負載。

範例程式碼（SQL + PHP 堆積實現）：

-- 假設資料表：user_activities(user_id, activity_count)
CREATE INDEX idx_activity_count ON user_activities(activity_count);
SELECT user_id, activity_count 
FROM user_activities 
ORDER BY activity_count DESC 
LIMIT 10;

function topKActiveUsers(array $users, int $k): array {
    $heap = new SplMinHeap();
    foreach ($users as $user) {
        $heap->insert([$user['activity_count'], $user['user_id']]);
        if ($heap->count() > $k) {
            $heap->extract();
        }
    }
    
    $result = [];
    while (!$heap->isEmpty()) {
        $result[] = $heap->extract();
    }
    return array_reverse($result);
}

// 測試
$users = [
    ['user_id' => 1, 'activity_count' => 100],
    ['user_id' => 2, 'activity_count' => 150],
    ['user_id' => 3, 'activity_count' => 80],
    ['user_id' => 4, 'activity_count' => 200]
];
$k = 2;
print_r(topKActiveUsers($users, $k)); // 輸出：[[200, 4], [150, 2]]

時間與空間複雜度：

時間複雜度：
- 資料庫查詢：O(n log n)（若無索引，排序所需）；加索引後約 O(log n)。
- 程式層（堆積演算法）：O(n log k)，遍歷 n 個使用者，堆操作為 O(log k)。
空間複雜度：O(k)，用於儲存最小堆。

實戰建議：面試時可補充如何用 Redis 快取 Top-K 結果，或討論分頁查詢如何結合堆積演算法處理大規模資料。

總結與面試建議

面試技巧

結構化回答：將答案分為「問題分析 → 演算法選擇 → 程式碼實現 → 複雜度分析」，展現邏輯清晰。
展示實戰經驗：結合後端場景（如快取、資料庫查詢）說明演算法應用。
強調優化思維：提到如何用索引、快取或資料結構優化性能。

進階學習資源

演算法基礎：《Introduction to Algorithms》或 LeetCode PHP 題目練習。
PHP 資料結構：學習 PHP 的 Spl 資料結構（如 SplMinHeap、SplDoublyLinkedList）。
資料庫優化：閱讀《High Performance MySQL》或 Redis 官方文件。

透過反覆練習這些模擬問答，並結合 PHP 後端場景，你將能在面試中自信展現演算法與時間複雜度知識！若需將本文轉化為影片腳本或補充視覺化圖表（如樹遍歷流程圖），請隨時告訴我。

AI 驅動的開發新境：羅培宸的實戰碼匠術

2025年9月29日星期一