題幹與適用場景
請實作一個記憶體內的 TaskScheduler。呼叫方提交任務 ID、相依 ID 列表與函式；所有相依成功後任務才可被領取執行。排程器需要提供 submit、ready、complete、fail 與 cancel 等操作，並能回報無法執行的循環相依。請說明並行上限、重複提交、失敗傳播、關閉與重啟邊界。
這題把圖遍歷與可執行介面放在同一組限制中。候選人要先釐清任務狀態與失敗契約，再把入度維護、就緒佇列與狀態轉移寫進程式。Python 的 TopologicalSorter 將「沒有未完成前驅的節點」視為可處理節點，並把偵測到的循環保留為可診斷結果；這些語意可協助定義狀態機，但不能只呼叫現成排序函式，因為任務會動態完成、失敗與取消。
面試官考察點
- 能否區分
pending、ready、running、succeeded、failed、blocked、cancelled。 - 能否維護入度與反向鄰接表不變量，而不是每次掃描所有任務。
- 能否在相依完成時只釋放受影響的下游節點，讓每條邊只被處理有限次。
- 能否先定義循環、失敗與取消傳播規則，再選擇回傳值與錯誤型別。
- 能否限制 worker 並行、保證同一任務只被領取一次，並處理重複提交的版本語意。
- 能否給出時間與空間複雜度，以及覆蓋交錯時序的測試。
回答前需要釐清的問題
- 任務提交是一次性靜態 DAG，還是允許動態加入？預設任務必須在開始排程前提交，執行期間只允許提交尚未被引用的新版本。
- 相依失敗後，下游是
blocked、自動取消，還是允許人工重試？本題預設下游進入blocked，重試必須明確建立新版本。 - 取消一個任務是否級聯到所有後代？預設只取消該任務；後代觀察到必要相依取消後進入
blocked，不隱式刪除無關分支。 - 函式失敗是否自動重試？預設不自動重試；重試策略由呼叫方提交新版本並保證副作用具冪等性。
ready()回傳一個任務還是一批任務？預設回傳最多maxConcurrency - running個、順序穩定的任務。
30 秒回答框架
我會為每個任務保存狀態、未完成相依數與依賴它的反向鄰接表。提交完成後先做一次三色 DFS 或 Kahn 偵測，發現循環就回傳包含節點路徑的診斷。入度為零的任務進入就緒佇列；領取時原子地從 ready 改成 running，成功完成後遍歷反向鄰接表，讓下游未完成相依數減一，降到零就入隊。失敗或取消依照預先宣告的規則把後代標成 blocked。所有狀態轉移由同一把鎖或單執行緒事件迴圈保護，並用版本號拒絕舊提交。
分步驟深入解答
第一步：定義狀態與邊界
任務狀態只能沿有限方向前進：pending 到 ready，再到 running，最後到 succeeded 或 failed；取消可發生在 pending 或 ready，執行中的取消只記錄合作式停止請求。blocked 表示任務沒有執行，且至少一個必要相依不可能成功。終態不能回到 ready，否則同一函式可能被執行兩次。
每個任務記錄 generation。同一 ID 的重複提交要明確拒絕，或建立新版本並使舊版本失效；本題選擇後者，但只有尚未執行的舊版本可被替換。已經 running 的版本不能靜默覆蓋，應回傳衝突或等待它進入終態。
第二步：建立入度與反向鄰接表
任務表保存 remainingDeps，反向表保存 dependents[dependencyId]。提交任務時，先確認相依存在，或依契約建立佔位節點，再登記每條邊一次。初始化階段把入度為零的任務放入就緒佇列，之後只在相依狀態變化時更新計數。
核心資料結構如下：
Task:
id, generation, dependencies, dependents
remainingDeps, state, fn, error
submit(task):
validateUniqueDependencies(task)
registerEdges(task)
if task.remainingDeps == 0:
task.state = READY
readyQueue.push(task.id)若允許缺少相依，不能把它視為已完成。應保存 waiting 狀態，直到相依提交；否則入度會被錯誤減到零。若不允許缺少相依，提交時回傳可定位的 UnknownDependency。
第三步：在開始前回報循環
靜態圖可以使用 Kahn 演算法：複製入度，把零入度節點加入佇列，移除它們的出邊；若處理數量小於節點總數，剩餘節點至少屬於一個環。為讓答案可操作，應同時回傳一條具體路徑，例如 A → B → C → A，而不是只回傳「存在循環」。
若選擇 DFS，使用白、灰、黑三色標記：從灰節點再次遇到灰節點時，沿父指標截取循環。偵測必須在任務進入 running 前完成；執行期間動態加邊會讓已領取任務的語意含糊，最簡單契約是禁止修改已開始的圖。
第四步：領取任務並限制並行
ready() 計算可用槽位，按穩定提交序號從佇列取出任務，並在同一臨界區把狀態改為 running。回傳後即使 worker 尚未開始執行，其他呼叫也不能再次領取。complete(id, generation) 必須驗證版本與狀態，舊 worker 的遲到回呼只能回傳衝突，不得再次釋放下游。
並行上限可由固定 worker 數或 semaphore 表達。佇列長度不等於活動任務數；只有 running 計入上限。若一次請求批次大於剩餘槽位，應只回傳可用數量或明確回傳 CapacityExceeded，不能偷偷增加並行。
第五步：傳播成功、失敗與取消
成功完成後，遍歷直接下游，把仍為 pending 或 ready 的節點之 remainingDeps 減一；降到零就入隊。失敗時，本題將直接下游及其後代標成 blocked，並保存第一個阻塞原因；也可以選擇允許替代相依，但必須寫入契約，不能在程式中隱式判斷。
取消只影響尚未執行的版本。若執行中的函式支援 AbortSignal，排程器可以發出取消請求，但只有函式確認退出後才把狀態設為 cancelled。後代看到必要相依為 failed 或 cancelled 時進入 blocked，不能假裝相依成功。
第六步：處理重複提交與冪等回呼
以 (taskId, generation) 作為外部操作的冪等鍵。重複的 complete、fail 或 cancel 請求回傳目前終態，不重複減少下游入度。新提交若替換舊的 pending 版本，應先從反向表撤銷舊邊，再登記新邊並重新計算可達狀態；直接覆蓋物件會留下舊邊，讓下游永遠等待。
若系統不需要更新語意，拒絕重複 ID 會更簡單。面試中應說明選擇：靜態建構器可以拒絕重複，長期執行的工作流則通常需要 generation、稽核與重試版本。
第七步：處理關閉、重試與恢復
close() 先拒絕新提交，再停止 ready() 領取，最後等待 running 任務回呼或達到明確逾時。佇列中的任務應依契約取消或保留，不能只清空記憶體結構而遺失原因。重試建立新 generation，重新檢查相依快照；直接把 failed 改回 ready 會繞過失敗原因與並行回呼。
純記憶體實作不能在程序崩潰後恢復。若要持久化，需要保存任務、版本、狀態、相依與租約；恢復 worker 透過條件更新搶佔任務，並讓函式具備冪等性。恢復只能提供至少一次執行，不能承諾恰好一次副作用。
第八步：複雜度與測試
初始化圖的時間複雜度是節點數加邊數，記作 O(V + E)。每次完成任務只遍歷它的出邊，因此整批傳播總成本仍為 O(V + E)；就緒佇列若使用堆，領取為 O(log V)。空間複雜度為 O(V + E)。
測試至少覆蓋空圖、多個獨立分支、長鏈、環、缺少相依、同一節點被兩個相依同時完成、失敗傳播、取消後代、重複回呼、重複提交、並行槽位為零、關閉期間領取及舊 generation 的遲到回呼。可用小型狀態模型對拍每次可執行集合，並記錄每個任務最多一次 pending → running 轉換。
高品質示範回答
我會先凍結任務圖，為每個任務保存狀態、generation、未完成相依數與反向鄰接表。建構階段用 Kahn 加父指標偵測循環並回傳一條環路；沒有相依的任務進入帶穩定序號的就緒佇列。ready() 在鎖內按剩餘並行槽位領取，立即把任務改成 running。成功回呼只接受匹配 generation 的一次性終態，沿反向邊遞減下游計數，降到零才入隊。失敗與取消不會冒充成功，而是把受影響後代設為 blocked。重複回呼具冪等性，重試建立新版本；關閉先拒絕新任務，再停止領取並等待執行中的回呼。整批是 O(V + E)，並行與副作用邊界都由測試驗證。
常見錯誤
- 只做一次拓撲排序，沒有說明動態完成與失敗後的狀態變化。
- 每次尋找就緒任務都掃描全部節點，忽略反向鄰接表與入度不變量。
- 發現環時只回傳布林值，無法指出哪組任務阻塞了發佈。
- 任務完成回呼不帶版本號，舊 worker 會重複釋放下游。
- 把相依失敗當成相依成功，讓下游在前置條件不滿足時執行。
- 把取消執行中函式描述成強制中止，卻沒有合作式訊號或資源回收契約。
- 透過增加 worker 數解決佇列積壓，結果同時突破並行上限與下游容量。
- 重試直接重用舊狀態，遺漏冪等、副作用與租約恢復邊界。
追問及應對
如果任務圖很大，如何避免一次把所有節點放進記憶體？
把任務中繼資料與邊存入持久化儲存，按租戶或分區載入可執行視窗；記憶體只保留活動節點與游標。領取使用條件更新或短租約，完成時仍驗證 generation。要說明跨分區相依、分頁一致性與租約過期後的重複執行。
如何允許失敗分支繼續執行，但阻止相依失敗的節點？
把邊標註為必要或可選；任務只有所有必要相依成功且可選相依已終態時才進入 ready。可選相依失敗應寫入輸入摘要與指標，不能靜默丟棄，這會擴大狀態機與測試矩陣。
如何支援動態加入相依？
只允許任務仍為 pending 時追加邊，並在同一臨界區增加入度；已經 ready 或 running 的任務拒絕修改。若業務必須支援執行中變更，應建立新 generation，等待舊版本終態後再按新圖執行。
取消共享相依時，怎樣避免誤傷其他分支？
取消只改變該相依節點終態，傳播器沿反向邊逐一判斷必要關係。沒有該相依的分支繼續執行；共享相依的所有必要下游進入 blocked。稽核紀錄要保留取消者、時間與傳播路徑。
多個 worker 程序如何保證同一任務只執行一次？
用持久化儲存的原子領取或租約欄位搶佔任務，並把 generation 放入條件。租約過期後允許再次領取，因此函式必須具冪等性或提供補償。記憶體鎖只能保護單一程序，不能作為跨程序唯一保證。
面試官要求可觀測指標，你會選什麼？
記錄循環任務數、阻塞任務數、就緒等待時間、執行時長、領取衝突、租約過期、重複回呼，以及每條邊的傳播延遲。按任務類型與租戶分層，避免只看平均值掩蓋尾部積壓；指標還要區分圖設定錯誤與執行函式失敗。
如何證明不會把任務領取兩次？
把「檢查狀態、減少槽位、寫入 running」放在同一臨界區或原子條件更新中，並讓回呼攜帶 generation。模型測試列舉兩個並發 ready() 呼叫，斷言每個版本最多一次 pending → running；重複完成只回傳已知終態。