PHP 資深工程師面試必備：六大經典演算法問題解析與實戰、什麼是時間複雜度？

前言：演算法，資深 PHP 工程師的試金石

在 PHP 的世界裡，我們常常與框架、資料庫、API 互動，但當面臨資深工程師的職位時，面試官往往會回歸到程式設計的本質：演算法與資料結構。這不僅考驗你的邏輯思維，更衡量你解決問題的深度與程式碼的效率。

本文將為你精選六個 PHP 資深工程師面試中常見的演算法問題，從基礎的字串操作到進階的資料結構設計。每個問題都附上詳細的解法思路和 PHP 程式碼範例，希望能幫助你在面試中脫穎而出！

---

1. 反轉字串：理解基礎操作與雙指針技巧

問題描述：給定一個字串，請在不使用 PHP 內建 strrev 函數的情況下，將其反轉並返回結果。

解法思路：最直觀且高效的方法是使用雙指針（two-pointer）。想像字串的兩端各有一個指針，我們不斷交換它們指向的字符，然後將兩個指針向中間移動，直到它們相遇或交錯。

PHP 程式碼範例：

PHP

function reverseString($str) {
    $chars = str_split($str); // 將字串轉為陣列以便操作字符
    $left = 0;
    $right = count($chars) - 1;

    while ($left < $right) {
        // 交換左右指針的字符
        $temp = $chars[$left];
        $chars[$left] = $chars[$right];
        $chars[$right] = $temp;
        $left++;
        $right--;
    }

    return implode('', $chars); // 將陣列轉回字串
}

// 測試
echo reverseString("Hello, World!"); // 輸出: !dlroW ,olleH

為何常見？ 這個問題看似簡單，卻能有效檢驗候選人對字串基本操作的理解，以及如何運用指針邏輯來解決問題。同時，它也展現了你對 PHP 陣列操作的熟悉度。

---

2. 兩數之和：掌握哈希表的威力

問題描述：給定一個整數陣列 nums 和一個目標值 target，找出陣列中兩個數字的索引，使得它們的和等於 target。假設每個輸入只有一個解，且同一個元素不能重複使用。

解法思路：解決這個問題的關鍵在於時間複雜度。如果使用暴力法（雙重迴圈），時間複雜度將是 O(n2)。更優雅的解法是利用哈希表（Hash Table），在 PHP 中即為關聯陣列。

遍歷陣列時，對於每個數字 num，我們計算出它與 target 的差值 complement。然後檢查哈希表中是否已經存在這個 complement。如果存在，我們就找到了答案；如果不存在，則將當前數字 num 及其索引存入哈希表，以便後續查找。這樣能將時間複雜度優化到 O(n)。

PHP 程式碼範例：

PHP

function twoSum($nums, $target) {
    $map = []; // 用於儲存已遍歷數字的哈希表 (關聯陣列: [數字 => 索引])

    foreach ($nums as $i => $num) {
        $complement = $target - $num;
        // 檢查哈希表中是否存在 complement
        if (isset($map[$complement])) {
            return [$map[$complement], $i];
        }
        // 將當前數字及其索引存入哈希表
        $map[$num] = $i;
    }

    return []; // 無解的情況 (根據題目假設，通常不會發生)
}

// 測試
$nums = [2, 7, 11, 15];
$target = 9;
print_r(twoSum($nums, $target)); // 輸出: Array ( [0] => 0 [1] => 1 )

為何常見？ 這是一個經典的問題，用來考驗候選人對哈希表的應用能力，以及如何將時間複雜度從 O(n2) 降低到 O(n) 的優化思維。PHP 關聯陣列的特性，讓哈希表的實現變得非常直觀。

---

3. 檢查回文數：數字與字串的巧妙轉換

問題描述：給定一個整數，判斷它是否是回文數（即正序和倒序讀起來都相同，例如 121）。

解法思路：有兩種常見思路。

1. 字串轉換法：將數字轉換為字串，然後使用類似反轉字串的雙指針方法進行比較。
2. 數學計算法：不將數字轉換為字串，而是通過數學運算將數字反轉，然後與原數字進行比較。這種方法更能展現對數字操作的熟練度。

我們這裡採用數學計算法來示範：

PHP 程式碼範例 (數學方式)：

PHP

function isPalindrome($num) {
    if ($num < 0) return false; // 負數不可能是回文數

    $reversed = 0;
    $original = $num; // 保存原始數字，用於最後比較

    while ($num > 0) {
        $digit = $num % 10; // 取出最低位數字
        $reversed = $reversed * 10 + $digit; // 將數字加入反轉數的末尾
        $num = (int)($num / 10); // 移除最低位數字
    }

    return $reversed === $original;
}

