Amazon 亚马逊 OA 真题解析

题目 1：机器人协作系统有效配置计数

题目描述

在亚马逊仓库机器人系统中，多个机器人同时运行以高效运输包裹。每个机器人可以处于两种状态之一：待机（Standby）或运行（Operating）。

为了协调顺畅，每个机器人 i 都有一个预定义的协调阈值 coordinationThreshold[i]。这个阈值决定了机器人何时会发生故障：

如果机器人 i 处于运行状态，但其他处于运行状态的机器人总数小于 coordinationThreshold[i]，则该机器人发生故障。
如果机器人 i 处于待机状态，但处于运行状态的机器人总数大于或等于 coordinationThreshold[i]，则该机器人发生故障。

如果任意机器人发生故障，则系统被视为不稳定。返回没有机器人发生故障的不同有效配置的总数量。

注意：配置是对 n 个机器人每个分配为运行或待机状态。如果在这种分配下没有机器人发生故障，则配置被认为是有效的。如果至少有一个机器人处于不同的状态，则两个配置是不同的。

示例

n = 8
coordinationThreshold = [6, 0, 3, 3, 6, 7, 2, 7]

有三个有效方式选择处于运行状态的机器人：

只有索引 1 处的机器人处于运行状态（coordinationThreshold[1] = 0）。由于至少有 0 个其他机器人在运行，它满足阈值。所有其他机器人保持待机状态，且它们的 coordinationThreshold 值超过 1 个运行中的机器人，确保系统稳定。
索引 1、2、3 和 6 处的机器人处于运行状态（coordinationThreshold 值为：0、3、3 和 2）。这是有效的，因为这些机器人每个都有至少 coordinationThreshold[i] 个其他机器人在运行，且所有处于待机状态的其他机器人的 coordinationThreshold 值都大于运行中的机器人数量，防止故障发生。
所有机器人都处于运行状态。这是有效的，因为每个机器人都至少有 coordinationThreshold[i] 个其他机器人在运行，确保系统稳定。

因此，有效配置的总数量为 3。

函数描述

在编辑器中完成函数 getValidConfigurations，参数如下：

int[] coordinationThreshold：数组，其中 coordinationThreshold[i] 表示第 i 个机器人正确运行所需处于运行状态的其他机器人的最小数量

返回值

int：确保系统稳定（无故障）的机器人运行状态有效配置的数量

Constraints

2 ≤ n ≤ 2 * 10⁵
0 ≤ coordinationThreshold[i] ≤ n - 1

解题思路

方法：排序与贪心边界判定

该问题的核心在于：一个有效的配置仅取决于处于运行状态（Operating）的机器人数量 $k$。

核心逻辑：
- 若机器人 $i$ 处于 Operating 状态，需满足 k-1 <= coordinationThreshold[i]（即 coordinationThreshold[i] < k）。
- 若机器人 $i$ 处于 Standby 状态，需满足 k < coordinationThreshold[i]（即 coordinationThreshold[i] > k）。
排序简化：将阈值数组 s 进行升序排序。对于任意数量 $k$：
- 前 k 个机器人（阈值最小的）必须处于 Operating 状态，其最大阈值 s[k-1] 必须满足 s[k-1] < k。
- 后 n-k 个机器人（阈值最大的）必须处于 Standby 状态，其最小阈值 s[k] 必须满足 s[k] > k。
边界情况：
- k=0（全部 Standby）：只需最小阈值 s[0] > 0。
- k=n（全部 Operating）：只需最大阈值 s[n-1] < n。

复杂度分析

时间复杂度：O(n \log n)。主要瓶颈在于对 coordinationThreshold 数组进行排序，后续遍历数组只需 O(n)。
空间复杂度：O(n)。取决于排序算法在 Python 中的空间消耗（通常为 O(n)）以及存储排序后数组的空间。

题目 2：服务器功率非递减最小增量求和

题目描述

AWS 提供可扩展系统。一组 n 台服务器用于水平扩展应用程序。目标是使服务器的算力按非递减顺序排列。为此，您可以对任意连续段中的每台服务器增加 x 的算力。选择 x 的值，使得在算力按非递减顺序排列后，x 值之和最小。

示例

有 n = 5 台服务器，其算力为 [3, 4, 1, 6, 2]。

对子数组 (2, 4) 增加 3 个单位，对子数组 (4, 4) 增加 4 个单位。服务器最终排列为：[3, 4, 4, 9, 9]。答案为 3 + 4 = 7。

函数描述

完成以下函数 findMinimumSum。

findMinimumSum 有以下参数：

int power[n]：n 台不同服务器的算力

返回值

int：使数组变为非递减所需的最小整数和

解题思路

方法：贪心差值累加

该算法的核心思想是贪心策略。为了使服务器功率序列满足非递减要求且增加的总代价最小，我们从左向右遍历数组。每当发现当前位置的功率 power[i] 小于前一个位置的功率 power[i-1] 时，我们必须至少补齐这个差值。

由于题目允许对连续子段进行加值操作，最优的选择是每次发现"跌落"时，将从当前位置 i 到数组末尾的所有元素同时增加 power[i-1] - power[i]。这样做既解决了当前的递减问题，又不会改变后续元素之间的相对大小关系，且能最大程度地辅助后续元素满足非递减条件。最终的最小总代价即为所有相邻递减差值的总和。

复杂度分析

时间复杂度：O(n)，其中 n 是服务器的数量，只需对数组进行一次线性遍历。
空间复杂度：O(1)，仅使用了常数级别的额外变量（res, n, i, d）。

总结

本题涵盖了两类经典的算法问题：

机器人协作系统 - 通过排序和贪心边界判定，将复杂的状态组合问题简化为对单一参数（运行中机器人数量 $k$）的枚举，大幅降低时间复杂度。
服务器功率问题 - 利用贪心策略，每次遇到递减就补齐差值，这种局部最优选择能保证全局最优，体现了贪心算法的核心思想。

大家有需要Amazon oa题库的都可以联系，做了比较多了，基本上都围绕题库进行出题