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

「 問題演習: 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 万円くらいなので、実際はもっと余ってます。残りから食費や旅行費、貯蓄にまわしています。 ただ上記の検索結果で出てくる記事が問題にしているのは、家賃や物価が高いという点でした。これらに関しては「 シリコンバレーの物価と家賃 」に記載しましたが、簡単にまとめると家賃は高いが物価は東京と変わらないか少し高いくらいです。その高さの程度ですが、もちろん各人の生活スタイルに依りますが、収入が上がったら少し良い物件に住んだり、少し贅沢を

「 問題演習: 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 つの解き方だけでなく、他の解法も探す習慣をつけると良いと思います。 実は他にも

今回は「Power of Two」という問題です。前回の演習問題「 Pow 」でも説明したように、数学の累乗は英語で power と言います。今回の問題では与えられた整数が 2 の累乗かを判定する関数を作ります。難易度は「Easy」です。 問題 1 つの整数が与えられるので、その整数が 2 の累乗かを判定しなさい。 解答テンプレート Javaの例を示します。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧ください。 入出力例 1 のとき、true（2 の 0 乗は 1 なので true を返す） 2 のとき、true 3 のとき、false 4 のとき、true 5 のとき、false 6 のとき、false それでは、解答と解説は 次の投稿 で。

シリコンバレーの IT 企業でエンジニアとして就職するには、主に次の 5 つの審査を通過する必要があります。企業や職種によっては、電話面接が一度しかなかったり他の審査があるなど多少の差異はありますが、だいたいこれらの 5 つの審査があると心づもりをしておきましょう。 書類審査 電話面接その１ 電話面接その２ 電話面接その３ 現地面接 この記事では、それぞれの審査でどのような試験が行われるかを説明するとともに、採用面接官としての経験を持つ筆者が感覚として得た通過率も記載します。 書類審査 就職の応募は各企業が用意している Web サイトで行います。あらかじめリクルータとコンタクトを取れている場合は、リクルータの指示に従ってください。Email で必要な情報を提出する場合もあれば、Web サイトで入力するように指示される場合もあります。 送られた履歴書は、リクルータによって審査されます。ここでは応募要件を満たしているかのチェックなど簡単な審査が多いです。 書類審査の通過率は 50% くらいだと思います。数字的には半分しか通らない厳しい審査のように思えますが、実際には必要要件を満たしていない応募の足切りです。給与や待遇の良い会社には、要件を満たしていなくてもユニークな自己アピールをして何とか職を得ようとする多くの人が世界中から応募してきます。これら一人一人に対応している時間もないので、足切りが行われます。 電話面接その１ リクルータとの電話面接です。これは実際は審査ではなくて、次のステップであるエンジニアとの電話面接の日程調整だったりします。あと、応募する職種についての相談などができ、変更などもできます。 特に審査が行われる訳ではないので、このステップの通過率は 100% だと思います。 電話面接その２ ここからが本当の審査です。電話、もしくはスカイプなどの会話ツールを使い、エンジニアから出されたアルゴリズムの問題を解きます。時間は1 時間ほどです。難しい問題を 1 問だけ出す出題者もいれば、簡単な問題を数問解かせる出題者もいます。Google Docs や Collabedit などのオンライン・文書共有ツールを用い、エンジニアと会話しながらリアルタイムでプログラムを書く必要があります。 ポイントとし

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

今回は「Pow」という問題です。数学の階乗は英語で power と言うのですが、プログラミング言語の数学関数ライブラリには関数名 pow として実装されていることが多いです。今回の問題は pow 関数を自作させるものなので、問題名を pow としています。難易度は「Easy」としましたが、「Medium」レベルの質問も用意しました。 問題 次の 2 つの引数を持ち、double 型の返り値を持つ階乗関数 pow を実装しなさい。 double base: 基数 int exponent: 係数 解答 テンプレート Javaの例を示します。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧ください。 入出力例 入力 2.00000 3 出力 8.00000 解答を見る前に O(n) より小さい時間計算量で解けますか。 入力が 0 の場合に対応していますか。 負の入力にも対応していますか。 それでは、解答と解説は 次の投稿 で。

