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

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

「 問題演習: Insert, delete, contains and getRandom with O(1)（重複許容版） 」の解答編です。今回の解答は前回の 重複を許容しない場合の解答 と似ているので、解法の大枠はそちらをご覧ください。今回の解説では重複を許容する際に注意すべき点を挙げます。 解答例 Javaでの解答例です。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 解説 重複を許容しない場合との違いは、マップの値がセットであることに加え、insert と delete の実装が変わったことです。contains と getRandom の実装は変わりません。 マップのキーには insert の引数として与えられた整数 n を用い、値にはリスト上でのインデックスが複数格納できるようにセットを値としています。ここでセットを用いているのは、値の入手した順序を記憶しておく必要がないためです。 insert の実装は特に難しいところはありません。重複を許すので、どのような値に対しても追加するだけです。delete ではマップの値であるセットが空になった場合、引数である整数 n は全て削除されたということなので、マップから整数 n のエントリーを削除します。 以上が解説です。前回の重複を許容しない場合を自力で解くことができていれば、今回の問題は簡単に解くことができたと思います。解き方をすぐに思いつくことができるように、繰り返し挑戦しましょう。

前回出題した「 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) 」の解答編です。この問題ではデータ構造の選択が非常に重要になります。そこで下記の解説では、正しいデータ構造を選択するにはどのような思考過程を経れば良いかを明示したいと思います。 解答例 Javaでの解答例です。 このプログラムはJavaScriptで読み込みます。Webブラウザで閲覧してください。 解説 まずはクラス内部でどのようにデータを保持すれば、すべての操作を時間計算量 O(1) で処理できるか考えます。その後、細かい注意点について言及します。 配列 or リスト 配列やリストを使用した場合、insert は引数で与えられた整数を末尾に追加すれば良いので時間計算量は O(1) となり、getRandom も無作為に生成したインデックスに格納されている値を取得することで O(1) で操作を行うことができます。しかし delete や contains では引数として与えられてた整数を探索しなくてはいけません。これは O(n) の操作です。 セット or マップ 時間計算量 O(1) と聞いて HashSet を思い浮かべた方が多いと思います。たしかに HashSet を使えば insert、delete、contains の 3 つの処理は時間計算量 O(1) で行うことができますが、getRandom ではそうはいきません。HashSet のインスタンスを set としたとき、set.iterator().next() で要素を 1 つ取得することができますが、ここで取得できる要素は無作為（ランダム）ではありません。next() で取得できる順序は入力の順序と異なるものの、一意に定まってしまうからです。 マップの使用を考えた方は、おそらく insert の引数 n をキーに用いることを想定していると思いますが、値には何を入れると良いでしょうか。もし思い当たらず適当な値を入れてしまっている場合は、セットを用いた場合と同じく getRandom で躓いてしまいます。 組み合わせ セットを使用した場合は getRandom が時間計算量 O(1) を満たしませんでした。一方、配列やリストを使った場合は、無作為に...

今回は「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 しか保有していない）。 それでは、解答と解説は 次の投稿 で。

同僚に日本育ちで日本語がペラペラな外国人がいるのですが、先日彼と話をしている時に、ある日本語の記事が話題になりました。いや、笑い話になりました。 その記事の内容は「シリコンバレーのエンジニアは高給を得られるが、家賃や物価が高いので、貧しい生活をしている」といういう内容でした。ここで話題にしているシリコンバレーの企業とは、有名どころの IT 企業です。Google で「 シリコンバレー エンジニア 年収 」とかのキーワードで調べると、同等の内容の記事が多く存在することがわかります。結構有名なサイトも同様の記事を掲載しています。 シリコンバレーのエンジニアを目指している方が、間違った情報によって就職を断念してほしくないので、今回は私の経験談を元に、実状を正確に示した記事を書きたいと思います。もちろんシリコンバレーにも様々な企業がありますが、今回話題にしているのは有名どころの IT 企業であることを、念のため初めに明示しておきます。 物価が高いから生活は厳しい？ 本ブログの過去の記事「 シリコンバレーのエンジニアの年収 」で 1年目のエンジニアの年収はだいたい 1,600 万円くらい、5 年目では 3,000 万円くらいになることを紹介しました。私個人の経験からすると、年収 1,600 万円としたとき最低限の出費は下記のような感じになります。 税金: 600万円 家賃・光熱費: 360万円 家や車の保険: 10万円 通信費: 10万円 5 年目、年収 3,000 万円ではこんな感じです。 税金: 1,000万円 家賃・光熱費: 360万円 家や車の保険: 10万円 通信費: 10万円 結構手元に残ります。一応、ここでは一般的な出費を憶測しましたが、実際に私が払っている通信費は年間 5 万円、家賃も 300 万円くらいなので、実際はもっと余ってます。残りから食費や旅行費、貯蓄にまわしています。 ただ上記の検索結果で出てくる記事が問題にしているのは、家賃や物価が高いという点でした。これらに関しては「 シリコンバレーの物価と家賃 」に記載しましたが、簡単にまとめると家賃は高いが物価は東京と変わらないか少し高いくらいです。その高さの程度ですが、もちろん各人の生活スタイルに依りますが、収入が上がったら少し良い物件に住んだり、少し贅沢を...