Citadel OA Real Question Review｜Process Allocation + Load Balancing Complete Analysis
Introduction: Citadel's OA exam is known for system design and algorithm optimization. These two questions examine core problems in distributed systems: how to efficiently allocate process resources and how to dynamically balance processor loads. The first question tests combinatorics, the second tests binary search and greedy strategy.
📌 Question 1: Process Allocation Scheme Counting
Problem Description
Allocate n processes to k processors such that adjacent processes cannot use the same processor. Find the total number of allocation schemes modulo a given modulus.
Examples:
- n = 2, k = 3: First process has 3 choices, second process has 2 choices (cannot be same as first), total schemes = 3 × 2 = 6
- n = 1, k = 3: Only 1 process, schemes = 3
- n = 3, k = 2: Schemes = 2 × 1 × 1 = 2
Core Approach
This is a combinatorics problem solved using dynamic programming or mathematical formula.
Method 1: Mathematical Formula (Optimal)
Key Observation:
- 1st process: k choices
- 2nd to nth process: each has k-1 choices (cannot be same as previous)
Formula:
Total schemes = k × (k-1)^(n-1)
Special Cases:
- If n = 1, return k
- If k = 1 and n > 1, return 0 (impossible to satisfy adjacent different condition)
Method 2: Dynamic Programming
Define dp[i][j] as the number of schemes for first i processes allocated to processor j.
def count_allocations_dp(n, k, mod):
if n == 1:
return k % mod
if k == 1:
return 0
# dp[i][j] = schemes for first i processes, i-th allocated to processor j
dp = [[0] * k for _ in range(n + 1)]
# Initialize: 1st process can be allocated to any processor
for j in range(k):
dp[1][j] = 1
# Fill DP table
for i in range(2, n + 1):
for j in range(k):
# i-th process allocated to processor j
# (i-1)-th process must not be on processor j
for prev_j in range(k):
if prev_j != j:
dp[i][j] = (dp[i][j] + dp[i-1][prev_j]) % mod
# Sum all possible last processors
result = sum(dp[n]) % mod
return result
Time Complexity: O(n × k²)
Space Complexity: O(n × k)
Optimal Solution: Mathematical Formula + Fast Exponentiation
def count_allocations(n, k, mod):
"""
Calculate process allocation schemes
Args:
n: number of processes
k: number of processors
mod: modulus
Returns:
Total schemes % mod
"""
if n == 1:
return k % mod
if k == 1:
return 0
# Calculate k × (k-1)^(n-1) % mod
# Use fast exponentiation
base = (k - 1) % mod
power = pow(base, n - 1, mod) # Python built-in fast exponentiation
result = (k % mod * power) % mod
return result
Time Complexity: O(log n)
Space Complexity: O(1)
Complete Code
def processScheduling(n, k, mod):
"""
Q1: Process allocation scheme counting
Allocate n processes to k processors, adjacent processes cannot use same processor
Return total schemes % mod
"""
# Handle special cases
if n == 1:
return k % mod
if k == 1:
return 0
# Formula: k × (k-1)^(n-1)
# Use Python built-in pow for fast exponentiation
result = (k % mod) * pow(k - 1, n - 1, mod) % mod
return result
# Test cases
if __name__ == "__main__":
MOD = 10**9 + 7
# Test 1
print(processScheduling(2, 3, MOD)) # Output: 6
# Test 2
print(processScheduling(1, 3, MOD)) # Output: 3
# Test 3
print(processScheduling(3, 2, MOD)) # Output: 2
# Test 4: Large data
print(processScheduling(1000000, 1000000, MOD)) # Fast computation
Interview Key Points
✅ Clarification:
- Are processes ordered? (Yes, adjacent means sequential)
- What is the modulus? (Usually 10^9+7)
- What are the ranges of n and k? (Affects algorithm choice)
✅ Optimization Ideas:
- Optimize from DP to mathematical formula (O(n×k²) → O(log n))
- Use fast exponentiation for large data
❌ Common Mistakes:
- Forget to handle k=1 special case
- No fast exponentiation, causing timeout
- Incorrect modulo operation order
📌 Question 2: Processor Load Balancing Minimum Rounds
Problem Description
System has k processors with initial task allocation tasks[0..k-1]. Each round:
- Each processor can process one task (task count decreases by 1)
- Or transfer one task to another processor
Find the minimum rounds to complete all tasks with balanced processor load.
Example:
k = 3, tasks = [1, 2, 3]
Initial: processor 0 has 1 task, processor 1 has 2 tasks, processor 2 has 3 tasks
Round 1:
- Processor 0 processes 1 task → 0 remaining
- Processor 1 processes 1 task, transfers 1 to processor 0 → 1 remaining
- Processor 2 processes 1 task, transfers 1 to processor 1 → 1 remaining
Round 2:
- Processor 0 processes 1 task → 0 remaining
- Processor 1 processes 1 task → 0 remaining
- Processor 2 processes 1 task → 0 remaining
Minimum rounds = 2
Core Approach
Use binary search on the answer. For a given round count t, check feasibility.
Feasibility Check
For round count t, each processor can process at most t tasks.
Key Calculation:
- If processor i initially has
cnt[i]tasks:- If
cnt[i] > t: excessneed = cnt[i] - ttasks need transfer - If
cnt[i] ≤ t: available capacityavail = (t - cnt[i]) / 2(floor division)- Why divide by 2? Because each task transfer takes 1 round, processing takes 1 round
- If
Feasibility Condition: Total available capacity ≥ total tasks to transfer
def is_feasible(tasks, k, t):
"""
Check if round count t is feasible
"""
need = 0 # Total tasks to transfer
avail = 0 # Total available capacity
for cnt in tasks:
if cnt > t:
need += cnt - t
else:
avail += (t - cnt) // 2
return avail >= need
Binary Search
def minRounds(tasks, k):
"""
Binary search for minimum rounds
"""
# Worst case: all tasks on one processor
left, right = 1, max(tasks)
while left < right:
mid = (left + right) // 2
if is_feasible(tasks, k, mid):
right = mid
else:
left = mid + 1
return left
Complete Code
def getMinTime(k, tasks):
"""
Q2: Processor load balancing minimum rounds
Args:
k: number of processors
tasks: initial task allocation array, tasks[i] is task count on processor i
Returns:
Minimum rounds to complete all tasks
"""
def is_feasible(t):
"""Check if round count t is feasible"""
need = 0 # Total tasks to transfer
avail = 0 # Total available capacity
for cnt in tasks:
if cnt > t:
# Processor has too many tasks, need transfer
need += cnt - t
else:
# Processor has spare capacity
# Available capacity = (t - cnt) // 2
# Reason: transfer 1 task takes 1 round, processing takes 1 round, total 2 rounds
avail += (t - cnt) // 2
return avail >= need
# Binary search for minimum rounds
left, right = 1, max(tasks)
while left < right:
mid = (left + right) // 2
if is_feasible(mid):
right = mid
else:
left = mid + 1
return left
# Test cases
if __name__ == "__main__":
# Test 1
print(getMinTime(3, [1, 2, 3])) # Output: 2
# Test 2
print(getMinTime(2, [5, 5])) # Output: 5
# Test 3
print(getMinTime(4, [1, 1, 1, 1])) # Output: 1
# Test 4: Unbalanced
print(getMinTime(2, [10, 1])) # Output: 5
Complexity Analysis
Time Complexity: O(k × log(max(tasks)))
- Binary search: O(log(max(tasks)))
- Each check: O(k)
Space Complexity: O(1) (excluding input)
Interview Key Points
✅ Clarification:
- Does task transfer take time? (Yes, 1 round)
- How many tasks can one processor handle per round? (1)
- What is the goal? (Minimize total rounds)
✅ Key Insights:
- Binary search on answer space (rounds)
- Understand available capacity calculation (why divide by 2)
- Greedy strategy: prioritize processors with more tasks
❌ Common Mistakes:
- Incorrect understanding of available capacity calculation
- Binary search boundary condition errors
- Ignore time cost of task transfer
🎯 Summary Comparison
| Question | Algorithm | Time Complexity | Difficulty |
|---|---|---|---|
| Q1: Process Allocation | Combinatorics + Fast Exponentiation | O(log n) | ⭐⭐ |
| Q2: Load Balancing | Binary Search + Greedy | O(k log m) | ⭐⭐⭐ |
🚀 Interview Tips
- Time Management: 90 minutes for both questions, suggest 45 minutes each
- Code Quality: Focus on edge cases and modulo operations
- Communication: Clearly explain algorithm logic and complexity
- Optimization Awareness: Show evolution from brute force to optimal solution
📞 Need Interview Assistance?
oavoservice provides professional OA/VO assistance services.
👉 Contact WeChat: Coding0201