Amazon OA 真題複盤：Bug 優先級排序 + 倉庫安全存儲

題目一：Bug 報告優先級排序

問題描述

你正在幫助 Amazon 的質量保證工程師處理自動化測試日誌生成的 Bug 報告。每條日誌包含一個整數 Bug 代碼，單個測試會話可能包含重複的 Bug 代碼。

排序規則：

• 出現頻率低的 Bug 優先級更高（可能表示罕見或邊界情況）
• 如果兩個 Bug 出現頻率相同，代碼號較小的優先級更高

任務：按照上述規則對 Bug 代碼進行排序。

示例

輸入：bugs = [8, 4, 6, 5, 4, 8]

Bug 代碼	頻率
8	2
4	2
6	1
5	1

排序過程：

1. 頻率為 1 的 Bug：6 和 5，按代碼號排序 → [5, 6]
2. 頻率為 2 的 Bug：8 和 4，按代碼號排序 → [4, 8]
3. 最終輸出：[5, 6, 4, 8]

解題思路

方法一：排序 + 哈希表（O(n log n)）⭐ 推薦

def sortBugReportFrequencies(bugs):
    from collections import Counter
    
    # 統計每個 Bug 的頻率
    freq = Counter(bugs)
    
    # 按照規則排序：先按頻率升序，再按代碼號升序
    sorted_bugs = sorted(freq.keys(), key=lambda x: (freq[x], x))
    
    return sorted_bugs

時間複雜度：O(n log n)（排序） 空間複雜度：O(n)（哈希表）

方法二：自定義比較器

def sortBugReportFrequencies(bugs):
    from collections import Counter
    from functools import cmp_to_key
    
    freq = Counter(bugs)
    
    def compare(a, b):
        # 先比較頻率
        if freq[a] != freq[b]:
            return freq[a] - freq[b]
        # 頻率相同，比較代碼號
        return a - b
    
    sorted_bugs = sorted(freq.keys(), key=cmp_to_key(compare))
    return sorted_bugs

關鍵要點

✅ 使用哈希表統計頻率：O(n) 時間 ✅ 雙重排序條件：頻率優先，其次代碼號 ✅ 利用 Python 的 sorted() 和 key 參數：簡潔高效 ✅ 考慮邊界情況：單個 Bug、所有 Bug 相同等

---

題目二：倉庫安全存儲最大化

問題描述

作為汽車製造公司的物流經理，你需要在 k 個安全倉庫中存儲配件。

存儲規則：

• 每個倉庫只能存儲來自單一配件日誌的配件
• 不同日誌的配件不能混合存儲在同一倉庫
• 單個日誌的配件可以分散到多個倉庫

安全威脅：

• 存儲後，配件數量最多的 k/2 個倉庫會被入侵
• 只有剩餘的 k/2 個倉庫中的配件才算安全

任務：找到最大的安全配件數量。

示例

輸入：

• n = 4
• deliveryLogs = [3, 5, 9, 6]
• k = 4

分析：

方案一（不優化）：

• 每個日誌單獨存儲：[3, 5, 9, 6]
• 最多的 2 個倉庫：[9, 6] 被入侵
• 安全配件：3 + 5 = 8

方案二（優化）：

1. 將第二個日誌（5）的配件分散：
   • 第一個倉庫：3 個（來自日誌 1）
   • 第二個倉庫：5 個（來自日誌 2）
2. 將第三個日誌（9）的配件分散：
   • 第二個倉庫：4 個（來自日誌 3）
   • 第三個倉庫：5 個（來自日誌 3）
3. 將第四個日誌（6）的配件分散：
   • 第三個倉庫：1 個（來自日誌 4）
   • 第四個倉庫：5 個（來自日誌 4）

結果：[3, 5, 5, 5]

• 最多的 2 個倉庫：[5, 5] 被入侵
• 安全配件：3 + 5 = 8

解題思路

方法：貪心 + 二分查找（O(n log m)）⭐ 最優

核心思想：

1. 對配件數量進行排序（降序）
2. 使用二分查找找到最大的安全配件數量
3. 對於每個候選答案，檢查是否可行

def maximumSecureDeliveries(deliveryLogs, k):
    def canAchieve(target):
        # 檢查是否能達到 target 個安全配件
        warehouses = []
        
        for delivery in deliveryLogs:
            remaining = delivery
            
            # 盡量填充現有倉庫（不超過 target）
            for i in range(len(warehouses)):
                if warehouses[i] < target:
                    add = min(remaining, target - warehouses[i])
                    warehouses[i] += add
                    remaining -= add
                    if remaining == 0:
                        break
            
            # 如果還有剩餘，創建新倉庫
            while remaining > 0:
                add = min(remaining, target)
                warehouses.append(add)
                remaining -= add
        
        # 檢查是否有足夠的安全倉庫
        safe_count = sum(1 for w in warehouses if w == target)
        return len(warehouses) <= k and safe_count >= k // 2
    
    # 二分查找最大安全配件數
    left, right = 0, sum(deliveryLogs)
    result = 0
    
    while left <= right:
        mid = (left + right) // 2
        if canAchieve(mid):
            result = mid
            left = mid + 1
        else:
            right = mid - 1
    
    return result * (k // 2)

時間複雜度：O(n log m)，其中 m 是配件總數 空間複雜度：O(k)

關鍵要點

✅ 理解問題的本質：最大化安全倉庫中的配件 ✅ 貪心策略：盡量平衡倉庫中的配件數量 ✅ 二分查找：在可行性和最優性之間找到平衡 ✅ 邊界情況：k = 1、所有配件相同等

---

常見陷阱

題目一

❌ 只按頻率排序，忘記處理頻率相同的情況 ✅ 使用元組排序：(freq[x], x)

❌ 直接對原數組排序，導致重複計數 ✅ 先統計頻率，再對唯一值排序

題目二

❌ 貪心地將所有配件放在一個倉庫 ✅ 需要分散配件以最大化安全存儲

❌ 沒有考慮 k/2 個倉庫被入侵的約束 ✅ 確保有足夠的安全倉庫

---

面試技巧

1. 題目一：

   • 從簡單的排序開始
   • 解釋為什麼需要雙重排序條件
   • 展示如何使用 Python 的排序功能

2. 題目二：

   • 先理解問題的約束條件
   • 從暴力解開始（每個日誌單獨存儲）
   • 逐步優化到貪心 + 二分查找
   • 用具體例子演示算法過程

---

🚀 需要面試輔助？

oavoservice 提供專業的 Amazon OA/VO 輔助服務。

👉 立即添加微信：Coding0201

獲取：

• 真實 OA 題目庫
• 一對一模擬面試
• 實時編碼輔助
• 臨場應對策略