又一场 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 是我们的核心服务场景，高频题库覆盖率极高。
立即添加微信：Coding0201
获取：
- ✅ Amazon OA 实时辅助（屏幕共享 + 实时打字提示）
- ✅ CodeSignal 真实题库（覆盖 80%+ 高频题）
- ✅ 一对一模拟 OA + 详细反馈
- ✅ VO 面试辅助（算法 + 系统设计）
📱 微信：Coding0201 | 💬 Telegram：@OAVOProxy | 📧 [email protected]