Amazon Intern OA 两道题，思路清晰，全AC。Q1 是分组计数贪心，Q2 是约数替换贪心。以下是纯思路复盘，不含代码。
考试概况
| 项目 | 详情 |
|---|---|
| 平台 | HackerRank |
| 题数 | 2 道 |
| 难度 | Medium |
| 岗位 | Intern SDE |
| 结果 | 全AC |
Q1：安全等级分组（Security Level Grouping）
题目核心
给定一组人员，每人有一个安全等级。需要将他们分配到若干组，满足：
- 每组只能有一种安全等级的人
- 任意两组的人数之差 ≤ 1
求最少需要多少组。
解题思路
第一步：统计频率
用一个哈希表统计每种安全等级出现的次数，得到频率数组。
第二步：对每个等级独立计算所需组数
对于某个等级出现了 cnt 次，要把这 cnt 个人分配到若干组，使得每组人数相差 ≤ 1。
关键问题：这 cnt 个人最少分成几组？
换个角度思考：如果分成 g 组，每组人数要么是 cnt // g，要么是 cnt // g + 1。要满足相差 ≤ 1，只需要 g 满足这个条件即可——实际上，对于任意 g，把 cnt 个人分成 g 组都能满足相差 ≤ 1（因为可以用 cnt // g 和 cnt // g + 1 组合分配）。
所以问题等价于：所有等级共同分组时，总组数最少是多少？
全局约束：任意两组（跨等级也算）人数之差 ≤ 1，意味着全局所有组的人数只能是某个值 k 或 k+1。
枚举组大小 k：
- 对每种等级，频率为
cnt，分成大小为k的组需要ceil(cnt / k)组 - 总组数 = 所有等级的组数之和
- 枚举
k从 1 到 max_cnt，取总组数最小的方案
复杂度分析
- 时间复杂度：O(n + L · max_cnt)，L 为等级种数，max_cnt 为最大频率
- 空间复杂度：O(L)
关键洞察
「任意两组人数相差 ≤ 1」这个约束把问题转化为：全局组大小只能取两个连续整数 k 和 k+1。枚举 k 再对每个等级上取整即可。
Q2：约数替换最小总和（Divisor Replacement Min Sum）
题目核心
给定一个整数数组，每个数可以替换为数组中存在的它的某个约数（包括自身）。目标是让替换后数组的总和最小，求该最小总和。
解题思路
贪心方向：总和最小，所以每个数应该尽量替换成尽可能小的约数。
关键性质：每个数的最小约数（大于1的）是它的最小质因数。但替换必须用数组中已有的数。
正确做法：
- 对数组排序去重，得到有序集合
S - 对
S中每个数x，找它在S中的最小约数：- 枚举
S中比x小的数d，若x % d == 0，则d是x在数组中的最小约数 - 用
d替换x（x映射到d） - 若不存在这样的
d，x保持不变
- 枚举
- 对原数组每个元素，按映射关系替换后求总和
优化：排序后从小到大处理，对每个数只需要找比它小的数中是否有约数，无需完整质因数分解。
复杂度分析
- 时间复杂度：O(n log n + m²)，n 为原数组长度，m 为去重后元素数
- 空间复杂度：O(m)
关键洞察
问题的本质是：在数组内部建立一个「替换映射」，每个数映射到数组中它的最小因子。排序后贪心从小到大处理，保证每个数找到的是真正的最小可用约数。
两题核心思路对比
| 题目 | 核心技巧 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| Q1 安全等级分组 | 频率统计 + 枚举组大小 | O(n + L·max_cnt) | O(L) |
| Q2 约数替换 | 排序去重 + 贪心找最小约数 | O(n log n + m²) | O(m) |
常见思维误区
| 题目 | 误区 | 正确方向 |
|---|---|---|
| Q1 | 直接对所有人排序分组，忽略等级限制 | 先按等级分桶，再枚举全局组大小 k |
| Q1 | 以为每个等级独立最小化组数 | 全局约束：所有组大小只能是 k 或 k+1 |
| Q2 | 对每个数做完整质因数分解 | 只需在数组内找最小约数，排序后枚举即可 |
| Q2 | 忘记约数必须在数组中存在 | 先建立数组元素集合，只能替换为集合内的约数 |
Amazon Intern OA 应试策略
Amazon Intern OA 特点
- 平台：HackerRank
- 题目风格：贪心、数学、排序为主，逻辑推导比代码量更重要
- 核心考点：能否快速把问题等价转化为更简单的形式
- 数据规模中等，通常 O(n²) 可以通过，但 O(n log n) 更稳
临场策略
- Q1 类分组题：先想「约束是什么」，把模糊的「相差 ≤ 1」转化为「所有组大小只能是 k 或 k+1」
- Q2 类替换题：先想「替换的目标是什么」，贪心方向是最小化，所以找最小可用替换值
- 排序往往是关键第一步——有序之后很多贪心性质自然成立
- 注意题目中「数组中存在」这类隐含约束，不要遗漏
- 写完跑样例再提交
相关 LeetCode 练习
| 题号 | 题目 | 对应考点 |
|---|---|---|
| 2966 | Divide Array Into Arrays With Max Difference | Q1 分组差值约束 |
| 945 | Minimum Increment to Make Array Unique | Q1 贪心分配 |
| 2344 | Minimum Deletions to Make Array Divisible | Q2 约数关系 |
| 1998 | GCD Sort of an Array | Q2 因子与数组关系 |
🚀 需要 Amazon Intern OA 辅助？
oavoservice 专注北美大厂 OA/VO 全程辅助，Amazon Intern OA 是我们的核心服务场景，HackerRank 高频题库覆盖率极高。
立即添加微信：Coding0201
获取：
- ✅ Amazon OA 实时辅助（屏幕共享 + 实时打字提示）
- ✅ HackerRank 真实题库（覆盖 80%+ 高频题）
- ✅ 一对一模拟 OA + 详细反馈
- ✅ VO 面试辅助（算法 + 系统设计）
📱 微信：Coding0201 | 💬 Telegram：@OAVOProxy | 📧 [email protected]