最近🇺🇸亚麻又在开始批量发oa了，Coding+Work Simulation +Workstyles Assessments (two parts)，相当于把以前不同轮次的OA整合在了一起； Amazon oa coding部分更新的高频题汇总了，领取可以联系我们，还是70分钟2题；
通常，Code question的第一个题需要15/15通过测试用例，第二个Code题目最低12/15。分享下最近做过的Amazon oa真题。
Amazon OA Q1：内容分发负载均衡
这道题更像亚麻的视频分发的逻辑，题目给出了N 个服务器的负载情况，之后系统会增加K个请求，要求 是模拟请求的分配情况。每次请求分配都需要分配到负载最低的那台服务器上，之后更新这台服务器的负载情况，循环这个过程。这样在做完M次分配后，要求从小到大排序输出每台服务器的负责情况。
解题思路
这道题用最小堆就可以，把每台服务器的负载情况放到最小堆里，堆顶就是负载最小的服务器，这台服务器增加K个请求后放回堆里，然后堆做调整，保持最小堆的特性，堆操作的时间复杂度是O(logN)，但是这个过程需要操作M次，所以总的复杂度是 O(Mlog N)。
在编码过程中需要考虑下边界情况，比如N = 0 (空服务器)、N = 1 (单一服务器)、K = 0 (无请求)、负载有负数、所有负载相同和N很大的情况，另外最终输出前要把堆中的内容弹出，这样才能保证排序是正确的。
Amazon OA Q2：虚拟机租用的费用
有 n种 VM 类型，初始存量 vmStock[n]。每种类型初始有一定数量的可用实例。现在有 m 个 客户依次到来，每个客户都会选择当前剩余数量最多的那种 VM 类型来租用一台，每次租用成功后，客户需要支付的费用为：
- 当前所有 VM 类型中，剩余数量 > 0 的类型里，最小的剩余数量
- 当前所有 VM 类型中，最大的剩余数量
要求：模拟完 m 个客户全部租用后，计算总收入
解题思路
这道题用堆的模拟即可，用最大堆维护当前每种 VM 的剩余库存，每次弹出当前库存最大的 VM，计算费用后减 1，再放回堆，在用最小堆额外维护当前所有非零的剩余数量，累加所有费用就是总费用，堆的时间复杂度是O(log N)，但是需要做m次计算，总的时间复杂度是O(m log n)。
Amazon OA Q3：带宽权重总和
n 个处理节点，每个节点的带宽能力在数组 bandwidth 中给出。要建立 streamCount 条数据通道。
每条通道需要选择一对节点，从中选出streamCount 个不重复的对，让权值总和最大。
解题思路
这道题思路比较简单，先将带宽数组降序排序，用最大堆逐步取出前 K 大。计算每个节点作为主连接的最大可能贡献：前 streamCount 个最高带宽节点作为主连接放到最大堆，每个主连接搭配当前剩余的最高带宽节点（可以是自身），每次弹出堆顶，把它的值累加进答案，求这些配对的和即可。
Amazon OA Q4：Amazon订阅方案
需要设计Amazon新的订阅方案：总费用 = 基础套餐费用 + 附加功能费用，需要求在一个 n × m 的“套餐 + 功能”二维组合中，排除若干非法点，求剩余点中 planCost[i] + featureCost[j] 的最大值，限制条件是有X个 不允许的组合，X中的基础套餐与附加功能不能同时选择。
解题思路
暴力方法是枚举所有的组合，用set存非法组合，如果当前选择不在非法集合中，就计算花费结果，时间复杂度是O(n * m)，但是当n或者m很大时，会出现超时异常。
优化解法
先按照费用从大到小排序，然后遍历，一旦找到可用 feature（找第一个不在非法集合里的 feature），就不需要继续往下找了，维护一个全局最大值即可。
Amazon OA 就像一场限时的马拉松，你要又快又准，还不能掉链子。我们在 Interview Aid 已经帮过很多同学稳稳通过这一关，不仅拿到高分，如果你马上要参加 Amazon SDE Intern OA，想要稳稳的通过，请与我们联系。