2019-08-30

Googleのインターンホストマッチングに2年連続落ちた話

（追記）こんにちは、社会人のJoeです。この当時はいろいろ未熟なところが多く、記事の内容がかなり過激なのですが、当時の気持ちを尊重したいという考えもあって、残しておきます。記事の最後に社会人目線での今の感想も載せておくのでよければそこまで目を通していただけると幸いです。では。

まあ今回はホストマッチング用のFormを提出しなかったぼくが悪いようですが(マッチング時期を夏休みのインターンとかぶらないように変えたかっただけなんですが未提出という扱いになったっぽい)、以前から言いたいことが多かったので書きます。

ほんとは受かったら思う存分苦情を書いてやろうと思ったのですが、受からずに書くのは恥ずかしいですね

インターンに合格するまで

Step 1

応募する。これはStudent向けのインターンに応募すれば90%ぐらいの確率で返信が来るはずです。海外のインターンやインターンでない募集に応募した場合、ほぼ返信が来ないはずで、この時点で選考終了になります。

Step 2

ウェブでプログラミングクイズを受ける。これは練習すればほぼ100%の確率で通過します。プログラミング力が足りない場合、この時点で選考終了になります。

Step 3

Phone Interview 1を受ける。まわりを見ていると普通に能力十分でしょという人でもたまに落ちるようです。直感的にAtCoder青あれば70%ぐらいで通過するんではないでしょうか。使用言語をマイナー言語にすると競プロに詳しくない面接官とあたるので問題が簡単になるという噂があります(ア) ある程度のコミュ力・実装力がない場合この時点で選考終了になります。

Step 4

Phone Interview 2を受ける。このプロセスは去年まではオンサイト面接だった気がするのですが、おそらく今年は応募者が多いようで、Phone Interviewになりました。Phone Interview 1と同じ程度の運ゲーです。ある程度のコミュ力・実装力がない場合この時点で選考終了になります。

Step 5

Hiring Committeeです。これは、面接の結果をまとめ直して、本社に送って数週間後にGlobal基準を満たしているかチェックされ結果が返ってきます。これはかなりの運ゲーで、Phone Interview (もしくはオンサイト面接)を比較的手応えありな状態でこなしたとしても落ちるようです。ここまでくるとサンプルがだいぶ少ないのですが通過率は30%とかな気がします(適当)。比較的まともなことを書いておくと、面接で問題を解けたとしても、どれぐらいアルゴリズム的な思考ができているかとか実装ができているかなどが細かく点付けされているようで、そこをチェックされると思います。十分に優秀でない場合この時点で選考終了になります。しかし、ここまでは精進すればたどり着くとは思います。

Step 6

Host Matchingです。まずはFormを提出しましょう。次に1ヶ月待ちます。いいプロジェクトがマッチングすると拾われます。完全に運ゲーすぎてどうしようもないです。運が良くなければこの時点で選考終了になります。

やっかいな点

一度落ちると次の選考はStep 1からやり直し

運ゲーをやり直すのは骨が折れますね。ちなみに受かると、次年度以降のインターンはHost Matchingからです(せこすぎ)

Step 6までかれこれ3~5ヶ月ぐらいかかる

これはどれぐらい急ぐかによる気がします。ぼくは夏インターンがPreferred Networksとかぶったので、選考を遅めにしました。

Step 6に来る頃にはリピータで枠が埋まる

上の2つの問題点を読むとこの最大の問題点が類推できるかと思います。というのも、リピータたちは異常にプロジェクト決めが早いです。ぼくたちがまだプログラミングクイズをしている頃に彼らはプロジェクトを決めています。そうすると、Step 6にたどり着く頃には楽しそうなプロジェクトがほぼほぼ埋まっていて、熾烈な運ゲーが始まる構造になります。

冬休みは研究だな！（素振り）

（追記）社会人になった感想