// 測試
echo "121 是回文數嗎？ " . (isPalindrome(121) ? 'true' : 'false') . "\n"; // 輸出: true
echo "123 是回文數嗎？ " . (isPalindrome(123) ? 'true' : 'false') . "\n"; // 輸出: false

為何常見？ 這個問題考驗你對數字的數學邏輯處理能力，以及是否能細心考慮邊界情況（例如負數或個位數）。

---

4. 合併兩個有序陣列：指針藝術與原地操作

問題描述：給定兩個已排序的整數陣列 nums1 和 nums2，以及它們包含的有效元素數量 m 和 n。請將 nums2 合併到 nums1 中，使 nums1 成為一個有序陣列。假設 nums1 有足夠的空間來容納 nums2 中的所有元素。

解法思路：由於兩個陣列都是有序的，我們可以利用這一特性。最有效率的方法是從兩個陣列的末尾開始比較，將較大的元素放到 nums1 的末尾（因為 nums1 後面有足夠的空位）。這樣可以避免在陣列中間插入元素時頻繁移動元素，從而提高效率。

我們需要三個指針：分別指向 nums1 的有效元素末尾 (p1)、nums2 的末尾 (p2)，以及合併後 nums1 的末尾 (p)。

PHP 程式碼範例：

PHP

function mergeSortedArrays(&$nums1, $m, $nums2, $n) {
    $p1 = $m - 1; // nums1 的有效元素指針
    $p2 = $n - 1; // nums2 的指針
    $p = $m + $n - 1; // 合併後 nums1 的寫入指針

    // 當 nums2 還有元素時，不斷比較並寫入
    while ($p2 >= 0 && $p1 >= 0) {
        if ($nums1[$p1] > $nums2[$p2]) {
            $nums1[$p] = $nums1[$p1];
            $p1--;
        } else {
            $nums1[$p] = $nums2[$p2];
            $p2--;
        }
        $p--;
    }

    // 如果 nums2 還有剩餘元素 (代表 nums2 中有比 nums1 開頭更小的元素)
    while ($p2 >= 0) {
        $nums1[$p] = $nums2[$p2];
        $p2--;
        $p--;
    }
}

// 測試
$nums1 = [1, 3, 5, 0, 0, 0]; // nums1 有足夠的空間
$m = 3; // nums1 的有效元素數量
$nums2 = [2, 4, 6];
$n = 3; // nums2 的元素數量
mergeSortedArrays($nums1, $m, $nums2, $n);
print_r($nums1); // 輸出: Array ( [0] => 1 [1] => 2 [2] => 3 [3] => 4 [4] => 5 [5] => 6 )

為何常見？ 這個問題考驗你對陣列操作的熟練度、指針的靈活運用，以及如何在**原地（in-place）**進行操作，以達到最佳的空間複雜度。

---

5. 二元搜尋樹的驗證：遞迴與範圍約束

問題描述：給定一個二元樹的根節點，判斷它是否是一個有效的二元搜尋樹（Binary Search Tree, BST）。有效的 BST 需滿足以下條件：

• 每個節點的左子樹只包含小於當前節點的數。
• 每個節點的右子樹只包含大於當前節點的數。
• 左右子樹本身也必須是有效的 BST。

解法思路：解決 BST 驗證問題最常見且優雅的方法是使用遞迴。在遞迴過程中，我們需要維護一個有效的數值範圍 [min,max]。對於每個節點：

• 它的值必須在這個範圍內。
• 遞迴檢查左子樹時，新的最大值應該是當前節點的值。
• 遞迴檢查右子樹時，新的最小值應該是當前節點的值。

PHP 程式碼範例：

PHP

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

function isValidBST($root) {
    // 初始時，根節點的範圍是無限大
    return validate($root, PHP_INT_MIN, PHP_INT_MAX);
}

function validate($node, $min, $max) {
    // 空樹是有效的 BST
    if ($node === null) return true;

    // 檢查當前節點的值是否在有效範圍內
    if ($node->val <= $min || $node->val >= $max) return false;

    // 遞迴檢查左子樹：更新最大值為當前節點的值
    // 遞迴檢查右子樹：更新最小值為當前節點的值
    return validate($node->left, $min, $node->val) &&
           validate($node->right, $node->val, $max);
}

