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

「 問題演習: Fibonacci Sequences 」の解答編です。Web 上でよく見かけるフィボナッチ数列のプログラムは再帰を使っています。今回は再帰を使うことができないという制約を付けて問題を出題しました。 解答例 Javaでの解答例です。 解答例１） このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 解答例２） このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 解説 解答例の解説をする前に、フィボナッチ数列を初めて見た人のために再帰を使ったプログラムを載せておきます。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 解答例１は動的計画法を用いたプログラムです。上記の再帰を使ったプログラムでは、同じ値に対するフィボナッチ数を何度も計算していました。例えば fibonacci(5) を求めるとき fibonacci(4)  +  fibonacci(3) が呼ばれます。このとき fibonacci(4) は fibonacci(3)  +  fibonacci(2) を実行します。この時点で fibonacci(3) が 2 回実行されていることがわかります。1 度だけ実行して解を保存し、再度必要になったときに再利用する方が効率的です。これを実装したのが解答例１になります。 解答例２は a に 1 つ前のフィボナッチ数、b に現在のフィボナッチ数を格納し、n に近づくたびに b には両者の和を入れ、a には前回のフィボナッチ数である b を入れるようにしています。これを n まで繰り返すと b には n 番目のフィボナッチ数が入ります。 他にも数学的な解法などありますので興味ある方はご覧ください。 ウィキべディアへのリンク を貼っておきます。 以上が今回の解説になります。

「 問題演習: Average of each Level in Binary Tree 」の解答編です。問題出題時に述べたように、この問題は本サイトに掲載してきた 2 分木に関する問題「 Max Depth of Binary Tree 」や「 Find Max Element per Level in Binary Tree 」と似ており、解答も非常に似ています。そのため、解答例の細かい解説はそちらの記事を見ていただきたいと思います。今回の解説では問題出題時の最後に記載した "もし数値の 1 つが int 型の最大値だった場合" について解法を紹介したいと思います。 解答例 Javaでの解答例です。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 解説 もし数値の 1 つが int 型の最大値だった場合、1 を足しただけでも int 型の範囲を超えてしまうことによって符号が反転し、負の整数になってしまいます。具体的な数値は下記になります。 Integer.MAX_VALUE = 2147483647 Integer.MAX_VALUE + 1 = -2147483648 今回の問題では、複数の値の平均値を求めるために、複数の数値の和を数値の数で割ろうとしていました。しかし数値に int 型の最大値が含まれていた場合、単純に和を求めようとしても、期待した結果が得ることはできません。 解法は解答例の 20 行目で示したように、全ての和を求めてから割り算するのではなく、各数値を 1 つずつ足していく際に数値の数で割っています。あらかじめ数値の数が分かっているので、このような処理を行うことができます。非常に単純なことですが、実際の面接ではこのような処理を瞬時に思いつくことができなくてはならないので、今回この問題を取り上げました。 以上が今回の解説になります。

「 問題演習: Symmetric Binary Tree 」の解答編です。今回は再帰を用いた解答例と深さ優先探索を用いた解答例の 2 つを用意しました。 解答例 Javaでの解答例です。 解答例１）再帰 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 解答例２）深さ優先探索 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 解説 この問題では両端の枝を根から葉まで下降する際に、枝上の各ノードを順に比較する方法がイメージできると解きやすいと思います。 解答例１では、helper 関数内で 2 つのノードの比較を行い、値が異なった場合は左右対称でないと判断して false を返します。値が同じだった場合は、左ノードの左の子と右のノードの右の子を helper 関数に渡すことによって、両端の枝を下降していることがわかります。そして左ノードの右の子と右のノードの左の子の比較を行えば、1 つ内側の枝を下降するができ、これを繰り返し行うことで全ての枝上にあるノードの左右対称性を調べることができます。 解答例２では、スタックを 2 つ使って深さ優先探索を左右から同時に行っています。各ノードに辿り着く度にノードの値を比較しています。ポイントとしては、子要素をスタックに積むとき、片方のスタックに左の子要素を積んだ場合はもう一方には右の子要素を入れることがです。左右が逆の場合も同様です。このようにすることで、両端のノードから順に左右対称性を調べることができます。 以上が今回の解説になります。