こちらの記事、グーグルに入社している同期や後輩から、それなりに広く知られているとの話を聞いてお恥ずかしい限りです。当時はかなり世間知らずで、自分の実力なら頑張ればいけるはずだと思っていたようですが、シンプルに実力不足かなという気がします。社会人になってインターン採用をしていると（その年たまたまある部門に非常に優秀な学生があつまり厳選せざるを得ない状況や、そのインターン生にマッチする分野でインターンが募集されていないなど運要素は少なからずあるのですが）インターンに実際に合格するような生徒は本当にレベルが高いです。プログラミングコンテスト出身者もたまにいますが、全国で指折りの学生であったり、研究に重きを置いている学生ならトップ学会に主著論文複数、などがざらにいます。必ずしもプログラミングコンテストや論文での業績がなくても、専門の勉強に真剣に取り組んできた学生は考察が鋭く、何もないところからアルゴリズムの動作原理を説明できたり必要とさせる設定にすぐに応用できたりと完全に自分のものにしています。落ちた人たちの中にはもしかしたら非常に優秀だったのに、という方がいらっしゃるかもしれませんが、受かった人たちを眺めてみると、まあこの人なら何回受けても受かるんだろうなという人たちばかり、というのが実際のところかなと思います。

さて、これを読んでいる方の中にはこれからインターンを受けるという学生さんも多いと思います。当時これほど調子に乗っていた私が偉そうなことを言えた立場ではありませんが、自分に素直に受けるのがいいかなと思います。それと、マッチングの運要素は確かに本当にあります。私の経験からすると学生の時はあまり自分の興味も定まっていなく、どんな会社があってどんなチームがあって、具体的にどんな技術に携わるか全くわかっていませんでした。PFNのインターンでは偶然Chainerチームに採用いただき（Chainerはすぐその後なくなってしまいましたが）GPU効率を上げるために、ユーザが書いたスクリプトの裏でどのような最適化ができるか/されているか、という世界を知ることができました。結局私はそれ以降その分野がすごく気に入っており、社会人3年目になった今も似たような分野で働かせていただいています。こうした運を好意的に受け止めて、自分が偶然マッチした新しい世界を楽しんでみるというのはいかがでしょうか。

2019-08-24

b-matchingについて

b-matchingというものを知った。

グラフ $G = (V, E)$ が与えられたとき、次の条件を満たす辺集合 $M$ はb-matchingであるという。

各頂点のdegree restrictionを $b_v$ とし、各辺のcapacity $c_e$ が与えられる。このとき各辺についてcapacity以下の重みをとって、各頂点について隣接する辺の重みの和がdegree constraints以下になるとき、この重みのとり方はb-matchingであるという。

とくに、 $b = c = 1$ とすると通常のマッチングである。各辺の価値 $w_e$ と各辺の重みの積の和を最大化するとき、maximum weight capaciteted b-matchingという。多項式時間アルゴリズムが存在する。

https://www.di.ens.fr/~cchuang/work/small_weight.pdf

f:id:xuzijian629:20190824180040p:plain

2019-08-24

グラフのSeparatorについて2

A separator theorem for minor-closed classes を読むと、minor-closedなグラフは $o(n)$ のseparatorを持つのでは？という話がされている。この論文では実際に、 $K_t$ をminorとして含まないようなグラフについて、 $O(t\sqrt{n})$ のseparatorを持つことを証明している。

したがって、bounded degreeのグラフは $O(d\sqrt{n})$ のseparator持つことがわかった。

考察として、 $K_t$ には辺が $O(t^2)$ 本含まれるため、辺の数が $O(n)$ のグラフだと、たかだか $O(\sqrt{n})$ な $t$ について $K_t$ しか含むことができない。

このままの条件だと、やはりほとんどすべてのbounded average degreeなグラフが $o(n)$ のseparatorを持つことができないことになってしまうが、 $o(\sqrt{n})$ な $t$ について $K_t$ しか含めないようなグラフは $o(\sqrt{n})$ のsepartorを持てることになる。

Strongly Sublinear Separators and Polynomial Expansion を読みたい。

平面グラフを拡張したクラス

平面グラフは平面(genus: 0)に埋め込めるグラフだが、これを拡張した概念として、torus(genus: 1)に埋め込めるトロイダルグラフや、それ以上のgenusについても考えることができる。

雑知見

一般グラフの最小交差数を求めることはNP-hardっぽい。与えられた $k$ についてグラフから $k$ 本の辺または頂点を削除して平面グラフにできるかの判定は線形時間っぽい

平面グラフの同型判定は線形時間らしい

2019-08-17

グラフのSeparatorについて

A Separator Theorem for Planar GraphsとOn Sparse Graphs with Dense Long Pathsを読む。

ちょっとずつまとめていく。

On Sparse Graphs with Dense Long Paths

論文の主定理は以下の通り

どんな $n$ 頂点を取り除いても長さ $n$ のPathが残るようなDAGの辺数を $m$ とし、 $f(n) = \min m$ とすると

