問題演習: Insert, delete, contains and getRandom with O(1) （重複許容版）

前回出題した「Insert, delete, contains and getRandom with O(1)」では同じ値を複数保存する必要はありませんでした。しかし解答と解説記事での末尾に「値の重複を許容する場合、どのように実装するか」という質問をしました。今回はこの重複を許容する場合の実装について考えたいと思います。難易度は「Medium」です。

問題

次の 4 つのメソッドを持つクラスを実装しなさい。ただし、格納するデータは重複を考慮し、全てのメソッドは時間計算量 O(1) を超えてはならない。重複を考慮するとは、同じ値を複数回保存でき、また同数回削除を行うことができることである。

• boolean insert(int n): n を保有しない場合は n を格納し true を返す。既に保有している場合は false を返す。
• boolean delete(int n): n を保有している場合は n を削除し true を返す。まだ保有していない場合は false を返す。
• boolean contains(int n): n を保有している場合は true を返し、保有しない場合は false を返す。
• int getRandom(): 保有している整数の中から無作為に 1 つ取り出す。各整数が取り出される確率は重複を考慮した上で一律でなければならない。つまり確率は 1 / (保存している整数の数) である。

解答テンプレート

Java の例を示します。各メソッドの中身以外にも、コンストラクタやクラス変数などを定義しても良いです。

	public class Solution {
	// You can add constructors and class variables.
	public boolean insert(int n) {
	// Write your code here.
	}
	public boolean delete(int n) {
	// Write your code here.
	}
	public boolean contains(int n) {
	// Write your code here.
	}
	public int getRandom() {
	// Write your code here.
	}
	}

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

入出力例

1. insert(0): true を返す。
2. insert(1): true を返す。
3. insert(0): false を返す。
4. remove(0): true を返す。
5. insert(2): true を返す。
6. remove(1): true を返す。
7. remove(2): true を返す。
8. getRandom: 0 を返す（この時点では 0 を 2 つ保有している）。

それでは、解答と解説は次の投稿で。
---
シリコンバレーでエンジニアとして就職するには、アルゴリズムやプログラミング、システムデザインの問題が出題される面接を突破する必要があります。本サイトでは、シリコンバレーでエンジニアとして働き、面接官としての経験も豊富な筆者が、面接への対策に関する情報を配信しています。