GAFAMとかFAANGとかいわれるような企業群、あるいはそれに近い傾向(東京であればおそらくIndeedとかPFNとか)のソフトウェアエンジニア面接対策についてメモを残す。

コーディング面接とleetcode

外資IT企業ではソフトウェアエンジニアを雇う際にコーディング面接を非常に重視する。
業務上のコーディングよりは簡単めのプログラミングコンテスト問題に近く、アメリカの学生やエンジニアがIT企業を受ける際には事前対策を数ヶ月するのが常識になっているようだ。
一般的な面接プロセスについては世界で闘うプログラミング力を鍛える本という本に詳しいが、ソフトウェアエンジニアとしてオファーを得るまでには通常、45~60分程度のコーディング面接を3~5セッション程度経ることになる。

ここ数年、leetcode.comというコーディング面接の過去問サイトが広く候補者に使われるようになっている。
2018年ごろにコロンビア大の学生に聞いた話では、コンピュータサイエンスの学生はほぼ全員アカウントを持っていて半数は課金しているとのこと。
面接の際は出た問題を漏らさないよう候補者に約束させることが普通だが、leetcodeは大手企業で実際に出されたと思われる問題を収集し課金ビジネスをしているので、道義的にはグレー。
漏れた問題は使いづらくなるので、「問題をひねる->漏れる」のいたちごっこが発生しているようで、コーディング面接自体が近年やや難化している気配がある。

こうした懸念はありつつも、プロコン魔人や天才プログラマでないエンジニアにとってはleetcodeを使った面接対策は非常に役立つ。
面接で要求されるスキルの中には漫然とleetcodeをやっていても鍛えにくい側面が存在するので、それを意識して準備することで面接を有利に進められると考える。

以下、採用側の意図から逆算してどのような準備をするのがよいかを論じる。

採用側の意図

コーディング面接は形式的にはプロコンのように見えるが、問題に正解できるかだけを競う「試験」ではない。
面接官は候補者がエンジニアとして一緒に働ける相手かどうかを見極めようとしており、主に以下のような能力が候補者にあるかを確認しようとしている。

1. 自ら成果を出す能力

• 1a. 複雑なロジックを理解し、正確に、十分なスピードでコーディングできる
• 1b. 主要なアルゴリズムとデータ構造の性質を詳細に知っており、実装時に最適な選択ができる
• 1c. 妥当なソフトウェア設計ができる

1. 組織の中でうまく開発をする能力

• 2a. 読みやすく保守しやすいコードが書ける
• 2b. 対面での双方向の情報交換を正確に、十分なスピードで行える
• 2c. 積極的かつ協力的な態度を取り、人と相談してよりよい解を見つけることができる

これを踏まえて具体的な対策を述べていく。

leetcodeを使った事前訓練

leetcodeに課金するといくつか追加機能がアンロックされる。
特に業界全体および会社別の出題頻度は価値が高く、ある程度時間を費やして面接準備するのであれば課金した方が有利(leetcodeに金を払うことの道義的判断は各人で)。

古典化した高頻度問題は出題側に避けられる傾向もあるが、類題が出る可能性は十分あることと、多くは良問で学ぶ価値が高いことから、まずは頻度順に解くのがよい。
受ける企業が決まっているならその会社の頻度順と全体の頻度順との両方を進めるのがよい(両者はある程度重複する)。
トップ企業を受ける場合、時間が許せば200問くらいはやったほうがよさそう。

面接の一コマは45分から60分くらいで、(easy or medium) + (medium or hard)の2問くらいが標準的。
解いた後にディスカッションをするので、実際に問題を解くことに使える時間はmediumで15-20分、hardでも長くて30分程度になると思われる。
問題を解くスピードがそれなりに大事になるので、アルゴリズムコードを手早く書くことに手慣れていくようにする。

