Amazon OA 2026 Intern 真題複盤｜排列排序 + 服務器重定向完整解析
導讀：Amazon 2026 Intern OA 考試以實際工程問題著稱。這兩道題考察的是系統優化中的核心問題：如何高效排序排列，以及如何在分佈式系統中智能路由請求。第一題考察貪心策略和循環檢測，第二題考察高級數據結構和路徑壓縮優化。
📌 題目一：排列排序（Permutation Sorter）
問題描述
給定一個 1 到 n 的排列，有兩種操作：
- 反轉操作：將整個數組反轉
- 循環移位操作：將第一個元素移到最後
求用最少操作次數將排列變成升序 [1, 2, 3, ..., n]。
示例：
n = 10
arr = [2, 3, 4, 5, 6, 7, 8, 9, 10, 1]
操作1：反轉 → [1, 10, 9, 8, 7, 6, 5, 4, 3, 2]
操作2：循環移位 → [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
操作3：反轉 → [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
最少操作數 = 3
核心思路
關鍵觀察：排列只能通過反轉和循環移位兩種操作變換。
方法一：檢查特殊情況
第一步：檢查當前數組是否已是升序
if arr == sorted(arr):
return 0
第二步：檢查是否為循環位移的升序
def is_cyclic_sorted(arr):
n = len(arr)
start = 0
while start < n and arr[start] == start + 1:
start += 1
if start == n:
return True, 0
for i in range(start, n):
if arr[i] != i + 1:
return False, -1
return True, start
第三步：如果是循環位移，計算需要的循環移位次數
return start # 需要 start 次循環移位
方法二：檢查反轉後的循環位移
如果當前數組不是循環位移的升序，嘗試反轉後是否為循環位移的升序。
def find_min_operations(arr):
n = len(arr)
is_cyclic, shift_count = is_cyclic_sorted(arr)
if is_cyclic:
return shift_count
reversed_arr = arr[::-1]
is_cyclic_rev, shift_count_rev = is_cyclic_sorted(reversed_arr)
if is_cyclic_rev:
return 1 + shift_count_rev
return bfs_min_operations(arr)
完整代碼
from collections import deque
def findMinimumOperations(arr):
"""
Q1: 排列排序
給定排列，用反轉和循環移位兩種操作排序
返回最少操作數
"""
n = len(arr)
target = list(range(1, n + 1))
if arr == target:
return 0
def is_cyclic_sorted(a):
start = 0
while start < n and a[start] == start + 1:
start += 1
if start == n:
return True, 0
for i in range(start, n):
if a[i] != i + 1:
return False, -1
return True, start
is_cyclic, shift = is_cyclic_sorted(arr)
if is_cyclic:
return shift
reversed_arr = arr[::-1]
is_cyclic_rev, shift_rev = is_cyclic_sorted(reversed_arr)
if is_cyclic_rev:
return 1 + shift_rev
queue = deque([(tuple(arr), 0)])
visited = {tuple(arr)}
target_tuple = tuple(target)
while queue:
current, ops = queue.popleft()
reversed_tuple = tuple(reversed(current))
if reversed_tuple == target_tuple:
return ops + 1
if reversed_tuple not in visited:
visited.add(reversed_tuple)
queue.append((reversed_tuple, ops + 1))
rotated_tuple = current[1:] + (current[0],)
if rotated_tuple == target_tuple:
return ops + 1
if rotated_tuple not in visited:
visited.add(rotated_tuple)
queue.append((rotated_tuple, ops + 1))
return -1
# 測試用例
if __name__ == "__main__":
print(findMinimumOperations([2, 3, 4, 5, 6, 7, 8, 9, 10, 1])) # 輸出: 3
print(findMinimumOperations([1, 2, 3, 4, 5])) # 輸出: 0
print(findMinimumOperations([5, 4, 3, 2, 1])) # 輸出: 1
複雜度分析
時間複雜度：O(n) 快速檢查，O(n! × n) BFS 最壞情況
空間複雜度：O(n!)
面試要點
✅ 澄清問題：排列範圍、是否保證有解、n 的範圍
✅ 優化思路：先檢查特殊情況再用 BFS
❌ 常見錯誤：沒有檢查循環位移、BFS 狀態爆炸
📌 題目二：服務器重定向（Server Redirect）
問題描述
在 2D 平面上有 n 個服務器，每個服務器由坐標 (x, y) 定義。給定 q 個重定向記錄，每條記錄指定一個方向。
請求從 locations[0] 開始，按照 4 個方向之一重定向到最近的未訪問服務器：
- 方向 1：(x, y) → (x + Z, y + Z)
- 方向 2：(x, y) → (x + Z, y - Z)
- 方向 3：(x, y) → (x - Z, y + Z)
- 方向 4：(x, y) → (x - Z, y - Z)
其中 Z 是任意正整數。如果該方向沒有服務器，則跳過。
求最終請求到達的服務器坐標。
核心思路
關鍵觀察：
- 方向 1 和 3：x - y 相同的服務器（x - y = constant）
- 方向 2 和 4：x + y 相同的服務器（x + y = constant）
方法：分組 + 雙向鏈表 + 路徑壓縮
第一步：按 (x-y) 和 (x+y) 分組
from collections import defaultdict
diff_map = defaultdict(list)
sum_map = defaultdict(list)
for i, (x, y) in enumerate(locations):
diff_map[x - y].append(i)
sum_map[x + y].append(i)
for key in diff_map:
diff_map[key].sort(key=lambda i: locations[i][0])
for key in sum_map:
sum_map[key].sort(key=lambda i: locations[i][0])
第二步：使用雙向鏈表維護前驅後繼
第三步：處理重定向，刪除已訪問的節點
完整代碼
from collections import defaultdict
def getServerCoordinates(locations, redirectRecords):
"""
Q2: 服務器重定向
從 locations[0] 開始，按照 redirectRecords 重定向
返回最終到達的服務器坐標
"""
if not locations:
return []
n = len(locations)
visited = set()
diff_map = defaultdict(list)
sum_map = defaultdict(list)
for i, (x, y) in enumerate(locations):
diff_map[x - y].append(i)
sum_map[x + y].append(i)
for key in diff_map:
diff_map[key].sort(key=lambda i: locations[i][0])
for key in sum_map:
sum_map[key].sort(key=lambda i: locations[i][0])
current_idx = 0
visited.add(current_idx)
for direction in redirectRecords:
x, y = locations[current_idx]
next_idx = None
if direction == 1:
key = x - y
target_sum = x + y
best_dist = float('inf')
for idx in diff_map[key]:
if idx not in visited:
nx, ny = locations[idx]
dist = abs(nx + ny - target_sum)
if dist < best_dist:
best_dist = dist
next_idx = idx
elif direction == 2:
key = x + y
target_diff = x - y
best_dist = float('inf')
for idx in sum_map[key]:
if idx not in visited:
nx, ny = locations[idx]
dist = abs(nx - ny - target_diff)
if dist < best_dist:
best_dist = dist
next_idx = idx
elif direction == 3:
key = x + y
target_diff = x - y
best_dist = float('inf')
for idx in sum_map[key]:
if idx not in visited:
nx, ny = locations[idx]
dist = abs(nx - ny - target_diff)
if dist < best_dist:
best_dist = dist
next_idx = idx
elif direction == 4:
key = x - y
target_sum = x + y
best_dist = float('inf')
for idx in diff_map[key]:
if idx not in visited:
nx, ny = locations[idx]
dist = abs(nx + ny - target_sum)
if dist < best_dist:
best_dist = dist
next_idx = idx
if next_idx is not None:
current_idx = next_idx
visited.add(current_idx)
return locations[current_idx]
# 測試用例
if __name__ == "__main__":
locations = [[3, 4], [1, 2], [2, 7], [8, 5], [5, 6]]
redirectRecords = [1, 4]
print(getServerCoordinates(locations, redirectRecords)) # 輸出: [5, 6]
複雜度分析
時間複雜度：O(n log n + q × n)
空間複雜度：O(n)
面試要點
✅ 澄清問題：方向定義、距離計算方式、是否保證有解
✅ 關鍵洞察：按 x-y 和 x+y 分組是關鍵、雙向鏈表快速刪除
❌ 常見錯誤：混淆方向、距離計算錯誤、沒有處理已訪問服務器
🎯 總結對比
| 題目 | 算法 | 時間複雜度 | 難度 |
|---|---|---|---|
| Q1：排列排序 | BFS + 貪心檢查 | O(n) / O(n! × n) | ⭐⭐⭐ |
| Q2：服務器重定向 | 分組 + 雙向鏈表 | O(n log n + q×n) | ⭐⭐⭐ |
🚀 面試建議
- 時間管理：兩道題共 90 分鐘，建議各 45 分鐘
- 代碼質量：注重邊界條件和數據結構選擇
- 溝通能力：清晰解釋分組策略和優化思路
- 優化意識：從暴力解到最優解的演進過程
📞 需要面試輔助？
oavoservice 提供專業的 OA/VO 輔助服務。
👉 立即添加微信：Coding0201