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

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

シリコンバレーの IT 企業でエンジニアとして就職するには、主に次の 5 つの審査を通過する必要があります。企業や職種によっては、電話面接が一度しかなかったり他の審査があるなど多少の差異はありますが、だいたいこれらの 5 つの審査があると心づもりをしておきましょう。 書類審査 電話面接その１ 電話面接その２ 電話面接その３ 現地面接 この記事では、それぞれの審査でどのような試験が行われるかを説明するとともに、採用面接官としての経験を持つ筆者が感覚として得た通過率も記載します。 書類審査 就職の応募は各企業が用意している Web サイトで行います。あらかじめリクルータとコンタクトを取れている場合は、リクルータの指示に従ってください。Email で必要な情報を提出する場合もあれば、Web サイトで入力するように指示される場合もあります。 送られた履歴書は、リクルータによって審査されます。ここでは応募要件を満たしているかのチェックなど簡単な審査が多いです。 書類審査の通過率は 50% くらいだと思います。数字的には半分しか通らない厳しい審査のように思えますが、実際には必要要件を満たしていない応募の足切りです。給与や待遇の良い会社には、要件を満たしていなくてもユニークな自己アピールをして何とか職を得ようとする多くの人が世界中から応募してきます。これら一人一人に対応している時間もないので、足切りが行われます。 電話面接その１ リクルータとの電話面接です。これは実際は審査ではなくて、次のステップであるエンジニアとの電話面接の日程調整だったりします。あと、応募する職種についての相談などができ、変更などもできます。 特に審査が行われる訳ではないので、このステップの通過率は 100% だと思います。 電話面接その２ ここからが本当の審査です。電話、もしくはスカイプなどの会話ツールを使い、エンジニアから出されたアルゴリズムの問題を解きます。時間は1 時間ほどです。難しい問題を 1 問だけ出す出題者もいれば、簡単な問題を数問解かせる出題者もいます。Google Docs や Collabedit などのオンライン・文書共有ツールを用い、エンジニアと会話しながらリアルタイムでプログラムを書く必要があります。 ポイントとし

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

過去の記事「 シリコンバレーのエンジニアの年収 」でシリコンバレーで働いたときにもらえる給料の話をしました。収入の話だけではなく出費の話もした方が、こちらでの生活を想像しやすいと思います。そこで今回はシリコンバレーでの物価と、特に大きな出費となる家賃について言及します。 物価 物価に関しては、日本よりは少々高いかもしれません。高いというよりは、日本のように安くて良質なものがないので、許容できる質のものを買うとなると、結果的に出費は多くなるといった方が正しいかもしれません。 特に食品に関しては、日本との差が大きく感じられます。例えば、日本だと 500 円あれば、結構美味しいものを食べられますよね。昼時にはランチメニューがあったり、コストパフォーマンスは非常に良いです。しかしこちらで 500 円相当のランチってなかなか無くて、あったとしても衛生面に不安があったり、味が凄まじかったりします。普通レベルの食事をしようと思ったら、最低でも 10 ドルは払うことになります。さらに、レストランだと 18% のチップを払います。 食品以外では、日本とそこまで変わらないと思います。私が日本に住んでいたときは東京都内に住んでいたのですが、都内と比べて特に高いと感じることはないです。 家賃 家賃に関しては、サンフランシスコ市内は高いです。安くても月 40 万円くらいするので、どうしてもシティに住みたい若者たちはルームシェアをするのが一般的です。もちろん探せば月 30 万円のアパートを見つけることもできますが、一般的な価格として 40 万円といったところでしょう。新興企業はサンフランシスコ市内に多く、市街から電車で通う人も多いです。 Google や Facebook、Apple などのシリコンバレーの有名 IT 企業はサンフランシスコから車で1時間ほど南下した地域にオフィスを構えています。Mountain View や Palo Alto、Cupertino といった地域になります。その辺だと、1ベットルームは月 25 万円、2ベットルームだと月 30 万円が目安となります。私はこのエリアに住んでおり、家賃は 22 万円程度です。 ただし、近年この地域での家賃が高騰しています。私が以前住んだアパートは毎年家賃が 7% 上がりました。3 年目の契約更新時に他

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

