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

「 問題演習: 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 番目のフィボナッチ数が入ります。 他にも数学的な解法などありますので興味ある方はご覧ください。 ウィキべディアへのリンク を貼っておきます。 以上が今回の解説になります。

今回は「Fibonacci Sequences」という問題です。日本語で「フィボナッチ数列」というとご存知の方も多く、プログラムを作成したことがある方も多いと思います。実際に面接でフィボナッチ数列を書けという簡単な問題は出題されないと思いますが、問題を掘り下げると実はフィボナッチ数列を書けば解けるような問題があったりします。そのときのために一応解いておきましょう。また、よくあるプログラムは再帰を使う解法ですが、再帰が使えないように制約を加えました。難易度は「Easy」です。 問題 フィボナッチ数列で n 番目の整数を返すプログラムを書け。フィボナッチ数列とは 1, 1, 2, 3, 5, 8, 13, 21... のような数列である。ただし、使用できるメモリの量が少ないため n が大きい場合に再帰を用いて何度も関数呼び出しを行うとスタックオーバーフローが発生してしまう。そのため再帰を使用しない解答を示せ。 解答テンプレート Javaの例を示します。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 入出力例 n = 0 のとき、0 を返す。 n = 1 のとき、1 を返す。 n = 6 のとき、8 を返す。 n = 18 のとき、2584 を返す。 それでは、解答と解説は 次の投稿 で。

「 問題演習: 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 つずつ足していく際に数値の数で割っています。あらかじめ数値の数が分かっているので、このような処理を行うことができます。非常に単純なことですが、実際の面接ではこのような処理を瞬時に思いつくことができなくてはならないので、今回この問題を取り上げました。 以上が今回の解説になります。

今回は「Average of each Level in Binary Tree」という問題です。この問題はこれまでに本サイトに掲載してきた 2 分木に関する問題「 Max Depth of Binary Tree 」や「 Find Max Element per Level in Binary Tree 」と似ているので掲載するか迷ったのですが、1 点だけ注意してほしいことがあったので掲載することにしました。その注意して欲しい点は下記の「解答を見る前に」に記載したので考えてみてください。難易度は「Easy」です。 問題 各ノードに整数値を持つ 2 分木が与えられる。2 分木の深さごとの平均値を求め、リストに入れて返せ。 解答テンプレート Javaの例を示します。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 入出力例 次の 2 分岐が与えられるとする。このとき返すリストは [1, 2.5, 11] である。       1     /   \    2     3   / \   / \  4   5 6   7 解答を見る前に 平均値を求めるとき、数値の和を数値の数で割ります。もし数値の 1 つが int 型の最大値だった場合、1 を足すだけでもオーバーフローを起こし、意図した計算結果が得られません。このような場合、どのような処理をして平均値を求めれば良いでしょうか。 それでは、解答と解説は 次の投稿 で。

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

今回は「Symmetric Binary Tree」という問題です。Symmetric とは左右対称のことです。難易度は「Easy」です。 問題 与えられた 2 分木が左右対称か判定しなさい。 解答テンプレート Javaの例を示します。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 入出力例 この 2 分木は左右対称です。       1     /   \    2     2   / \   / \  3   4 4   3 しかし、次の 2 分木は左右対称ではありません。       1     /   \    2     2   / \   /  3   4 4 次の 2 分木も左右対称ではありません。       1     /   \    2     2     \     \      4     3 それでは、解答と解説は 次の投稿 で。

「 問題演習: 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) となります。この解法では与えられた文字列を先頭から走査するとき、各文字が現れるとセットにその文字を保

今回は「Longest Palindrome」という問題です。難易度は「Easy」です。Palindrome とは回文のことです。前後のどちらから読んでも同じように読める文です。 問題 与えられた文字列から作ることができる回文の最長の長さを求めよ。 解答テンプレート Javaの例を示します。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 入出力例 "abbccdde" から作ることができる最長の回文は "bcdadcb" や "cbdedbc" などである。これらの長さは 7 なので、7 を返す。 それでは、解答と解説は 次の投稿 で。