// 測試
$root = new TreeNode(2);
$root->left = new TreeNode(1);
$root->right = new TreeNode(3);
echo "BST 1 2 3 是有效的嗎？ " . (isValidBST($root) ? 'true' : 'false') . "\n"; // 輸出: true

$root2 = new TreeNode(5);
$root2->left = new TreeNode(1);
$root2->right = new TreeNode(4);
$root2->right->left = new TreeNode(3);
$root2->right->right = new TreeNode(6);
echo "BST 5 1 4(3,6) 是有效的嗎？ " . (isValidBST($root2) ? 'true' : 'false') . "\n"; // 輸出: false (因為4的左子樹3不符合BST規則，3應該比4小，但4的右子樹不能有小於5的數)

為何常見？ 這是資深工程師面試中常見的進階問題，它深入考驗你對樹結構、遞迴思維的理解，以及如何精確處理遞迴中的邊界條件和參數傳遞。PHP 對物件的操作也會在這類問題中被檢驗。

---

6. LRU 快取：複雜資料結構的整合應用

問題描述：設計一個 LRU（Least Recently Used，最近最少使用）快取。這個快取需要支持兩個主要操作：get(key) 和 put(key, value)。當快取達到其容量限制時，需要移除最近最少使用的項目。

解法思路：LRU 快取是經典的資料結構設計問題。它的核心是需要同時滿足：

1. O(1) 時間複雜度的 get 和 put 操作（用於快速查找和更新值）。
2. O(1) 時間複雜度的「最近使用」和「最少使用」的更新（用於淘汰機制）。

要實現這些目標，通常會結合使用哈希表（Hash Map）和雙向鏈表（Doubly Linked List）。哈希表用於快速查找 key 對應的 value 和鏈表節點；雙向鏈表則用於維護快取中 key 的使用順序。當一個 key 被訪問或更新時，它會被移動到鏈表的頭部（表示最近使用）；當快取滿時，鏈表尾部的 key（最少使用）將被移除。

在 PHP 中，雖然沒有內建的雙向鏈表，但我們可以巧妙地使用陣列來模擬雙向鏈表的行為，或者建立自定義的鏈表節點類。這裡我們提供一個使用 PHP 陣列模擬鏈表行為的簡化範例：

PHP 程式碼範例：

PHP

class LRUCache {
    private $capacity;
    private $cache = []; // 儲存 key-value 對 (模擬哈希表)
    private $order = []; // 儲存 key 的使用順序 (模擬雙向鏈表，頭部為最近使用，尾部為最少使用)

    public function __construct($capacity) {
        $this->capacity = $capacity;
    }

    public function get($key) {
        if (!isset($this->cache[$key])) {
            return -1; // 不存在
        }

        // 訪問後，更新其在 order 中的順序：移到最前面
        $this->updateOrder($key);
        return $this->cache[$key];
    }

    public function put($key, $value) {
        if (isset($this->cache[$key])) {
            // 如果 key 已存在，更新其值和順序
            $this->cache[$key] = $value;
            $this->updateOrder($key);
        } else {
            // 如果 key 不存在，檢查容量
            if (count($this->cache) >= $this->capacity) {
                // 容量已滿，移除最久未使用的 key (array_pop 移除尾部元素)
                $lruKey = array_pop($this->order);
                unset($this->cache[$lruKey]);
            }
            // 新增 key-value 對，並將其放到 order 的最前面 (array_unshift 添加到頭部)
            $this->cache[$key] = $value;
            array_unshift($this->order, $key);
        }
    }

    private function updateOrder($key) {
        // 從 order 中找到 key 並移除
        $index = array_search($key, $this->order);
        if ($index !== false) { // 確保 key 存在
            unset($this->order[$index]);
            // 重新索引陣列，避免空洞
            $this->order = array_values($this->order);
        }
        // 將 key 放到 order 的最前面 (表示最近使用)
        array_unshift($this->order, $key);
    }
}

// 測試
$cache = new LRUCache(2);
$cache->put(1, 1); // 快取: {1=1}, order: [1]
$cache->put(2, 2); // 快取: {1=1, 2=2}, order: [2, 1]
echo "Get 1: " . $cache->get(1) . "\n"; // 輸出: 1, 快取: {1=1, 2=2}, order: [1, 2]
$cache->put(3, 3); // 移除 key 2 (最少使用)，新增 key 3
                  // 快取: {1=1, 3=3}, order: [3, 1]