シリコンバレーの有名 IT 企業に勤めたときにもらえる、お金の話をしましょう。 これまで私の同僚や他企業の友人など、様々な役職の方と収入について時折話す機会がありました。そこで、彼らから得られた情報と私の経験から、シリコンバレーの有名 IT 企業に勤めたときに得ることができる年収を見積もります。ただし私を含め友人たちは大体 2 年くらいで昇進し、5 年も同じ企業に勤めている人は少なく、5 年のうち 1 度は転職している人が多いです。 もちろん役職だけでなく個々の経験や実績によって額は異なりますが、基本的な給与に加え、株やボーナスを含めた年間でもらえる総額としては、大まかに下記のように見積もることができました。 1年目、$160,000 (1,600万円くらい) 2年目、$190,000 (1,900万円くらい) 3年目、$220,000 (2,200万円くらい) 4年目、$260,000 (2,600万円くらい) 5年目、$300,000 (3,000万円くらい) 大卒の1年目で $240,000 ももらっている人もいました。内訳は大体下記のような感じです。 給与: 年間総額の 3 分の 2 弱 ボーナス: 給与の 5 ~ 15% RSU または ストックオプション: 年間総額の 3 分の 1 弱 ESPP: 年間総額の 1 ~ 5% 追記） 上記では毎年給与が 1 ~ 2 割近く上がっています。これも会社や個人の業績によって異なってしまうので一般化できないかもしれませんが、知人から得た情報や私の経験からすると、半年や 1 年ごとに行われる契約更新の際に RSU が追加贈与されることによって、年収が順調に増加していきます。 例えば、初回の基本給を $120,000 として毎年 10% アップするとします。理由としては、個人の努力だけでなく企業の業績によっても年収上昇率が変わるのですが、だいたい 5 ~ 15% 上がっているようなので平均の 10% としました。ボーナスは初めは 7%、2 年ごとの昇進で 3% 上がるとします。つまりボーナスは 3 年目に 10%、5 年目で 13%とします。そして初回の RSU $120,000 分を 4 年で満期とし、2 ~ 4 年目に新たに RSU $60,000 分を 4

本ブログの初投稿なので、ざっくりですが自己紹介をします。 略歴 私は現在シリコンバレーの某有名IT企業でエンジニアとして働き（2017 年時点で）5 年目になります。 生まれも育ちも日本で、日本の大学と大学院で情報工学を学びました。大学の授業でプログラミング演習で楽しさを見出していたこともあり、当時から将来の自分像としてエンジニアを思い浮かべていました。 学生時代には「シリコンバレーのIT企業ではエンジニアへの待遇が格別に良い」、「日本のエンジニアの給料の 3、4 倍もらえる」という噂を耳にし、シリコンバレーへの憧れを漠然と抱いていました。また、それほど待遇が良いなら当然ですが「入社試験が非常に難しく、世界レベルで超優秀なエンジニアでないと入社できない」という話も聞いており、自分がそのレベルに達している訳がなく、ただただ憧れるばかりでした。 卒業後に一度日本の企業でエンジニアとして働いたものの、自分がこれまで見聞きしてきたシリコンバレーのエンジニアとのギャップを目の当たりにし、愕然としました。特に給与の低さや残業などの仕事のあり方が挙げられます。 その頃からシリコンバレーのIT企業でエンジニアとして働くには、具体的に何が必要かを調べ、自分に不足している技術や知識を勉強し始めました。その甲斐あって、日本にいながらシリコンバレーの IT 企業の面接に臨み、晴れて入社することができました。 具体的にどのような知識や技術が必要か、どのような勉強をすればよいかについては、このブログで詳細に記述したいと思います。 主な仕事内容 先に挙げたように、私は現在シリコンバレーの某有名 IT 企業で働いています。仕事内容としてはプログラミングはもちろんのこと、システムのデザインやレビューを行ったり、採用面接での面接官として候補者に問題を出したりしています。 本サイト開設にあたって アメリカを含め世界には、シリコンバレーの IT 企業で働くことを目指し、日々奮闘している方々が大勢います。彼らに参考になる書籍や Web サイトも多々あり、彼らはそれらを自分で見つけ、勉強しています。 ただ日本では、シリコンバレーで働くことによって得られるメリットが一般的に認識されておらず、かつそれを理解した方々でも実際にシリコンバレーの