問題と適用されるコンテキスト
4 つのメソッドを持つ EventEmitter クラスを実装します。on(eventName, listener) は永続的なリスナーを登録し、once(eventName, listener) は一度だけ実行されるリスナーを登録し、off(eventName, listener) は一致する登録を 1 つ削除し、emit(eventName, ...args) はイベントを同期的にディスパッチします。イベント名は文字列または Symbol を使用できます。同じ関数を 1 つのイベントに対して複数回登録することも可能です。
この問題では、Node スタイルのセマンティクスの明示的なサブセットを使用します。リスナーは登録順に同期的に実行されます。通常のリスナー関数内の this は emitter を指します。emit は、イベントにリスナーが存在する場合は true を返し、そうでない場合は false を返します。リスナーの戻り値は無視されます。再入可能な emit が再び呼び出さないように、once 登録はそのリスナーが呼び出される前に削除される必要があります。
1 回のディスパッチに対するリスナーは、そのディスパッチが開始された時点で確定します。ディスパッチ中に 1 つのリスナーが別のリスナーを削除した場合でも、削除されたリスナーは既に進行中のディスパッチには参加しますが、以降のディスパッチには参加しません。新しく追加されたリスナーは、以降のディスパッチまで待機します。この実装では、Node.js 特有の error イベント、リスナー数の警告、prependListener、非同期イテレーション、Promise の拒否（rejection）のキャプチャなどは再現しません。これらはより広範な互換性要件に属します。
面接官が評価している点
優れた回答は、コンテナを選択する前にイベントの規約を定義します。Map<eventName, entries[]> がイベントごとの配列を特定し、その配列が登録順序を保持します。各エントリには、元の関数、once 登録であるかどうか、実行済みかどうか、およびアクティブなままであるかどうかが格納されます。Set を使用すると削除は容易になりますが、重複した関数が暗黙的に統合されてしまい、規定された重複登録ルールに違反します。
2 つ目の評価ポイントは、アクティブな配列とディスパッチ時のスナップショットを区別しているかです。アクティブな配列を直接イテレーションすると、先行するリスナーの off 呼び出しによってインデックスがずれ、次の項目がスキップされる可能性があります。また、on の呼び出しによって、予期せず現在のディスパッチにリスナーが追加されてしまうこともあります。最初にアクティブなエントリをコピーしておくことで、変更の境界を次の emit に固定できます。
3 つ目の評価ポイントは、再入可能な once の挙動です。コールバックが戻った後に一度限りのリスナーを削除するのでは遅すぎます。コールバックの登録が残っている間にコールバック自身が同じイベントを発行する可能性があるためです。呼び出しの前に、エントリを非アクティブかつ実行済みとしてマークする必要があります。また、実行済みフラグにより、ネストされたディスパッチによって既に実行された後に、外側のスナップショットがそのエントリを再度呼び出すのを防ぐことができます。
計算量は正確に述べる必要があります。イベントに k 個のリスナーがある場合、on および once での配列への追加は償却 O(1) です。off は後方からスキャンして配列要素を削除するため、O(k) となります。スナップショットの作成、呼び出し、およびクリーンアップにより、emit はリスナー自体の実行時間に加えて O(k) となります。イベントの検索は、Map の実装において平均して O(1) として扱われることが一般的ですが、ECMAScript が要求しているのは線形探索より優れた平均アクセス性能のみです。Map を使ったからといって、4 つの操作すべてが無条件で O(1) になるわけではありません。
回答前に確認すべき明確化のための質問
- どのメソッドと戻り値が必要か？
on、off、emitのみであれば、一度限りの状態を保持する必要はありません。onceを追加する場合は、正確な削除タイミングが必要になります。emitからリスナーの結果を返すようにするとデータフローが変わります。この規約では、リスナーが存在したかどうかのみを返します。 - 同じ関数を複数回登録できるか、また
offは 1 つの登録を削除するのか、それともすべての登録を削除するのか？ この規約では重複を許可し、最も新しく登録された一致するリスナーを削除します。重複を排除する Set を使用すると、異なる規約の実装になってしまいます。 - ディスパッチ中の追加や削除はいつ反映されるか？ この規約ではスナップショットのセマンティクスを採用しています。開始時に存在していたリスナーが現在のディスパッチに参加し、追加や削除は以降のディスパッチに影響します。即時削除を要求する規約の場合は、各呼び出しの前にアクティブ状態のチェックが必要になります。
- リスナーは同期的に実行されるか、またリスナーが例外をスローした場合はどうなるか？ リスナーは順序通りに同期実行されます。スローされたエラーは
emitから伝播するため、後続のリスナーは実行されません。非アクティブなエントリのクリーンアップは、依然としてfinallyで行う必要があります。 - Node.js との完全な互換性が必要か？ 必要な場合は、特殊な
errorの挙動、メタイベント、リスナー数制限、その他の API も対象に含まれます。この実装は宣言されたコアサブセットのみをカバーします。クラス名が同じであっても完全な互換性があるとは限りません。
これらの回答によってストレージモデル、ループの条件、戻り値、エラー境界が変わるため、コーディング前にこれらを確定させておきます。
30秒の回答フレームワーク
「イベントごとのエントリ配列を Map に保存し、登録順に同期的にディスパッチし、重複登録を許可します。off は最新の一致項目を削除し、ディスパッチ中の変更は次回から有効になります。emit はアクティブなエントリのスナップショットを作成します。once を呼び出す前に、再入を防ぐためエントリを非アクティブかつ実行済みとしてマークし、その後 finally でクリーンアップします。Map の平均検索性能のもとで、登録は償却 O(1)、off と emit は O(k) です。」
ステップバイステップの詳細解説
最小限の実装では、各イベントを関数の配列にマッピングし、それらを順番に呼び出します。これは 2 つの関数を登録して 1 回 emit するサンプルはパスしますが、結果を左右する 4 つの疑問が未解決のまま残ります。すなわち、重複する関数の削除方法、ディスパッチ中に配列が変更された場合の挙動、一度限りのリスナーの削除タイミング、そしてリスナーが例外をスローした後の状態クリーンアップ方法です。
推奨される実装では、登録レコードと関数そのものを分離します。同じ関数の 2 つの登録は別々のエントリとして保持され、once はラッパーの背後に元の関数を隠す必要がありません。
class EventEmitter {
constructor() {
this.events = new Map();
}
on(eventName, listener) {
return this._add(eventName, listener, false);
}
once(eventName, listener) {
return this._add(eventName, listener, true);
}
off(eventName, listener) {
const entries = this.events.get(eventName);
if (!entries) return this;
for (let index = entries.length - 1; index >= 0; index -= 1) {
const entry = entries[index];
if (entry.active && entry.listener === listener) {
entry.active = false;
entries.splice(index, 1);
break;
}
}
if (entries.length === 0) {
this.events.delete(eventName);
}
return this;
}
emit(eventName, ...args) {
const entries = this.events.get(eventName);
if (!entries) return false;
const snapshot = entries.filter((entry) => entry.active);
if (snapshot.length === 0) return false;
try {
for (const entry of snapshot) {
if (entry.once) {
if (entry.fired) continue;
entry.fired = true;
entry.active = false;
}
entry.listener.apply(this, args);
}
} finally {
const currentEntries = this.events.get(eventName);
if (currentEntries) {
const activeEntries = currentEntries.filter((entry) => entry.active);
if (activeEntries.length === 0) {
this.events.delete(eventName);
} else if (activeEntries.length !== currentEntries.length) {
this.events.set(eventName, activeEntries);
}
}
}
return true;
}
_add(eventName, listener, once) {
if (typeof listener !== "function") {
throw new TypeError("listener must be a function");
}
const entries = this.events.get(eventName);
const entry = { listener, once, fired: false, active: true };
if (entries) {
entries.push(entry);
} else {
this.events.set(eventName, [entry]);
}
return this;
}
}スナップショットは現在のディスパッチのメンバーと順序を固定しますが、エントリへの参照を保持します。ディスパッチ中に off によって削除された通常のエントリも、現在のスナップショットから引き続き呼び出されます。そのエントリは次のスナップショットが構築される際に消去されます。新しいエントリはアクティブな配列にのみ追加されるため、古いスナップショットに入ることはありません。
一度限りのエントリには 2 つの状態フィールドが必要です。active = false はネストされた emit からそのエントリを隠します。fired = true は、あまり目立たない再入順序を処理します。外側のスナップショットが同じ参照を保持している間に、ネストされたディスパッチが先にそのエントリを呼び出す可能性があります。外側のループは後から fired を確認し、2 回目の呼び出しをスキップします。両方のマーキングはリスナーの呼び出し前に行われるため、スローされたエラーによって一度限りの登録が復活することはありません。
finally ブロックは非アクティブなエントリを圧縮（整理）します。これがないと、エラーをスローしたリスナーによって、論理的に削除された once エントリがアクティブな配列に残ってしまう可能性があります。例外は依然として emit の呼び出し元に伝播します。finally は失敗を握りつぶすことなく内部の不変条件を保護します。
最低限、次の境界ケースをテストしてください。リスナーがない場合は false を返すこと、引数と this が転送されること、重複登録によって複数回呼び出しが発生し off が最新の 1 つのみを削除すること、繰り返しのディスパッチで once リスナーが 1 回だけ呼び出されること、ディスパッチ中に後続のリスナーを削除してもそのディスパッチからは削除されないこと、追加されたリスナーは次のディスパッチまで待機すること、ネストされたディスパッチによって once エントリが 2 回呼び出されないこと、例外をスローしたリスナーでも一度限りのエントリが確実に削除された状態になること。
質の高い模範解答
「完全な互換性ではなく、Node スタイルのコアな規約にスコープを絞ります。イベント名は文字列または Symbol です。リスナーは登録順に同期実行され、重複が許可され、off は最も新しく一致した登録を削除します。ディスパッチにはスナップショットを使用するため、ディスパッチ中の追加や削除は以降のディスパッチに影響します。emit はリスナーが見つかったかどうかを報告し、リスナーの例外は呼び出し元に伝播します。
イベントごとのエントリ配列を Map に保存します。配列は順序を保持し、各エントリは元の関数と一度限りの状態を保持します。emit は最初に現在のスナップショットをフィルタリングします。一度限りのエントリを呼び出す前に、非アクティブかつ実行済みとしてマークします。非アクティブ化によりネストされたディスパッチでの選択を防ぎ、実行済みフラグによりネストされたディスパッチが既に実行した後に外側のスナップショットが再度呼び出すのを防ぎます。ループを囲む try...finally により、例外をキャッチすることなく、リスナーがスローした後のクリーンアップを保証します。
このモデルは、重複登録とスナップショットセマンティクスを維持します。Map の検索が平均的であるという従来の仮定の下では、on および once での追加は償却 O(1) です。off は配列をスキャンして要素をシフトし、emit はエントリのコピー、呼び出し、クリーンアップを行うため、両方とも O(k) となります。もし off を O(1) にする必要がある場合は、コード量とメモリ消費の増加を許容した上で、二重リンクリストのエントリとインデックスを使用しますが、現在の制約ではそのコストをかける妥当性はありません。」
よくある間違い
- リスナーを
Setに保存する → 同じ関数を 2 回登録しても 1 つしか残らず、重複に関するセマンティクスが変わってしまう → すべての登録が区別されたままになるよう、エントリの配列を使用する。 - アクティブな配列を直接イテレーションする →
offによってインデックスがずれ、onによって新しい項目が現在のディスパッチに引き込まれる可能性がある → ディスパッチ開始時にアクティブなエントリのスナップショットを作成する。 - コールバックが戻った後に
onceを削除する → コールバックが削除前にイベントに再入する可能性があり、例外がスローされると削除自体が行われない可能性がある → 呼び出し前にactive = falseとfired = trueを設定する。 - 実行済み（fired）状態を記録せずに非アクティブ状態のみを記録する → ネストされたディスパッチが once を実行した後、古い外側のスナップショットが同じエントリを再度呼び出す可能性がある → 共有エントリに実行済みガードを保持する。
off内でfilterを使って一致するすべての関数を削除する → 1 回の呼び出しで重複するすべての登録が消去されてしまう → 後方からスキャンして最新のアクティブなエントリのみを削除する。- リスナーのエラーをキャッチして処理を継続する → 呼び出し元が失敗を検知できず、エラー境界が暗黙的に変更されてしまう → 状態のクリーンアップを
finallyで行い、例外はそのまま伝播させる。 - すべての操作が
O(1)であると主張する → Map は厳密な定数時間の検索を保証しておらず、配列の検索、削除、スナップショット作成、トラバーサルはリスナー数に依存する → Map の前提条件を述べた上で、償却on/once O(1)とoff/emit O(k)を個別に説明する。
フォローアップの質問と回答
フォローアップ 1: ディスパッチ中に削除されたリスナーが、そのディスパッチを最後まで完了すべきなのはなぜですか？
スナップショットは emit 開始時に対象者を確定させ、先行するリスナーが後続のインデックスを変更するのを防ぎます。この実装ではスナップショット内にエントリの参照を保持しますが、通常のリスナーを呼び出す前に active を再チェックしないため、現在のディスパッチではそのまま実行されます。次のスナップショットからは除外されます。プロダクトによっては各呼び出しの前に active をチェックして即時削除を選択することもありますが、それは異なる規約であり、別のテストが必要になります。
フォローアップ 2: 再入環境下で once が最大でも 1 回しか実行されないことをどのように証明しますか？
一度限りのエントリは、fired が false である間のみ呼び出しパスに入ることができます。そのエントリに最初に到達したディスパッチが、リスナーを呼び出す前に fired を true に設定します。ネストされたスナップショットと外側のスナップショットは同じエントリ参照を保持しているため、その後のすべての試行で true が確認され、スキップされます。これにより、ネストの順序に関係なく「最大 1 回」の挙動が保証されます。初回呼び出し時のみ再帰的に emit を行う通常のリスナーを先頭に配置し、その後に once リスナーを配置することで、最も厳しい順序をテストできます。
フォローアップ 3: off を O(1) にする必要がある場合、何が変わりますか？
配列では、O(1) での任意のエントリの削除と安定した順序の維持を両立できません。イベントごとに二重リンクリストを保持し、関数の最も新しく登録されたノードを特定する Map<listener, nodes[]> を管理します。そのノードのリンクを解除するのは O(1) であり、emit は依然として O(k) です。その代償として、登録ごとに 2 つのポインタが必要になり、重複関数のインデックスの維持が必要となり、スナップショットの挙動がより複雑になります。リスナー数が少なく削除頻度が低い場合は、配列の方が検証が容易です。
フォローアップ 4: リスナーが Promise を返す場合や例外をスローした場合はどうなりますか？
現在の emit は同期処理であり、戻り値を無視します。同期的な例外のスローはディスパッチを停止させて呼び出し元に伝播し、finally は状態のクリーンアップのみを行います。返された Promise は await されません。呼び出し元が完了を待つ必要がある場合は、別の emitAsync 規約を定義し、順次実行か並列実行か、フェイルファストか全結果取得型のエラーハンドリングかを選択します。それらの決定なしに既存のループに await を追加すると、API が曖昧になります。
フォローアップ 5: ディスパッチ中に追加されたリスナーが次のディスパッチまで待機することをどのように検証しますか？
A を登録し、A が呼び出されたときに B を登録するようにします。最初の emit のスナップショットには A のみが含まれるため、A のみが出力されます。2 回目のスナップショットには A と B が含まれ、A、B の順に出力されます。また、C が最初のスナップショットに入った後に A が C を削除するケースも作成します。この場合、最初のディスパッチでは依然として A、C の順で出力され、2 回目のディスパッチでは C が除外されます。これらのアサーションを組み合わせることで、変更境界の両方の側面を網羅して検証できます。