Citadel OA 真題複盤｜進程分配 + 負載均衡兩道題完整解析
導讀：Citadel 的 OA 考試以系統設計和算法優化著稱。這兩道題考察的是分佈式系統中的核心問題：如何高效分配進程資源，以及如何動態平衡處理器負載。第一題考察組合數學，第二題考察二分查找與貪心策略。
📌 題目一：進程分配方案計數
問題描述
將 n 個進程分配到 k 個處理器，要求相鄰進程不能使用同一處理器。求滿足條件的分配方案總數，結果對給定模數取模。
示例：
- n = 2, k = 3：第一個進程有 3 種選擇，第二個進程有 2 種選擇（不能與第一個相同），總方案數 = 3 × 2 = 6
- n = 1, k = 3：只有 1 個進程，方案數 = 3
- n = 3, k = 2：方案數 = 2 × 1 × 1 = 2
核心思路
這是一個組合數學問題，使用動態規劃或數學公式求解。
方法一：數學公式（最優）
關鍵觀察：
- 第 1 個進程：有 k 種選擇
- 第 2 到第 n 個進程：每個都有 k-1 種選擇（不能與前一個相同）
公式：
總方案數 = k × (k-1)^(n-1)
特殊情況：
- 若 n = 1，返回 k
- 若 k = 1 且 n > 1，返回 0（無法滿足相鄰不同的條件）
方法二：動態規劃
定義 dp[i][j] 表示前 i 個進程分配到處理器 j 的方案數。
def count_allocations_dp(n, k, mod):
if n == 1:
return k % mod
if k == 1:
return 0
# dp[i][j] = 前i個進程，第i個分配到處理器j的方案數
dp = [[0] * k for _ in range(n + 1)]
# 初始化：第1個進程可以分配到任何處理器
for j in range(k):
dp[1][j] = 1
# 填充DP表
for i in range(2, n + 1):
for j in range(k):
# 第i個進程分配到處理器j
# 第i-1個進程必須不在處理器j
for prev_j in range(k):
if prev_j != j:
dp[i][j] = (dp[i][j] + dp[i-1][prev_j]) % mod
# 求和所有可能的最後一個處理器
result = sum(dp[n]) % mod
return result
時間複雜度：O(n × k²)
空間複雜度：O(n × k)
最優解：數學公式 + 快速冪
def count_allocations(n, k, mod):
"""
計算進程分配方案數
Args:
n: 進程數
k: 處理器數
mod: 模數
Returns:
方案總數 % mod
"""
if n == 1:
return k % mod
if k == 1:
return 0
# 計算 k × (k-1)^(n-1) % mod
# 使用快速冪優化
base = (k - 1) % mod
power = pow(base, n - 1, mod) # Python內置快速冪
result = (k % mod * power) % mod
return result
時間複雜度：O(log n)
空間複雜度：O(1)
完整代碼
def processScheduling(n, k, mod):
"""
Q1: 進程分配方案計數
將n個進程分配到k個處理器，相鄰進程不能使用同一處理器
求方案總數 % mod
"""
# 特殊情況處理
if n == 1:
return k % mod
if k == 1:
return 0
# 公式：k × (k-1)^(n-1)
# 使用Python內置pow函數進行快速冪運算
result = (k % mod) * pow(k - 1, n - 1, mod) % mod
return result
# 測試用例
if __name__ == "__main__":
MOD = 10**9 + 7
# 測試1
print(processScheduling(2, 3, MOD)) # 輸出: 6
# 測試2
print(processScheduling(1, 3, MOD)) # 輸出: 3
# 測試3
print(processScheduling(3, 2, MOD)) # 輸出: 2
# 測試4：大數據
print(processScheduling(1000000, 1000000, MOD)) # 快速計算
面試要點
✅ 澄清問題：
- 進程是否有順序？（是的，相鄰指的是序列中的相鄰）
- 模數是多少？（通常是 10^9+7）
- n 和 k 的範圍？（影響算法選擇）
✅ 優化思路：
- 從 DP 優化到數學公式（O(n×k²) → O(log n)）
- 使用快速冪處理大數據
❌ 常見錯誤：
- 忘記處理 k=1 的特殊情況
- 沒有使用快速冪，導致超時
- 模運算順序錯誤
📌 題目二：處理器負載均衡最小輪次
問題描述
系統有 k 個處理器，初始任務分配為 tasks[0..k-1]。每一輪中：
- 每個處理器可以處理一個任務（任務數減 1）
- 或者將一個任務轉移給其他處理器
求完成所有任務的最小輪次，使得所有處理器的負載均衡。
示例：
k = 3, tasks = [1, 2, 3]
初始狀態：處理器0有1個任務，處理器1有2個任務，處理器2有3個任務
第1輪：
- 處理器0處理1個任務 → 剩餘0個
- 處理器1處理1個任務，轉移1個給處理器0 → 剩餘1個
- 處理器2處理1個任務，轉移1個給處理器1 → 剩餘1個
第2輪：
- 處理器0處理1個任務 → 剩餘0個
- 處理器1處理1個任務 → 剩餘0個
- 處理器2處理1個任務 → 剩餘0個
最小輪次 = 2
核心思路
使用二分查找答案。對於給定的輪次 t，檢查是否可行。
可行性檢查
對於輪次 t，每個處理器最多可以處理 t 個任務。
關鍵計算：
- 若處理器 i 初始有
cnt[i]個任務：- 若
cnt[i] > t：多出need = cnt[i] - t個任務需要轉移給其他處理器 - 若
cnt[i] ≤ t：剩餘可用容量avail = (t - cnt[i]) / 2（向下取整）- 為什麼除以 2？因為每個任務轉移需要 1 輪時間，處理也需要 1 輪時間
- 若
可行條件：所有處理器的總可用容量 ≥ 總需轉移任務數
def is_feasible(tasks, k, t):
"""
檢查輪次t是否可行
"""
need = 0 # 需要轉移的任務總數
avail = 0 # 可用容量總數
for cnt in tasks:
if cnt > t:
need += cnt - t
else:
avail += (t - cnt) // 2
return avail >= need
二分查找
def minRounds(tasks, k):
"""
二分查找最小輪次
"""
# 最壞情況：所有任務都在一個處理器上
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
完整代碼
def getMinTime(k, tasks):
"""
Q2: 處理器負載均衡最小輪次
Args:
k: 處理器數量
tasks: 初始任務分配數組，tasks[i]表示處理器i的任務數
Returns:
完成所有任務的最小輪次
"""
def is_feasible(t):
"""檢查輪次t是否可行"""
need = 0 # 需要轉移的任務總數
avail = 0 # 可用容量總數
for cnt in tasks:
if cnt > t:
# 處理器任務過多，需要轉移
need += cnt - t
else:
# 處理器有剩餘容量
# 可用容量 = (t - cnt) // 2
# 原因：轉移1個任務需要1輪，處理需要1輪，共2輪
avail += (t - cnt) // 2
return avail >= need
# 二分查找最小輪次
left, right = 1, max(tasks)
while left < right:
mid = (left + right) // 2
if is_feasible(mid):
right = mid
else:
left = mid + 1
return left
# 測試用例
if __name__ == "__main__":
# 測試1
print(getMinTime(3, [1, 2, 3])) # 輸出: 2
# 測試2
print(getMinTime(2, [5, 5])) # 輸出: 5
# 測試3
print(getMinTime(4, [1, 1, 1, 1])) # 輸出: 1
# 測試4：不均衡
print(getMinTime(2, [10, 1])) # 輸出: 5
複雜度分析
時間複雜度：O(k × log(max(tasks)))
- 二分查找：O(log(max(tasks)))
- 每次檢查：O(k)
空間複雜度：O(1)（不計輸入）
面試要點
✅ 澄清問題：
- 任務轉移是否需要時間？（是的，需要 1 輪）
- 一個處理器一輪最多處理幾個任務？（1 個）
- 目標是什麼？（最小化總輪次）
✅ 關鍵洞察：
- 二分查找答案空間（輪次）
- 理解可用容量的計算（為什麼除以 2）
- 貪心策略：優先處理任務多的處理器
❌ 常見錯誤：
- 沒有正確理解可用容量的計算
- 二分查找邊界條件錯誤
- 忽視任務轉移的時間成本
🎯 總結對比
| 題目 | 算法 | 時間複雜度 | 難度 |
|---|---|---|---|
| Q1：進程分配 | 組合數學 + 快速冪 | O(log n) | ⭐⭐ |
| Q2：負載均衡 | 二分查找 + 貪心 | O(k log m) | ⭐⭐⭐ |
🚀 面試建議
- 時間管理：兩道題共 90 分鐘，建議各 45 分鐘
- 代碼質量：注重邊界條件和模運算
- 溝通能力：清晰解釋算法思路和複雜度
- 優化意識：從暴力解到最優解的演進過程
📞 需要面試輔助？
oavoservice 提供專業的 OA/VO 輔助服務。
👉 立即添加微信：Coding0201