資深 PHP 後端工程師面試指南：演算法與時間複雜度在電商場景中的應用

在電商平台的開發中，資深 PHP 後端工程師需要熟練運用演算法來解決高效能問題，如商品搜尋、訂單處理、推薦系統等。本文針對電商場景，整理出七大類常見的面試問題，涵蓋模擬問答、PHP 程式碼範例、演算法分析、時間與空間複雜度，以及在電商系統中的具體應用場景。內容旨在幫助你在面試中展現技術深度，並提供實務建議，讓你能將演算法直接應用於電商平台。

1. 商品搜尋優化

問題：如何在電商平台中實現高效的商品關鍵字搜尋？

回答要點：

使用倒排索引（Inverted Index）或前綴樹（Trie）優化關鍵字搜尋。
結合資料庫索引與快取（如 Elasticsearch 或 Redis）提升性能。
討論模糊搜尋與分詞處理。

模擬答案：

場景：電商平台需要快速匹配用戶輸入的關鍵字（如「手機」）到商品名稱。
演算法：使用前綴樹儲存商品名稱，支援快速前綴查詢。
應用：將前綴樹與 Redis 結合，儲存熱門搜尋詞的快取，減少資料庫查詢。

範例程式碼：

class TrieNode {
    public $children = [];
    public $isEnd = false;
    public $products = [];
}

class Trie {
    private $root;
    
    public function __construct() {
        $this->root = new TrieNode();
    }
    
    public function insert(string $word, int $productId): void {
        $node = $this->root;
        foreach (str_split(strtolower($word)) as $char) {
            if (!isset($node->children[$char])) {
                $node->children[$char] = new TrieNode();
            }
            $node = $node->children[$char];
        }
        $node->isEnd = true;
        $node->products[] = $productId;
    }
    
    public function searchPrefix(string $prefix): array {
        $node = $this->root;
        foreach (str_split(strtolower($prefix)) as $char) {
            if (!isset($node->children[$char])) {
                return [];
            }
            $node = $node->children[$char];
        }
        return $node->products;
    }
}

// 測試
$trie = new Trie();
$trie->insert("smartphone", 1);
$trie->insert("smartwatch", 2);
print_r($trie->searchPrefix("smart")); // 輸出：[1, 2]

時間與空間複雜度：

時間複雜度：
- 插入：O(m)，m 為單詞長度。
- 搜尋：O(m)，遍歷前綴。
空間複雜度：O(N * M)，N 為單詞數，M 為平均單詞長度。

電商應用：

場景：用戶輸入「smart」時，快速返回包含「smartphone」「smartwatch」的商品 ID。
實現：將前綴樹儲存於 Redis，定期從資料庫同步商品名稱。結合 Elasticsearch 處理模糊搜尋與分詞（如中文商品名稱）。
實戰建議：面試時可補充如何用 Redis 快取熱門搜尋結果，或如何用 MySQL LIKE 查詢作為備案。

2. 訂單去重處理

問題：如何在電商系統中檢測重複訂單（例如短時間內多次提交）？

回答要點：

使用哈希表或布隆過濾器（Bloom Filter）檢查訂單是否重複。
結合 Redis 實現高效去重。
討論誤判率與性能權衡。

模擬答案：

場景：電商平台需檢測用戶在 5 分鐘內是否重複提交相同訂單（基於用戶 ID 與商品 ID）。
演算法：使用 Redis 的 Set 結構儲存訂單簽名，檢查是否已存在。
應用：為每個訂單生成唯一簽名（如 user_id:product_id:timestamp），並設定過期時間。

範例程式碼：

function checkDuplicateOrder($redis, int $userId, int $productId, int $timestamp): bool {
    $signature = "$userId:$productId:$timestamp";
    $exists = $redis->sIsMember('orders', $signature);
    
    if (!$exists) {
        $redis->sAdd('orders', $signature);
        $redis->expire('orders', 300); // 5 分鐘過期
        return false;
    }
    return true;
}

// 測試（假設使用 Predis 客戶端）
$redis = new Predis\Client();
$userId = 123;
$productId = 456;
$timestamp = time();
echo checkDuplicateOrder($redis, $userId, $productId, $timestamp) ? "Duplicate" : "New"; // 輸出：New

