解答と解説: Insert, delete, contains and getRandom with O(1)

「問題演習: Insert, delete, contains and getRandom with O(1)」の解答編です。この問題ではデータ構造の選択が非常に重要になります。そこで下記の解説では、正しいデータ構造を選択するにはどのような思考過程を経れば良いかを明示したいと思います。

解答例

Javaでの解答例です。

	public class Solution {
	private List<Integer> list;
	private Map<Integer, Integer> map; // key=n, value=index in the list
	private Random random = new Random();
	public Solution() {
	list = new ArrayList<>();
	map = new HashMap<>();
	}
	public boolean insert(int n) {
	if (map.containsKey(n)) {
	return false;
	}
	map.put(n, list.size());
	list.add(n);
	return true;
	}
	public boolean delete(int n) {
	if (!map.containsKey(n)) {
	return false;
	}
	int index = map.remove(n);
	if (index < list.size() - 1) {
	int lastVal = list.get(list.size() - 1);
	list.set(index, lastVal);
	map.put(lastVal, index);
	}
	list.remove(list.size() - 1);
	return true;
	}
	public boolean contains(int n) {
	return map.containsKey(n);
	}
	public int getRandom() {
	int n = random.nextInt(list.size());
	return list.get(n);
	}
	}

view raw answer-insert-delete-contains-and-getrandom-with-o1.java hosted with ❤ by GitHub

解説

まずはクラス内部でどのようにデータを保持すれば、すべての操作を時間計算量 O(1) で処理できるか考えます。その後、細かい注意点について言及します。

配列 or リスト

配列やリストを使用した場合、insert は引数で与えられた整数を末尾に追加すれば良いので時間計算量は O(1) となり、getRandom も無作為に生成したインデックスに格納されている値を取得することで O(1) で操作を行うことができます。しかし delete や contains では引数として与えられてた整数を探索しなくてはいけません。これは O(n) の操作です。

セット or マップ

時間計算量 O(1) と聞いて HashSet を思い浮かべた方が多いと思います。たしかに HashSet を使えば insert、delete、contains の 3 つの処理は時間計算量 O(1) で行うことができますが、getRandom ではそうはいきません。HashSet のインスタンスを set としたとき、set.iterator().next() で要素を 1 つ取得することができますが、ここで取得できる要素は無作為（ランダム）ではありません。next() で取得できる順序は入力の順序と異なるものの、一意に定まってしまうからです。

マップの使用を考えた方は、おそらく insert の引数 n をキーに用いることを想定していると思いますが、値には何を入れると良いでしょうか。もし思い当たらず適当な値を入れてしまっている場合は、セットを用いた場合と同じく getRandom で躓いてしまいます。

組み合わせ

セットを使用した場合は getRandom が時間計算量 O(1) を満たしませんでした。一方、配列やリストを使った場合は、無作為に生成したインデックスに格納されている値を取得することで getRandom を O(1) で操作を行うことができていました。上手く組み合わせることができないでしょうか。

セットとリスト（または配列）を同時に使用した場合、両者に格納されているデータは同期していなくてはなりません。insert の処理では単純に両者とも O(1) で値の追加を行うことができます。しかしリストの delete の処理では、先述の通り時間計算量 O(n) の探索が必要となってしまいます。これを O(1) で行う必要があります。

リストでは削除する場所（インデックス）さえ分かって入れば O(1) で処理することができます。そこでマップを用いて整数をキーとし、その整数がリスト上で保存されている場所（インデックス）を値として記憶します。こうすることで、下記のように 4 つの操作を O(1) で行うことができるようになります。

• insert: 整数 n をリストの最後に追加する。マップに整数 n とリスト上でのインデックスを保存する。
• delete: マップから整数 n に対応する値（つまりリスト上でのインデックス）を使い、リストからエントリーを削除する。また整数 n を使いマップからエントリーを削除する。
• contains: マップのキーに整数 n が登録されているか調べる。
• getRandom: 無作為にインデックスを生成し、そのインデックスに格納されている値をリストから返す。

削除処理での注意

リストから要素を削除した場合、後方に格納されている値の位置は変わってしまいます。例えば、インデックス 2 に登録されている 20 を削除する場合を考えます。

1. 10
2. 20 <- これを削除
3. 30
4. 40
5. 50

削除後のリストは、インデックス 2 以降の値が前方に来てしまいます。

1. 10
2. 30
3. 40
4. 50

この変化に合わせて、マップの情報も更新しなくてはなりません。つまり、リストからインデックス 2 以降の値 (30, 40, 50) を取得し、それらのインデックスの値をマップ上で -1 する必要があります。これは削除する場所に依存する時間計算量が必要となり、最悪のケースでは n - 1 個のインデックスを -1 する必要があります。つまり時間計算量は O(n) です。

これを避けるために、上記の私の解答例では工夫をしています。インデックス 2 に最後尾の値をコピーします。

1. 10
2. 50 <- 最後尾の値をコピーする。
3. 30 
4. 40
5. 50

そして最後尾を削除します。

1. 10
2. 50
3. 30
4. 40

この方法では、インデックス 2 以外の値が変化していません。後処理としては、マップから 50 がキーとして登録されている値（つまりインデックス）を 2 で上書きするだけです。


以上が解説になります。少々長くなってしまいましたが、実際の面接ではこのような思考の過程を話しながら問題を解くことが大事なので、細かく書きました。面接では、この問題を解けた候補者には「値の重複を許容する場合、どのように実装するか」という質問を口頭ですることもあります。ぜひ考えてみてください。
---
シリコンバレーでエンジニアとして就職するには、アルゴリズムやプログラミング、システムデザインの問題が出題される面接を突破する必要があります。本サイトでは、シリコンバレーでエンジニアとして働き、面接官としての経験も豊富な筆者が、面接への対策に関する情報を配信しています。