题目一：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 的 Bug：6 和 5，按代码号排序 →
[5, 6] - 频率为 2 的 Bug：8 和 4，按代码号排序 →
[4, 8] - 最终输出：
[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 = 4deliveryLogs = [3, 5, 9, 6]k = 4
分析：
方案一（不优化）：
- 每个日志单独存储：
[3, 5, 9, 6] - 最多的 2 个仓库：
[9, 6]被入侵 - 安全配件：
3 + 5 = 8
方案二（优化）：
- 将第二个日志（5）的配件分散：
- 第一个仓库：3 个（来自日志 1）
- 第二个仓库：5 个（来自日志 2）
- 将第三个日志（9）的配件分散：
- 第二个仓库：4 个（来自日志 3）
- 第三个仓库：5 个（来自日志 3）
- 将第四个日志（6）的配件分散：
- 第三个仓库：1 个（来自日志 4）
- 第四个仓库：5 个（来自日志 4）
结果：[3, 5, 5, 5]
- 最多的 2 个仓库：
[5, 5]被入侵 - 安全配件：
3 + 5 = 8
等等，让我重新分析...
最优方案：
- 仓库 1：3 个（日志 1）
- 仓库 2：5 个（日志 2）
- 仓库 3：5 个（日志 3 的一部分）
- 仓库 4：5 个（日志 3 的另一部分 + 日志 4 的一部分）
最多的 2 个仓库被入侵，剩余 2 个仓库安全。 安全配件 = 3 + 5 = 8
解题思路
方法：贪心 + 二分查找（O(n log m)）⭐ 最优
核心思想：
- 对配件数量进行排序（降序）
- 使用二分查找找到最大的安全配件数量
- 对于每个候选答案，检查是否可行
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 个仓库被入侵的约束 ✅ 确保有足够的安全仓库
面试技巧
题目一：
- 从简单的排序开始
- 解释为什么需要双重排序条件
- 展示如何使用 Python 的排序功能
题目二：
- 先理解问题的约束条件
- 从暴力解开始（每个日志单独存储）
- 逐步优化到贪心 + 二分查找
- 用具体例子演示算法过程
🚀 需要面试辅助？
oavoservice 提供专业的 Amazon OA/VO 辅助服务。
👉 立即添加微信：Coding0201
获取：
- 真实 OA 题目库
- 一对一模拟面试
- 实时编码辅助
- 临场应对策略