💻 資深 PHP 工程師面試題：五大陷阱與解法深度解析（附完整程式碼）
本文將以資深 PHP 工程師的視角，對五道常見的演算法與陷阱題提供完整、可直接執行的 PHP 8.x 程式碼、嚴謹的時間/空間複雜度分析，以及對 PHP 特性的陷阱防禦說明。
所有程式碼都經過精心設計，確保高效、穩定並能應對各種邊界情況。
🎯 1. 排序陷阱：穩定排序（Score 降冪，相同 Score 保留原始順序）
在 PHP 中，內建的 usort() 並不保證穩定性 (Stability)，這在業務場景中（如分頁或資料流）是個大問題。我們必須手動建立穩定排序機制。
程式碼與分析
PHP
<?php
/**
* 實現穩定排序：Score 降冪，相同 Score 時保留原始順序。
*
* @param array $items 待排序的陣列，每個元素包含 'score' 鍵。
* @return array 穩定排序後的陣列。
*/
function stableSortByScore(array $items): array
{
// 1. 為每個元素加上原始 index 作為 tie-breaker
// array_keys($items) 提供當前索引，確保即使輸入陣列不是從 0 開始，也能取得正確的相對位置。
$indexed = array_map(fn($item, $idx) => [
'score' => $item['score'],
'ts' => $item['timestamp'], // 雖然沒用到，但保留原始數據
'idx' => $idx, // 關鍵：原始索引
'orig' => $item, // 關鍵：保留原始物件
], $items, array_keys($items));
// 2. 使用 array_multisort（內部實現穩定，且效率高）
// 先按 score 降冪，再按 idx 升冪作為第二排序鍵。
$scores = array_column($indexed, 'score');
$idxs = array_column($indexed, 'idx');
// array_multisort() 是 PHP 陣列排序中最快的函式之一。
array_multisort($scores, SORT_DESC, $idxs, SORT_ASC, $indexed);
// 3. 只要原始物件，去除輔助資訊
return array_column($indexed, 'orig');
}
// ---------- 測試 ----------
$items = [
['score' => 100, 'timestamp' => 1], // idx 0
['score' => 200, 'timestamp' => 2], // idx 1
['score' => 100, 'timestamp' => 3], // idx 2
['score' => 300, 'timestamp' => 4], // idx 3
];
$sorted = stableSortByScore($items);
print_r($sorted);
輸出：
Array
(
[0] => Array([score] => 300 [timestamp] => 4)
[1] => Array([score] => 200 [timestamp] => 2)
[2] => Array([score] => 100 [timestamp] => 1) // 原始 idx 0
[3] => Array([score] => 100 [timestamp] => 3) // 原始 idx 2 (順序保留)
)
| 項目 | 描述 |
| 時間複雜度 | $O(N \log N)$ (由 array_multisort 決定) |
| 空間複雜度 | $O(N)$ (用於建立 $indexed 輔助陣列) |
陷阱與防禦說明
| 陷阱 | 防禦方式 | 為什麼這樣寫 |
usort() 不穩定 | 改用 array_multisort + 原始 Index | array_multisort 效率高且內部穩定，結合 idx 作為次要鍵，模擬出穩定的排序行為。 |
| 忘記保留原始順序 | 加入 idx 作為第二排序鍵 | 當 score 相等時，根據原始 idx 排序，保證順序與原始輸入一致。 |
| 物件被改寫 | 只回傳原始子陣列 orig | 避免將輔助排序的欄位（如 idx）洩露給呼叫者，保持介面乾淨。 |
🚀 2. 遞迴與記憶體陷阱：費氏數列（$fib(n)$）
純遞迴的費氏數列 (Fibonacci) 具有 $O(2^n)$ 的時間複雜度，且容易造成堆疊溢位 (Stack Overflow)。資深工程師應使用動態規劃 (Dynamic Programming) 進行優化。
程式碼與分析
PHP
<?php
/**
* 高效計算費氏數列 (Fibonacci Sequence)。
* 使用 Bottom-up DP (迭代法)，時間 O(n), 空間 O(1)。
*
* @param int $n 費氏數列的項次 (n >= 0)。
* @return int 第 n 項的值。
* @throws InvalidArgumentException $n 小於 0 時。
*/
function fib(int $n): int
{
if ($n < 0) throw new InvalidArgumentException('n must be non-negative.');
if ($n <= 1) return $n;
// Bottom-up DP，僅需 O(1) 空間儲存前兩項
$a = 0; // f(i-2)
$b = 1; // f(i-1)
// 從 f(2) 開始計算到 f(n)
for ($i = 2; $i <= $n; $i++) {
// [新 f(i-2), 新 f(i-1)] = [舊 f(i-1), 舊 f(i-1) + 舊 f(i-2)]
[$a, $b] = [$b, $a + $b];
}
return $b; // $b 即為 f(n)
}
// ---------- 測試 ----------
foreach ([0,1,2,10,40] as $n) {
echo "fib($n) = " . fib($n) . PHP_EOL;
}
| 項目 | 描述 |
| 時間複雜度 | $O(N)$ (僅一次循環) |
| 空間複雜度 | $O(1)$ (僅使用三個變數) |
陷阱與防禦說明
| 陷阱 | 防禦方式 | 為什麼這樣寫 |
| 純遞迴 $O(2^n)$ + 堆疊溢位 | 改用 迭代 DP，$O(N)$ 時間、$O(1)$ 空間 | 效率最高的解法，避免了遞迴的重複計算和記憶體消耗。 |
| 大數溢出（$N$ 超過 92） | 假設 int 足夠 (PHP 64-bit)。若需更大，改用 gmp_add() 或 bcadd()。 | PHP 64 位整數 約可計算到 $fib(92)$。此設計滿足一般要求，對極大數值應使用 PHP 的 Big Integer 擴展。 |
| $N$ 負數 | 明確拋例外 InvalidArgumentException | 避免未定義行為，符合函式設計的嚴謹性。 |
🔑 3. 字串處理陷阱：最長不重複子字串（滑動視窗 + Hash）
找出一個字串中不包含重複字元的最長子字串長度。暴力解是 $O(N^2)$，資深工程師必須使用滑動視窗 (Sliding Window) 搭配 Hash Map 將複雜度降至 $O(N)$。
程式碼與分析
PHP
<?php
/**
* 使用滑動視窗 (Sliding Window) 找到最長不重複子字串的長度。
* 時間 O(n), 空間 O(m) (m 為字元集大小)。
*
* @param string $s 輸入字串。
* @return int 最長不重複子字串的長度。
*/
function lengthOfLongestSubstring(string $s): int
{
$map = []; // char => last seen index (紀錄每個字元最後出現的索引)
$max = 0; // 記錄最大長度
$left = 0; // 滑動視窗的左邊界
for ($right = 0; $right < strlen($s); $right++) {
$char = $s[$right];
// 檢查當前字元是否重複，且重複的字元在當前視窗 [left, right] 內
if (isset($map[$char]) && $map[$char] >= $left) {
// 如果重複，將左邊界移到重複字元的下一位置
$left = $map[$char] + 1;
}
// 更新字元的最新索引
$map[$char] = $right;
// 更新最大長度：(右邊界 - 左邊界 + 1)
$max = max($max, $right - $left + 1);
}
return $max;
}
// ---------- 測試 ----------
$cases = ["abcabcbb", "bbbbb", "pwwkew", "", " ", "au"];
foreach ($cases as $c) {
echo "'$c' => " . lengthOfLongestSubstring($c) . PHP_EOL;
}
| 項目 | 描述 |
| 時間複雜度 | $O(N)$ (每個字元僅被 $right$ 指針訪問一次) |
| 空間複雜度 | $O(M)$ (M 為字元集大小，例如 256 for ASCII) |
陷阱與防禦說明
| 陷阱 | 防禦方式 | 為什麼這樣寫 |
| 暴力 $O(N^2)$ | 滑動視窗 + Hash Map | 將重複檢查從 $O(N)$ 降到 $O(1)$，實現整體 $O(N)$ 效率。 |
| Unicode 多位元組 | 假設 ASCII/單一編碼。若需完整支援 Unicode，必須改用 mb_substr / mb_strlen / grapheme_strlen。 | PHP 的 $s[$i] 操作在多位元組字元上可能只取到部分位元組。此解法在 ASCII 或單純英文場景適用，但應註明 Unicode 限制。 |
| 空字串/單字元 | $left=0$ 和 $max=0$ 的初始化正確處理了這些邊界情況。 | 確保空字串 (長度 0) 和單字元字串 (長度 1) 的正確性。 |
🔢 4. 邊界陷阱：陣列中第二大的數字（$O(N)$ 單次掃描）
要求在 $O(N)$ 時間內找到陣列中的第二大數字。關鍵在於單次迭代中正確處理各種數值情況和邊界條件。
程式碼與分析
PHP
<?php
/**
* 在 O(n) 時間內找到陣列中第二大的數字。
*
* @param array $nums 數字陣列。
* @return int|float 第二大的數字。
* @throws InvalidArgumentException 輸入無效時。
* @throws RuntimeException 無法找到第二大數字時。
*/
function secondMax(array $nums)
{
// 邊界檢查 1: 數量不足
if (count($nums) < 2) {
throw new InvalidArgumentException('At least 2 numeric elements required');
}
// 初始化：使用 PHP 最小值，適用於正數、負數、零
$max = $second = PHP_INT_MIN;
foreach ($nums as $n) {
// 輸入防禦：確保元素為數值型別
if (!is_numeric($n)) {
throw new InvalidArgumentException('All elements must be numeric');
}
$n = $n + 0; // 強制將 '1.5' 等字串數值轉為 int/float
if ($n > $max) {
// 發現新的最大值
$second = $max; // 原來的最大值變成第二大
$max = $n; // 更新最大值
} elseif ($n > $second && $n < $max) {
// 發現新的第二大值 (必須小於 max，以排除重複最大值)
$second = $n;
}
}
// 邊界檢查 2: 所有元素相等 (此時 $second 仍為初始值)
if ($second === PHP_INT_MIN) {
// 檢查 $max 是否也為初始值，排除全為最小負數的情況
// 更簡單的檢查是：如果遍歷後 $second 仍然是初始值，表示沒有 "distinct" 的第二大數。
// 但由於我們要求 $n < $max，所以當所有元素都等於 $max$ 時，$second$ 不會更新。
throw new RuntimeException('No distinct second max (all elements equal or only one unique value)');
}
return $second;
}
// ---------- 測試 ----------
$cases = [
[3,1,4,2], // 3
[5,5,5], // exception
[-1,-5,-3,-2], // -2
[7], // exception
[1.5, 2.7, 2.7], // 1.5
[PHP_INT_MIN, 0, 1] // 0 (測試初始值)
];
foreach ($cases as $c) {
try {
echo implode(',',$c) . " => " . secondMax($c) . PHP_EOL;
} catch (Throwable $e) {
echo implode(',',$c) . " => [ERROR] " . $e->getMessage() . PHP_EOL;
}
}
| 項目 | 描述 |
| 時間複雜度 | $O(N)$ (僅一次遍歷) |
| 空間複雜度 | $O(1)$ (僅使用兩個變數) |
陷阱與防禦說明
| 陷阱 | 防禦方式 | 為什麼這樣寫 |
| 少於 2 個元素 | 拋例外 InvalidArgumentException | 題目定義至少需要兩個元素。 |
| 所有元素相等 | 拋例外 RuntimeException | $second$ 必須小於 $max$ 才能更新，如果所有元素相等，則 $second$ 保持初始值。 |
| 負數、浮點數 | 初始化為 PHP_INT_MIN；接受所有 is_numeric 的值。 | 確保能正確處理負數和浮點數，同時使用 PHP_INT_MIN 作為可靠的最小初始值。 |
| 非數字輸入 | 明確檢查 !is_numeric() | 增加程式碼的魯棒性 (Robustness)，防止意外的字串或非數值型別導致邏輯錯誤。 |
| 重複最大值 | 條件 elseif ($n > $second && $n < $max) | 確保重複的最大值 ($n == max$) 不會更新 `$second$，這是關鍵。 |
🔄 5. 時間複雜度陷阱：兩數之和（回傳 Index）
「兩數之和 (Two Sum)」是經典的考驗時間複雜度優化的題目。目標是在 $O(N^2)$ 的暴力解之外，使用 Hash Map 達到單次掃描 $O(N)$ 的效果。
程式碼與分析
PHP
<?php
/**
* 兩數之和問題：使用 Hash Map 在 O(n) 時間內找到和為 $target$ 的兩個元素的索引。
* * @param array $nums 數字陣列。
* @param int $target 目標和。
* @return array 兩個元素的索引 [index1, index2]。
* @throws RuntimeException 無解時。
*/
function twoSum(array $nums, int $target): array
{
$map = []; // value => index
// 單次遍歷，O(n)
foreach ($nums as $i => $n) {
$complement = $target - $n;
// 1. 檢查所需的 "互補數" 是否已存在於 $map 中
if (isset($map[$complement])) {
// 找到解，回傳 [互補數的索引, 當前數的索引]
return [$map[$complement], $i];
}
// 2. 將當前數值及其索引存入 $map
// (必須在檢查之後，才能保證不會使用同一個索引的數字)
$map[$n] = $i;
}
// 如果循環結束仍未找到
throw new RuntimeException('No solution found');
}
// ---------- 測試 ----------
$cases = [
[[2,7,11,15], 9], // [0,1]
[[3,2,4], 6], // [1,2]
[[3,3], 6], // [0,1]
[[3, 6], 10] // No solution
];
foreach ($cases as $c) {
[$nums, $target] = $c;
try {
echo "nums=[" . implode(',',$nums) . "], target=$target => [" .
implode(',', twoSum($nums, $target)) . "]\n";
} catch (Throwable $e) {
echo "nums=[" . implode(',',$nums) . "], target=$target => [ERROR] " . $e->getMessage() . "\n";
}
}
| 項目 | 描述 |
| 時間複雜度 | $O(N)$ (Hash Map 的存取為 $O(1)$) |
| 空間複雜度 | $O(N)$ (用於建立 $map Hash 表) |
陷阱與防禦說明
| 陷阱 | 防禦方式 | 為什麼這樣寫 |
| 暴力 $O(N^2)$ | Hash Map (空間換時間) | 將查找互補數的時間從 $O(N)$ 降至 $O(1)$。 |
重複值 (e.g., [3, 3], $target=6$) | 將 $n$ 和 $i$ 存入 $map$ 的動作放在檢查之後。 | 如果 $map[complement]$ 存在，它必然是當前索引 $i$ 之前的元素。這自動避免了同一元素兩次使用的情況。 |
| 無解 | 拋例外 RuntimeException | 程式碼需覆蓋所有可能性，若無解則應通知呼叫者。 |
💡 Bonus 題：PHP 特性陷阱深度解讀
資深 PHP 工程師必須熟知語言本身的怪癖 (quirks)。
6. 陣列鍵值混淆 (Type Juggling)
| 代碼 | 輸出 | 說明 |
var_dump([0 => 'zero', '0' => 'string zero']); | array(1) { [0]=> string(11) "string zero" } | 陷阱：PHP 會嘗試將字串鍵轉換為整數。字串 '0' 被轉成整數 0，覆蓋了前一個值。 |
7. 浮點數比較
| 代碼 | 輸出 | 說明 |
var_dump(0.1 + 0.2 == 0.3); | bool(false) | 陷阱：浮點數在電腦中是二進制近似值，不應使用 == 直接比較。 |
防禦：const EPS = 1e-12; return abs($a - $b) < EPS; | 使用一個極小的容忍值 (Epsilon) 進行比較。 |
8. 參照與複製陷阱 (Copy-on-Write)
| 代碼 | 輸出 | 說明 |
function modifyByVal(array $arr) { $arr[0] = 999; } | 呼叫後，原陣列 [1,2,3] 不變。 | 特性：PHP 陣列預設傳值，但底層實作是 Copy-on-Write (寫時複製)。只有在函式內真正寫入時，才會發生複製。 |
防禦：若要修改原陣列，必須明確使用 & 符號傳參照：function modifyByRef(array &$arr)。 |
📝 總結：資深工程師的思維模型
| 核心問題 | 資深解決方案與思維 |
| 穩定排序 | 必須手動利用 array_multisort 和原始 Index，彌補語言內建函式的不穩定性。 |
| 遞迴效率 | 使用迭代 DP (或 Memozation)，將指數級 $O(2^N)$ 降為線性 $O(N)$，同時 $O(1)$ 空間。 |
| 字串處理 | 使用 Hash Map + 滑動視窗，將 $O(N^2)$ 降至 $O(N)$，並警惕 Unicode 陷阱。 |
| 邊界處理 | 考慮空/少於 2 個元素、所有元素相等、極端值 ($PHP\_INT\_MIN$)、非數字輸入。 |
| 演算法優化 | 優先採用空間換時間的策略 (如 Hash Map)，追求 $O(N)$ 的最佳時間複雜度。 |
| PHP 特性 | 熟知型別自動轉換、浮點誤差、以及傳值/參照的底層邏輯。 |
希望這份整理能幫助您分享您的專業知識！
沒有留言:
張貼留言