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

「 問題演習: 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 の値によって変化するこ

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

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