echo "Get 2: " . $cache->get(2) . "\n"; // 輸出: -1 (key 2 已被移除)
echo "Get 3: " . $cache->get(3) . "\n"; // 輸出: 3, 快取: {1=1, 3=3}, order: [3, 1]

為何常見？ 這是一個綜合性的資料結構設計問題，它不僅考驗你對哈希表和雙向鏈表的理解，更考驗你如何將這些概念整合起來，解決實際問題。同時，它也檢驗了你對 PHP 物件導向編程（OOP）和陣列操作的高級應用能力。

---

總結與展望

以上六個經典的演算法問題，涵蓋了字串、陣列、數學、樹、快取等多種常見的演算法和資料結構類型。它們的難度從基礎到進階，是衡量一位 PHP 資深工程師綜合能力的絕佳標準。

在面試過程中，除了正確寫出程式碼，更重要的是：

• 清晰地解釋你的解法思路：讓面試官理解你的思考過程。
• 考慮邊界條件（Edge Cases）：例如空輸入、負數、極值等。
• 分析時間和空間複雜度：展現你對程式碼效率的理解。
• 與面試官交流：這不僅是解題，更是展示你的溝通能力。

---

什麼是時間複雜度？

時間複雜度是衡量一個演算法執行效率的重要指標，它描述了演算法執行時間隨著輸入資料量增加而增長的趨勢。簡單來說，就是當你的程式處理的資料越來越多時，它需要花費的時間會怎麼變化。

我們通常使用**大 O 符號（Big O Notation）**來表示時間複雜度，例如 O(n)、O(n2)、O(logn) 等。這個符號只關心最主要的增長趨勢，而忽略常數因子和低階項，因為當資料量足夠大時，這些因素的影響微乎其微。

為什麼時間複雜度很重要？

1. 評估演算法效率：它能讓你預測演算法在處理大量資料時的表現，幫助你選擇最適合特定場景的演算法。
2. 優化程式碼：了解時間複雜度有助於識別程式碼中的效能瓶頸，從而進行有針對性的優化。
3. 面試必考：在軟體工程面試中，時間複雜度是衡量工程師對演算法理解深度的關鍵指標。

---

常見的時間複雜度類型

以下是一些常見的時間複雜度類型，從最優到最差排列：

---

1. O(1)：常數時間複雜度 (Constant Time)

• 定義：無論輸入資料量多大，演算法的執行時間都保持不變。
• 範例：
  • 存取陣列中特定索引的元素。
  • 哈希表（Hash Map）的查找、插入、刪除操作（在沒有哈希衝突的情況下）。
• 解釋：就像你打開抽屜拿東西，不管抽屜裡有多少東西，你找到特定物品所需的時間幾乎是固定的。

PHP

function getFirstElement($arr) {
    return $arr[0]; // 不管陣列有多大，取第一個元素的時間固定
}

---

2. O(logn)：對數時間複雜度 (Logarithmic Time)

• 定義：執行時間隨著輸入資料量的增加而非常緩慢地增加，通常每次操作都會將資料量減少一半。
• 範例：
  • 二分查找（Binary Search）：在一個有序陣列中查找元素。
• 解釋：想像你在電話簿裡找一個名字，你不會從頭翻到尾，而是每次都翻到中間，根據首字母判斷在哪一半。這樣每次查找的範圍都會減半，非常高效。

PHP

function binarySearch($arr, $target) {
    $left = 0;
    $right = count($arr) - 1;

    while ($left <= $right) {
        $mid = floor(($left + $right) / 2);
        if ($arr[$mid] == $target) {
            return $mid;
        } elseif ($arr[$mid] < $target) {
            $left = $mid + 1;
        } else {
            $right = $mid - 1;
        }
    }
    return -1;
}

---

3. O(n)：線性時間複雜度 (Linear Time)

• 定義：執行時間與輸入資料量成正比。如果資料量增加一倍，執行時間也大約增加一倍。
• 範例：
  • 遍歷一個陣列或鏈表。
  • 尋找陣列中的最大/最小值。
• 解釋：就像你讀一本書，頁數越多，讀完所需的時間就越長。

PHP

function sumArray($arr) {
    $sum = 0;
    foreach ($arr as $num) { // 需要遍歷所有元素
        $sum += $num;
    }
    return $sum;
}

---

4. O(nlogn)：線性對數時間複雜度 (Linearithmic Time)

• 定義：執行時間是線性時間和對數時間的乘積，通常在高效的排序演算法中出現。
• 範例：
  • 快速排序（Quick Sort）。
  • 歸併排序（Merge Sort）。
