Amazon Intern OA 兩道題，思路清晰，全AC。Q1 是分組計數貪心，Q2 是約數替換貪心。以下是純思路複盤，不含程式碼。
考試概況
| 項目 | 詳情 |
|---|---|
| 平台 | HackerRank |
| 題數 | 2 道 |
| 難度 | Medium |
| 職位 | Intern SDE |
| 結果 | 全AC |
Q1：安全等級分組（Security Level Grouping）
題目核心
給定一組人員，每人有一個安全等級。需要將他們分配到若干組，滿足：
- 每組只能有一種安全等級的人
- 任意兩組的人數之差 ≤ 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)
關鍵洞察
問題的本質是：在陣列內部建立一個「替換映射」，每個數映射到陣列中它的最小因子。排序後貪心從小到大處理，保證每個數找到的是真正的最小可用約數。
兩題核心思路對比
| 題目 | 核心技巧 | 時間複雜度 | 空間複雜度 |
|---|---|---|---|
| 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 高頻題庫覆蓋率極高。
立即加 WeChat：Coding0201
獲取：
- ✅ Amazon OA 即時輔助（螢幕共享 + 即時打字提示）
- ✅ HackerRank 真實題庫（覆蓋 80%+ 高頻題）
- ✅ 一對一模擬 OA + 詳細回饋
- ✅ VO 面試輔助（演算法 + 系統設計）
📱 WeChat：Coding0201 | 💬 Telegram：@OAVOProxy | 📧 [email protected] 「任意兩組人數相差 ≤ 1」這個約束把問題轉化為：全局組大小只能取兩個連續整數 k 和 k+1。枚舉 k 再對每個等級上取整即可。
Q2：約數替換最小總和（Divisor Replacement Min Sum）
題目核心
給定一個整數陣列，每個數可以替換為陣列中存在的它的某個約數（包括自身）。目標是讓替換後陣列的總和最小，求該最小總和。
解題思路
貪心方向：總和最小，所以每個數應該盡量替換成盡可能小的約數。
具體做法：
- 對陣列排序去重，得到有序集合
S - 對
S中每個數x，找它在S中的最小約數：- 枚舉
S中比x小的數d，若x % d == 0，則d是x在陣列中的最小約數 - 用
d替換x（x映射到d） - 若不存在這樣的
d，x保持不變
- 枚舉
- 對原陣列每個元素，按映射關係替換後求總和
優化：排序後從小到大處理，若 d 本身已映射到更小的值，可以鏈式傳遞替換。
複雜度分析
- 時間複雜度：O(n log n + m²)，n 為原陣列長度，m 為去重後元素數
- 空間複雜度：O(m)