OA代做 | 编程代写 | 代面试 | vo辅助 | 面试辅助 | 一亩三分地 | hackerrank代考
返回文章列表
AmazonOAAlgorithmhackerrank

Amazon 亚马逊 OA 真题解析

•

Amazon 亚马逊 OA 真题解析

题目 1：VM 租赁收益最大化

题目描述

在 Amazon EC2 中，有 n 种虚拟机类型，每种类型有一定数量的实例可用。每次租用虚拟机时，客户支付的费用等于：所有 VM 类型中最低非零库存量 + 最高库存量。

有 m 个客户依次到达。每个客户总是从当前库存量最高的 VM 类型租用。租用后，该 VM 类型的库存减少 1。求服务完所有租赁请求后的总收入。

示例

  • n = 3
  • vmStock = [1, 2, 4]
  • m = 4

| Customer | VM type | Cost | Remaining | |----------|---------|------|-----------| | Initial state | — | — | [1, 2, 4] | | 1 | 3 | 1 + 4 = 5 | [1, 2, 3] | | 2 | 3 | 1 + 3 = 4 | [1, 2, 2] | | 3 | 2 (or 3) | 1 + 2 = 3 | [1, 1, 2] | | 4 | 3 | 1 + 2 = 3 | [1, 1, 1] |

总收入：5 + 4 + 3 + 3 = 15，答案为 15。

约束

  • 1 ≤ n ≤ 10^5
  • 1 ≤ vmStock[i] ≤ 10^6
  • 1 ≤ m ≤ 10^6
  • 所有 vmStock[i] 之和始终大于 m

题目 2：安全仓库最大配送数

题目描述

作为汽车制造公司的物流经理，你需要将配送物品存放到安全的仓库中。

给定一个大小为 n 的数组 deliveryLogs，每个元素表示第 i 个日志的配送数量。给定一个偶数 k，表示可用的安全仓库数量。

存储规则：

  • 每个仓库只能存储来自单个配送日志的物品，来自不同日志的物品不能混合存放在同一仓库，但来自同一日志的物品可以拆分到多个仓库
  • 存储后，正好有 k/2 个拥有最多物品的仓库会被 compromise
  • 剩余 k/2 个仓库是安全的，其中存放的物品才算安全

求能够存储的最大安全物品数。

示例

  • n = 4
  • deliveryLogs = [3, 5, 9, 6]
  • k = 4

答案为 9（详细分析见原题）

约束

  • 1 ≤ n ≤ 1000
  • 2 ≤ k ≤ 1000
  • 0 ≤ deliveryLogs[i] ≤ 1000
  • k 是偶数

解题思路

题目 1 解法：最大堆 + 频率数组维护最值

  1. 核心规则回顾 每次租赁当前库存量最大的虚拟机，租金 = 当前所有虚拟机中非零最小库存量 + 最大库存量，租赁后对应虚拟机库存减 1，执行 m 次后统计总收益。

  2. 算法核心设计

    • 用最大堆：快速获取每一轮库存量最大的虚拟机（Python 无原生最大堆，用最小堆存储负数实现等效效果）
    • 用频率数组：统计每个库存数值出现的次数，O(1) 快速定位当前非零最小库存量，避免每次遍历全数组
    • 迭代流程：循环 m 次，每次取出堆顶最大库存 → 计算租金并累加 → 更新库存和频率数组 → 将新库存重新入堆 → 同步维护最小非零库存

  3. 关键优化点 堆内做合法性校验，剔除过期无效的库存数据；最小非零值实时更新，保证每次计算租金的效率

复杂度分析

  • 时间复杂度：O(m log n)（m 次堆操作，单次堆操作耗时 log n）
  • 空间复杂度：O(n + maxStock)（堆存储 n 个元素，频率数组长度为最大库存值）

题目 2 解法：阈值枚举 + 贪心 + 余数排序

  1. 核心规则回顾 k 个仓库（偶数），单个仓库只能存放同一份配送日志的货物，一份日志可拆分；最大的 k/2 个仓库货物失效，求剩余 k/2 个仓库的最大货物总量

  2. 算法核心设计

    • 枚举阈值 t：假设最终安全仓库的单仓最大容量为 t，遍历所有可能的 t（范围 1 ~ 最大单份配送量）
    • 拆分计算：对每份日志，计算能拆出多少个满 t 容量的仓库（商）和最后一个不足 t 的余数
    • 贪心筛选：统计总满仓数，优先取满仓凑够 k/2 个安全仓库，若满仓数不足，用最大的余数补足
    • 记录最大值：遍历所有阈值，保留能得到的最大安全货物总量

  3. 关键优化点 余数排序后取最大的几个补足缺口，保证总和最大化；仅枚举有效阈值，无冗余计算

复杂度分析

  • 时间复杂度：O(maxVal × n log n)（maxVal 为最大配送量，每次遍历需排序余数数组）
  • 空间复杂度：O(n)（存储每份日志的余数）

总结

两道题目都是考察对数据结构的灵活运用和贪心算法的理解：

  1. 第一题关键在于高效维护最大堆和最小非零值，可以用最大堆 + 频率数组的组合达到 O(m log n) 的复杂度
  2. 第二题核心思路是枚举阈值 + 贪心选择，通过拆分日志来平衡仓库数量，是典型的二分/枚举优化问题

大家有需要近期Amazon OA题库的也可以联系，重复概率非常高。 如果怕拿捏不稳，也可以找我们辅助。