hard問題の中には常人には初見で解くのがかなり厳しい問題もある(https://leetcode.com/problems/cat-and-mouse/ とか)。
考え方は面接官によるが、極端に難しい問題が出る場合はノーヒントで解き切る頭のキレ(1a)よりはヒント前提で議論する能力(2b、2c)を見ようとしていると思われる。
なので練習の際は解けない問題を長時間考える必要はなく、長くとも1時間で解けなければ解説や他人のコードを見てしまったほうがよい。

解けた場合も解説や他人のコードは必ず見た方がよい。
面接では問題を解いた後に空間計算量・時間計算量を尋ね、ありうる別解とのトレードオフを議論する(1b)ので、複数の解法に触れることは価値が高い。
コンパクトなうまい書き方なども他人のコードが参考になることは多い。

面接ではleetcodeのオンラインジャッジ機能と異なりコードを実行することはできないので、コードを書いたら変数の値のメモをとりながらテストケースを手で実行して、コンピュータを使わずデバッグする習慣をつけること。
エッジケースに自分から気づくと面接での印象は非常によい。

多くの面接官は「細かい文法は問題にしない」と言うが、正確なコードを淀みなく書けるほうが当然よい。
面接官も人間なので、評価するつもりの点以外の印象に無意識に影響されることはありうる。
まずはeasyから、コードを書いたら一発でAcceptedになるよう練習する。
そのため、使う言語の文法とアルゴリズム関係の標準ライブラリはなるべく正確に覚えておくのがよい(後述)。

面接では読みやすいコードを書かないといけない(2a)ので、普段から共通ロジックは関数にくくり出す、forやifなどのネストを深くしすぎない等意識しながら問題を解くこと。

解法を頭に定着させるため、解けなかった問題は1-3ヶ月間隔をあけて繰り返して解くのがよい。
人によるとは思うが、2-3ヶ月集中してやっても(私は)急にスキルは上がらないので、長期間かけて少しずつ練習するのがおすすめ。

leetcode以外の事前訓練

プログラミング言語

コーディング面接で使う言語はPythonが推奨。
タイプ量が少なく、よく使うアルゴリズムが標準ライブラリにほぼ揃っており、面接官が読める場合が多いため有利。実際に大多数の候補者はPythonを使う。
他に習熟している言語があればそれでもよいが、アルゴリズム系の標準ライブラリが弱い言語やタイプ量が多い言語(C++/Java)はやや不利。

正確でidiomaticなコードが書けるよう、使う言語の文法とアルゴリズム系の標準ライブラリはよく学んでおく。
Pythonであれば、defaultdict、OrderedDict、Counter、deque、bisect、heap、map/reduce、内包(comprehension)表記、lambda式(ソートのkeyを書くのに便利)、with表記などできるだけしっかり覚えておくとよい。
leetcodeではインタフェース上書くことが少ないファイルの読み書きやconcurrency(スレッディングやロック)、乱数発生も面接では突然聞かれることがあるので注意して覚えておく。
余裕があれば、itertoolsのaccumulate、chain、product、permutations、combinationsなども覚えるとコードが簡潔に書ける。

アルゴリズム

基礎的なアルゴリズムとその計算量はじっくり学んでおく。
アルゴリズム設計マニュアルという教科書の上巻がおすすめ(下巻は発展的なアルゴリズムの事典なので不要)。

自分でスクラッチから実装でき、計算量が説明できるべき基礎アルゴリズム:

• 非ソート済配列、ソート済配列、単方向・双方向リンクリスト、ハッシュテーブルに対するfind, add, delete操作
• 非平衡二分探索木に対するfind, add操作(deleteは複雑なのでパス)
• ヒープのpush, peek, pop(bubble up, bubble down)
• スタックとキュー
• 関数の再起呼び出しを明示的なスタックを使って書き換える記法
• 挿入ソート、バブルソート、クイックソート、マージソート (クイックソート・マージソートがなぜO(NlogN)時間か答えられるようにすること)
• (追記)quickselect: 線形時間で非ソート列の中央値(もしくはk番目に大きい要素)が求まる
• ナイーブな文字列検索
• ナイーブなtrie
• バイナリサーチ
• グラフのDFS/BFS
• ダイクストラ法、primのアルゴリズム (priority queueを使うと計算量オーダーが変わる)
• 動的計画法 (文字列の編集距離を例題にするとよい)

バイナリサーチ、クイックソート、DFS/BFSなど再帰アルゴリズムは自分で書くとすぐミスして無限ループになるので繰り返し練習して慣れておくこと。
再帰が正しく書けるかはコーディングスキルのチェックポイントとして重視される。

自分ですぐに実装できなくてもよいが概要が説明でき計算量が答えられるべきアルゴリズム:

• ハッシュテーブルの衝突対策(open address vs chain)
• 平衡二分探索木の実装
• timsort: Pythonを使っているとき、2つのソートされた配列を連結してsort()するとO(N)時間でソートできる
• ヒープの初期化 (なぜO(N)時間か答えられるようにすること)
• Kruskalのアルゴリズム(union-find)、Floyd-Warshall、Bellman-Ford

システム設計面接

大手では1コマはシステム設計面接があることが普通。
ジョブレベルが高くなるほど大規模なシステムや抽象的課題設定になり、課題発見する力や設計力が要求される。

システム設計面接はコーディング面接ほど体系化されておらず、面接官が何を基準に良し悪しを決めるかも主観的なので事前対策はより難しい。
自分の職歴や応募先ポジションから想定される問題は事前にシミュレーションしておくとよい。
この教材は途中から有料だが非常に役に立つ: https://www.educative.io/courses/grokking-the-system-design-interview

その他CS基礎

いわゆるコンピュータサイエンス系出身でない場合、教養はできる範囲でつけておくに越したことはない。
基礎を全く知らないとまずいが、CS系出身以外のエンジニアはたくさんいるのであきらめる必要はない。

発展的な内容をアピールする場合、付け焼き刃で語ると逆効果になる可能性があるので知らないなら知らないと正直に言っておいたほうがベター(2b/2c)。

必須

• 最低限のTCP/IPなどコンピュータシステムの知識(自信がなければ書籍「プログラムはなぜ動くのか」などからでもいい。「みんなのコンピュータサイエンス」という本も基礎知識の抜けをチェックするのによいようだ。)

nice to have

• コンピュータアーキテクチャ
• OS
• コンパイラ (パーザについては多少知っていると有利)
• 数値計算
• セキュリティ
• 計算理論
• 確率統計や機械学習
• etc.etc.

英語

一般に要求レベルは高くない。
基本的なコミュニケーションが取れれば十分だが、全然何を言っているか分からないとやはり落ちる可能性は高まる。

netflixで英語字幕で好きなコンテンツを200時間くらい見れば雰囲気程度は話せるようになる気がする。

直前準備

面接時の記述環境はできるだけ事前に確認すること。
ホワイトボードかエディタか、オンサイト面接でタイプ用のマシンが貸与される場合キーボード配列は慣れたものか。

本番がホワイトボードコーディングの場合は必ずホワイトボードにコードを書く練習をしておく。
エディタが使える場合も、leetcodeにある自動インデント機能がない状態での練習をしておく。

面接本番

コーディング面接

問題に対して、黙ってコードを書き始めると解法が正しくとも大きな失点になるので注意。
オンラインジャッジでなく人が面接をする理由は広義のコミュニケーション(2a、2b、2c)であることに留意する。

時間枠と何問問題を出すつもりか最初に聞いておき、極力自分からタイムマネジメントをする。

問題はわざと曖昧にしてあることが多いので、問題を聞いたら仕様の確認のための質問をいくつかする。
入出力のフォーマット、データの大きさの想定、値の範囲の想定、エッジケース(空のコンテナ、ゼロ除算、グラフの自己ループなど)、複数解の可能性などがよくある質問。
leetcodeでは付帯条件は全て問題文に書いてあるが、実際の面接では自分で聞き出すことが期待されていることに注意。
数値オーバーフローの可能性などは、最終的に無視してコーディングするとしても一度言及しておくと印象がよい。

アプローチを考えるときはできるだけ声に出して考えを言う。
面接が英語で候補者が英語に慣れていない場合かなりきついが、厳しければ事前に多少練習しておく。
ホワイトボードが使える環境ならなるべく使う。
面接は英語の試験ではないのでコミュニケーションがとれれば手段は何でもいい。
ビデオ会議での電話面接のときは白紙と太いペンを用意しておいて紙に大きく書いて説明するのもよい。

考えに詰まったらどう詰まったのかを伝え、面接官に相談する。
特に問題が難しい場合、ノーヒントで解き切ることよりは相談しながら解を見つけていくことが求められている可能性が高い。
面接官に「ヒントをくれ」といった感じに丸投げしてしまうと印象が悪いが、「xxと思うがどう思うか?」といった相談調や、具体的な質問はむしろプラスになりうる。
思い出せない知識があれば、黙って詰まるよりさっさと質問した方がいい。

コードを書き始める前にとりうるアプローチを(できれば複数)簡潔に説明し、計算量と実装の複雑さのトレードオフを説明する。
選んだアプローチについてそれでいいか書き始める前に面接官に確認する。

コードは読みやすさに注意する。
標準ライブラリにない機能を仮定することはしていいが、その仕様はきちんと伝えること。

書き終わったら例を使って手動テストする。
この際、面接官の反応からヒントが得られることがある。
面接官がバグに気づいている場合も、候補者が自分で気付いて直す可能性をつぶしてしまうため、面接官は直接指摘をしたくない。
微妙な沈黙があるとか、「テストをしろ」「動作を説明しろ」と促された時にはコードに誤りがある可能性がある。

行動に関する面接

大手では過去の経験や仮想的な状況を挙げ、リーダーシップや対人関係についての質問をすることがある。
技術面で非常によい評価を得たとしても、行動面でレッドフラグとみなされると基本的に落ちるので注意する必要がある。

採用側は基本的に「正しい価値判断ができ自発的に動いて積極的にリーダーシップをとってくれる人が欲しい、でもあまりにチームワークを乱したり周囲のやる気を失わせる人は困る」と考えている。
企業文化にもよるが、周囲に対して攻撃的な人間は外資であっても強く警戒される(brilliant jerks)ので、面接ではリーダーシップアピールと協調性アピールのバランスをうまくとること。

転職の動機について聞かれた時には、前職を悪く言うことは避けてポジティブな理由を言うべき。
うまくいかないことの原因を周囲のせいばかりにする人間とみなされると危険。
この辺は外資でも日本企業と同じなので注意。

補遺

面接では面接官との相性(interview anti-loop)など運の要素は避けられない。
理不尽に思える落ち方をすることはどうしてもあって、たくさん準備をして落ちるのはとても辛いものだが、不合格は実力不足のためとは限らない。

同種の企業での面接経験がない場合、第一希望を最初に受けるのは避け、なるべく複数社を受けて経験を積むのがよい。