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

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