問題と適用すべき場面
整数の ID が途切れることなく 1 つずつ到着するストリームがあります。add(x) は ID x の出現回数を 1 増やします。topK(k) は、現在の頻度が最も高い最大 k 個の重複しない ID とそのカウントを返します。同数の ID は順不同で出力でき、k はクエリごとに変更可能です。読み取り重視および書き込み重視のワークロードに対応する正確な解法を設計し、それぞれの時間計算量と空間計算量を分析してください。また、メモリが固定されている中で重複しない ID の数が無制限に増加する可能性がある場合について、近似的な設計を提示し、その誤差の意味を定義してください。
この問題は、ソフトウェアエンジニアリングやアルゴリズムの面接に適しています。厳密な要件として、頻度のインクリメントのみを許可し、削除、スライディングウィンドウ、分散マージは対象外とします。これまでに行われた更新回数を N、重複しない ID の総数を D とし、一般的なケースでは k << D であるとします。一般に公開されている出題例では、ワークロードに応じた設計と、メモリ制限のあるストリーミング拡張が明示的に求められるため、「ハッシュマップ＋最小ヒープ」を答えるだけでは不十分です。
面接官が評価しているポイント
第 1 に、候補者が操作の前提条件とワークロードの比率を明確に定義できるかどうかです。ストリーム終了後に 1 度だけ結果を要求するバッチ処理と、更新のたびに問い合わせが発生するオンラインランキングとでは、同じメンテナンスコストをかけるべきではありません。
第 2 に、提示された計算量が保持されている状態と一致しているかどうかです。ハッシュマップでカウントし、クエリ実行時にサイズ k の最小ヒープを構築する場合、O(1) に対する期待値は add、O(D log k) に対する期待値は topK となります。更新ごとに O(log k) のヒープメンテナンスを行うと主張する場合は、ヒープ内の位置追跡と、ヒープ外の要素がヒープ内に入るタイミングについての説明も求められます。
第 3 に、動的データ構造の正当性を証明できるかどうかです。優れた回答では、3 つの不変条件が示されます。「すべての ID は必ず 1 つの頻度バケットに属する」「バケットの頻度は狭義の単調増加であり、空のバケットは存在しない」「ID が属するバケットの頻度はその真の累積カウントに等しい」。計算量の議論は、これらの不変条件に基づいて行われる必要があります。
第 4 に、厳密な Top-K、ヘビーヒッター（Heavy Hitters）、頻度推定の違いを区別できるかどうかです。Space-Saving は、固定されたカウンター数の予算内でカウントの境界を持つ候補キーを保持します。Count-Min Sketch は主に指定されたキーの頻度を推定するものであり、それ自体で列挙可能な ID の集合を保持するわけではありません。スケッチ単体を Top-K リストとして扱うと、候補の特定方法が説明されないままになります。
回答前に確認すべき明確化のための質問
kは固定ですか、それともクエリごとに異なりますか？Kが固定であれば、インデックス付きのサイズKのヒープが使えます。任意のkであれば、すべての頻度でソートされた構造が有利になります。- 更新とクエリの比率はどのくらいですか？ 書き込み重視のシステムでは、クエリ時まで処理を遅延させることができます。頻繁なクエリが発生する場合は、
addのたびに順序を維持する正当性が高まります。 - タイ（同数）の順序は決定論的である必要がありますか？ この要件では任意の順序が許可されているため、各バケット内にハッシュセットがあれば十分です。ID の昇順を要求すると順序付きセットが必要になり、更新処理の期待値
O(1)が維持できなくなります。 - 削除や時間ウィンドウは必要ですか？ インクリメントのみの場合、アイテムは頻度
fから隣接する頻度f + 1に移動します。削除があると逆方向の移動が発生し、ウィンドウを扱う場合は有効期限の状態管理も必要になります。 Dはメモリに収まりますか？ 制約のないデータ分布に対して厳密な解を得るには、重複しないすべての ID のカウントを保持する必要があります。メモリが固定されている場合は、近似手法または再現可能な 2 パス処理が必要です。- どの程度の誤差が許容されますか？ 「おおよそ正しい」という表現ではテストできません。加法的なカウント誤差、不確実な候補セット、または Top-K を保証するための頻度分離条件を明確に定義してください。
- カウンターのオーバーフローは発生しますか？ 長期間稼働するサービスでは 64 ビット以上のカウンターが必要です。この例では JavaScript の
numberを使用しており、安全な整数の範囲内でのみ厳密性が保証されます。
30秒の回答フレームワーク
「まず、k が変動するかどうか、読み書きの比率、同順位の順序付け、メモリ制限について確認します。書き込み頻度が高くクエリが少ないワークロードでは、ハッシュマップを使って期待値 O(1) で追加し、クエリごとに D 個のカウントをサイズ k の最小ヒープにスキャンして O(D log k) で処理します。任意の k に対するクエリが頻繁に発生する場合は、頻度バケットの昇順の重方向連結リストと ID → bucket マップを維持します。更新時は ID がバケット f から隣接するバケット f + 1 にのみ移動するため、更新の期待値は O(1) となり、末尾から逆方向に走査して k 件の結果を取得するコストは O(min(k, D))、空間計算量は O(D) です。D がメモリに収まらない場合は、誤差範囲を持つ固定された Space-Saving カウンターを使用し、境界が明確に分離している場合にのみ Top-K を保証します。Count-Min Sketch で ID を列挙するには、別途候補セットが必要です」
ステップごとの解決策
ステップ 1: ワークロードに応じた厳密な設計の比較
| 設計 | add | topK(k) | 空間計算量 | 最適なユースケース |
|---|---|---|---|---|
| カウントをハッシュ化し、クエリ時に最小ヒープを構築 | 期待値 O(1) | O(D log k) | O(D + k) | 書き込みが多くクエリが少ない、最もシンプルな実装 |
固定の 1 つの K 用のインデックス付き最小ヒープ | O(log K) | O(K)（ソートする場合は O(K log K)） | O(D + K) | すべてのクエリで同一の K を使用 |
(frequency, ID) で順序付けられた平衡二分木 | O(log D) | O(k + log D) | O(D) | 同順位の決定論的順序、または最悪ケースの計算量保証 |
| 位置ハッシュ＋双方向連結頻度バケット | 期待値 O(1) | O(min(k, D)) | O(D) | 可変な k かつ頻繁なクエリ |
「ハッシュマップ＋最小ヒープ」が常に最善というわけではありません。これは意図的にソート処理をクエリ側に寄せるアプローチであり、書き込みが圧倒的に多い場合に適しています。add のたびにリーダーボードを描画するようなプロダクトでは、D 個のキーを繰り返しスキャンすることがボトルネックとなるため、多少複雑であっても頻度バケット構造を採用する価値があります。
ステップ 2: 頻度バケットの不変条件を確立する
頻度の昇順に並んだバケットの双方向連結リストを保持します。各バケットはその頻度を持つ ID の集合を保持し、ハッシュマップによって各 ID のバケットを直接特定します。新規の ID は頻度 1 のバケットに追加されます。既存の ID はバケット f からバケット f + 1 に移動します。1 回の更新でカウントは 1 つしか増えないため、新しいバケットは元のバケットとその次のバケットの間にのみ挿入され、リストの探索は不要です。元のバケットが空になったら即座に削除します。
結果の正当性は 3 つの不変条件によって証明されます。
locations内のすべての ID は、厳密に 1 つのバケットセットに現れる。- 空でないすべてのバケットの
frequencyは、そこに含まれるすべての ID の真のカウントと等しい。 - 頻度は
headからtailに向かって厳密に増加する。
したがって、tail から逆方向に走査することで、より頻度の高い ID を見落とすことはなく、同順位の要素は任意の順序で返すことができます。訪問した各バケットからは少なくとも 1 つの結果が得られるため、走査するバケット数は出力サイズ以下となり、クエリ時間は O(min(k, D)) になります。
ステップ 3: 任意の k に対する厳密なクエリの実装
interface Bucket {
frequency: number;
values: Set<number>;
prev: Bucket | null;
next: Bucket | null;
}
interface TopKEntry {
value: number;
count: number;
}
class FrequencyIndex {
private readonly locations = new Map<number, Bucket>();
private head: Bucket | null = null;
private tail: Bucket | null = null;
add(value: number): void {
const source = this.locations.get(value);
if (!source) {
let target = this.head;
if (!target || target.frequency !== 1) {
target = this.insertBefore(this.head, 1);
}
target.values.add(value);
this.locations.set(value, target);
return;
}
let target = source.next;
if (!target || target.frequency !== source.frequency + 1) {
target = this.insertAfter(source, source.frequency + 1);
}
source.values.delete(value);
target.values.add(value);
this.locations.set(value, target);
if (source.values.size === 0) {
this.removeBucket(source);
}
}
topK(k: number): TopKEntry[] {
if (!Number.isInteger(k) || k < 0) {
throw new RangeError("k must be a non-negative integer");
}
const result: TopKEntry[] = [];
let bucket = this.tail;
while (bucket && result.length < k) {
for (const value of bucket.values) {
result.push({ value, count: bucket.frequency });
if (result.length === k) break;
}
bucket = bucket.prev;
}
return result;
}
private insertBefore(next: Bucket | null, frequency: number): Bucket {
const bucket: Bucket = {
frequency,
values: new Set<number>(),
prev: next?.prev ?? null,
next,
};
if (bucket.prev) bucket.prev.next = bucket;
else this.head = bucket;
if (next) next.prev = bucket;
else this.tail = bucket;
return bucket;
}
private insertAfter(prev: Bucket, frequency: number): Bucket {
const bucket: Bucket = {
frequency,
values: new Set<number>(),
prev,
next: prev.next,
};
if (prev.next) prev.next.prev = bucket;
else this.tail = bucket;
prev.next = bucket;
return bucket;
}
private removeBucket(bucket: Bucket): void {
if (bucket.prev) bucket.prev.next = bucket.next;
else this.head = bucket.next;
if (bucket.next) bucket.next.prev = bucket.prev;
else this.tail = bucket.prev;
}
}この計算量は、Map および Set における一般的な期待値としての定数時間計算量の前提に基づいており、JavaScript 仕様における厳密な最悪ケース O(1) の保証ではありません。topK(0) は空の配列を返し、k > D はすべての ID を返し、負の数や整数でない k はエラーをスローします。
ステップ 4: メモリ制限下での近似保証の定義
厳密なハッシュマップは D に比例して増大します。これに対し Space-Saving では、ID、推定カウント、最大誤差を保持するカウンターを m 個のみ保持します。境界の候補 k + 1 と比較するために m > k が必要となります。すでに追跡中の ID が出現した場合はカウンターをインクリメントします。すべてのカウンターが埋まっている状態で未追跡の ID が到着した場合、最小推定カウント c_min を持つ ID が置き換えられ、新しい推定値は c_min + 1、記録される誤差は c_min になります。
監視対象のすべての ID について、真の頻度は [estimate - error, estimate] の範囲内にあり、原論文では最大過大評価が N / m で抑えられることが示されています。上位 k 個の候補の中で最小の下限が、k + 1 番目の候補の推定上限値以上である場合、Top-K の集合を保証できます。これらの区間が重複する場合は、推定順序を厳密なものとして提示するのではなく、近似候補として返します。ストリーム全体で D <= m である場合、置き換えは発生せず、カウントは正確なまま維持されます。
Count-Min Sketch は固定サイズの width × depth カウンター配列を使用します。インクリメントのみのストリームにおいて width = ceil(e / ε) および depth = ceil(ln(1 / δ)) を設定すると、指定された ID の推定値が真のカウントを下回ることはなく、少なくとも 1 - δ の確率で true count + εN 以下になります。スケッチ自体は ID を保持しないため、別途候補ヒープ、候補セット、または列挙可能なドメインが必要です。スケッチ単体では「どの ID が Top-K か」に答えることはできません。
ステップ 5: 1 つの例だけでなくオラクルを用いて検証する
まず [1, 2, 1, 3, 2, 1] から開始し、topK(2) が頻度 3 と 2 を持つ 2 つの ID を返すことを検証します。次に、空の構造、k = 0、k > D、すべて同頻度、1 つの頻出アイテムと多数の単一アイテム、1 つの ID が多数のバケットを移動するケースをカバーします。
最後に、ランダムな更新ストリームを生成し、単純なハッシュカウントと完全ソートを組み合わせたものをオラクル（正解判定器）として使用します。一定間隔ごとに、結果の長さが min(k, D) であること、ID が一意であること、報告された各カウントが正確であること、除外されたどの ID も選択された最小カウントを上回っていないことを検証します。上記の実装は、10,000 回の決定論的ランダム更新および複数の k の値を用いたこの差分テストを通過しています。
模範解答の例
「厳密な要件として、インクリメントのみの更新、クエリごとに指定される k、同順位は順不同とします。書き込みが多くクエリが稀な場合、期待値 O(1) の追加コストで済むよう ID → count ハッシュマップのみを保持します。クエリ時は D 個の ID をサイズ k の最小ヒープを通して走査し、時間計算量は O(D log k)、追加空間計算量は O(k) となります。
リーダーボードへのクエリが頻繁に行われる場合は、双方向連結頻度バケットを使用します。バケットは低頻度から高頻度の順に並び、その頻度で並んでいる ID を保持します。ハッシュマップで各 ID のバケットを特定します。1 回の add は ID を f から f + 1 にのみ移動させるため、隣接バケットを確認し、空になった元のバケットを削除します。更新の期待値は O(1) であり、末尾から逆方向に走査することで O(min(k, D)) で結果を返し、合計空間計算量は O(D) です。正当性は、一意のバケット所属、正確なバケットカウント、狭義単調増加のバケット順序から導かれます。
D がメモリに収まらない場合は、厳密性の要件を変更する必要があります。候補の誤差区間を持つ m 個の Space-Saving カウンターを保持します。最大の過大評価は N / m で抑えられ、上位 k 個の下限がそれ以降の上限と完全に分離している場合にのみ集合を保証します。Count-Min Sketch は指定された ID の頻度を推定できますが、候補を探索する仕組みが別途必要です。リリース前には、完全ソートをオラクルとしたランダム差分テストを実施し、同順位、無効な k、カウンターのオーバーフロー境界を明示的にテストします」
よくあるミス
- ワークロードを確認する前に最小ヒープを選択してしまう → 頻繁なクエリはすべての
D個の ID をスキャンすることになり、クエリが稀であれば継続的なメンテナンスコストが無駄になります → 実際の比率に応じて、更新側かクエリ側のどちらにコストを寄せるかを決定してください。 kが可変であるのに 1 つの固定Kを保持してしまう → 保持しているKよりも大きなクエリが来た場合に完全な候補セットがなくなります →kを明示的に制限するか、任意のkに対応できる頻度バケットや順序付き構造を使用してください。- ヒープ内のキーをその場で変更してしまう → 通常のヒープは要素の位置を把握していないため、順序が壊れるか古いレコードが蓄積します →
ID → heap indexを保持するか、明示された計算量で古いキーを削除して再挿入してください。 - 空になった頻度バケットをリストに残してしまう → クエリ時に頻度 1 から最大カウントまでの空のギャップを走査することになります → 最後の ID が移動した直後に、そのバケットをリストから切り離してください。
- ハッシュ処理を厳密な
O(1)であると主張してしまう → Map や Set は一般的な期待計算量の分析をサポートしますが、言語仕様として厳密に保証されているわけではありません → ハッシュの前提条件を明示し、最悪ケースの保証が必要な場合は平衡二分木を使用してO(log D)を許容してください。 - Count-Min Sketch から直接 Top-K を返そうとする → スケッチは指定されたキーのクエリに答えるものであり、未知の ID を列挙することはできません → 候補探索を別途維持するか、候補キーを保持する Space-Saving を使用してください。
- 誤差を示さずに近似結果を返してしまう → 面接官は順位
kとk + 1が区別可能かどうかを判断できません → 推定値、上限・下限、およびそのセットが保証されているかどうかを返してください。 - サンプルのテストケースだけで済ませてしまう → リンク切れ、空のバケット、タイの境界などは、長い更新シーケンスの後に初めて現れることがよくあります → 完全ソートによるオラクルを用いた差分テストを実施し、不変条件をアサートしてください。
フォローアップの質問と回答
フォローアップ 1: topK が常に K = 100 を使用する場合、それでも頻度バケットは必要ですか？
必ずしも必要ではありません。カウントマップ、サイズ 100 の最小ヒープ、および ID → heap index を使用すれば、更新のたびに O(log 100) でヒープ要素を調整したり最小値と比較したりできます。コードやメモリ配置がシンプルになる可能性がありますが、topK(1000) には対応できません。頻度バケットは、k が任意であり、かつ更新処理における期待値としての定数時間処理が重要である場合にその複雑さの価値を発揮します。
フォローアップ 2: 同頻度の ID を昇順にする必要がある場合は何が変わりますか？
各バケットの Set を順序付きセットに置き換えるか、クエリで一部のみが取得される境界バケットのみをソートします。前者はサイズ s のバケットに対して移動ごとに O(log s) のコストが追加され、後者はクエリ時にのみ境界ソートのコストを支払います。決定論的な順序がどの程度の頻度で必要とされるかに応じて選択してください。
フォローアップ 3: remove(x) を追加するにはどうすればよいですか？
前方のバケットを対称的にチェックして ID を頻度 f から f - 1 に移動させ、カウントが 0 に達したときに locations からその ID を削除します。存在しない ID の削除で例外をスローするか無視するかを定義してください。並行して add と remove が行われる環境では、バケットの特定、移動、空バケットの切り離しを 1 つのアトミックなクリティカルセクション内で行う必要があります。そうしないと同じ ID が 2 つのバケットに現れる可能性があります。
フォローアップ 4: 過去 10 分間のみを対象にクエリを実行する場合はどうなりますか？
頻度はもはや単調増加ではなくなります。バケットインデックスにタイムスタンプ付きイベントまたは時間バケット単位のカウントを持たせ、有効期限切れに伴い逆方向の更新を発行できるようにする必要があります。イベントごとのキューは正確ですが、ウィンドウ内のイベント数に比例した空間を使用します。時間バケットを使うと状態を削減できますが、明示的な境界誤差が生じます。全履歴を対象とする Space-Saving サマリーでは、期限切れとなった任意のイベントを直接減算することはできません。
フォローアップ 5: 順位 k と k + 1 に対する Space-Saving の区間が重複した場合はどうしますか？
カウンターの予算 m を増やすか、候補セットがまだ保証されていないことを報告するか、データを再生して候補セットを正確にカウントし直します。2 パス目の処理は保持されている候補のみを修正します。真の Top-K がそのセットに入っていることを保証するにはサマリーが小さすぎた場合は、再生前に候補セットを拡大してください。
フォローアップ 6: シャードを跨いでグローバルな Top-K を取得するにはどうすればよいですか？
任意のデータ分布において、ローカルの Top-K リストから厳密なグローバル Top-K を作成することはできません。各シャードでカットオフの直下にいた ID が、集約後にグローバルで上位に入る可能性があるためです。厳密な設計では、関連するすべてのカウントを集約するか、カバー範囲を証明する候補の境界を維持する必要があります。近似設計ではマージ可能なサマリーを結合できますが、その契約には追加の誤差とレポート遅延を含める必要があります。