• 解釋：許多「分治」演算法的複雜度都是這種形式。每次將問題分解成更小的子問題，然後合併結果。

PHP

// 歸併排序的簡化概念 (實際實現較複雜)
function mergeSort($arr) {
    $n = count($arr);
    if ($n <= 1) {
        return $arr;
    }
    $mid = floor($n / 2);
    $left = mergeSort(array_slice($arr, 0, $mid));
    $right = mergeSort(array_slice($arr, $mid));
    // 合併操作會是 O(n)
    return merge($left, $right);
}

// 實際的 merge 函數會遍歷兩個子陣列
function merge($left, $right) {
    $result = [];
    $i = 0; $j = 0;
    while ($i < count($left) && $j < count($right)) {
        if ($left[$i] < $right[$j]) {
            $result[] = $left[$i++];
        } else {
            $result[] = $right[$j++];
        }
    }
    while ($i < count($left)) $result[] = $left[$i++];
    while ($j < count($right)) $result[] = $right[$j++];
    return $result;
}

---

5. O(n2)：平方時間複雜度 (Quadratic Time)

• 定義：執行時間與輸入資料量的平方成正比。通常出現在嵌套迴圈中。
• 範例：
  • 冒泡排序（Bubble Sort）。
  • 選擇排序（Selection Sort）。
  • 兩個嵌套迴圈遍歷陣列。
• 解釋：當你需要在一個陣列中找到所有可能的配對時，就可能遇到這種情況。資料量稍微增大，時間就會急劇增加。

PHP

function bubbleSort($arr) {
    $n = count($arr);
    for ($i = 0; $i < $n - 1; $i++) { // 外層迴圈 O(n)
        for ($j = 0; $j < $n - $i - 1; $j++) { // 內層迴圈 O(n)
            if ($arr[$j] > $arr[$j+1]) {
                $temp = $arr[$j];
                $arr[$j] = $arr[$j+1];
                $arr[$j+1] = $temp;
            }
        }
    }
    return $arr;
}

---

6. O(2n)：指數時間複雜度 (Exponential Time)

• 定義：執行時間隨輸入資料量呈指數級增長。這類演算法效率極低，通常只適用於非常小的資料量。
• 範例：
  • 遞迴計算費波那契數列（未優化版本）。
  • 旅行推銷員問題（暴力解）。
• 解釋：這種複雜度意味著每次增加一個資料，所需時間會翻倍。很快就會變得無法接受。

PHP

function fibonacci($n) {
    if ($n <= 1) {
        return $n;
    }
    // 每次呼叫會產生兩個新的遞迴呼叫，形成指數增長
    return fibonacci($n - 1) + fibonacci($n - 2);
}

---

7. O(n!)：階乘時間複雜度 (Factorial Time)

• 定義：執行時間隨輸入資料量的階乘增長。這是最差的複雜度之一，僅適用於極小資料量。
• 範例：
  • 生成所有可能的排列組合。
• 解釋：這類演算法的執行時間增長速度快到令人難以置信，基本上不可能用於實際應用。

PHP

// 生成所有排列的簡化概念 (實際實現較複雜)
function generatePermutations($arr) {
    // 內部會涉及到 n 次選擇，每次選擇後剩下 n-1 個選項，以此類推
    // 導致複雜度為 O(n!)
}

---

如何計算時間複雜度？

計算時間複雜度主要有以下幾個原則：

1. 只看最高次項：忽略常數和低階項。例如 $O(2n+5)$ 就是 O(n)，$O(n^2+n+100)$ 就是 O(n2)。
2. 加法原則：如果演算法包含多個獨立的步驟，總時間複雜度取其中最大的那個。例如一個 O(n) 的步驟後跟一個 O(n2) 的步驟，總複雜度是 O(n2)。
3. 乘法原則：如果一個操作在另一個操作內部重複執行（例如嵌套迴圈），則複雜度相乘。例如一個 O(n) 的迴圈內部有一個 O(m) 的迴圈，總複雜度是 $O(n\times m)$。如果 $m=n$，則為 O(n2)。
4. 遞迴：對於遞迴演算法，通常可以使用遞迴樹或主定理（Master Theorem）來分析。

---

結語

理解時間複雜度是每位開發者，特別是資深工程師的必備技能。它不僅能幫助你寫出更高效、更具擴展性的程式碼，也是你在技術面試中展現實力的重要環節。當你下次編寫程式時，不妨多思考一下，你的程式碼在處理大量資料時，它的「時間」會怎麼跑呢？

---