「 問題演習: Longest Palindrome 」の解答編です。今回は直感的で分かりやすい解法と少し最適化を施した解法の 2 種類の解答を用意しました。 解答例 Javaでの解答例です。 解答例１） このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 解答例２） このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 解説 回文は中央の文字以外は左右対称になります。そのため、最長の回文を作るには偶数回存在する文字をすべて左右に振り分け、奇数回存在する文字も左右に振り分けた後に余った 1 つを中央に置けば良いはずです。 解答例１はまず初めに各文字が現れる回数をマップに保存しています。文字が偶数回出現する場合、その文字を全て使うことになるので sum に出現回数 v を足しています。文字が奇数回出現する場合は、その文字は n - 1 回は確実に使うので sum に v - 1 を足しています。そして最後に奇数回出現する文字がある場合は、その文字を中央に置くことができるので sum に 1 を足しています。 ちなみに 8 行目では Java 1.8 で導入された Map インタフェースの getOrDefault メソッドを使用しています。Java 1.7 以前で同様の処理を行うには、下記の記述のように若干長い記述をする必要がありました。記述量が減ることはバグを埋め込む余地も減らせるので、このようなメソッドは積極的に使いましょう。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 解答例１では、初めのループは与えられた文字列の長さ n に依存し、2 つ目のループでは文字の種類数 m に依存しているので時間計算量は O(n+m) です。最悪のケースは与えられた文字の全てが異なる場合であり、m = n となるので時間計算量は O(2n) となります。この解法に対し、少し最適化を行った解答が解答例２になります。 解答例２は、与えられた文字列の長さ n に依存したループを 1 つしか使わないので時間計算量は O(n) となります。この解法では与えられた文字列を先頭から走査するとき、各文字が現れるとセットにその文字を保

「 問題演習: Hamming Weight 」の解答編です。模範解答に加え、Java が提供している便利なメソッドを使った解答を用意しました。 解答例 Javaでの解答例です。 解答例１） このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 解答例２） このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 解説 模範解答である解答例１について解説する前に、解答例２の解法について簡単に述べます。この解法では、以前「 Power of Two の解答と解説 」と「 Hamming Distance の解答と解説 」で紹介した Integer.bitCount(int n) というメソッドを用いています。繰り返しになりますが、このメソッドは整数 n を 2 進数で表現したとき、ビットが 1 となる回数を返します。つまり、このメソッドに整数を渡せばハミング重みが求まります。 解答例１は、整数 n の最下位の 1 ビットを取り出し、それが 1 のときに count をインクリメントしています。そして整数 n を 1 ビットずつ右にづらし、n が 0 になるまで繰り返します。ここまでは特に注意することはありません。 前回の問題出題時に「与えられる整数は正の整数であると問題文に指定されています。左端のビットが 1 である整数は負数をして扱っていないか注意してください。」と述べました。C 言語のように unsigned 修飾子を用いることによって正の整数を宣言することができますが、Java にはそのような修飾子はありません。そのため、特に特別な処理をしなければ Java では左端のビットが 1 の整数は符号あり整数、つまり負の整数になります。今回の問題では、これを符号なし整数、つまり常に正の整数として扱う必要があります。それでは Java でプログラムを記述する際に注意すべき点を 2 点挙げます。 1 つ目の注意点は、整数 n を右にシフトするとき、解答例１のように符号なしシフト演算子 ">>>" を用いることです。符号なしシフト演算子を用いると左端のビットが 1 の整数に対しても、シフト後に左端に 0 が挿入されます。一方、左端

