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

「 問題演習: 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" を返せ。 それでは、解答と解説は 次の投稿 で。

「 問題演習: 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 のノードを返す。 それでは、解答と解説は 次の投稿 で。

「 問題演習: 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 を返す。 それでは、解答と解説は 次の投稿 で。

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

今回は「Isomorphic Strings」という問題です。この問題も非常に有名な問題です。皆に知られすぎている問題なので、面接には出てこないかもしれません。難易度は「Easy」です。 問題 2 つの文字列が与えられる。片方の文字列に含まれる文字が、もう一方に含まれる文字列に 1 対 1 にマッピングできるか調べよ。ただし、与えられる 2 つの文字列の長さは等しい。 解答テンプレート Javaの例を示します。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 入出力例 出力が true になる例 "aaa" と "xxx" "ccddee" と "lljjvv" "abcde" と "vwxyz" 出力が false になる例 "aaa" と "xyz" "aa" と "ab" "aabcc" と "xxxzz" それでは、解答と解説は 次の投稿 で。

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

今回は「Lowest Common Ancestor in Binary Search Tree」という問題です。難易度は「Easy」です。 問題 2 分探索木の 2 つのノードが与えられる。その 2 つのノードに共通する親ノードのうち、葉にもっとも近いものを返せ。ただし片方のノードが他方の親ノードの場合、その親ノードを共通する親ノードとする。 解答テンプレート Javaの例を示します。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 入出力例 例として次の木を用いる。       4     /   \    2     6   / \   / \  1   3 5   7 例えば、1 と 3 のノードが与えられた場合、共通の親ノードのうち葉にもっとも近いものは 2 なので、2 のノードを返す 2 と 7 の場合は 4 を返す。 5 と 6 の場合は 6 を返す。 それでは、解答と解説は 次の投稿 で。

「 問題演習: 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 の数を取得することができます。 以上が今回の解説になります。

今回は「Hamming Distance」という問題です。日本語ではハミング距離です。大学や高専で情報系の科目を履修していた方は聞いたことがあるかもしれません。ハミング距離の説明と例は下記の問題文と入出力例に記載しました。難易度は「Easy」です。 問題 2 つの正の整数のハミング距離を返せ。ハミング距離とは 2 つの整数を 2 進数で表記したとき、符号が異なるビットの数である。 解答テンプレート Java の例を示します。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 入出力例 例１） 1 と 5 が与えられた場合、1 (001) と 5 (101) は先頭の 1 つの符号が異なるのでハミング距離は 1 である。故に 1 を返す。 例２） 2 と 7 が与えられた場合、2 (010) と 7 (111) は 2 つの符号が異なるのでハミング距離は 2 である。故に 2 を返す。 それでは、解答と解説は 次の投稿 で。

「 問題演習: 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 に置き換えることによって深さ優先探索のプログラムになります。非常に便利はパターンなので覚えてしまいましょう。

今回は「Find Max Element per Level in Binary Tree」という問題です。難易度は「Easy」です。 この問題は、実は 前回の問題の解答例 を作成している際に思い出しました。解法が非常に似ているからです。ヒントになってしまっていますね。。。もし解法がわからない場合は前回の記事を参考にしてください。 問題 2 分木の高さごとの最大値をリストに入れて返せ。 解答テンプレート Java の例を示します。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 入出力例 木構造のルートノードが渡されます。例えば次の木の場合は [1, 3, 4] を返します。       1     /   \    2     3   /  4 次の木の場合は [1, 2, 3] を返します。      1     /    2   /  3 次の木の場合は [1, 3, 6] を返します。       1     /   \    2     3   /     /  \  4     5    6 それでは、解答と解説は 次の投稿 で。

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

今回は「Max Depth of Binary Tree」という問題です。難易度は「Easy」です。 問題 2 分木の高さ（根からの葉までの距離の最大値）を求めよ。 解答テンプレート Java の例を示します。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 入出力例 木構造のルートノードが渡されます。出力には新たな木構造のルートノードを返してください。例えば次の木の高さは 3 です。       1     /   \    2     3   /  4 また、次の木の高さは 1 です。       1 次の木の高さは 3 です。      1     /    2   /  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 しか保有していない）。 それでは、解答と解説は 次の投稿 で。

同僚に日本育ちで日本語がペラペラな外国人がいるのですが、先日彼と話をしている時に、ある日本語の記事が話題になりました。いや、笑い話になりました。 その記事の内容は「シリコンバレーのエンジニアは高給を得られるが、家賃や物価が高いので、貧しい生活をしている」といういう内容でした。ここで話題にしているシリコンバレーの企業とは、有名どころの IT 企業です。Google で「 シリコンバレー エンジニア 年収 」とかのキーワードで調べると、同等の内容の記事が多く存在することがわかります。結構有名なサイトも同様の記事を掲載しています。 シリコンバレーのエンジニアを目指している方が、間違った情報によって就職を断念してほしくないので、今回は私の経験談を元に、実状を正確に示した記事を書きたいと思います。もちろんシリコンバレーにも様々な企業がありますが、今回話題にしているのは有名どころの IT 企業であることを、念のため初めに明示しておきます。 物価が高いから生活は厳しい？ 本ブログの過去の記事「 シリコンバレーのエンジニアの年収 」で 1年目のエンジニアの年収はだいたい 1,600 万円くらい、5 年目では 3,000 万円くらいになることを紹介しました。私個人の経験からすると、年収 1,600 万円としたとき最低限の出費は下記のような感じになります。 税金: 600万円 家賃・光熱費: 360万円 家や車の保険: 10万円 通信費: 10万円 5 年目、年収 3,000 万円ではこんな感じです。 税金: 1,000万円 家賃・光熱費: 360万円 家や車の保険: 10万円 通信費: 10万円 結構手元に残ります。一応、ここでは一般的な出費を憶測しましたが、実際に私が払っている通信費は年間 5 万円、家賃も 300 万円くらいなので、実際はもっと余ってます。残りから食費や旅行費、貯蓄にまわしています。 ただ上記の検索結果で出てくる記事が問題にしているのは、家賃や物価が高いという点でした。これらに関しては「 シリコンバレーの物価と家賃 」に記載しましたが、簡単にまとめると家賃は高いが物価は東京と変わらないか少し高いくらいです。その高さの程度ですが、もちろん各人の生活スタイルに依りますが、収入が上がったら少し良い物件に住んだり、少し贅沢を