「 問題演習: Two Sum 」の解答編です。問題出題ページの最後に、下記の 2 点について考えるように提案しました。このような質問は実際の面接時に聞かれますので、これらを考えた上で解答例を見てください。 ループを 2 つ使った方は、1 つしか使わずに解く方法も考えてください。 ループの数の違いによって、どちらの解法にどのようなメリットがありますか。 解答例 Javaでの解答例です。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 解説 上記の 1 つのループを用いた解法では Map を用いて、現在の値を使用した場合の不足分target - nums[i] をキーとし、現在のインデックス i を値に保存しています。その後ループで i をインクリメントし、他の配列 nums の値が Map のキーに既に登録されていないか確認します。もし既に登録されていた場合は、現在のインデックスと過去の値のインデックスを返せばよいです。時間計算量はループが 1 つなので O(n)、空間計算量は最大でも n - 1 個の値しか Map に保存しないので O(n) になります。 次に 2 つのループを用いた解法も紹介しておきます。おそらくこの問題を初めて見た方は、まずこの解法に辿り着いたと思います。この解法は全探索、つまり全ての値を調べる手法で少々効率が悪いです。例えばこのようなプログラムです。このプログラムの時間計算量は O(n^2) で、特別に何かをメモリに保存する必要はありません。つまり空間計算量は O(1) です。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 ここで計算量の概念を知らない方に、念のため説明しておきましょう。時間計算量とはプログラムの処理数のことで、空間計算量とは記憶領域使用量です。どちらとも小さい方が良いです。計算量は O(1) や O(n)、 O(n^2) という O-記法で表記されます。ざっくり言うと O(n) は n 回の計算で解答を見つけることができるという意味です。O(n) は n の値の増大に対し線形関数的に値が増えますが、下記のように O(n^2) は平方関数的に増加します。一方、O(1) は n の値によって変化するこ

今回は「Two Sum」という問題です。難易度は「Easy」です。とても有名な問題なので既に知っている方が多いと思います。簡単ですが、実際にシリコンバレーの某有名 IT 企業の電話面接で出題されたこともあるので、解法がすぐに思い付くレベルになるまで復習しましょう。 問題 整数の配列 nums と 1 つの整数 target が与えられます。nums に含まれる 2 つ整数の和が target になるとき、その 2 つの整数の位置を返しなさい。ただし、target になる和が複数存在する場合は 1 組だけ返せばよく、存在しない場合は null を返しなさい。 解答テンプレート Javaの例を示します。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 入出力例 入力 nums = [2, 7, 11, 15] target = 9 出力 [0, 1] 解答を見る前に ループを 2 つ使った方は、1 つしか使わずに解く方法も考えてください。 ループの数の違いによって、どちらの解法にどのようなメリットがありますか。 それでは、解答と解説は 次の投稿 で。

過去の記事「 シリコンバレーのエンジニアの年収 」でシリコンバレーで働いたときにもらえる給料の話をしました。収入の話だけではなく出費の話もした方が、こちらでの生活を想像しやすいと思います。そこで今回はシリコンバレーでの物価と、特に大きな出費となる家賃について言及します。 物価 物価に関しては、日本よりは少々高いかもしれません。高いというよりは、日本のように安くて良質なものがないので、許容できる質のものを買うとなると、結果的に出費は多くなるといった方が正しいかもしれません。 特に食品に関しては、日本との差が大きく感じられます。例えば、日本だと 500 円あれば、結構美味しいものを食べられますよね。昼時にはランチメニューがあったり、コストパフォーマンスは非常に良いです。しかしこちらで 500 円相当のランチってなかなか無くて、あったとしても衛生面に不安があったり、味が凄まじかったりします。普通レベルの食事をしようと思ったら、最低でも 10 ドルは払うことになります。さらに、レストランだと 18% のチップを払います。 食品以外では、日本とそこまで変わらないと思います。私が日本に住んでいたときは東京都内に住んでいたのですが、都内と比べて特に高いと感じることはないです。 家賃 家賃に関しては、サンフランシスコ市内は高いです。安くても月 40 万円くらいするので、どうしてもシティに住みたい若者たちはルームシェアをするのが一般的です。もちろん探せば月 30 万円のアパートを見つけることもできますが、一般的な価格として 40 万円といったところでしょう。新興企業はサンフランシスコ市内に多く、市街から電車で通う人も多いです。 Google や Facebook、Apple などのシリコンバレーの有名 IT 企業はサンフランシスコから車で1時間ほど南下した地域にオフィスを構えています。Mountain View や Palo Alto、Cupertino といった地域になります。その辺だと、1ベットルームは月 25 万円、2ベットルームだと月 30 万円が目安となります。私はこのエリアに住んでおり、家賃は 22 万円程度です。 ただし、近年この地域での家賃が高騰しています。私が以前住んだアパートは毎年家賃が 7% 上がりました。3 年目の契約更新時に他