「 問題演習: Add Binary Strings 」の解答編です。この問題のポイントとしては、文字列で表記された 2 進数を最下位のビットから計算する際に桁上げ処理を忘れずに行うことです。それでは解答例を見ていきましょう。 解答例 Javaでの解答例です。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 解説 7 行目で count という int 型の変数を用意しています。この変数は与えられた 2 つの 2 進数を走査するとき、各桁においてビットが 1 となる数を保持します。つまり、 1 つの 2 進数のi 番目の桁が 1 のとき、count に 1 を追加します。もう一方の 2 進数についても同様です。また、2 つの 2 進数の両方とも i - 1 番目の桁が 1 だった場合、i 番目のビットは 1 を加える必要があるため、count に 1 を追加します。 この処理を行うことで、下記のように最終的に求める 2 進数の各桁の値と桁上げ処理の有無を判断することができます。 count=0 のとき、i 番目のビットは 0 となり、桁上げは行わない。 count=1 のとき、i 番目のビットは 1 となり、桁上げは行わない。 count=2 のとき、i 番目のビットは 0 となり、桁上げを行う。 count=3 のとき、i 番目のビットは 1 となり、桁上げを行う。 つまり、count の値が 2 で割り切れるときは i 番目のビットは 0、そうでないときは 1 なので、15 行目のように "count % 2 + '0'" と記述することができます。また、count の値が 2 より大きい時に桁上げを行う必要があります。この処理は 16 行目のように "count /= 2" で行うことができます。 また、最後の桁を走査し終えてループを抜けた後も、最後の桁で桁上げが発生した場合には count の値に 1 が入っているはずです。そのための処理は 18 行目で行っています。 以上が今回の解説になります。

「 問題演習: Reverse Digits of Integer 」の解答編です。今回の解答では 2 つのポイントがありますので、それらを中心に解説します。 解答例 Javaでの解答例です。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 解説 問題出題時に入出力例として 12345 が与えられた場合は 54321 を返し、-12345 が与えられた場合は -54321 を返す必要があることを示しました。この例から分かることは、与えられた整数の正負は桁の反転によって変化することはないということです。整数の処理における正負の違いは混乱を生みやすくバグも入り込みやすいので、避けることが可能ならば積極的に避けましょう。解答例では入力時の整数の符号を初めに記憶しておき、桁の反転を行う際には常に正の整数であると仮定して処理を行います。最後に入力時と同じ正負の符号で出力しています。 また、この問題では反転後の整数が int 型に入らない場合は 0 を返す必要がありました。int 型の範囲に収まるかの判断は "result > Integer.MAX_VALUE / 10" で行うことができます。間違えて "result * 10 > Integer.MAX_VALUE" としてしまうと、左項が int 型の範囲を越えて負数になってしまい、思い通りの計算結果になりませんので注意しましょう。 以上が今回の解説になります。

「 問題演習: Identical Binary Trees 」の解答編です。再帰と深さ優先探索を用いた解答例を示します。 解答例 Javaでの解答例です。 解答例１） このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 解答例２） このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 解説 解答例１は再帰を使い、解答例２は深さ優先探索を使った解法です。 解答例１の再帰を使った解法では、現在のノード n1 と n2 が等しい場合は左右の子要素についても isIdentical() メソッドを呼び出すことで、全てのノードが等しいか調べることができます。解答例２では、2 つのスタックを用いて同時に木構造を下降し、各ノードで 2 つのノードが等しいか調べています。 この問題では再帰を使った方がコードが短く、バグが入り込みにくいのでオススメです。ただし、「 解答と解説: Max Depth of Binary Tree 」でも述べましたが、木の高さが非常に高いと再帰関数（メソッド）呼び出し回数が多くなり、StackOverflowError を引き起こす可能性があります。そのような場合はループを用いて探索を行う必要があります。 問題にメモリ使用量の制約などがある場合は注意しましょう。 以上が今回の解説になります。

「 問題演習: Reverse a String 」の解答編です。解答例を複数載せました。面接で思いついて欲しいのは解答例３ですが、解答例１から順に見ていきましょう。 解答例 Javaでの解答例です。 解答例１） このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 解答例２） このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 解答例３） このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 解答例４） このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 解説 解答例１は、i 番目の文字を文字配列 cs の s.length() - 1 - i  番目に格納しています。この操作を 0 番目の文字列から s.length() - 1 番目まで繰り返すことで、文字配列 cs の中には逆順で文字を並べることができます。 基本的なアイデアは解答例１の方法で良いのですが、ここで気づいて欲しいのは i 番目の文字を文字配列 cs の s.length() - 1 - i  番目に格納ときに、同時に s.length() - 1 - i  番目の文字を cs の i 番目に格納しても良いということです。この操作によって for ループで操作する回数は半分に減らせます。これを実装したのが解答例２になります。 ただし、解答例２では文字列の長さが奇数のとき、真ん中の文字の処理を忘れないでください。解答例２の 12 ~ 14 行目に特殊な処理が入っているのはこのためです。このような特殊な処理は気付けない場合も多く、気付けたとしてもプログラムの記述でバグが入り込みやすいです。可能ならば特殊な処理が存在しないアルゴリズムを選びたいところです。 解答例３は特別な処理が存在せず、ループを回る回数も文字列の長さの半分に抑えることができています。この解法では、i と j の 2 つのインデックスを使って文字列を前後の両方から操作しています。 解答例４は、StringBuilder の reverse() メソッドを使っています。もし知っているならコードの記述量が短くミスが混入しにくいので使いたいと

