問題と適用コンテキスト
deepClone(value) を実装してください。入力は単一の JavaScript レルム（realm）からの有限オブジェクトグラフです。プリミティブ、プロトタイプが Object.prototype または null であるプレーンオブジェクト、Date、RegExp、Map、および Set を含む場合があります。サポートされている各コピー元オブジェクトは、コピー側で個別のオブジェクトを持つ必要があります。2つのコピー元のエッジが同一のオブジェクトを指している場合、対応するコピー側のエッジも同一のコピー済みオブジェクトを指す必要があります。循環によって無限再帰が発生してはなりません。
この関数は、プロパティ記述子（descriptor）を保持したまま、列挙不可（non-enumerable）およびシンボルキー付きプロパティを含む、すべての自身のデータプロパティ（own data properties）もコピーする必要があります。配列の疎な要素（holes）、Date の時間値、RegExp の source、flags、および lastIndex、Map のキーと値の両方、そして Set の値を保持してください。
関数、アクセサプロパティ、WeakMap、WeakSet、Proxy、型付き配列（TypedArray）、ArrayBuffer、カスタムクラスのインスタンス、および記載されていない組み込みオブジェクトは規約の対象外であり、TypeError を発生させる必要があります。実装は再帰的であるため、ネストによってコールスタックが枯渇しないことも前提とします。プラットフォームの構造化複製可能な型に適合する本番データについては、この面接用の実装を汎用ライブラリにする前に structuredClone の採用を検討してください。
面接官が評価している点
第1の評価ポイントは、候補者が「ディープクローン」の意味を定義しているかどうかです。JavaScript には、関数のクロージャ、DOM ノード、プライベートフィールド、Proxy、およびすべての組み込み内部スロットを再現できる普遍的なユーザーランドルールは存在しません。優れた回答は、再帰処理を書く前に、サポートする型、プロパティのセマンティクス、循環時の挙動、および失敗時の挙動を列挙します。
第2の評価ポイントは、オブジェクトツリーではなくオブジェクトグラフとして認識しているかどうかです。オブジェクトを再帰的に割り当てる方法はツリーをコピーできますが、source.self = source を処理できず、誤って source.a === source.b を2つの独立したコピーにしてしまいます。必要な状態は単なる「訪問済み」ではなく、「どのコピーがこのコピー元オブジェクトに対応しているか」です。
第3の評価ポイントは、割り当ての順序です。空のターゲットを割り当て、出力エッジを走査する前にコピー元からコピー先へのマッピングを記録します。子要素を登録前にコピーしてしまうと、最初の後方エッジ（back edge）でターゲットが見つからず、循環に沿って再帰が続いてしまいます。
第4の評価ポイントは、プロパティと組み込みオブジェクトの境界を正確に把握しているかです。Object.entries はシンボルキーや列挙不可プロパティを見落とします。source[key] を読み取るとゲッターが実行される可能性があります。Date、Map、または Set に対して同じプロトタイプを持つオブジェクトを渡しても、その内部スロットは再現されません。
回答前に確認すべき質問
- どの型をサポートする必要がありますか？ JSON 形式のデータであれば、配列とプレーンオブジェクトで十分です。
Date、RegExp、Map、およびSetを追加するには、型に応じた構築と走査が必要になります。型付き配列や ArrayBuffer を追加すると、バッファのコピーや所有権の選択が生じます。 - 循環や重複参照は失敗させるべきですか、それとも解除するか、トポロジーを保持すべきですか？ この問題ではそれらを保持するため、コピー元からコピー先へのマップが必要です。
WeakSetでは重複を検出できますが、正しいコピーを返すことはできません。 - プロパティとは列挙可能な文字列キーのみを意味しますか、それともシンボル、列挙不可プロパティ、記述子も含まれますか？ 本規約では後者を選択し、アクセサを拒否することで、ゲッターの実行や共有ゲッター/セッター関数の混入を防ぎます。
- カスタムクラスやプロトタイプチェーンはコピーする必要がありますか？ この問題では、プレーンオブジェクトと記載された組み込みオブジェクトのみを受け入れます。
Object.create(instancePrototype)はプライベートフィールドやコンストラクタで確立された状態を再現できないため、その結果を完全なインスタンスとして提示することは誤解を招きます。 - これは面接用アルゴリズムですか、それとも本番環境用 API ですか？ 面接用の実装は、規約とグラフ不変条件を実証するものです。本番コードでは、制御されたカスタムシリアライザを選択する前に、
structuredCloneの型の網羅性、転送セマンティクス、メタデータの損失を比較検討する必要があります。 - 最大ネスト深度はどれくらいですか？ 再帰は
O(d)の補助スタックを使用します。10万個のオブジェクトを含む可能性のあるチェーンには明示的な作業スタックが必要となり、実装とテストが変化します。
30秒の回答フレームワーク
「サポートする型を定義し、入力をグラフとして扱います。プリミティブは直接返します。各オブジェクトについて WeakMap を確認し、初回の訪問時に、プロパティやエントリをコピーする前に空のコピーを割り当てて登録します。これにより、循環参照や重複参照は単一のコピーに解決されます。Date と RegExp は再構築し、関数、アクセサ、およびサポート対象外のオブジェクトは例外をスローします。期待される時間およびコピー空間は O(V + E) で、再帰スタックは O(d) です。」
ステップごとの詳細解説
JSON.parse(JSON.stringify(value)) は、より限定的な JSON 規約にのみ有効です。循環参照で失敗し、undefined、BigInt、シンボル、Date、RegExp、Map、Set、および特殊な数値を変更または失います。単純な再帰はより多くの制御を提供しますが、コピー元からコピー先へのマッピングがなければ、依然としてツリーしか処理できません。
中心となる不変条件は次のとおりです。サポートされているオブジェクトのプロパティまたはエントリを走査する前に、seen.get(sourceObject) はすでにそのオブジェクトのために割り当てられた一意のコピーと等しくなっています。
function deepClone(input) {
const seen = new WeakMap();
function clone(value) {
if (typeof value === 'function') {
throw new TypeError('Functions are not supported');
}
if (value === null || typeof value !== 'object') {
return value;
}
if (seen.has(value)) {
return seen.get(value);
}
let result;
if (value instanceof Date) {
result = new Date(value.getTime());
seen.set(value, result);
copyOwnDataProperties(value, result);
return result;
}
if (value instanceof RegExp) {
result = new RegExp(value.source, value.flags);
result.lastIndex = value.lastIndex;
seen.set(value, result);
copyOwnDataProperties(value, result, new Set(['lastIndex']));
return result;
}
if (value instanceof Map) {
result = new Map();
seen.set(value, result);
for (const [key, item] of value) {
result.set(clone(key), clone(item));
}
copyOwnDataProperties(value, result);
return result;
}
if (value instanceof Set) {
result = new Set();
seen.set(value, result);
for (const item of value) {
result.add(clone(item));
}
copyOwnDataProperties(value, result);
return result;
}
if (Array.isArray(value)) {
result = new Array(value.length);
seen.set(value, result);
copyOwnDataProperties(value, result, new Set(['length']));
Object.defineProperty(
result,
'length',
Object.getOwnPropertyDescriptor(value, 'length'),
);
return result;
}
const prototype = Object.getPrototypeOf(value);
if (prototype !== Object.prototype && prototype !== null) {
throw new TypeError('Unsupported object type');
}
result = Object.create(prototype);
seen.set(value, result);
copyOwnDataProperties(value, result);
return result;
}
function copyOwnDataProperties(source, target, skipped = new Set()) {
for (const key of Reflect.ownKeys(source)) {
if (skipped.has(key)) {
continue;
}
const descriptor = Object.getOwnPropertyDescriptor(source, key);
if (!('value' in descriptor)) {
throw new TypeError('Accessor properties are not supported');
}
descriptor.value = clone(descriptor.value);
Object.defineProperty(target, key, descriptor);
}
}
return clone(input);
}seen は、単なる訪問済みフラグではなく、コピー元からコピー先への関係を保存する必要があります。仮に source.first と source.second の両方が shared を指しているとします。最初の訪問で sharedCopy を割り当てて登録し、2回目の訪問ではその同じオブジェクトを返すことで、エイリアシングを保持します。source.self が source を指し戻す場合、ルートはそのプロパティがコピーされる前に登録されているため、後方エッジはルートのコピーを指します。
すべてのキーがオブジェクトであり、アルゴリズムが列挙を必要としないため、WeakMap が適しています。通常の Map も1回の呼び出し内では正しく機能し、関数から戻った後に自動的に永久リークすることはありません。弱い参照を持つキーは関連付けのライフタイムに合致しますが、「メモリリークを防ぐ」ことは循環参照が正しく処理されることの証明にはなりません。
Reflect.ownKeys は、列挙不可プロパティを含む文字列キーとシンボルキーを返します。コードは値ではなく記述子を読み取るため、能動的にゲッターを実行することはありません。アクセサは規約に従って失敗します。データ記述子の値を再帰的に置き換え、その writable、enumerable、configurable フラグを使用してプロパティを定義します。配列の length は特殊な変更不可（non-configurable）プロパティであるため、他のキーを先にコピーし、最後にその記述子を復元します。疎な配列のホールが誤って値が undefined の要素に変換されることはありません。
Date、RegExp、Map、および Set は、通常のプロパティコピーでは到達できない内部状態を持っています。実装では、時間値、正規表現の source、flags、lastIndex、Map のキーと値、および Set の値を再構築します。各コンテナは反復処理の前に登録されるため、Map や Set も循環参照に参加できます。コードは同一レルムのオブジェクトを前提としています。レルムを越えた instanceof チェックは信頼性が低く、プラットフォームのクローン機能やより厳密なブランドチェックが必要となります。
境界は明確に保たれます。このコードは、frozen、sealed、または non-extensible の状態を保持せず、プロトタイプチェーンを複製せず、アクセサ、プライベートフィールド、Proxy、バッファ、または記載されていない組み込みオブジェクトをサポートしません。structuredClone はより多くのプラットフォーム型、循環、重複した同一性をサポートしますが、関数を除外し、プロパティ記述子、ゲッター、セッター、プロトタイプチェーン、RegExp.lastIndex は保持しません。これらは両方ともディープクローンと呼ばれますが、規約が互換であるわけではありません。
V を個別のオブジェクト数、E を自身のプロパティ、Map のエントリ、および Set の要素によって提供される参照数とします。組み込みマッピングの標準的な平均パフォーマンスの前提下では、各コピー元オブジェクトが1回展開されるため、走査処理とコピー空間は O(V + E) になります。再帰コールスタックは O(d) です（ここで d は最も長いネストパス）。ECMAScript は Map、Set、WeakMap に対して平均的な劣線形（sublinear）アクセスのみを要求しており、すべての実装で厳密な O(1) 操作を保証しているわけではありません。
テストでは、シリアライズされたテキストを比較するのではなく、グラフ構造を検証する必要があります：自己循環参照、1つの子を共有する2つのプロパティ、別のプロパティからも参照される Map のキー、共有オブジェクトを含む Set、疎な配列、null プロトタイプオブジェクト、列挙不可およびシンボルキーのデータプロパティ、Date、ゼロ以外の lastIndex を持つ RegExp、関数・アクセサ・カスタムクラスに対するエラー、およびコピー変更後の分離性です。非常に深い非循環チェーンに対しても再帰の境界をテストする必要があります。
質の高い模範解答
「これを、プリミティブ、Array、プレーンな Object、Date、RegExp、Map、および Set を含む、有限の同一レルムのオブジェクトグラフに限定します。関数、アクセサ、弱参照コレクション、バッファ、およびカスタムクラスは、問題でテスト可能なコピーセマンティクスが定義されていないため、例外をスローします。
重要なのは、再帰そのものではなく、オブジェクトの同一性関係を保持することです。私は WeakMap<source, copy> を保持します。オブジェクトを見つけるたびに、まずマップを確認します。初回の訪問時には、プロパティやエントリをコピーする前に空のコピーを割り当てて登録します。これにより、自己循環は現在のコピーに解決され、1つのコピー元オブジェクトへの2つのエッジは1つのターゲットオブジェクトに解決されます。Map のキーと値、および Set の要素も同じクローンパスを使用するため、コンテナを跨いだエイリアシングが保持されます。
通常のプロパティには Reflect.ownKeys と記述子を使用します。これにより、ゲッターを暗黙的に実行することなく、シンボル、列挙不可プロパティ、およびデータ記述子のフラグが保持されます。Date、RegExp、Map、および Set は型固有の再構築を行います。個別のオブジェクトと参照エッジを数えると、期待される作業量とコピー空間は O(V + E) であり、コールスタックは O(d) です。本番環境では、サポート要件に適合する場合は structuredClone を使用しつつ、記述子、プロトタイプ、または RegExp の lastIndex が保持されないことをドキュメントに明記します。」
よくある間違い
- JSON のシリアライズとパースを行う → 循環で例外が発生し、いくつかの有効な JavaScript 値が失われたり変更されたりし、共有参照が分離してしまう → 必要に応じて JSON 専用規約、グラフアルゴリズム、または
structuredCloneを使用する。 - 配列とオブジェクトのみを再帰的にコピーする → 自己循環で無限再帰が発生し、重複した参照が別個のオブジェクトになってしまう → すべてのコピー元オブジェクトを1つのコピーにマッピングする。
seenに挿入する前に子要素をコピーする → 最初の後方エッジがまだマッピングを持たない → エッジを展開する前に空のコピーを割り当てて登録する。WeakSetで訪問を追跡する → 重複は検出できるが、アルゴリズムにどのコピーを返すべきかを伝えられない →WeakMap<source, copy>を使用する。- すべてのプロパティに対して
for...inまたはObject.entriesを使用する → 前者は継承された列挙可能プロパティを含み、後者はシンボルや列挙不可プロパティを見落とす → 規約で必要な場合は自身の記述子とReflect.ownKeysを使用する。 source[key]を直接読み取る → ゲッターが副作用を実行したり例外をスローしたりして、クローンの観測可能な挙動を変えてしまう可能性がある → 記述子を検査し、明示的なアクセサポリシーを定義する。- すべてのターゲットを
Object.create(proto)で作成する → Date、Map、Set の内部スロットが欠落したままになり、カスタムクラスのプライベートフィールドも失われる → サポートされている組み込みオブジェクトを再構築し、その他の型は拒否する。 - 厳密な
O(V + E)を主張する → ECMAScript は Map、Set、WeakMap の定数時間操作を保証しておらず、再帰がオーバーフローする可能性がある → 平均的なパフォーマンスの前提とO(d)スタックの境界を述べる。
フォローアップ質問と回答
フォローアップ 1: 循環参照を防ぐだけでなく、重複参照を保持するのはなぜですか？
同一性はアプリケーションの意味を持つことがあります。もし order.customer === cache.currentCustomer である場合、それらを個別にクローンするとコピー内でその等価性が false になり、一方のコピーされたパスを介した変更がもう一方から観測できなくなります。1対1のコピー元からコピー先へのマッピングは、循環とエイリアシングの両方を保持します。テストでは copy.first === copy.second をアサートすべきであり、単にクローンがオーバーフローしなかったことをアサートするだけでは不十分です。
フォローアップ 2: 10万オブジェクトの深さのチェーンはどのように処理しますか？
同じ seen 不変条件を維持しつつ、再帰呼び出しを明示的な作業スタックに置き換えます。初遭遇時にコピーを割り当てて登録し、コピー元コンテナ、ターゲットコンテナ、保留中のキーまたはエントリを含むフレームをプッシュします。反復ループがそれらのフレームを処理します。時間とヒープの使用量は依然として V + E に比例して増加しますが、補助状態は言語のコールスタックから制御されたヒープ構造に移動します。Date と RegExp は即座に完了し、Object、Array、Map、および Set は後続のフレームを必要とします。
フォローアップ 3: ArrayBuffer をコピーまたは転送（transfer）できるようにする場合、何が変わりますか？
API に明示的なオプションが必要になります。コピーは同じ長さのバッファを割り当ててバイトをコピーします。転送はコピー元のバッファを無効化するため、副作用を伴う所有権の移動となり、deepClone の内部に隠すことはできません。プラットフォームはすでにこれを structuredClone(value, { transfer: [...] }) を通じて定義しています。ストレージをデタッチ（切り離し）できないカスタム実装は、1つのバッファに対する2つのビューを返してその結果をディープコピーと呼ぶのではなく、転送を拒否すべきです。
フォローアップ 4: カスタムクラス、ゲッター、プライベートフィールドはどのようにサポートしますか？
汎用的なリフレクションではプライベートフィールドを読み取ったり、クロージャを再現したりすることはできません。ゲッターやセッターを保持すると関数やクロージャが共有され、ゲッターを評価すると副作用が発生する可能性があります。妥当な拡張策はシリアライザレジストリです。各クラスがその不変条件を再構築する serialize および deserialize 関数を提供し、そのアダプタがアクセサを保持するか、評価するか、拒否するかを決定します。アダプタがない場合は、内部状態が壊れているにもかかわらず instanceof が true になるオブジェクトを作成するよりも、例外をスローする方が安全です。