「 問題演習: Invert a Binary Tree 」の解答編です。 解答例 Javaでの解答例です。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 解説 ルートノードの位置は変わらず、左右の子ノードを入れ替える問題です。同様の処理を葉ノードまで実行すれば良いです。つまり再帰を使うと簡単に解けます。 最初に与えられるルートノードが null の可能性があるので、初めに調べておきます。ここで null チェックをしているので、その後 solve メソッドを呼ぶ前に null をチェックする必要はありません。solve メソッドに子ノードを投げてしまいましょう。余計なコードを減らすことで間違いが混入する可能性を減らすことも大事です。 この問題で一番大事なのは、余計なメモリを使用しないことです。例えば、新しい木構造を作る際に各ノードを複製し、最終的に木が 2 つできてしまう解法は好ましくないです。特に IT 企業の場合は、余計なメモリを使用することで処理が遅くなり、それが計算コストを高くすることで出費が多くなります。そのような無駄なコストは避けたいので、不要なメモリの利用や余計な計算はしないように工夫しましょう。

今回は 「Invert a Binary Tree」という問題です。難易度は「Easy」です。 この問題はかつて Google の採用面接で使われていました。Mac OS 上でのパッケージ管理システム「Homebrew」の開発者が Google の面接を受けた時に出題された事でも有名です。彼は解くことができず、こんなツイートをしていました。 Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off. — Max Howell (@mxcl) June 10, 2015 問題 A の二分木を B のように変換しなさい。ただし、メモリの使用量が最小になるように工夫すること。 A)       1     /   \    2     3  /  \   /  \ 4   5  6    7 B)       1     /   \    3     2  /  \   /  \ 7   6  5    4 解答テンプレート Javaの例を示します。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧ください。 入出力例 木構造のルートノードが渡されます。出力には新たな木構造のルートノードを返してください。 解答と解説は、 次の投稿 で。

「 問題演習: FizzBuzz 」の解答編です。 解答例 Javaでの解答例です。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 解説 シンプルに1からnまで昇順にループを使って 1つ1つ値を評価しましょう。まず、値が "Fizz" か "Buzz" に該当するかを見極め、そうでなければ現在のiの値をそのまま文字列として格納してしまえば OK です。 問題出題時にも記載しましたが、この問題は特に工夫できる点がなく、間違いやすい点もありません。このような問題は、面接官がツッコミ難いので、実際に面接に使用されることはないでしょう。ただし、間違えてしまった場合には復習し、解法を身につけるようにしましょう。

有名な FizzBuzz の問題です。難易度は「Easy」です。面接時に出される質問には、多くの場合、ミスしやすいポイントとかエッジケースが存在します。しかし、この FizzBuzz 問題は特に工夫することもなく間違いやすい点も特にないので、面接には出ないでしょう。軽いウォーミングアップのつもりで解いてください。 問題 1からnまでの数字を次の規則にそって出力しなさい。 3の倍数のとき、"Fizz" 5の倍数のとき、"Buzz" 3と5の倍数のとき、"FizzBuzz"。 解答テンプレート Javaの例を示します。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧ください。 入出力例 n=2のとき、戻り値は「"1", "2"」。 n=3のとき、戻り値は「"1", "2", "Fizz"」。 n=15のとき、戻り値は「"1", "2", "Fizz", "4", "Buzz", "Fizz", "7", "8", "Fizz", "Buzz", "11", "Fizz", "13", "14", "FizzBuzz"」。 解答と解説は こちら 。