「 問題演習: 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

「 問題演習: No Adjacent Neighbors 」の解答編です。 解答例 Javaでの解答例です。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 解説 解答例では配列 bs を先頭から順に調べる際、前後と自身が false のときに自身に true を格納しています。true を格納した数だけ count をインクリメントし、配列をすべて調べた後に count の数が整数 n より大きければ、少なくとも n 個の true を置くことができると言えます。 ポイントとしては、配列を先頭から見ていく際に、前後と自身が false だと分かると躊躇なく自身に true を格納している点です。格納できると分かっても、今は格納しない方が後々になって有利になるかもしれないと思うかもしれません。このような疑問を持った際には図などを使って紙やホワイトボードに数パターン書いてみてください。今回の問題では先頭から順に詰めていくので十分です。 以上が今回の解説になります。

「 問題演習: Isomorphic Strings 」の解答編です。今回の解答例には、比較的すぐに思いつきそうなものと、簡単な制約がある場合に思いつきたい解答を載せました。 解答例 Javaでの解答例です。 解答例１） このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 解答例２） このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 解説 この問題は 2 つの文字列に含まれる各文字が 1 対 1 にマッピングできるか否かを調べる問題でした。この問題文からまず思いつくのが、解答例１のようにマップを使った解答です。マップを使って文字列 s1 と s2 で用いられている文字の対応表を作り、１対多もしくは多対１の関係が見つかり次第、調査を終了し false を返しています。 さらっと書きましたが、ここで注意したいことは１対多を調べるだけでなく、多対１も調べなくてはならない点です。例えば 2 つの文字列 "aaaaa" と"abcde" が引数 s1 と s2 として与えられた場合、解答例１では map.containsKey(c1) によって 'a' マップに既に登録されているか調べています。しかしこれだけでは "abcde" と "aaaaa" が引数 s1 と s2 として与えられた場合は重複を発見することができません。そのため map.containsValue(c2) にて 2 つ目の文字列がマップの値として既に登録されていないか調べています。 もし、マップを使うことができないという制約が問題に付け加えられた場合どうしますか。解答例２がそのときの解法になります。解答例２では、長さ 256 の文字配列を 2 つ用意しています。長さを 256 にしているのは、アルファベットや数字を含む ASCII 文字列が 256 文字以内に収まるからです。扱わなくてはならない文字の増減によって、サイズを変える必要があります。 配列には、文字を int 型で表現した整数をインデックスとし、他方の文字列での対応する文字を格納します。つまり、文字列 "abc"

「 問題演習: Lowest Common Ancestor in Binary Search Tree 」の解答編です。この問題は単なる二分木ではなく、二分探索木であることに注目する必要があります。それらの違いについては解説で述べたいと思います。 解答例 Javaでの解答例です。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 解説 単なる二分技は子要素が最大 2 つに別れている木です。二分探索木は二分技が持つ特徴に加え、左の子要素は自身より小さく、右の子要素は自身より大きいという特徴を持っています。前回の記事で問題の入出力例を示す際に例として与えた木は、下記のように二分探索木の特徴を有しています。       4     /   \    2     6   / \   / \  1   3 5   7 今回の問題は、2 つのノードの共通の親ノードのうち葉にもっとも近いものを探すというものでした。二分探索木の特徴を用いると、今回の問題は 3 つの場合を考慮すれば十分であることがわかります。 与えられた 2 つのノードが両方とも現在のノードより小さい時、それらの共通の親で葉にもっとも近いものは、左の子要素以下に存在する。 与えられた 2 つのノードが両方とも現在のノードより大きい時、それらの共通の親で葉にもっとも近いものは、右の子要素以下に存在する。 与えられた 2 つのノードの片方が現在のノードより小さく、もう一方が大きい場合、現在のノードが共通の親でもっとも葉に近いノードである。 解答例に示したプログラムは、上記の 3 つの場合分けを忠実に行い、再帰を用いて葉ノードに向かって順に調べているが分かると思います。 以上が今回の解説になります。

