← 返回博客列表
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)

        ans = max(ans, n - left_non_overlap - right_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. 建立前綴和陣列：
    • prefix_a[k] = 球 1..k 中在 A 組的數量
    • prefix_b[k] = 球 1..k 中在 B 組的數量
    • prefix_c[k] = 球 1..k 中在 C 組的數量
  3. 枚舉分割點 i（A/B 邊界）和 j（B/C 邊界），每次 O(1) 查詢放對的球數
  4. 返回 n - max(放對的球數)

程式碼框架

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

    group = {}
    for ball in A: group[ball] = 0
    for ball in B: group[ball] = 1
    for ball in C: group[ball] = 2

    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
    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