シリコンバレーの有名 IT 企業に勤めたときにもらえる、お金の話をしましょう。 これまで私の同僚や他企業の友人など、様々な役職の方と収入について時折話す機会がありました。そこで、彼らから得られた情報と私の経験から、シリコンバレーの有名 IT 企業に勤めたときに得ることができる年収を見積もります。ただし私を含め友人たちは大体 2 年くらいで昇進し、5 年も同じ企業に勤めている人は少なく、5 年のうち 1 度は転職している人が多いです。 もちろん役職だけでなく個々の経験や実績によって額は異なりますが、基本的な給与に加え、株やボーナスを含めた年間でもらえる総額としては、大まかに下記のように見積もることができました。 1年目、$160,000 (1,600万円くらい) 2年目、$190,000 (1,900万円くらい) 3年目、$220,000 (2,200万円くらい) 4年目、$260,000 (2,600万円くらい) 5年目、$300,000 (3,000万円くらい) 大卒の1年目で $240,000 ももらっている人もいました。内訳は大体下記のような感じです。 給与: 年間総額の 3 分の 2 弱 ボーナス: 給与の 5 ~ 15% RSU または ストックオプション: 年間総額の 3 分の 1 弱 ESPP: 年間総額の 1 ~ 5% 追記） 上記では毎年給与が 1 ~ 2 割近く上がっています。これも会社や個人の業績によって異なってしまうので一般化できないかもしれませんが、知人から得た情報や私の経験からすると、半年や 1 年ごとに行われる契約更新の際に RSU が追加贈与されることによって、年収が順調に増加していきます。 例えば、初回の基本給を $120,000 として毎年 10% アップするとします。理由としては、個人の努力だけでなく企業の業績によっても年収上昇率が変わるのですが、だいたい 5 ~ 15% 上がっているようなので平均の 10% としました。ボーナスは初めは 7%、2 年ごとの昇進で 3% 上がるとします。つまりボーナスは 3 年目に 10%、5 年目で 13%とします。そして初回の RSU $120,000 分を 4 年で満期とし、2 ~ 4 年目に新たに RSU $60,000 分を 4

本ブログの初投稿なので、ざっくりですが自己紹介をします。 略歴 私は現在シリコンバレーの某有名IT企業でエンジニアとして働き（2017 年時点で）5 年目になります。 生まれも育ちも日本で、日本の大学と大学院で情報工学を学びました。大学の授業でプログラミング演習で楽しさを見出していたこともあり、当時から将来の自分像としてエンジニアを思い浮かべていました。 学生時代には「シリコンバレーのIT企業ではエンジニアへの待遇が格別に良い」、「日本のエンジニアの給料の 3、4 倍もらえる」という噂を耳にし、シリコンバレーへの憧れを漠然と抱いていました。また、それほど待遇が良いなら当然ですが「入社試験が非常に難しく、世界レベルで超優秀なエンジニアでないと入社できない」という話も聞いており、自分がそのレベルに達している訳がなく、ただただ憧れるばかりでした。 卒業後に一度日本の企業でエンジニアとして働いたものの、自分がこれまで見聞きしてきたシリコンバレーのエンジニアとのギャップを目の当たりにし、愕然としました。特に給与の低さや残業などの仕事のあり方が挙げられます。 その頃からシリコンバレーのIT企業でエンジニアとして働くには、具体的に何が必要かを調べ、自分に不足している技術や知識を勉強し始めました。その甲斐あって、日本にいながらシリコンバレーの IT 企業の面接に臨み、晴れて入社することができました。 具体的にどのような知識や技術が必要か、どのような勉強をすればよいかについては、このブログで詳細に記述したいと思います。 主な仕事内容 先に挙げたように、私は現在シリコンバレーの某有名 IT 企業で働いています。仕事内容としてはプログラミングはもちろんのこと、システムのデザインやレビューを行ったり、採用面接での面接官として候補者に問題を出したりしています。 本サイト開設にあたって アメリカを含め世界には、シリコンバレーの IT 企業で働くことを目指し、日々奮闘している方々が大勢います。彼らに参考になる書籍や Web サイトも多々あり、彼らはそれらを自分で見つけ、勉強しています。 ただ日本では、シリコンバレーで働くことによって得られるメリットが一般的に認識されておらず、かつそれを理解した方々でも実際にシリコンバレーの