特定の O(1)/O(log n) 要件を持つデータ構造をどのように設計しますか?

Question

Accepted Answer

カスタム構造の設計は、**既存の構造を組み合わせる**ことを意味します。そうすることで、必要な各操作がその目標計算量に到達し、1つの構造が別の構造の弱点をカバーできます。古典的な手法は、**ハッシュマップ**を**配列、ヒープ、または連結リスト**と組み合わせることです。

## 実践例：insert、delete、getRandom — すべて O(1)

要件: `insert(x)`、`remove(x)`、`getRandom()` のそれぞれが O(1)。ハッシュマップだけでは O(1) のランダムアクセスができません。配列だけでは O(1) の削除ができません。**両者を組み合わせましょう**。

```python
import random
class RandomizedSet:
    def __init__(self):
        self.idx = {}      # value -> index in list
        self.vals = []     # values for O(1) random pick
    def insert(self, x):                    # O(1)
        if x in self.idx: return False
        self.idx[x] = len(self.vals)
        self.vals.append(x)
        return True
    def remove(self, x):                    # O(1): swap with last, pop
        if x not in self.idx: return False
        i, last = self.idx[x], self.vals[-1]
        self.vals[i] = last                 # move last into the hole
        self.idx[last] = i
        self.vals.pop()
        del self.idx[x]
        return True
    def getRandom(self):                    # O(1)
        return random.choice(self.vals)
```

## 一般的な設計レシピ

```text
1. List every required operation + its target complexity.
2. For each, name a structure that hits it:
     by key O(1)      -> hash map
     by index O(1)    -> array
     min/max O(log n) -> heap
     ordered O(log n) -> balanced tree / skip list
     O(1) splice      -> doubly linked list
3. COMBINE them; use the hash map to map keys -> positions/nodes
   in the other structure so updates stay O(1).
4. Verify each operation against its target.
```

| パターン | 組み合わせた構造 | 実現できること |
|---|---|---|
| LRU cache | ハッシュマップ + 双方向連結リスト | O(1) get/put |
| O(1) randomized set | ハッシュマップ + 配列 | O(1) insert/remove/random |
| Min in O(1) on a stack | スタック + 補助的な最小値スタック | O(1) getMin |

## なぜ重要なのか

実際のシステムが必要とするのは、単一の教科書的な構造ではなく、特定のアクセスパターンに調整された複合構造です。これがまさにこれらの設計が提供するものです。

インタビュアーがこれらの問題を使用するのは、**操作のコストから合成へと推論できるか**、高性能なシステム設計の背後にある中核的なスキルをテストするためです。

パターン	組み合わせた構造	実現できること
LRU cache	ハッシュマップ + 双方向連結リスト	O(1) get/put
O(1) randomized set	ハッシュマップ + 配列	O(1) insert/remove/random
Min in O(1) on a stack	スタック + 補助的な最小値スタック	O(1) getMin