題幹與適用場景
請實作一個支援 getstate() 和 setstate() 的可恢復迭代器：先處理單一清單，再擴充到多個資料源並行迭代和非同步讀取。你如何定義狀態、保證恢復後不重複不遺漏，並處理結束、失敗和非法狀態？
這道題對應公開記錄中的 OpenAI 程式設計面試題，遞進範圍包括清單迭代器、多檔案組合迭代器和 coroutine。它適合通用程式設計、基礎設施、資料處理和機器學習工程職位。核心不是把產生器暫停，而是把「下一次 next 會回傳什麼」編碼成可驗證、可序列化的狀態。
面試官考察點
- 是否先定義
next()的輸入、輸出、結束和例外語意，而不是依賴hasNext()。 - 是否把執行期物件與可持久化狀態分離。
- 是否能證明保存點恢復後既不重複也不跳過元素。
- 是否正確處理多個資料源各自進度與全域調度順序。
- 是否處理非同步讀取、取消、失敗重試和資源關閉。
- 是否覆蓋空資料源、非法狀態、資料源變更和冪等恢復測試。
回答前需要釐清的問題
- 資料源是不變清單、可追加檔案，還是可能被重寫的外部串流？資料源若會變動，狀態必須帶版本或內容指紋。
- 恢復語意是「重複最後一次回傳值」還是「從下一個未回傳值開始」？下文採用後者，並在成功交付後推進游標。
- 多源順序是輪詢、全域時間順序，還是任一就緒源優先？不同選擇會改變狀態欄位和公平性證明。
get_state()是否要跨程序或跨版本持久化？若要持久化，狀態只能包含版本化純量和來源識別，不能包含檔案控制代碼、Promise 或產生器物件。
30 秒回答框架
「我先定義保存點語意：狀態代表下一次 next() 將回傳的元素。單一清單只需保存索引和來源版本；多源保存每個來源的游標以及全域調度器狀態。next() 成功產出後才推進對應游標，因此恢復同一狀態會回傳同一元素，不會重複已確認的元素。狀態採用版本化 JSON，恢復前驗證來源指紋和邊界。非同步版本把未完成 I/O 與可恢復狀態分開，支援取消、關閉和按來源重試，禁止把執行期控制代碼直接序列化。」
分步驟深入解答
第一步：定義最小介面與保存點
把介面寫成 next()、getstate()、setstate(state)，不增加 hasNext()。有限迭代器結束時回傳統一的 done 結果或拋出約定的結束例外；呼叫方不能透過提前探測再呼叫一次來猜測狀態。
保存點放在「下一項」而非「上一項」。清單資料源的狀態可以是 {sourceId, version, index, done}。呼叫 next() 讀取 items[index]，只有讀取成功並交付給呼叫方後才把 index 加一；讀取失敗時保持原狀態，允許重試。
class ListIterator:
def __init__(self, items, source_id, version):
self.items = items
self.source_id = source_id
self.version = version
self.index = 0
def next(self):
if self.index == len(self.items):
return {"done": True}
value = self.items[self.index]
self.index += 1
return {"done": False, "value": value}
def get_state(self):
return {
"schema": 1,
"sourceId": self.source_id,
"version": self.version,
"index": self.index,
}
def set_state(self, state):
if state["schema"] != 1 or state["sourceId"] != self.source_id:
raise ValueError("incompatible state")
if state["version"] != self.version or not 0 <= state["index"] <= len(self.items):
raise ValueError("stale or invalid state")
self.index = state["index"]第二步：寫出不變量並證明恢復正確
核心不變量是：游標 index 等於已成功交付的元素數量；狀態中的 index 與記憶體游標相同；來源版本不變。next() 只有在成功回傳值後推進游標，set_state() 只接受相同版本和合法邊界，因此從同一保存點開始會看到相同後綴。
若業務允許「至少一次」而不是「恰好一次」，可以在交付與保存之間重複最後一項；此時狀態需記錄確認位或冪等鍵。不要把兩種語意混在同一個 set_state() 契約裡。
第三步：擴充到多個資料源
組合迭代器保存 children[sourceId] 的獨立狀態，並額外保存調度器狀態，例如輪詢佇列、已完成來源集合和序號。輪詢策略每次選擇下一個未完成來源；全域排序策略則需要保存每個來源的預取頭部，才能恢復比較結果。
多源狀態範例：{schema, children: [{id, state}], scheduler: {kind, cursor}, emitted}。恢復時先驗證來源集合與順序，再恢復子迭代器，最後恢復調度器；不能只保存一個總計數，因為不同來源的進度會分歧。
第四步：讓狀態可序列化且可演進
持久化狀態應只含 JSON 可表達的純量、陣列和物件，並帶 schema 版本。檔案控制代碼、網路連線、執行緒鎖、Promise、產生器堆疊和閉包都屬於執行期資源，恢復時重新開啟，不應寫入快照。
新版本讀取舊狀態時執行明確遷移；無法判斷相容性就拒絕恢復並從安全邊界重新開始。來源內容若可能變動，保存 ETag、長度、分片校驗或邏輯版本，防止相同 index 指向不同資料。
第五步：加入非同步讀取、取消與失敗重試
非同步 next() 回傳 Promise，內部可以並行等待多個來源，但狀態更新仍按「成功交付後提交」原則進行。取消應停止新讀取、關閉檔案或網路資源，並讓未提交的游標保持原值。
失敗重試要區分可重試 I/O、永久格式錯誤和來源已變更。可重試錯誤保留保存點並使用退避；永久錯誤記錄 sourceId 和偏移後結束該來源；來源變更則要求重新驗證或產生新快照，不能默默跳到新內容。
第六步：設計測試與複雜度
單源 next()、保存、繼續、恢復應驗證回傳序列完全相同；測試空清單、邊界容量、最後一項後再次 next、重複 set_state 和非法版本。多源測試要覆蓋某一來源先結束、非同步完成順序與調度順序不同、取消中斷和單源失敗。
單清單 next 和快照讀寫為 O(1)，狀態大小為 O(1)。有 m 個來源時，快照至少為 O(m)；若調度器維護堆或預取頭部，next 可能為 O(log m)，輪詢則可做到攤銷 O(1)。複雜度必須與選定調度策略一致。
高品質示範回答
「我會先把恢復語意說清楚：快照表示下一次 next() 要回傳的元素，只有成功交付後才推進游標。單一清單保存 sourceId、版本和 index，並驗證 index 邊界；讀取失敗不提交游標，所以可以安全重試。
擴充到多源時，每個子迭代器保存自己的狀態，組合器再保存輪詢游標、已結束來源和輸出序號。若要求全域順序，還要保存每個來源的預取頭部。快照只使用帶 schema 版本的 JSON 資料，檔案控制代碼、Promise 和產生器堆疊在恢復時重建。
非同步 next 可以並行等待 I/O，但狀態提交仍遵循成功交付後更新。取消會關閉資源並保留未提交狀態；錯誤按可重試、永久錯誤和來源版本變化分類。測試重點是同一快照產生相同後綴、沒有重複或跳過，以及多個來源完成順序變化時仍符合調度契約。單源操作是 O(1)，m 源快照是 O(m)，複雜度取決於輪詢或堆調度。」
常見錯誤
- 把目前已回傳索引保存為下一項索引 → 恢復會重複或跳過元素 → 明確快照語意並在成功交付後推進。
- 序列化檔案控制代碼或產生器物件 → 程序重啟後物件不可用 → 只保存版本化純量，恢復時重建資源。
- 用
hasNext()先探測 → 非同步來源可能在探測和消費之間改變狀態 → 讓next()一次性回傳值或結束結果。 - 只保存多源總計數 → 各來源進度和調度位置遺失 → 保存每個子源狀態及調度器狀態。
- 讀取失敗後仍推進游標 → 重試會遺漏資料 → 提交點放在成功交付之後。
- 恢復不驗證來源版本 → 相同偏移可能對應不同內容 → 驗證指紋、長度或邏輯版本，失敗時拒絕恢復。
追問及應對
如果快照保存發生在讀取成功但交付確認之前，怎麼辦？
需要定義確認邊界。若快照可能先於確認落盤，系統採用至少一次語意，並為元素提供冪等鍵；若必須避免重複，則把交付確認和游標提交放進同一可恢復交易或外部確認日誌。
多個非同步來源同時就緒，如何保證公平？
輪詢調度記錄上次選擇的游標，並在每次成功交付後移動；不要讓最快來源持續佔滿輸出。若要求全域時間順序，改用帶頭部元素的最小堆，並把堆頭和比較規則納入狀態。
檔案在暫停期間被追加，能否繼續恢復？
只有契約明確支援追加時才允許。保存版本、已讀長度和分片校驗，恢復後從舊長度繼續；如果檔案可能重寫或重排，版本不符時拒絕恢復，重新建立快照。
如何取消一個正在等待多個 I/O 的 next？
傳入取消訊號，停止尚未開始的讀取，並對已開啟資源執行 close。任何未完成 Promise 都不能推進游標；取消後再次 next 要麼從原保存點重試，要麼回傳明確的取消狀態。