$c_1 n\log n / \log \log n \lt f(n) \lt c_2 n \log n$

が成り立つ。

Corollary

どんな $n$ 頂点を削除しても、 $n$ 本の辺を含む連結成分が存在するような無向グラフが $m$ 辺をもつとし、 $f(n) = \min m$ とすると、

$f(x) \lt c_2 n$

が成り立つ。 $n$ 本の辺を含む連結成分、の部分は大きさ $n$ の連結成分、に置き換えてもよい（定数は変わるが）

任意の $\varepsilon \lt 0$ について、ある定数 $c$ が存在し、任意の $n$ について $O({}_{{}_{(2 + \varepsilon)n}C_2}C_{cn})$ 個のグラフを除いた $(2 + \varepsilon)n$ 頂点 $cn$ 辺のグラフは、どんな $n$ 頂点を取り除いたとしても、大きさ $n$ 以上の連結成分が残る。

Related Theoremで主定理を使うかと思ったけどとくに関係なかった。確率的な議論をして証明している。

要は、辺のオーダーが頂点の定数倍であるようなSparseなグラフでもいいSeparatorが存在するとは限りませんよ、という話。

A Separator Theorem for Planar Graphs

Separtorという概念は平面グラフに限らず、グラフに一般的なもので、たとえば二分木はある一辺をseparatorとして、残りの成分がすべて2/3以下のコストをもつようにすることができる。一般の木は一頂点をseparatorとして同様のことができる。

上の論文でも触れたとおり、一般のsparseなグラフに関していつも $o(n)$ のseparatorが存在するかと言われるとそうではない。

この論文では平面グラフで $O(\sqrt n)$ のseparatorが存在することを示している。全域木をとって、全域木に含まれない辺を1本追加したときにできるサイクルで、サイクルの内側と外側を両方コスト2/3以下にするようなサイクルが存在することを示している。

いろいろなパターンに場合分けして示している感じ。実は平面グラフよりも広いクラスについても適用可能で、finite element graphとよばれる、平面グラフの平面への埋め込みを考えたときに、各面について、可能な対角線をすべて引いてcliqueを作ったものに関しても似たようなことをやっている（オーダーは $O(\sqrt n)$ ではなく $k$ をboundary vertexの上限として $O(k\sqrt n)$ なので別に任意のグラフについて $O(\sqrt n)$ という主張にはなっていなそう）

構築も $O(n)$ のアルゴリズムがあるが、実装やばそう（リストを用いた平面グラフを埋め込むためのデータ構造などがあるっぽい）

2019-08-17

A simple max-cut algorithm for planar graphs

e-archive.informatik.uni-koeln.de

を読んだ。

https://icpc-girigiri.slack.com/archives/GJM417MNV/p1566016527000100

にファイルがある。

概要

平面グラフのmax-cutをmaximum weighted matchingに帰着させて解いている。平面グラフのmaximum weighted matchingが $O(n^{1.5}\log n)$ で解けることからmax-cutもこの計算量で解ける。

アルゴリズム

連結な単純グラフ $G$ が入力として与えられたとき、まず $G$ の双対グラフ $G_D$ をとる。双対グラフの辺のコストは、その辺が横切る元のグラフの辺のコストと同じにする。 $G_D$ の次数5以上の頂点を分割し、分割した頂点同士をコスト0の辺でつなぐ。さらに、 $G_D$ の各頂点を $K_4$ に置き換えたグラフを考える。 $K_4$ 内部の辺の重みは0.
以上のグラフでmaximum weighted matchingを考える。必ずperfect matchingが存在することが示せ、このとき、各 $K_4$ に着目すると必ず $K_4$ から外に出る辺は偶数本になっていることがわかり、perfect matchingはEulerianになることがわかる。
双対グラフでのEulerian subgraphと元のグラフのカットには1対1対応があり、この最大重みeulerian subgraphが元のグラフでの最大cutになっている。

計算量

平面グラフを三角形分割したものを考えると、辺の数や面の数が超点数のオーダーで抑えられる。そうすると面の数も頂点数オーダーになる。双対グラフの頂点数、辺数も従って元のグラフの頂点数オーダーで、 $K_4$ をとってもオーダーは不変。あとはmaximum weighted matchingだが、これはTarjanによると $O(n^{1.5} \log n)$

2019-08-16

GNNで次数に比例した重みがかかる問題

テーマ案

次数行列をかけて正規化してやらないとだめ。

証明したい