又一場 Amazon OA，兩道題都是從高頻題庫裡抽的，考察方向非常典型——一道模擬貪心，一道字串雜湊。以下是完整思路複盤，不含程式碼，專注於拆題邏輯和解題路徑。
考試概況
| 項目 | 詳情 |
|---|---|
| 平台 | CodeSignal |
| 題數 | 2 道 |
| 難度 | Medium |
| 職位 | Intern / New Grad SDE |
| 結果 | 全AC |
T1：虛擬機庫存租賃調度
題目核心
有 n 類虛擬機，每類有一定庫存數量。m 個客戶依次來租賃，每個客戶的行為是固定的：
- 總是租賃當前庫存最多的那一類虛擬機
- 租金 = 當前庫存最大值 + 當前所有非零庫存中的最小值
- 租賃完成後，該類虛擬機庫存減 1
求所有 m 次租賃的總租金。
解題思路
關鍵在於每次操作後需要快速知道兩件事：最大庫存是多少、非零庫存的最小值是多少。
直覺上想到排序，但每次操作都重新排序是 O(m·n log n)，資料量大時會超時。
正確思路：用計數陣列 + 雙指針
不直接記錄每台虛擬機的庫存量，而是用一個陣列 cnt 記錄每種庫存量出現了多少次。舉例：如果庫存狀態是 [3, 3, 1, 5]，那麼 cnt[1]=1, cnt[3]=2, cnt[5]=1。
同時維護兩個指針：
hi指針：始終指向當前最大的非零庫存量lo指針：始終指向當前最小的非零庫存量
每次租賃流程：
- 租金 =
hi + lo，累加入答案 cnt[hi]減 1（最大庫存那一類少了一台）cnt[hi-1]加 1（那一類庫存從hi降到了hi-1）- 檢查是否需要移動指針：
- 若
cnt[hi]歸零，hi向左移（找新的最大值） - 若
hi-1 < lo，說明產生了一個新的更低庫存，需要更新lo - 若當前
lo對應的cnt[lo]為零，lo向右移
- 若
複雜度分析
- 時間複雜度：O(n + m)，每次租賃操作是 O(1)，指針最多各移動 max_inventory 次
- 空間複雜度：O(max_inventory)，計數陣列大小取決於最大庫存值
關鍵洞察
這道題的精髓在於：不需要追蹤哪台機器的庫存是多少，只需要知道「有多少台機器的庫存恰好是 k」。把問題從追蹤個體轉換為追蹤分佈，雙指針就能以 O(1) 維護最大最小值。
T2：字串前綴最大等分塊數
題目核心
給定一個只含大寫字母的字串 S。對於 S 的每一個前綴，求出：最多能把該前綴等分成多少個子段，使得每個子段中每種字母出現的次數完全相同。
回傳一個陣列，第 i 個元素表示長度為 i 的前綴對應的最大分塊數。
解題思路
暴力做法：對每個前綴枚舉子段長度，逐段比較字元頻率，複雜度 O(n² · 26) 或更高，無法通過。
優化方向：隨機雜湊判斷子段頻率相等
直接比較兩個子段的字元頻率需要比較 26 個數，能不能壓縮成一個數來比較？
核心構造：
- 為 A-Z 每個字母隨機分配一個 64 位元整數（隨機權重）
- 定義每個位置的雜湊貢獻值 = 該位置字母對應的隨機權重
- 計算雜湊值的前綴和陣列
H
這樣，H[r] - H[l] 就代表區間 [l+1, r] 的雜湊值之和。
關鍵性質：兩個子段的字元頻率完全相同，當且僅當它們的雜湊值相等（以極高機率成立）。
枚舉策略：
- 枚舉子段長度
L（從 1 到 n） - 對於長度為
k*L的前綴，依次檢驗第 1 塊、第 2 塊……第 k 塊是否雜湊值都相等 - 若前 k 個塊雜湊值均相等，則更新第
k*L位前綴的答案為 k
複雜度：枚舉 L 時，對於每個 L，要檢驗的塊數是 n/L。總操作次數是 n/1 + n/2 + n/3 + ... + n/n = n·H(n)（調和級數），即 O(n log n)。
為什麼隨機雜湊有效？
如果兩個子段字元頻率不同，它們的雜湊值相等的機率極低（約 1/2^64）。對於題目規模下的所有子段對，誤判機率可以忽略不計。這是競賽和面試中經典的「隨機化降維」技巧。
複雜度分析
- 時間複雜度：O(n log n)，調和級數枚舉
- 空間複雜度：O(n)，儲存前綴雜湊陣列
兩題核心思路對比
| 題目 | 核心技巧 | 時間複雜度 | 空間複雜度 |
|---|---|---|---|
| T1 虛擬機租賃 | 計數陣列 + 雙指針 | O(n + m) | O(max_val) |
| T2 前綴等分 | 隨機雜湊 + 調和級數枚舉 | O(n log n) | O(n) |
常見思維誤區
| 題目 | 誤區 | 正確方向 |
|---|---|---|
| T1 | 每次排序找最大最小 | 計數陣列，O(1) 更新 |
| T1 | 用堆維護最大值但忽略最小值 | 雙指針同時維護 hi 和 lo |
| T2 | 直接比較 26 維頻率向量 | 隨機雜湊壓縮為單一整數 |
| T2 | 枚舉所有子段對，O(n²) | 調和級數枚舉，O(n log n) |
Amazon OA 應試策略
Amazon OA 特點
- 平台：CodeSignal
- 題目風格：模擬、貪心、雜湊為主，考察工程化思維
- 核心考點：能否把「暴力正確」的解法優化到可接受複雜度
- 資料規模通常較大，O(n²) 基本無法通過
臨場策略
- 先讀懂題，再動手——Amazon 題目描述較長，關鍵約束經常藏在最後幾行
- 先想暴力，再想優化——暴力解法能幫你理清狀態和轉移
- T1 類模擬題：先想「維護什麼狀態」，再想「怎麼高效更新」
- T2 類字串題：看到「頻率相等」立刻聯想雜湊，看到「枚舉長度」立刻聯想調和級數
- 寫完跑範例再提交，CodeSignal 有隱藏測試案例
相關 LeetCode 練習
| 題號 | 題目 | 對應 Amazon OA 考點 |
|---|---|---|
| 295 | Find Median from Data Stream | T1 動態維護雙端極值 |
| 1539 | Kth Missing Positive Number | T1 計數陣列思維 |
| 1316 | Distinct Echo Substrings | T2 字串雜湊 |
| 1044 | Longest Duplicate Substring | T2 隨機雜湊 + 枚舉 |
🚀 需要 Amazon OA 輔助？
oavoservice 專注北美大廠 OA/VO 全程輔助，Amazon OA 是我們的核心服務場景，高頻題庫覆蓋率極高。
立即加 WeChat：Coding0201
獲取：
- ✅ Amazon OA 即時輔助（螢幕共享 + 即時打字提示）
- ✅ CodeSignal 真實題庫（覆蓋 80%+ 高頻題）
- ✅ 一對一模擬 OA + 詳細回饋
- ✅ VO 面試輔助（演算法 + 系統設計）
📱 WeChat：Coding0201 | 💬 Telegram：@OAVOProxy | 📧 [email protected]