問題に適切なデータ構造を選ぶには、どうしますか？

Question

Accepted Answer

**最も頻繁な操作が最も安い**構造を選びます。アクセスパターンに対してです。実行する操作をリストアップし、その頻度を推定してから、構造の強みにマッチさせます。

## 判断チェックリスト

```text
1. How do you access data?  by index -> array
                            by key   -> hash map
                            by order -> tree / heap
2. Need ordering?           sorted   -> balanced BST / sorted array
                            FIFO     -> queue
                            LIFO     -> stack
3. Frequent middle inserts? -> linked list
4. Need fast "seen it?"     -> set / hash map
5. Need "best/min/max next" -> heap (priority queue)
```

## 操作を計算量にマップする

| 必要な操作 | 最適な構造 | キー操作コスト |
|---|---|---|
| インデックスでのランダムアクセス | 動的配列 | O(1) |
| キーでのルックアップ | ハッシュマップ | O(1) avg |
| ソート済み + 範囲クエリ | 平衡二分探索木 | O(log n) |
| 繰り返しMin/Max | ヒープ | O(log n) pop |
| FIFO / LIFO | キュー / スタック | O(1) |
| プレフィックス検索 | トライ木 | O(L) |

## 推論の例

```text
"Find the 10 most frequent words in a huge file."
 - count frequencies  -> hash map (O(1) updates)
 - keep top 10        -> min-heap of size 10 (O(log 10) per word)
```

## なぜ重要なのか

適切に選ぶことは、O(n) とO(n²) ソリューションの違いになることが多いです — パフォーマンスに対する最大のレバーです。

面接官はまさにこの推論をテストします。構造を暗記することではなく、要件を操作コストにマップするプロセスを見たいのです。

インデックスでのランダムアクセス	動的配列	O(1)
キーでのルックアップ	ハッシュマップ	O(1) avg
ソート済み + 範囲クエリ	平衡二分探索木	O(log n)
繰り返しMin/Max	ヒープ	O(log n) pop
FIFO / LIFO	キュー / スタック	O(1)
プレフィックス検索	トライ木	O(L)