「 問題演習: 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 が挿入されます。一方、左端

今回は「Hamming Weight」という問題です。日本語ではハミング重みです。以前出題し Hamming Distance  と類似の問題ですが、ビット演算のおさらいも兼ねて挑戦しましょう。難易度は「Easy」です。 問題 与えられた正の整数のハミング重みを返せ。ハミング重みとは整数を 2 進数で表したとき、符号が 1 となるビットの数である。 解答テンプレート Javaの例を示します。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 入出力例 5 が与えられた場合、5 は 2 進数だと 101 なので 2 を返す。 11 が与えられた場合、11 は 2 進数だと 1011 なので 3 を返す。 解答を見る前に 与えられる整数は正の整数であると問題文に指定されています。左端のビットが 1 である整数は負数をして扱っていないか注意してください。 それでは、解答と解説は 次の投稿 で。

「 問題演習: 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 行目で行っています。 以上が今回の解説になります。

今回は「Add Binary Strings」という問題です。難易度は「Easy」です。 問題 2 つの 2 進数が文字列で与えられる。これらの和を 2 進数の文字列で返せ。 解答テンプレート Javaの例を示します。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 入出力例 "1" と "11" が与えられたとき "100" を返す。また、"101" と "111" が与えられたとき "1100" を返す。 それでは、解答と解説は 次の投稿 で。

「 問題演習: 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 型の範囲を越えて負数になってしまい、思い通りの計算結果になりませんので注意しましょう。 以上が今回の解説になります。

今回は「Reverse Digits of Integer」という問題です。難易度は「Easy」です。 問題 与えられた整数の桁を反転せよ。ただし、負数も考慮し、反転後の整数が int 型に入らない場合は 0 を返せ。 解答テンプレート Javaの例を示します。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 入出力例 例えば、12345 が与えられた場合は 54321 を返す。-12345 が与えられた場合は -54321 を返す。 それでは、解答と解説は 次の投稿 で。

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

今回は「Identical Binary Trees」という問題です。難易度は「Easy」です。 問題 2 つの二分木が同一か判定せよ。ただし、木が同一であるとは木の形が同じであり、各ノードが保持する値も同じことである。 解答テンプレート Javaの例を示します。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 入出力例 木の根ノードが 2 つ与えられます。2 つの木が同一なら true を返し、同一でない場合は false を返してください。 それでは、解答と解説は 次の投稿 で。

「 問題演習: 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 String」という問題です。難易度は「Easy」です。非常に単純な問題なので、多くの方が解けると思います。その分、ミスが命取りになるので注意しましょう。 問題 与えられた文字列を反転せよ。 解答テンプレート Javaの例を示します。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 入出力例 "apple" が与えられた場合、"elppa" を返せ。 それでは、解答と解説は 次の投稿 で。

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

今回は「No Adjacent Neighbors」という問題です。難易度は「Easy」です。 問題 1 つの boolean 型の配列 a と 1 つの整数 n が与えられる。配列にはいくつかの true と false が既に格納されており、あと n 個の true を格納できるか調べたい。ただし true の隣には false しか置けない。あと n  個の true を格納できるとき true を返し、格納できないときは false を返せ。 この問題は家や花壇を用いるとイメージしやすいと思います。true を家や花がある状態を指し、false はない状態を指します。家や花が 1 件（本）おきにしか置くことができず、あと n 件（本）置くことができるか調べます。 解答テンプレート Javaの例を示します。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 入出力例 bs = [true, false, false, false, true]、n = 1 のとき true を返す。 bs = [true, false, false, false, true]、n = 2 のとき false を返す。 bs = [false, false, true, false, false]、n = 1 のとき true を返す。 それでは、解答と解説は 次の投稿 で。