シリコンバレー・エンジニアへの道

「 問題演習: Reverse a Singly Linked List 」の解答編です。この問題は単方向リストを逆順に並び替えるという一見すると単純に見える問題ですが、空間計算量を O(1) で処理しなくてはならない点が難易度を上げています。 念のため空間計算量 O(1) という制約について確認しておきましょう。空間計算量 O(1) を換言すると、メモリの使用量は入力に依存することなく、一定でなくてはならないということです。参考までに言及しておくと、リストを複製することはリストの長さを n としたときメモリの使用量は n に依存するので O(n) になってしまいます。 以上を確認した上で、解答を見てみましょう。 解答例 Javaでの解答例です。 解答１） このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 解答２） このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 解説 解答１の解説 この問題の解法は複数存在するのですが、解答１の考え方が一番シンプルだと思います。この解法では、引数として与えられたリストの先頭ノード head から順に後方に向かって走査する際に、各ノードをこれまでに走査したノードの中での先頭のノードにしてしまおうという考え方です。下記に各操作における head と newHead の値について示しました。 初期状態 head は単方向リスト「1 -> 2 -> 3 -> 4 -> 5 -> null」の 1 を指す。 newHead は null 。 ノード 1 が head から newHead に移る。つまり head は 1 の後ろのノードである 2 を指し、newHead が新たなリストの先頭ノードとして 1 を持つ。 head は 単方向リスト「2 -> 3 -> 4 -> 5 -> null」の 2 を指す。 newHead は 単方向リスト「1 -> null」の 1 を指す。 ノード 2 に対して同様の操作を行う。 head は 単方向リスト「3 -> 4 -> 5 -> null」の 3 を指す。 newHea...

今回は「Reverse a Singly Linked List」という問題です。シンプルな問題ですが思考過程で混乱しやすい問題です。難易度は「Medium」です。 問題 単方向リストを逆順にし、返還後のリストの先頭のノードを返せ。ただし、空間計算量は O(1) であること。 解答テンプレート Javaの例を示します。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 入出力例 リストの要素が [1, 2, 3] のとき [3, 2, 1] とし、3 のノードを返す。 それでは、解答と解説は 次の投稿 で。

「 問題演習: Insert, delete, contains and getRandom with O(1)（重複許容版） 」の解答編です。今回の解答は前回の 重複を許容しない場合の解答 と似ているので、解法の大枠はそちらをご覧ください。今回の解説では重複を許容する際に注意すべき点を挙げます。 解答例 Javaでの解答例です。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 解説 重複を許容しない場合との違いは、マップの値がセットであることに加え、insert と delete の実装が変わったことです。contains と getRandom の実装は変わりません。 マップのキーには insert の引数として与えられた整数 n を用い、値にはリスト上でのインデックスが複数格納できるようにセットを値としています。ここでセットを用いているのは、値の入手した順序を記憶しておく必要がないためです。 insert の実装は特に難しいところはありません。重複を許すので、どのような値に対しても追加するだけです。delete ではマップの値であるセットが空になった場合、引数である整数 n は全て削除されたということなので、マップから整数 n のエントリーを削除します。 以上が解説です。前回の重複を許容しない場合を自力で解くことができていれば、今回の問題は簡単に解くことができたと思います。解き方をすぐに思いつくことができるように、繰り返し挑戦しましょう。

前回出題した「 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 の例を示します。各メソッドの中身以外にも、コンストラクタやクラス変数などを定義しても良いです。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧ください。 入出力例 insert(0): true を返す。 insert(1): true を返す。 insert(0): false を返す。 remove(0): true を返す。 insert(2): true を返す。 remove(1): true を返す。 remove(2): true を返す。 getRandom: 0 を返す（この時点では 0 を 2 つ保有している）。 それでは、解答と解説は 次の投稿 で。

「 問題演習: Insert, delete, contains and getRandom with O(1) 」の解答編です。この問題ではデータ構造の選択が非常に重要になります。そこで下記の解説では、正しいデータ構造を選択するにはどのような思考過程を経れば良いかを明示したいと思います。 解答例 Javaでの解答例です。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 解説 まずはクラス内部でどのようにデータを保持すれば、すべての操作を時間計算量 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) を満たしませんでした。一方、配列やリストを使った場合は、無作為に...

今回は「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 の例を示します。各メソッドの中身以外にも、コンストラクタやクラス変数などを定義しても良いです。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 入出力例 insert(0): true を返す。 insert(1): true を返す。 insert(0): false を返す。 remove(0): true を返す。 insert(2): true を返す。 remove(1): true を返す。 remove(0): false を返す。 getRandom: 2 を返す（この時点では 2 しか保有していない）。 それでは、解答と解説は 次の投稿 で。