「 問題演習: Hamming Distance 」の解答編です。 解答例 Javaでの解答例です。 解答例１） このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 解答例２） このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 解説 問題文から直感的に思いつくのは、解答例１の方法だと思います。この解法では、x と y から 1 ビットずつ取り出し、XOR（排他的論理和）が 1 になる場合、count に 1 を追加します。これを 1 ビットずつずらし、両方の値が 0 になるまで続けます。ただし、ビットをシフトするときは、シフト後に 0 が挿入される符号なしシフト演算子 ">>>" を使いましょう。左端のビットが 1 のとき、符号ありシフト演算子 ">>" を用いると、シフト後の左のビットには 1 が挿入されてしまい、ループが終わりません。注意しましょう。 類似の解法として、まず初めに x と y の XOR を取得した後に 1 ビットずつ調べる解法も良いと思います。例えば次のようなプログラムになります。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 続いて解答例２ですが、以前「 Power of Two の解答と解説 」で Integer.bitCount(int n) というメソッドが用意されていることを紹介したのを覚えていますでしょうか。このメソッドは整数 n を 2 進数で表現したとき、ビットが 1 となる回数を返します。これを今回の問題で用いるには、まず x と y の XOR を取得した後、Integer.bitCount を用いることでビットが 1 の数を取得することができます。 以上が今回の解説になります。

「 問題演習: Find Max Element per Level in Binary Tree 」の解答編です。 解答例 Javaでの解答例です。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 解説 高さごとの最大値を求める問題なので、同じ高さのノードから順に走査を行う幅優先探索を用いています。以下に解答例での注意点について述べます。 11 行目で Queue インタフェースを実装した LinkedList クラスのインスタンス化を行います。Queue は offer メソッドで要素の追加を行い、poll メソッドで削除と取得を行います。List では add と remove、Stack では push と pop ですので混同しないようにしましょう。 12, 13 行目で root が null でない場合に Queue に追加した後、15 行目からの while 文で Queue の要素がなくなるまでループします。このループ内部の操作は主に次の 2 つの操作に分類できます。 同じ高さの要素を取り出し、最大値を見つける。 同じ高さの要素の左右の子を Queue に追加する。 Queue には次々に要素が追加されていくため、どの要素が同じ高さの要素なのかを区別する必要があります。そこで for ループに入る前の 17 行目で Queue のサイズを取得しています。この値が左右の子要素が追加される前の Queue のサイズ、つまり同じ高さの要素の数になります。このサイズを 18 行目の for ループの終了条件 "i < size" としていますが、"i < q.size()" としない理由は for ループ内で Queue に要素が追加され、子要素も含めたサイズになってしまうからです。 この問題は、前回の「 解答と解説: Max depth of binary tree 」で示した幅優先探索を用いた解答と非常によく似ています。Queue を Stack に置き換えることによって深さ優先探索のプログラムになります。非常に便利はパターンなので覚えてしまいましょう。

「 問題演習: Max Depth of Binary Tree 」の解答編です。2 通りの解答例を用意しました。それぞれの解法について解説します。 解答例 Javaでの解答例です。 １）再帰 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 ２）幅優先探索 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 解説 再帰を用いた解法は、コードの記述量が少なくエラーが混入しにくいので、問題に特に制約が付いていない場合はお薦めの解答です。しかし再帰が使えない場面では幅優先探索の解法がおすすめです。どのような場面で再帰が使えないかわかりますか？ 関数（メソッド）呼び出しをアセンブラ・レベルで見ると、引数や戻り先のアドレスがスタック（メモリ）に積まれます。この処理は関数呼び出しの度に行われるため、際限なく何度も関数を呼び出すとスタックの使用可能量を超えてメモリを確保しようとしてしまいます。このとき、例えば Java では StackOverflowError を引き起こし、プログラムが強制終了してしまいます。つまり木の高さが非常に高く、使用可能なメモリの量が少ない場合は StackOverflowError を引き起こす可能性があります。 この事態を避けるために、幅優先探索での解法が有効です。この解法では何度も関数を呼び出す必要がないため、スタックが溢れることはありません。 この問題が実際に面接で出題された場合でも、再帰が使えない場面について質問されるかはわかりません。もし質問された場合は、上記のように理由と対処法について言及できれば良い評価を得られるでしょう。

