コーディングインタビューの対策とその意義 (2/2)：インタビュー本番中に何を考えるか
前回の記事（下のリンクを参照）では、コーディングインタビュー前日までに役立つ知識とインタビューの意義を考察した。
この記事では、コーディングインタビュー当日の思考過程について考えてみる。
コーディングインタビュー最中の思考
あなたがGoogleやFacebookといった、競争の激しいテック企業のコーディングインタビューを受ける状況を想像してほしい。
何ヶ月にも及ぶ練習を乗り越え、準備は万端だ。
だが、面接官が問題の設定を説明し始めると、自分の鼓動が速まっていくのを感じる。
なんてことだ、今までやったことない問題だ。
あれだけ解いたのに。
いったいどうアプローチすればよいのだろう？
どのデータ構造を使えば解けるのかも分からない。
動的計画法のような気も、単なる分割統治法の気もする。
それともgreedyに解けるのか？
どんな境界例が考えられるのか頭に思い浮かばない。
頭が真っ白だ。
このような心理状態に陥ることは、十分に想定される。なぜなら現実の問題は複雑であり、以前に解いた問題と全く同じではありえない。相当な数の問題が、過去問と類似性が見えない（あるいは、面接官は類似性を隠すように説明する）。コーディングインタビューで見たことのない問題を解くという、ミクロに危機的な状況で突破口を見つける方策は、より複雑な現実の問題に対処するときの方策でもある。
コーディングインタビュー本番に、最も血湧き肉躍り、そして最も意義深い瞬間は、そのような「初見だが既知の知識が応用できる」問題が出たときだと私は思う。有望な道筋（"You're on the right track"）を見つけ出すには、質の高い思考力とコミュニケーション能力が必要になる。手持ちの知識と、面接官（＝経験を積んだ同僚や上司）が与えてくれるかもしれないヒントや反応、あるいは自分が今から数分間の考察のあいだに段々と気づくかも知れない洞察を、有機的に組み合わせる力が必要になる。それらは会社にとっても、候補者個人にとっても、価値がある優れた力だ。ハッシュテーブルや二分探索は具体例に過ぎない。具体的すぎるほどの具体例を通して、汎用な課題解決能力を鍛えるものがコーディングインタビューだというのは、あまりに飛躍が過ぎる解釈だろうか。
コーディングインタビューが単に無数の解答を覚えてなぞなぞを解く暗記運ゲー以上のものでありえるならば、それは「初見の問題を与えられた際に、どれだけ素早く、即ち会社にとって低コストで、ある程度効率の良いプログラムを正確に記述していけるのか」という問題解決能力にあるだろう。
人によって思考の手順は異なるので、一概に単純化できるものではないが（Interview Cakeのこの記事は興味深い）、そのような突破口を見つける方策として一般的に有効なものを以下に紹介する。
１．例の「動き」を分解する
多くの場合、インタビュワーは問題を説明するために入力例とその応答を実演する。例の動きを分解すると、以前に解いた類題との類似性が見えることがある。
- この動きはFIFOのキューじゃないか？
- いま最大値って頭をよぎったか？ということはPriority Queueか？
２．例を増やす
面接官は、「信頼できない語り手」である可能性がある。例を使って実演してくれた優しいその人は、もしかしたら本当に重要な例を避けているかもしれない。
- 要素が重複したらどうだろうか？
- 文字列が数万文字もあったら？
- 英語のアルファベットだけなのか、それともアスキーなら何でもありなのか？
- rootノードしか存在しない、あるいはそれすら存在しない？
- 反転しろとあるけど、もしかして全要素を反転するともとに戻る？
- rotatedされているとあるけど、もしかして最初の場所でrotateした場合は操作前と同一になる？
- 今、２つ目の要素を４と書いて、５に直さなかったか？
- もしかして偶数と奇数で扱いが違う？
- modの結果に何か意味がある？
また、low < highやlow = mid + 1などを書く際に、「等号あったっけ？」などと不安になったら、15秒程度でチェックできる小さな入力をその場で作り上げる。問題の入力とは別に、各行の入力と出力という部分問題については、この方策がよく効く。
３．データ構造をlinear scanする
上節で書いたようなデータ構造間の関係のメンタルマップが出来ていれば、以下の問いをlinear scanするだけで突破口が見つかることがある。
- Dequeを使うと解けるか？
- Priority Queueを使うと解けるか？
- Hash Tableを使うと解けるか？
- Binary Treeを使うと解けるか？
- ...
多くのデータ構造は瞬間で却下できる一方で、1つ2つ気にかかることがある。そうなったらチャンスだ。なぜそのデータ構造がうまくいきそうなのかを考察してみる。
４．アルゴリズムをlinear scanする
ここでは、手法について考える。
- greedyなアプローチはどうだろうか？
- divide and conquerなアプローチはどうだろうか？問題サイズを半分に減らせないか？
- ベースケースからボトムアップで構築できないだろうか？要素が2つのものの解は1つのものの解とどう関係しているか？
たとえばSearch in Rotated Sorted Arrayの問題は、sorted arrayなのでbinary searchをすることは分かる。問題はdivide and conquerをどう設計するかであり、「どこでrotationが起きているのか」がmidより左なのか右なのかが分かると、片方はもうrotationが起きておらず、普通のbinary searchが使えることに気づけるかも知れない。
５．制約を緩める、前提を増やす
たとえばTwo Sumのような配列の要素を何らかの形で比べる問題で、入力が何かによってソートされていると仮定する。この際、全ての要素についての比較が必要なくなることに気がつけば、ソートするO(n log n)が実は全要素を比べるO(n^2)より効率の良いアプローチであることに気がつくかも知れない。Two SumはO(n)で解けるやり方があるのでソートして解くことはまずないが、「全比較してO(n^2)ではなく、ソートしてO(n logn)」が最適な計算量となる問題はいくつか存在する。
あるいは二分探索木において、探す要素が必ず存在すると仮定する。重複がないことを仮定する。これらの仮定は面接官への質問のなかで見つかることも多い。
６．自分の発想に対する面接官の言動に注意する
これが競技プログラミングと最も異なる点だと思うが、コーディングインタビューは独力での問題解決である一方で、時に面接官と２人での問題解決になる。
特に１問目と２問目をすんなりとこなした場合など、面接官は解けないことを前提として暴力的な３問目を尋ねてくる可能性がある。そうなると、いきなり正答例のアプローチを答えられる可能性はほぼない。むしろ、データ構造やアルゴリズムを声に出しながら検討する中で、面接官が何に反応しているかを探ったほうがいい。
大して親切でもないヒントのように聞こえても、実は多くの試行錯誤をカットできる強力な手がかりであったりもする。話の誘導の仕方、気を抜いて見ている瞬間の推測など、一人でコードを書いているときにはアクセスできなかった情報がかなり提供される。たまに全く反応しない熟練の面接官が居るが、そのときはそのときだ。
学習の指針
面接対策用の書籍”Cracking the Coding Interview”などでも、BCR（Best Conceivable Runtime、速さの上限からアプローチを逆算する）や、BUD（Bottleneck, Unnecessary work, Duplicated workという３つの最適化機会）と言った論理的な観点を用いて、プログラミングによる問題解決の過程をより汎用にすることを狙っているように思える。興味がある人は同書を読んでみて、自分にしっくり来る形にまとめ直してみるとよいだろう。
解けない問題を1時間も2時間も考え続けることを奨励する人が居るが、コーディングインタビューの問題に関してはそのような癖をつけるべきではないと思う。上記の思考過程は、3から7分程度で一巡しなければならない。それを過ぎたら、むしろヒントを見て、いまの7分間にそのヒントにたどり着ける道筋はあったか？答えでは優先度付きキューを使っていて、一瞬それを使うことを考えたのに、どうして使わなかったのだろうか？などを点検するほうが、よほど実践的で、なおかつ頭を使うと思う。
最後に、筆者の好きな計算機科学者、ロバート・フロイドがチューリング賞（計算機科学におけるノーベル賞に相当するもの）の講演原稿で述べた言葉を引用する。
「やっかいなアルゴリズムの設計を行ったときに味わった私自身の経験では、ある種の技術が自分の能力を高めるために非常に役立った。すなわち、意欲をそそる問題を1 つ解いた後で、そのときの『洞察』だけを頼りにして、同じ問題を再び最初から解く。この過程を解ができるかぎり明解かつ直接的になるまで繰り返す。そうして同様な問題を解くための、一般性があり、しかもそれがあれば与えられた問題に最も効果的な方法ではじめから接近できるというようなルールを探し出す。そのようなルールは永久に価値のあるものになることが多い」
（書籍『問題解決大全』の方策番号26、「フロイドの解き直し」の章より引用）
（ロバート・フロイドは、ワーシャル・フロイド法を考案した人物である）
コーディングインタビューが得意な人は、「それがあれば与えられた問題に最も効果的な方法ではじめから接近できるというようなルール」を自然に把握して真っ先に使うことが多い。インタビューの練習の際は、ぜひこのような汎用的な視点で臨んでみてほしい。最初はうまく行かなくて悔しくても、続けていくうちに、いつか自分でも驚くほどの解法発想力が身に付くはずだ。