時間與空間複雜度：

時間複雜度：O(1)，Redis 的 sIsMember 和 sAdd 操作為常數時間。
空間複雜度：O(n)，n 為儲存的訂單簽名數量。
替代方案（布隆過濾器）：
- 時間複雜度：O(1)，檢查與插入均為常數時間。
- 空間複雜度：O(1)，固定大小但有誤判風險。

電商應用：

場景：防止用戶因網路延遲重複提交訂單，減少伺服器負擔。
實現：用 Redis Set 儲存訂單簽名，設定 5 分鐘過期時間。若資料量極大，可用布隆過濾器降低記憶體使用。
實戰建議：面試時可討論布隆過濾器的誤判率（如 0.1%），以及如何結合資料庫記錄最終確認。

3. 庫存扣減

問題：如何在高併發電商系統中安全扣減庫存？

回答要點：

使用資料庫悲觀鎖或 Redis 原子操作防止超賣。
介紹 Lua 腳本實現 Redis 原子性。
討論分散式環境下的鎖機制。

模擬答案：

場景：電商秒殺活動中，確保庫存扣減不發生超賣。
演算法：使用 Redis 的原子操作（如 INCR/DECR）或 Lua 腳本檢查並更新庫存。
應用：結合資料庫事務作為最終一致性保證。

範例程式碼（Redis Lua 腳本）：

function deductStock($redis, string $productId, int $quantity): bool {
    $luaScript = <<<LUA
        local stock = tonumber(redis.call('GET', KEYS[1]))
        if stock >= tonumber(ARGV[1]) then
            redis.call('DECRBY', KEYS[1], ARGV[1])
            return 1
        end
        return 0
    LUA;
    
    $result = $redis->eval($luaScript, [$productId, $quantity], 1);
    return $result === 1;
}

// 測試
$redis = new Predis\Client();
$redis->set('stock:1001', 10); // 初始庫存 10
$success = deductStock($redis, 'stock:1001', 3);
echo $success ? "Deducted" : "Failed"; // 輸出：Deducted
echo $redis->get('stock:1001'); // 輸出：7

時間與空間複雜度：

時間複雜度：O(1)，Redis 的 GET/DECRBY 和 Lua 腳本執行為常數時間。
空間複雜度：O(1)，僅儲存單個鍵值。

電商應用：

場景：秒殺活動中，防止多個用戶同時扣減同一商品庫存。
實現：用 Redis Lua 腳本確保原子性，結合 MySQL 事務記錄訂單明細。若為分散式系統，可用 Redlock 實現分散式鎖。
實戰建議：面試時可補充如何處理庫存超賣（如回滾機制）或用消息隊列（如 RabbitMQ）異步處理訂單。

4. 商品推薦系統

問題：如何實現一個簡單的商品推薦系統，基於用戶購買歷史？

回答要點：

使用協同過濾（Collaborative Filtering）或基於內容的推薦。
介紹集合操作計算相似用戶或商品。
討論 Redis 或資料庫的應用。

模擬答案：

場景：根據用戶購買歷史，推薦其他用戶也常購買的商品。
演算法：使用集合交集計算用戶間的購買相似度，找出 Top-K 相似商品。
應用：用 Redis Set 儲存用戶購買清單，快速計算交集。

範例程式碼：

function recommendProducts($redis, int $userId, int $k): array {
    // 假設每個用戶的購買清單儲存於 Redis Set
    $allUsers = $redis->keys('purchases:*');
    $similarProducts = [];
    
    foreach ($allUsers as $otherUserKey) {
        $otherUserId = str_replace('purchases:', '', $otherUserKey);
        if ($otherUserId == $userId) continue;
        
        $intersection = $redis->sInter("purchases:$userId", $otherUserKey);
        $similarProducts = array_merge($similarProducts, $intersection);
    }
    
    // 簡單計數並排序
    $productCounts = array_count_values($similarProducts);
    arsort($productCounts);
    return array_slice(array_keys($productCounts), 0, $k);
}

