問題演習: Invert a Binary Tree

投稿者:
今回は 「Invert a Binary Tree」という問題です。難易度は「Easy」です。

この問題はかつて Google の採用面接で使われていました。Mac OS 上でのパッケージ管理システム「Homebrew」の開発者が Google の面接を受けた時に出題された事でも有名です。彼は解くことができず、こんなツイートをしていました。


問題

A の二分木を B のように変換しなさい。ただし、メモリの使用量が最小になるように工夫すること。

A)
      1
    /   \
   2     3
 /  \   /  \
4   5  6    7

B)
      1
    /   \
   3     2
 /  \   /  \
7   6  5    4

解答テンプレート

Javaの例を示します。


入出力例

木構造のルートノードが渡されます。出力には新たな木構造のルートノードを返してください。

解答と解説は、次の投稿で。

---
シリコンバレーでエンジニアとして就職するには、アルゴリズムやプログラミング、システムデザインの問題が出題される面接を突破する必要があります。本サイトでは、シリコンバレーでエンジニアとして働き、面接官としての経験も豊富な筆者が、面接への対策に関する情報を配信しています。

このエントリーをはてなブックマークに追加

コメント

コメントを投稿

このブログの人気の投稿

解答と解説: Fibonacci Sequences

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

投稿者:
今回は「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 を返す。 それでは、解答と解説は 次の投稿 で。
続きを読む

問題演習: No Adjacent Neighbors

投稿者:
今回は「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 を返す。 それでは、解答と解説は 次の投稿 で。
続きを読む