問題演習: Insert, delete, contains and getRandom with O(1)

今回は「Insert, delete, contains and getRandom with O(1)」という問題です。この問題ではアルゴリズム力に加えてデータ構造の選び方が問われます。20 ~ 30 分程度で実践的なスキルを判断することができるので、実際に私が面接官として問題を出すときにはこの手の問題を好んで出題します。難易度は「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 つ取り出す。各整数が取り出される確率は一律でなければならない。

解答テンプレート

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

入出力例

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(0): false を返す。
8. getRandom: 2 を返す（この時点では 2 しか保有していない）。

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