問題演習: 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の例を示します。


入出力例

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

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

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

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

コメント

コメントを投稿

このブログの人気の投稿

問題演習: Hamming Weight

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

問題演習: Find Max Element per Level in Binary Tree

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