「 問題演習: 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) 」の解答編です。この問題ではデータ構造の選択が非常に重要になります。そこで下記の解説では、正しいデータ構造を選択するにはどのような思考過程を経れば良いかを明示したいと思います。 解答例 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) を満たしませんでした。一方、配列やリストを使った場合は、無作為に

「 問題演習: Power of Two 」の解答編です。この問題は様々な解法がありますので、それぞれの解の導き方を見ていきましょう。 解答例 Javaでの解答例です。 解答１） このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 解答２） このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 解答３） このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 解説 2 の累乗は 1, 2, 4, 8, 16, 32... のような数字です。2 の累乗を 2 で割り続けると最後に 1 が残ります。この特徴を利用した解法が解答１になります。問題文から最も直感的に導くことができる解法です。ループを回るごとに n の値は半分になるので、時間計算量は O(logn) です。 解答２では 2 の累乗を 2 進数で表現したとき、1 となるビットが 1 つしか存在しない点に注目しています。例えば、下記の 0 ~ 5 の 10 進数を 2 進数で表現した場合を見ると1, 2, 4 の時は 1 が 1 つしか存在しないことがわかると思います。この特徴を利用してビットが 1 になる回数が 1 つのときに true を返しています。この解法もループを回るごとに n の値は半分になるので、時間計算量は O(logn) です。 0: 0 1: 1 2: 10 3: 11 4: 100 5: 101 解答３は、知らなくても良いですが Java には Integer.bitCount(int n) というメソッドが用意されています。このメソッドは整数 n を 2 進数で表現したとき、ビットが 1 となる回数を返します。解答２で説明したように 2 の累乗はビットが 1 になる回数が 1 回という特徴を利用します。n の値によらずに 1 度で解が求まるので、時間計算量は O(1) です。 解答１と２で示した方法で解ければ問題ないのですが、面接官によっては他の解き方が思いつくか聞いてくることもあります。もちろん思いついた方が良いので、日頃から 1 つの解き方だけでなく、他の解法も探す習慣をつけると良いと思います。 実は他にも

「 問題演習: Pow 」の解答編です。問題出題ページの最後に、下記の 3 点について考えるように提案しました。このような質問は実際の面接時に聞かれますので、これらを考えた上で解答例を見てください。 O(n) より小さい時間計算量で解けますか。 入力が 0 の場合に対応していますか。 負の入力にも対応していますか。 解答例 Javaでの解答例です。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 解説 上記の解答のポイントを順に述べます。 計算量 私の経験からすると下記のようなプログラムを書いた方が多くいると思います。これは n 回 pow メソッドを呼び出すので時間計算量は O(n) です。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 一方、上記の私の解答では一度の処理で処理を半分に減らすことができるので、時間計算量は O(logn) です。logn は 2 を底とする対数です。つまり、一度目に pow メソッドが呼ばれたときに exponent の値を半分にして再度 pow メソッドを呼び出します。次に再度 pow メソッドを呼び出すときに exponent の値はさらに半分になります。 O(logn) は O(n) より小さいので、O(logn) の解答の方が優れています。補足しておくと、exponent が 2 で割り切れない場合は、pow(base, exponent / 2) を計算した後に base を一回だけ掛けることによって、辻褄を合わせています。 入力が 0 のとき 0 の値も忘れずに処理しましょう。exponent が 0 の時の解は常に 1 です。また、base が 0 の時は 0 を返します。 入力が負の値のとき 問題文に負の場合を除く旨が明示されていない限り、負の値も考慮に入れましょう。面接官に口頭で確認すると良いです。むしろこのようなディスカッションが面接の評価対象になりますので、積極的に質問する方が良いです。 係数が負の値の時は、例えば 2 の -3 乗 は 1 /8 ですので、先に正の値の計算結果を計算し 1 で割ります。 （上級者向け）exponent が Inte