Amazon OA 2026 Intern Real Question Review｜Permutation Sorter + Server Redirect Complete Analysis
Introduction: Amazon 2026 Intern OA exam is known for practical engineering problems. These two questions examine core problems in system optimization: how to efficiently sort permutations and how to intelligently route requests in distributed systems. The first question tests greedy strategy and cycle detection, the second tests advanced data structures and path compression optimization.
📌 Question 1: Permutation Sorter
Problem Description
Given a permutation of 1 to n, with two operations:
- Reverse operation: Reverse the entire array
- Cyclic shift operation: Move the first element to the end
Find the minimum number of operations to sort the permutation into ascending order [1, 2, 3, ..., n].
Example:
n = 10
arr = [2, 3, 4, 5, 6, 7, 8, 9, 10, 1]
Operation 1: Reverse → [1, 10, 9, 8, 7, 6, 5, 4, 3, 2]
Operation 2: Cyclic shift → [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
Operation 3: Reverse → [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Minimum operations = 3
Core Approach
Key observation: Permutation can only be transformed through reverse and cyclic shift operations.
Method 1: Check Special Cases
Step 1: Check if array is already sorted
if arr == sorted(arr):
return 0
Step 2: Check if it's a cyclic shift of sorted array
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
Step 3: If cyclic shift, calculate required operations
return start # Need 'start' cyclic shifts
Method 2: Check Reversed Array
If current array is not cyclic sorted, try reversing it first.
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)
Complete Code
from collections import deque
def findMinimumOperations(arr):
"""
Q1: Permutation Sorter
Sort permutation using reverse and cyclic shift operations
Return minimum number of operations
"""
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
# Test cases
if __name__ == "__main__":
print(findMinimumOperations([2, 3, 4, 5, 6, 7, 8, 9, 10, 1])) # Output: 3
print(findMinimumOperations([1, 2, 3, 4, 5])) # Output: 0
print(findMinimumOperations([5, 4, 3, 2, 1])) # Output: 1
Complexity Analysis
Time Complexity: O(n) for quick check, O(n! × n) for BFS worst case
Space Complexity: O(n!)
Interview Key Points
✅ Clarification: Permutation range, guarantee of solution, range of n
✅ Optimization: Check special cases first before BFS
❌ Common Mistakes: Missing cyclic shift check, BFS state explosion
📌 Question 2: Server Redirect
Problem Description
There are n servers on a 2D plane, each defined by coordinates (x, y). Given q redirect records, each specifying a direction.
Request starts from locations[0] and redirects to the nearest unvisited server in one of 4 directions:
- Direction 1: (x, y) → (x + Z, y + Z)
- Direction 2: (x, y) → (x + Z, y - Z)
- Direction 3: (x, y) → (x - Z, y + Z)
- Direction 4: (x, y) → (x - Z, y - Z)
Where Z is any positive integer. If no server exists in that direction, skip.
Return the final coordinates where the request arrives.
Core Approach
Key observation:
- Directions 1 & 3: Servers with same (x - y) value
- Directions 2 & 4: Servers with same (x + y) value
Method: Grouping + Doubly Linked List + Path Compression
Step 1: Group by (x-y) and (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])
Step 2: Use doubly linked list to maintain predecessors and successors
Step 3: Handle redirects and remove visited nodes
Complete Code
from collections import defaultdict
def getServerCoordinates(locations, redirectRecords):
"""
Q2: Server Redirect
Start from locations[0], redirect according to redirectRecords
Return final server coordinates
"""
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]
# Test cases
if __name__ == "__main__":
locations = [[3, 4], [1, 2], [2, 7], [8, 5], [5, 6]]
redirectRecords = [1, 4]
print(getServerCoordinates(locations, redirectRecords)) # Output: [5, 6]
Complexity Analysis
Time Complexity: O(n log n + q × n)
Space Complexity: O(n)
Interview Key Points
✅ Clarification: Direction definition, distance calculation, guarantee of solution
✅ Key Insight: Grouping by x-y and x+y is crucial, doubly linked list for fast deletion
❌ Common Mistakes: Confusing directions, distance calculation errors, not handling visited servers
🎯 Summary Comparison
| Question | Algorithm | Time Complexity | Difficulty |
|---|---|---|---|
| Q1: Permutation Sorter | BFS + Greedy Check | O(n) / O(n! × n) | ⭐⭐⭐ |
| Q2: Server Redirect | Grouping + Doubly Linked List | O(n log n + q×n) | ⭐⭐⭐ |
🚀 Interview Tips
- Time Management: 90 minutes for both questions, suggest 45 minutes each
- Code Quality: Focus on edge cases and data structure selection
- Communication: Clearly explain grouping strategy and optimization ideas
- Optimization Awareness: Show evolution from brute force to optimal solution
📞 Need Interview Assistance?
oavoservice provides professional OA/VO assistance services.
👉 Contact WeChat: Coding0201