// 測試
$redis = new Predis\Client();
$redis->sAdd('purchases:1', 101, 102, 103); // 用戶 1 購買商品
$redis->sAdd('purchases:2', 102, 103, 104); // 用戶 2 購買商品
print_r(recommendProducts($redis, 1, 2)); // 輸出：[102, 103]

時間與空間複雜度：

時間複雜度：O(U * P)，U 為用戶數，P 為平均購買清單長度（Redis 集合交集操作）。
空間複雜度：O(P)，儲存交集結果。

電商應用：

場景：在商品詳情頁顯示「其他買家也購買」的推薦。
實現：用 Redis 儲存用戶購買清單，定期用批次任務計算相似度並快取結果。若資料量大，可用協同過濾框架（如 Apache Mahout）。
實戰建議：面試時可討論如何用機器學習（如基於矩陣分解）提升推薦準確性，或如何用快取降低計算成本。

5. 購物車合併

問題：如何合併用戶的離線與線上購物車？

回答要點：

使用哈希表或集合合併購物車項目。
討論如何處理商品數量衝突（如取最大值）。
介紹 Redis 作為即時儲存的應用。

模擬答案：

場景：用戶離線購物車（本地儲存）與線上購物車（Redis）需合併。
演算法：使用哈希表合併商品 ID 與數量，衝突時取最大數量。
應用：用 Redis Hash 儲存購物車，支援快速更新與合併。

範例程式碼：

function mergeCart($redis, int $userId, array $offlineCart): void {
    $onlineCart = $redis->hGetAll("cart:$userId");
    
    foreach ($offlineCart as $productId => $quantity) {
        $currentQuantity = $onlineCart[$productId] ?? 0;
        $redis->hSet("cart:$userId", $productId, max($currentQuantity, $quantity));
    }
}

// 測試
$redis = new Predis\Client();
$offlineCart = [101 => 2, 102 => 3];
$redis->hSet('cart:1', 101, 1); // 線上已有商品
mergeCart($redis, 1, $offlineCart);
print_r($redis->hGetAll('cart:1')); // 輸出：[101 => 2, 102 => 3]

時間與空間複雜度：

時間複雜度：O(n)，n 為離線購物車的商品數量。
空間複雜度：O(n)，儲存合併後的購物車。

電商應用：

場景：用戶從 App 離線狀態切換到線上時，合併購物車。
實現：用 Redis Hash 儲存線上購物車，客戶端上傳離線購物車後執行合併。定期將購物車資料同步到資料庫。
實戰建議：面試時可補充如何處理商品庫存檢查，或如何用事件驅動架構（如 Kafka）記錄購物車變更。

6. 促銷價格計算

問題：如何計算購物車中所有商品的促銷價格（考慮多種折扣規則）？

回答要點：

使用動態規劃或貪婪演算法計算最佳折扣組合。
討論規則優先級與衝突處理。
介紹快取優化重複計算。

模擬答案：

場景：購物車有多種折扣規則（如滿減、單品折扣），需計算最低總價。
演算法：遍歷每種折扣規則，選擇對應商品應用折扣，貪婪選擇最大折扣。
應用：用 Redis 快取商品價格與折扣規則，減少計算開銷。

範例程式碼：

function calculatePromoPrice(array $cart, array $rules): float {
    $total = 0;
    $applied = [];
    
    // 規則格式：[type => 'amount/full', condition => value, discount => value]
    foreach ($rules as $rule) {
        if ($rule['type'] === 'amount' && !isset($applied[$rule['product_id']])) {
            if ($cart[$rule['product_id']]['quantity'] >= $rule['condition']) {
                $total += $cart[$rule['product_id']]['price'] * $rule['discount'];
                $applied[$rule['product_id']] = true;
            }
        } elseif ($rule['type'] === 'full') {
            $subtotal = array_sum(array_map(fn($item) => $item['price'] * $item['quantity'], $cart));
            if ($subtotal >= $rule['condition']) {
                $total = $subtotal - $rule['discount'];
                break; // 假設滿減優先級最高
            }
        }
    }
    
    // 未應用折扣的商品按原價計算
    foreach ($cart as $productId => $item) {
        if (!isset($applied[$productId])) {
            $total += $item['price'] * $item['quantity'];
        }
    }
    
    return $total;
}

