質問とコンテキスト
get_state()とset_state()を備えたイテレータを実装してください。まずは1つのリストから始め、次に複数ソースにわたる並行イテレーションと非同期読み取りへと拡張してください。状態をどのように定義し、リカバリ後の重複やスキップがないことをどのように保証し、完了、障害、無効なスナップショットをどのように処理しますか？
これは、リストイテレータ、複数ファイル複合イテレータ、コルーチンベースのバージョンへと発展するOpenAIの公開コーディング面接の記録に合致しています。一般的なコーディング、インフラストラクチャ、データ処理、機械学習エンジニアリングの役割に適しています。課題はジェネレータを一時停止することではなく、「次の呼び出しが何を返すべきか」を検証可能かつシリアライズ可能な状態としてエンコードすることです。
面接官が評価するポイント
hasNext()に依存せず、next()の入力、出力、完了、エラーのセマンティクスを定義しているか？- 実行時オブジェクトと永続化可能な状態を分離しているか？
- リカバリによって配信済み要素が重複したりスキップされたりしないことを証明できるか？
- 各ソースの進捗とグローバルなスケジューリング順序を追跡しているか？
- 非同期読み取り、キャンセル、リトライ、リソースのクリーンアップを処理しているか？
- 空のソース、無効なスナップショット、ソースの変更、冪等なリカバリをテストしているか？
コーディング前の明確化のための質問
- ソースは不変のリスト、追記専用（append-only）ファイル、それとも変更可能な外部ストリームですか？変更される可能性がある場合、スナップショットにはバージョンまたはコンテンツのフィンガープリントが必要です。
- リカバリは最後に返された値を再送しますか、それともまだ返されていない次の値から開始しますか？この回答では後者を採用し、正常に配信された後にのみカーソルを進めます。
- 複数ソースの順序はラウンドロビン、グローバルな時間順、あるいは準備ができたソース優先（any-ready-source-first）ですか？この選択によって状態フィールドと公平性の証明が変わります。
get_state()はプロセスの再起動やスキーマバージョンの変更後も維持される必要がありますか？その場合、ファイルハンドル、Promise、ジェネレータオブジェクトなどは含めず、バージョン付きのスカラーとソースIDのみを保存してください。
30秒での回答
「まず、チェックポイントを『次のnext()呼び出しが返す要素』として定義します。単一リストの場合はインデックスとソースバージョンを保存し、複数ソースの場合は各カーソルとスケジューラ状態を保存します。next()は配信が成功した後にのみカーソルを進めるため、同じ状態を復元すると同じ要素が返され、確認済みの要素が重複することはありません。スナップショットはバージョン管理されたJSONであり、復元前にソースのフィンガープリントと境界に対して検証されます。非同期バージョンでは、処理中のI/Oを実行時状態から分離し、キャンセル、クリーンアップ、ソースごとのリトライをサポートし、実行時ハンドルを決してシリアライズしません。」
ステップごとの詳細な回答
ステップ1：最小限のインターフェースとチェックポイントを定義する
hasNext()を追加することなく、next()、get_state()、set_state(state)を使用します。有限イテレータは一貫した1つの完了結果を返すか、合意された完了例外を送出します。呼び出し側が先読みして状態を推測するべきではありません。
チェックポイントは「最後のアイテム」ではなく「次のアイテム」に設定します。リストソースには{sourceId, version, index, done}を保存できます。next()はitems[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"]ステップ2：不変条件を述べ、リカバリを証明する
メインの不変条件は、indexが正常に配信された要素数と等しく、スナップショットのインデックスがインメモリのカーソルと等しく、ソースバージョンが変更されていないことです。next()は値を返した後にのみ進み、set_state()は一致するバージョンと有効な境界のみを受け入れるため、同じチェックポイントからは同じサフィックスが生成されます。
ビジネス要件が厳密に1回（exactly-once）ではなく少なくとも1回（at-least-once）である場合、配信とチェックポイントの間で最後のアイテムが繰り返されることは許容されますが、状態に応答確認（acknowledgement）マーカーまたは冪等性キーを含める必要があります。1つのset_state()コントラクト内で両方のセマンティクスを混在させないでください。
ステップ3：複数ソースへ拡張する
複合イテレータは、独立したchildren[sourceId]状態と、ラウンドロビンキュー、完了済みソースセット、シーケンス番号などのスケジューラ状態を保存します。ラウンドロビンは次の未完了ソースを選択します。グローバル順序付けでは、リカバリ後に比較を再現できるように各ソースのプリフェッチされた先頭要素を保存する必要があります。
マルチソースのスナップショットは{schema, children: [{id, state}], scheduler: {kind, cursor}, emitted}のようになります。まずソースの所属と順序を検証し、次に子イテレータを復元し、最後にスケジューラを復元します。ソースの進捗が分岐するため、単一の総カウント数だけでは不十分です。
ステップ4：状態をシリアライズ可能かつ進化可能にする
スキーマバージョンを含むJSON形式のスカラー、配列、オブジェクトのみを永続化します。ファイルハンドル、ネットワーク接続、ロック、Promise、ジェネレータスタック、クロージャは実行時リソースです。これらをスナップショットに書き込むのではなく、リカバリ時に再度開くか再構築してください。
新しいバージョンが古いスナップショットを読み取る場合は、明示的なマイグレーションを実行します。互換性が不明な場合はリカバリを拒否し、安全な境界から再開します。ソースコンテンツが変更される可能性がある場合は、ETag、長さ、チャンクチェックサム、または論理バージョンを保存し、同じインデックスが暗黙的に異なるデータを参照しないようにします。
ステップ5：非同期読み取り、キャンセル、リトライを追加する
非同期のnext()はPromiseを返し、複数のソースを並行して待機できますが、状態のコミットは依然として「配信成功後にコミットする」に従います。キャンセルは新しい読み取りを停止し、ファイルやネットワークリソースを閉じ、コミットされていないカーソルを変更しないままにします。
障害は、リトライ可能なI/Oエラー、永続的なフォーマットエラー、またはソースバージョンの変更に分類します。リトライ可能なエラーの場合はバックオフしてチェックポイントを保持します。永続的に異常なソースを終了する前にソースIDとオフセットを記録します。ソース変更後は、暗黙的にコンテンツを切り替えるのではなく、再検証または新しいスナップショットを要求します。
ステップ6：テストと計算量を設計する
単一ソースの場合、next()、保存、継続、復元がまったく同じシーケンスを生成することを検証します。空のリスト、境界インデックス、最後のアイテム後のnext呼び出し、繰り返されるset_state、無効なバージョンをテストします。マルチソースのテストでは、1つのソースの早期終了、スケジューリング順序と異なる完了順序、キャンセル、単一ソースの障害をカバーします。
単一ソースのnextおよびスナップショットの読み書きはO(1)であり、状態サイズはO(1)です。m個のソースがある場合、スナップショットは少なくともO(m)になります。ヒープまたはプリフェッチされた先頭要素を使用するとnextをO(log m)にでき、ラウンドロビンでは償却O(1)にできます。計算量は選択したスケジューラと一致している必要があります。
高品質な回答例
「まずリカバリコントラクトを明確にします。スナップショットは次のnext()呼び出しが返すべき要素を指定し、カーソルは配信が成功した後にのみ進みます。リストイテレータはソースID、バージョン、インデックスを保存し、インデックスを検証します。読み取りに失敗してもカーソルはコミットされないため、リトライは安全です。
複数ソースの場合、各子イテレータは独自の状態を保持し、複合イテレータはラウンドロビンカーソル、完了したソース、出力シーケンスを保存します。グローバルな順序が必要な場合は、各ソースのプリフェッチされた先頭要素も保存します。スナップショットはバージョン管理されたJSONであり、ファイルハンドル、Promise、ジェネレータスタックはリカバリ後に再構築されます。
非同期nextはI/Oを並行して待機できますが、状態のコミットは配信後にのみ行われます。キャンセルはリソースを閉じ、未コミットの状態を保持します。エラーはリトライ可能、永続的、またはソースバージョンの変更として分類されます。テストにより、1つのスナップショットから重複やスキップなしで同じサフィックスが得られること、および完了順序が変わってもスケジューリングコントラクトが満たされることを証明します。単一ソースの操作はO(1)であり、mソースのスナップショットはO(m)で、nextの計算量はラウンドロビンまたはヒープスケジューリングによって決定されます。」
よくある間違い
- 返されたインデックスを次のインデックスとして保存する → リカバリ時に要素が重複またはスキップされる → チェックポイントのセマンティクスを定義し、配信後に進める。
- ファイルハンドルやジェネレータオブジェクトをシリアライズする → プロセス再起動後にオブジェクトが維持されない → バージョン付きスカラーを保存し、リソースを再構築する。
hasNext()でプローブする → プローブと消費の間に非同期ソースが変化する可能性がある →next()が値または完了結果をアトミックに返すようにする。- 複数ソースに対して総カウント数のみを保存する → ソースごとの進捗とスケジューラの位置が失われる → すべての子の状態とスケジューラ状態を保存する。
- 読み取り失敗後にカーソルを進める → リトライ時にデータが失われる → 配信成功後にのみコミットする。
- ソースバージョンをチェックせずに復元する → 同じオフセットが異なるコンテンツを指す可能性がある → フィンガープリント、長さ、または論理バージョンを検証し、古い状態を拒否する。
フォローアップの質問と回答
読み取りが成功した後、配信が確認される前にスナップショットが書き込まれた場合はどうなりますか？
確認応答（acknowledgement）の境界を定義します。スナップショットが先に保存される可能性がある場合、システムは少なくとも1回（at-least-once）となり、各アイテムに冪等性キーまたは確認マーカーが必要になります。厳密に1回（exactly-once）の動作を実現するには、配信確認とカーソルコミットを単一のリカバリ可能トランザクションまたは外部コミットログに配置します。
準備完了状態の複数の非同期ソースの公平性をどのように保ちますか？
ラウンドロビンスケジューラで最後に選択されたカーソルを永続化し、配信が成功するたびにそれを進めます。最速のソースが出力を独占してはなりません。グローバルな時間順の場合は、ソース先頭要素の最小ヒープ（min-heap）を使用し、ヒープの先頭要素と比較ルールをスナップショットに含めます。
一時停止中に追記されたファイルは安全に再開できますか？
追記専用（append-only）の動作がコントラクトの一部である場合にのみ可能です。バージョン、消費された長さ、チャンクチェックサムを保存し、以前の長さから再開します。ファイルが書き換えられたり順序が変更されたりする可能性がある場合は、バージョンの不一致を拒否して新しいスナップショットを作成します。
複数のI/O操作を待機している間にnext()をキャンセルするにはどうすればよいですか？
キャンセルシグナルを渡し、まだ開始されていない読み取りを停止し、開いているリソースを閉じます。未解決のPromiseがカーソルを進めてはなりません。その後のnext()は、元のチェックポイントからリトライするか、明示的なキャンセル状態を返します。