Google Interview: 1TBテキストファイルの単語検索API設計

問題¶

1TBのテキストファイルがディスクに保存されている。単語を入力すると、そのファイル中の出現回数を返すAPIを設計せよ。

ナイーブな解答（ダメな例）¶

# 毎回ファイルを全文スキャンする → 1TBを読むのに数時間かかる
def count_word(word: str) -> int:
    count = 0
    with open("huge_file.txt") as f:
        for line in f:
            count += line.split().count(word)
    return count

→ レイテンシが話にならない。これを言うと面接では落とされる。

前処理: インデックスを作る¶

ポイントは 「クエリ時に1TBを走査するな、事前に転置インデックスを作れ」。

転置インデックスとは¶

元ファイル:
  "the quick brown fox jumps over the lazy dog"

転置インデックス:
  "the"   → 2
  "quick" → 1
  "brown" → 1
  "fox"   → 1
  ...

単語をキーに、出現回数（または出現位置のリスト）を値とするマップ。

構築方法: 分散処理（MapReduce的アプローチ）¶

1TBファイル
    ↓ 分割
チャンク1(100MB) チャンク2(100MB) ... チャンク10(100MB)
    ↓ 各ワーカーで並列処理
Worker1: {"the":150, "fox":30, ...}
Worker2: {"the":200, "fox":15, ...}
    ↓ Reduceでマージ
最終インデックス: {"the":350, "fox":45, ...}
    ↓ 永続化
Key-Value Store（Redis / DynamoDB / BigQuery）

APIの設計¶

エンドポイント¶

GET /words/{word}/count

レスポンス¶

{
  "word": "fox",
  "count": 45,
  "last_indexed_at": "2026-05-01T12:00:00Z"
}

実装（インデックスが作成済みの場合）¶

def count_word(word: str) -> int:
    # O(1)でRedisから取得
    count = redis.get(f"word:{word.lower()}")
    return int(count) if count else 0

ファイルが更新される場合¶

差分更新の戦略を議論する。

バッチ再構築: 1日1回全体を再インデックス（シンプルだが遅延あり）
差分追記: 更新部分だけを処理してカウントを加算（複雑だが鮮度が高い）
ストリーミング処理: ファイル変更をKafkaに流してリアルタイム更新

面接でのポイント¶

ナイーブ解 → 問題点 → 改善 の順で話す（いきなり最適解を言わない）
インデックスを作るアイデアを自力で出せるか
ファイル更新への対応を聞かれたら差分更新の話をする
レイテンシ要件（リアルタイム？バッチでOK？）を面接官に確認する
1TBを分割して並列処理するスケールの話ができるか

計算¶

1TB = 約1兆バイト
英語テキストの平均単語長 ≈ 5文字、スペース1文字で6バイト/単語
1TB ÷ 6 ≈ 約1,700億単語
ユニーク単語数は英語で約17万語程度
インデックス: 17万 × (単語の平均長5byte + count8byte) ≈ 数MB（非常に小さい）