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

今回は「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 点だけ注意してほしいことがあったので掲載することにしました。その注意して欲しい点は下記の「解答を見る前に」に記載したので考えてみてください。難易度は「Easy」です。 問題 各ノードに整数値を持つ 2 分木が与えられる。2 分木の深さごとの平均値を求め、リストに入れて返せ。 解答テンプレート Javaの例を示します。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 入出力例 次の 2 分岐が与えられるとする。このとき返すリストは [1, 2.5, 11] である。       1     /   \    2     3   / \   / \  4   5 6   7 解答を見る前に 平均値を求めるとき、数値の和を数値の数で割ります。もし数値の 1 つが int 型の最大値だった場合、1 を足すだけでもオーバーフローを起こし、意図した計算結果が得られません。このような場合、どのような処理をして平均値を求めれば良いでしょうか。 それでは、解答と解説は 次の投稿 で。

今回は「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」という問題です。難易度は「Easy」です。Palindrome とは回文のことです。前後のどちらから読んでも同じように読める文です。 問題 与えられた文字列から作ることができる回文の最長の長さを求めよ。 解答テンプレート Javaの例を示します。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 入出力例 "abbccdde" から作ることができる最長の回文は "bcdadcb" や "cbdedbc" などである。これらの長さは 7 なので、7 を返す。 それでは、解答と解説は 次の投稿 で。

今回は「Hamming Weight」という問題です。日本語ではハミング重みです。以前出題し Hamming Distance  と類似の問題ですが、ビット演算のおさらいも兼ねて挑戦しましょう。難易度は「Easy」です。 問題 与えられた正の整数のハミング重みを返せ。ハミング重みとは整数を 2 進数で表したとき、符号が 1 となるビットの数である。 解答テンプレート Javaの例を示します。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 入出力例 5 が与えられた場合、5 は 2 進数だと 101 なので 2 を返す。 11 が与えられた場合、11 は 2 進数だと 1011 なので 3 を返す。 解答を見る前に 与えられる整数は正の整数であると問題文に指定されています。左端のビットが 1 である整数は負数をして扱っていないか注意してください。 それでは、解答と解説は 次の投稿 で。

今回は「Add Binary Strings」という問題です。難易度は「Easy」です。 問題 2 つの 2 進数が文字列で与えられる。これらの和を 2 進数の文字列で返せ。 解答テンプレート Javaの例を示します。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 入出力例 "1" と "11" が与えられたとき "100" を返す。また、"101" と "111" が与えられたとき "1100" を返す。 それでは、解答と解説は 次の投稿 で。

今回は「Reverse Digits of Integer」という問題です。難易度は「Easy」です。 問題 与えられた整数の桁を反転せよ。ただし、負数も考慮し、反転後の整数が int 型に入らない場合は 0 を返せ。 解答テンプレート Javaの例を示します。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 入出力例 例えば、12345 が与えられた場合は 54321 を返す。-12345 が与えられた場合は -54321 を返す。 それでは、解答と解説は 次の投稿 で。

今回は「Identical Binary Trees」という問題です。難易度は「Easy」です。 問題 2 つの二分木が同一か判定せよ。ただし、木が同一であるとは木の形が同じであり、各ノードが保持する値も同じことである。 解答テンプレート Javaの例を示します。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 入出力例 木の根ノードが 2 つ与えられます。2 つの木が同一なら true を返し、同一でない場合は false を返してください。 それでは、解答と解説は 次の投稿 で。

今回は「Reverse a String」という問題です。難易度は「Easy」です。非常に単純な問題なので、多くの方が解けると思います。その分、ミスが命取りになるので注意しましょう。 問題 与えられた文字列を反転せよ。 解答テンプレート Javaの例を示します。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 入出力例 "apple" が与えられた場合、"elppa" を返せ。 それでは、解答と解説は 次の投稿 で。

今回は「Reverse a Singly Linked List」という問題です。シンプルな問題ですが思考過程で混乱しやすい問題です。難易度は「Medium」です。 問題 単方向リストを逆順にし、返還後のリストの先頭のノードを返せ。ただし、空間計算量は O(1) であること。 解答テンプレート Javaの例を示します。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 入出力例 リストの要素が [1, 2, 3] のとき [3, 2, 1] とし、3 のノードを返す。 それでは、解答と解説は 次の投稿 で。

今回は「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」という問題です。この問題も非常に有名な問題です。皆に知られすぎている問題なので、面接には出てこないかもしれません。難易度は「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」という問題です。難易度は「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」という問題です。日本語ではハミング距離です。大学や高専で情報系の科目を履修していた方は聞いたことがあるかもしれません。ハミング距離の説明と例は下記の問題文と入出力例に記載しました。難易度は「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」という問題です。難易度は「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」という問題です。難易度は「Easy」です。 問題 2 分木の高さ（根からの葉までの距離の最大値）を求めよ。 解答テンプレート Java の例を示します。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 入出力例 木構造のルートノードが渡されます。出力には新たな木構造のルートノードを返してください。例えば次の木の高さは 3 です。       1     /   \    2     3   /  4 また、次の木の高さは 1 です。       1 次の木の高さは 3 です。      1     /    2   /  3 それでは、解答と解説は 次の投稿 で。

前回出題した「 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)」という問題です。この問題ではアルゴリズム力に加えてデータ構造の選び方が問われます。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 しか保有していない）。 それでは、解答と解説は 次の投稿 で。

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