Question 1: Bug Report Priority Sorting
Problem Description
You are helping Amazon's Quality Assurance engineers process bug reports generated from automated testing logs. Each log contains an integer bug code, and a single test session may include duplicate bug codes.
Sorting Rules:
- Bugs with lower frequency have higher priority (may indicate rare or edge-case issues)
- If two bugs have the same frequency, the bug with the lower code number has higher priority
Task: Sort the bug codes according to the above rules.
Example
Input: bugs = [8, 4, 6, 5, 4, 8]
| Bug Code | Frequency |
|---|---|
| 8 | 2 |
| 4 | 2 |
| 6 | 1 |
| 5 | 1 |
Sorting Process:
- Bugs with frequency 1: 6 and 5, sort by code →
[5, 6] - Bugs with frequency 2: 8 and 4, sort by code →
[4, 8] - Final Output:
[5, 6, 4, 8]
Solution Approach
Method 1: Sorting + Hash Table (O(n log n)) ⭐ Recommended
def sortBugReportFrequencies(bugs):
from collections import Counter
# Count frequency of each bug
freq = Counter(bugs)
# Sort by frequency first, then by code number
sorted_bugs = sorted(freq.keys(), key=lambda x: (freq[x], x))
return sorted_bugs
Time Complexity: O(n log n) (sorting) Space Complexity: O(n) (hash table)
Method 2: Custom Comparator
def sortBugReportFrequencies(bugs):
from collections import Counter
from functools import cmp_to_key
freq = Counter(bugs)
def compare(a, b):
# Compare frequency first
if freq[a] != freq[b]:
return freq[a] - freq[b]
# If frequency is same, compare code number
return a - b
sorted_bugs = sorted(freq.keys(), key=cmp_to_key(compare))
return sorted_bugs
Key Points
✅ Use hash table to count frequency: O(n) time ✅ Dual sorting conditions: Frequency first, then code number ✅ Leverage Python's sorted() with key parameter: Concise and efficient ✅ Consider edge cases: Single bug, all bugs identical, etc.
Question 2: Warehouse Secure Storage Maximization
Problem Description
As a logistics manager in an automobile manufacturing company, you need to store parts in k secure warehouses.
Storage Rules:
- Each warehouse can only store parts from a single delivery log
- Parts from different logs cannot be mixed in the same warehouse
- Parts from a single log can be distributed across multiple warehouses
Security Threat:
- After storage, the k/2 warehouses with the most deliveries will be compromised
- Only parts in the remaining k/2 warehouses are considered secure
Task: Find the maximum number of secure deliveries.
Example
Input:
n = 4deliveryLogs = [3, 5, 9, 6]k = 4
Analysis:
Plan 1 (No optimization):
- Store each log separately:
[3, 5, 9, 6] - Top 2 warehouses:
[9, 6]are compromised - Secure deliveries:
3 + 5 = 8
Plan 2 (Optimized):
- Distribute log 2 (5 parts):
- Warehouse 1: 3 parts (from log 1)
- Warehouse 2: 5 parts (from log 2)
- Distribute log 3 (9 parts):
- Warehouse 2: 4 parts (from log 3)
- Warehouse 3: 5 parts (from log 3)
- Distribute log 4 (6 parts):
- Warehouse 3: 1 part (from log 4)
- Warehouse 4: 5 parts (from log 4)
Result: [3, 5, 5, 5]
- Top 2 warehouses:
[5, 5]are compromised - Secure deliveries:
3 + 5 = 8
Solution Approach
Method: Greedy + Binary Search (O(n log m)) ⭐ Optimal
Core Idea:
- Sort delivery quantities in descending order
- Use binary search to find the maximum secure deliveries
- For each candidate answer, check if it's feasible
def maximumSecureDeliveries(deliveryLogs, k):
def canAchieve(target):
# Check if we can achieve target secure deliveries
warehouses = []
for delivery in deliveryLogs:
remaining = delivery
# Try to fill existing warehouses (not exceeding target)
for i in range(len(warehouses)):
if warehouses[i] < target:
add = min(remaining, target - warehouses[i])
warehouses[i] += add
remaining -= add
if remaining == 0:
break
# If remaining, create new warehouses
while remaining > 0:
add = min(remaining, target)
warehouses.append(add)
remaining -= add
# Check if we have enough secure warehouses
safe_count = sum(1 for w in warehouses if w == target)
return len(warehouses) <= k and safe_count >= k // 2
# Binary search for maximum secure deliveries per warehouse
left, right = 0, sum(deliveryLogs)
result = 0
while left <= right:
mid = (left + right) // 2
if canAchieve(mid):
result = mid
left = mid + 1
else:
right = mid - 1
return result * (k // 2)
Time Complexity: O(n log m), where m is total deliveries Space Complexity: O(k)
Key Points
✅ Understand the problem essence: Maximize parts in secure warehouses ✅ Greedy strategy: Balance parts across warehouses ✅ Binary search: Find balance between feasibility and optimality ✅ Edge cases: k = 1, all deliveries identical, etc.
Common Pitfalls
Question 1
❌ Sort only by frequency, forget to handle same frequency cases
✅ Use tuple sorting: (freq[x], x)
❌ Sort original array directly, causing duplicate counting ✅ Count frequency first, then sort unique values
Question 2
❌ Greedily place all parts in one warehouse ✅ Need to distribute parts to maximize secure storage
❌ Forget the constraint that k/2 warehouses are compromised ✅ Ensure enough secure warehouses remain
Interview Tips
Question 1:
- Start with simple sorting
- Explain why dual sorting conditions are needed
- Show how to use Python's sorting features
Question 2:
- Understand the problem constraints first
- Start with brute force (each log stored separately)
- Gradually optimize to greedy + binary search
- Demonstrate algorithm with concrete examples
🚀 Need Interview Assistance?
oavoservice provides professional Amazon OA/VO assistance services.
👉 Contact WeChat: Coding0201
Get:
- Real OA question bank
- One-on-one mock interviews
- Real-time coding assistance
- On-site response strategies