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

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

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

「 問題演習: 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 つしか使わずに解く方法も考えてください。 ループの数の違いによって、どちらの解法にどのようなメリットがありますか。 それでは、解答と解説は 次の投稿 で。

「 問題演習: 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"」。 解答と解説は こちら 。