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
第二步：检查是否为循环位移的升序
- 找到第一个不满足
arr[i] == i+1的位置 - 检查从该位置开始是否为循环升序
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 # 已排序
# 检查从start开始是否为循环升序
for i in range(start, n):
if arr[i] != i + 1:
return False, -1
return True, start # 返回循环位移的起始位置
第三步：如果是循环位移，计算需要的循环移位次数
# 需要 start 次循环移位将第一个元素移到正确位置
return 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 # 1次反转 + shift_count_rev次循环移位
# 如果都不满足，需要更复杂的操作序列
# 使用BFS找最短路径
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
# 使用BFS找最短路径
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) # diff_map[x-y] = [(x, y), ...]
sum_map = defaultdict(list) # sum_map[x+y] = [(x, y), ...]
for i, (x, y) in enumerate(locations):
diff_map[x - y].append(i)
sum_map[x + y].append(i)
# 按 x 坐标排序
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])
第二步：使用双向链表维护前驱后继，删除已访问的节点
class Node:
def __init__(self, idx):
self.idx = idx
self.prev = None
self.next = None
# 构建双向链表
diff_lists = {}
for key, indices in diff_map.items():
nodes = [Node(idx) for idx in indices]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i + 1]
nodes[i + 1].prev = nodes[i]
diff_lists[key] = {indices[i]: nodes[i] for i in range(len(nodes))}
第三步：处理重定向，删除已访问的节点
def redirect(x, y, direction):
if direction == 1:
# x-y 不变，在 diff_map 中找最接近的
key = x - y
target_sum = x + y
# 遍历链表找最接近的未删除节点
...
# 类似处理其他方向
完整代码
from collections import defaultdict
def getServerCoordinates(locations, redirectRecords):
"""
Q2: 服务器重定向
从 locations[0] 开始，按照 redirectRecords 重定向
返回最终到达的服务器坐标
"""
if not locations:
return []
n = len(locations)
visited = set()
# 按 x-y 和 x+y 分组
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:
# (x, y) → (x+Z, y+Z)，x-y 不变
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:
# (x, y) → (x+Z, y-Z)，x+y 不变
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:
# (x, y) → (x-Z, y+Z)，x+y 不变
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:
# (x, y) → (x-Z, y-Z)，x-y 不变
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