// 測試
$cart = [
    101 => ['price' => 100, 'quantity' => 2],
    102 => ['price' => 200, 'quantity' => 1]
];
$rules = [
    ['type' => 'amount', 'product_id' => 101, 'condition' => 2, 'discount' => 0.8], // 101 買 2 件打 8 折
    ['type' => 'full', 'condition' => 300, 'discount' => 50] // 滿 300 減 50
];
echo calculatePromoPrice($cart, $rules); // 輸出：350 (101: 160 + 102: 200 - 50)

時間與空間複雜度：

時間複雜度：O(n + r)，n 為購物車商品數，r 為折扣規則數。
空間複雜度：O(n)，儲存已應用折扣的商品。

電商應用：

場景：結帳頁計算購物車總價，考慮多種促銷活動。
實現：用 Redis 快取商品價格與折扣規則，動態規劃可進一步優化複雜規則組合。
實戰建議：面試時可討論如何處理規則衝突，或如何用 Lua 腳本在 Redis 中實現原子價格計算。

7. 日誌分析與排行榜

問題：如何從日誌中提取最熱門的商品瀏覽記錄，生成排行榜？

回答要點：

使用 Top-K 堆積演算法處理大量日誌資料。
結合 Redis Sorted Set 實現即時排行榜。
討論批次處理與即時更新的平衡。

模擬答案：

場景：電商平台需從日誌中提取前 10 個最常被瀏覽的商品。
演算法：使用最小堆維護 Top-K 商品，或用 Redis Sorted Set 增量更新排行。
應用：用 Redis 儲存即時瀏覽次數，批次任務更新長期排行。

範例程式碼：

function updateViewRank($redis, int $productId): void {
    $redis->zIncrBy('product_views', 1, $productId);
}

function getTopKProducts($redis, int $k): array {
    return $redis->zRevRange('product_views', 0, $k - 1, true);
}

// 測試
$redis = new Predis\Client();
updateViewRank($redis, 101);
updateViewRank($redis, 101);
updateViewRank($redis, 102);
print_r(getTopKProducts($redis, 2)); // 輸出：[101 => 2, 102 => 1]

時間與空間複雜度：

時間複雜度：
- 更新：O(log n)，Redis Sorted Set 的增量更新。
- 獲取 Top-K：O(log n + k)，從 Sorted Set 提取前 k 項。
空間複雜度：O(n)，n 為商品數量。

電商應用：

場景：首頁展示「熱門商品」排行榜。
實現：用 Redis Sorted Set 儲存商品瀏覽次數，設定過期時間清理舊資料。批次任務將日誌資料匯入 MySQL 進行長期分析。
實戰建議：面試時可補充如何用最小堆處理離線日誌，或如何結合 Elasticsearch 分析多維度日誌。

總結與面試建議

面試技巧

場景化回答：將演算法與電商場景結合（如「前綴樹用於搜尋建議」），展現實務應用能力。
結構化分析：回答結構為「場景 → 演算法 → 程式碼 → 複雜度 → 電商應用」，清晰有條理。
強調效能優化：提到快取（Redis）、索引（MySQL）、原子操作（Lua 腳本）如何提升電商系統性能。

電商實務建議

快取策略：用 Redis 儲存熱門資料（如搜尋建議、排行榜），減少資料庫壓力。
分散式系統：在高併發場景（如秒殺）中使用 Redlock 或消息隊列（如 RabbitMQ）確保一致性。
監控與日誌：用 Elasticsearch 分析日誌，結合 Prometheus 監控系統性能。

進階學習資源

演算法基礎：《Introduction to Algorithms》或 LeetCode PHP 題目。
電商系統設計：閱讀《Designing Data-Intensive Applications》。
快取與資料庫：學習 Redis 官方文件與 MySQL 索引優化。

透過練習這些電商場景的演算法應用，你將能在面試中展現 PHP 後端與演算法的結合能力，並直接應用於電商平台開發！若需將本文轉化為影片腳本或補充視覺化圖表（如前綴樹結構圖），請隨時告訴我。

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

2025年9月29日星期一