← 返回博客列表
OA Amazon

Amazon OA 真题复盘：区间最大选取 + 球分组最少移动（n log n 优化）

2026-03-29

Amazon OA 两道题，考察二分 + 贪心 + 前缀和的综合运用。思路不难但实现细节多，节奏要稳。以下是完整复盘。

Amazon OA Q1 截图

考试概况

项目 详情
平台 HackerRank
题数 2 道
难度 Medium / Medium-Hard
岗位 SDE
核心考点 区间、二分、前缀和、贪心

Q1：区间最大选取（Interval Selection with Central Overlap）

Amazon OA Q1

题目核心

给定 n 个区间，从中选出尽可能多的区间，满足：其中存在一个"中心区间"，能与所有其他选中的区间都相交。求最多能选多少个区间。

解题思路

暴力思路（O(n²)，会超时）

枚举每个区间作为"中心区间"，统计它能与多少其他区间相交，取最大值。

但 n 可达 10⁵ 级别，O(n²) 必然超时，需要优化。

优化思路：反向计数 + 二分（O(n log n)）

关键转化：与其正向统计"能相交的区间数"，不如反向统计"一定不相交的区间数"。

两个区间 [a, b] 和 [c, d] 不相交，当且仅当：

算法步骤：

  1. 将所有区间按左端点排序，同时维护一个按右端点排序的数组
  2. 对于每个区间 [a, b] 作为中心区间：
    • 用二分在右端点数组中找出所有 right < a 的区间数量（完全在左侧）
    • 用二分在左端点数组中找出所有 left > b 的区间数量（完全在右侧）
    • 不相交数 = 两者之和
    • 相交数 = n - 不相交数
  3. 取所有中心区间对应相交数的最大值

代码框架

import bisect

def solution(intervals):
    n = len(intervals)
    if n == 0:
        return 0

    # 按左端点排序，用于二分查找「完全在右侧」的区间
    left_sorted = sorted(x[0] for x in intervals)
    # 按右端点排序，用于二分查找「完全在左侧」的区间
    right_sorted = sorted(x[1] for x in intervals)

    ans = 0
    for a, b in intervals:
        # 右端点 < a 的区间数：完全在当前区间左侧（不相交）
        left_non_overlap = bisect.bisect_left(right_sorted, a)
        # 左端点 > b 的区间数：完全在当前区间右侧（不相交）
        right_non_overlap = n - bisect.bisect_right(left_sorted, b)

        non_overlap = left_non_overlap + right_non_overlap
        ans = max(ans, n - non_overlap)

    return ans

复杂度分析

关键洞察

正向统计「与中心区间相交的数量」需要枚举，不好做；反向统计「一定不相交的数量」可以用二分直接得到，这是本题的核心优化点。

Q2：球分组最少移动（Ball Partition Min Moves）

Amazon OA Q2

题目核心

有编号 1 到 n 的球，分别放在 A、B、C 三组里。将三组按顺序拼接（A + B + C）后，要求恰好是 1, 2, 3, ..., n 的递增序列。每次可以把一个球从一组移到另一组，求最少移动次数。

解题思路

核心观察

最终结果是 A、B、C 拼接后为 [1..n]，因此三组的结构必然是：

其中 0 ≤ i ≤ j ≤ n（允许某组为空）。

关键性质

球在组内的相对顺序不影响移动次数，只有球是否在正确的组里才重要。原本就在正确组里的球不需要移动，其余的都需要移动一次。

最少移动次数 = n - 原本就放对了的球的数量

算法步骤

  1. 记录每个球 k 当前在哪组（A=0, B=1, C=2）
  2. 枚举分割点 i（A/B 的边界）和 j（B/C 的边界）
  3. 对于每种分割方案，统计放对的球数：
    • 球 k ∈ [1..i] 在 A 组中的数量
    • 球 k ∈ [i+1..j] 在 B 组中的数量
    • 球 k ∈ [j+1..n] 在 C 组中的数量
  4. 用前缀和预处理，使每次查询 O(1)，总复杂度 O(n)

代码框架

def solution(A, B, C):
    n = len(A) + len(B) + len(C)

    # 记录每个球在哪组 (1-indexed)
    group = {}
    for ball in A:
        group[ball] = 0  # A
    for ball in B:
        group[ball] = 1  # B
    for ball in C:
        group[ball] = 2  # C

    # 前缀和：prefix_a[k] = 球 1..k 中在 A 组的数量
    prefix_a = [0] * (n + 1)
    prefix_b = [0] * (n + 1)
    prefix_c = [0] * (n + 1)
    for k in range(1, n + 1):
        prefix_a[k] = prefix_a[k-1] + (1 if group[k] == 0 else 0)
        prefix_b[k] = prefix_b[k-1] + (1 if group[k] == 1 else 0)
        prefix_c[k] = prefix_c[k-1] + (1 if group[k] == 2 else 0)

    min_moves = n  # 最坏情况：全部移动

    # 枚举分割点 i（A 包含 1..i）和 j（B 包含 i+1..j）
    for i in range(0, n + 1):
        for j in range(i, n + 1):
            # 放对的球数
            correct = prefix_a[i] \
                    + (prefix_b[j] - prefix_b[i]) \
                    + (prefix_c[n] - prefix_c[j])
            min_moves = min(min_moves, n - correct)

    return min_moves

优化：双层枚举仍是 O(n²)，可进一步用后缀最大值优化到 O(n)，此处展示思路框架。

复杂度分析

关键洞察

不需要考虑组内顺序，只需关心球是否在正确的组。枚举分割点 + 前缀和，把「统计放对的球」变成 O(1) 查询，是本题的核心技巧。

两题核心思路对比

题目 核心技巧 时间复杂度 空间复杂度
Q1 区间选取 排序 + 二分反向计数 O(n log n) O(n)
Q2 球分组 枚举分割点 + 前缀和 O(n) O(n)

常见思维误区

题目 误区 正确方向
Q1 正向枚举相交区间，O(n²) 超时 反向计数不相交，二分优化到 O(n log n)
Q1 二分边界写错（bisect_left vs right） 仔细区分严格小于和小于等于
Q2 考虑组内顺序，思路复杂化 只看球是否在正确组，顺序无关
Q2 忘记某组可以为空的情况 枚举 i、j 时允许 i=0 或 j=n

Amazon OA 应试策略

临场节奏

  1. 先读完两题，判断难度分配时间
  2. Q1 类区间题：先想「两区间不相交的条件」，反向计数往往更简洁
  3. Q2 类分组题：先确定最终状态的结构，再用前缀和加速统计
  4. 写完跑样例，边界（空组、单元素）必须验证

相关 LeetCode 练习

题号 题目 对应考点
435 Non-overlapping Intervals Q1 区间不相交
452 Minimum Arrows to Burst Balloons Q1 区间相交
56 Merge Intervals Q1 区间合并
1043 Partition Array for Maximum Sum Q2 分割点枚举
813 Largest Sum of Averages Q2 前缀和 + 枚举

🚀 需要 Amazon OA 辅助？

oavoservice 长期稳定承接 Google、Amazon、TikTok、Uber、Bloomberg、微软 等各大科技公司 OA / VO 辅助，国内外面试笔试均可，高频题库覆盖率极高。

立即添加微信：Coding0201

获取：

📱 微信：Coding0201 | 💬 Telegram：@OAVOProxy | 📧 [email protected]

联系方式

Email: [email protected]
Telegram: @OAVOProxy