今年度はコーディングインタビューについてじっくり考える機会に恵まれた。
整理のため、私見を書き留める。
コーディングインタビューとは何か
コーディングインタビュー（Coding Interview、またはProgramming Interview）とは、1時間ほどの制限時間内に小さなプログラミング問題を解かせる面接形式のことをいう。「物理的なホワイトボード上にプログラムを書く」という形式で実施されることが多い。「オンライン上の共有エディタで書く」といった形式のこともある。
出題される問題には、簡単に解けるものもあれば、込み入ったコードが必要なものもある。簡単なものの例としては、「nコの数字と整数kが与えられたとき、合計がkとなる数字の組を1つ出力せよ」（この問題はTwo Sumと呼ばれる）といったものから、「次に大きい数値の順列を返せ」、「ミーティングの集合が与えられたとき必要な会議室の数を計算しろ」といった、いくらか込み入ったコードが必要なものが問われる。
簡単な問題だけ解いて、「なーんだこんなのfor文が書ければ簡単じゃん」と準備をサボると、本番になって「そのアプローチは非効率なのでもっと効率的な解き方で書いてください」と言われたときに困ってしまう。
たとえば上記の”Two Sum”はハッシュテーブルを用いて工夫するとO(n)の時間で済むが、素朴に2重のfor文で解くとO(n^2)の時間がかかる。仮にn = 1億（10^8）とした場合、前者のアプローチであればおよそ数億の手数で解けるが、後者だと数京（10^16）ほどの手数になる。乱暴に言えば、前者のやり方で0.0001秒で解ける問いは、後者のやり方だと10000秒、すなわち約2時間46分かかる。いくら最近のコンピュータが速いとはいえ、数億倍の効率の悪さは無視できない。雇用する側にとって、両方の解法を思い付けて適切に取捨選択できる労働者のほうが魅力的なことは言うまでもないだろう。
このような課題は、競技プログラミング（競プロ）と似ている。ただ、競プロと比べると必要な技法が少ない。なおかつ、「binary searchせよ」など基本的な操作がそのまま課題になることが多く、取り組みやすい。また、競プロでは単に問題が解ければよいが、コーディングインタビューでは、コミュニケーションの側面も多分に含まれる。例えば、意図的に曖昧に示された問題に対して的確な質問をすることで正確に把握したり（「数字に重複は？」「入力は空ではない？」など）、プログラムを書き始める前に解法を簡潔に面接官に説明したり、正しいプログラムを書いたあとで適切な入力例を用いて動くことを検証したりと、意外とやることが多い。
コーディングインタビューの効用
コーディングインタビューは役に立たないという論評も多い。たとえばRuby on Railsの著者であるDHHは「私はなぞなぞはしない（"I don't do riddles"）」と言って、この面接形式を厳しく批判している。実務で必要ない上記のようなアルゴリズムを、たとえば画像処理を10年やってきた専門家に問うようなことは、目的合理的とはいえないかもしれない。実際に、多くのプログラマが使っているHomebrewの開発者であるMax Howellが、二分木を反転できなかったからGoogleに落とされたと語った事実もある。
コーディングインタビューに批判的な人々の主張の大筋は次のようなものだ。
「やっかいなアルゴリズムを設計できる力が必要とされる部署も世界のどこかにはあるだろうが、情報システムを作る大多数のプログラマーにはホワイトボード上で効率の良い基礎的なプログラムを書くスキルなど必要ないだろう」
なるほど確かに、「マージソートやQuick Selectなんて、カリッカリに最適化された専用のライブラリがどうせ存在するだろう」という気持ちも分かる。一方で、システム設計のインタビューや「過去のプロジェクトについて話してください」といった形式の面接では、バグを作らないように細部のシミュレーションを行う受験者の姿は視認できないだろう。そのような側面を十分に代替する他の面接形式には、未だ出会っていない。効率が数億倍のプログラムを書けるかどうかはもちろん、バグが少ないプログラムを書けるかどうかは採用する側にとって大いに興味がある点だろう。バグはソフトウェアの将来の価値を損ない、時に人命に関わることもあるからだ。
例えば、
- ネットフリックスのコーディングに関するドキュメンタリーでは、2014年にアメリカの警察緊急通報911の電話受付プログラムが単純なバグにより6時間以上も応答不能になり、1,100万人以上が影響を受けたという実例が紹介されていた。
- 富士通の子会社が作った会計システムの中に多くのバグがあり、イギリスの郵便局で働く550人が、「数字が合わない」と横領の濡れ衣を着せられた。中には自己破産に追い込まれ、最終的に最低賃金で働く状況にまで追い込まれる人もいた。裁判所は約8億3400万円の和解金の支払いを命じた。 （出典）
これからコーディングインタビューを受ける人へ
以下では、コーディングインタビューに対して建設的な見方を深めるために、受ける前に知っているとよい知識と、インタビュー中の思考過程を考察する。コーディングインタビューを実施しない採用を行なっている有名な企業も存在するが、業界全体からコーディングインタビューが消えることはないだろう。選抜という面だけでなく、訓練という面からも、従業員の質を高める上である程度役に立つ手法だからだ。 労働者が自身の雇用流動性を高めるためにこの面接形式の対策をするのは、1つの妥当な選択肢だといえる。
なお、読者の期待値を正しく設定するために言うと、筆者はコーディングインタビューが苦手である。競技プログラミングについてはサッパリだ。しかし、学生時代に面接対策として150問から200問くらいの問題を解いてきたので、平均的な問題に関しては対応ができる。以下の内容はそのようなエンジニアが書いたものとして読んでほしい。また、何か大きく見落としている点に気付いたら、ぜひ教えてほしい。
筆者は面接官としての訓練を受けたことがないので、見方が未熟である可能性は十分に存在する。コンピューターサイエンスの授業では、インタビュー対策用の知識を全てはカバーできないことが常態のため、自学に役立てば幸いである。
コーディングインタビューに必要なデータ構造の知識
（この段落以降は、アルゴリズムとデータ構造の勉強をしたことがない人には読みにくい箇所が多々あるため、目的に応じて適宜飛ばしてもらえれば幸いである。）
筆者の理解では、およそ80%強のコーディングインタビュー問題を解く上で必要になるデータ構造の知識とその関係は、以下のようなデータ構造の概念地図として表せる。
青字がそのデータ構造が得意とする（＝効率的に行なえる）操作で、赤字がそのデータ構造が苦手とする操作を表す。全体として、青と赤が交互に配置され、たった１つ最強のデータ構造を使えば全て解決できる、と言った都合の良い状況ではないことが確認できる。
この図を見るうえでは、いくつか注意点がある。「集合の要素として含まれる」ことを表す記号 ∈ は雑に提示しているので深く解釈しなくてよい（例えばHyperLogLogはBit Map以外の構造も持つ）。また灰色の背景で塗られたデータ構造（Radix Tree, Red Black Tree, HyperLogLog, Bloom Filter, Bounded Priority Queue）はインタビューにはまず出ない。あくまで、どのような実務上のデータ構造に繋がっているか図示したのみである。たとえば赤黒木はLinuxのプロセススケジューリング、Bloomfilterは一意性の確認（既に視聴した動画を素早く除くなど）、HyperLogLogはビッグデータ処理の道具の一つとして、それぞれ実務に登場する可能性がある。それはそれとして、大事なことは、灰色になっていないデータ構造とその性質はマニアックでも何でもなく、知らないとしたら単に準備不足だと判断されるということだ。順に見ていこう。
データ構造の概念地図は、左上のDeque（Double-ended Queue）から始まる。Dequeというデータ構造は、FIFO（First Input First Output, キュー）やFILO（First Input Last Output, スタック）といった取り出し規則で済む問題について強い。幅優先探索（breadth first search）で次に訪れるノードはキューで表現できるし、数値の列を順に見ていく際のある時点における最小値はスタックとして記録できる。
一方で、「今までに訪れたノードの中で、まだ取り出しておらず「最良」のものを取り出す」操作は、Dequeを使うとO(n)と遅い。なので、そこを高速にしたい際は優先度付きキュー（Priority Queue）を実装することになる。ウィキペディアには優先度付きキューを実装するデータ構造が5つも6つも載っているが、コーディングインタビューにおいて、二分ヒープ（Binary Heap）以外の実装が求められることはまずない。
Priority Queueによって、「最良」のもの（最小値あるいは最大値）をO(log n)で取り続ける操作が可能になる。これは単純なDequeでは原理的に成し得ない重要な成果である。だが、「あるノードがまだPriority Queueの中に存在しているか？」というmembership checkの操作はO(n)であり、効率的ではない。これがどれくらい非効率かというと、例えばボードゲームのCPUプレイヤーが新しい盤面を考えるとき、Priority Queue（あるいはStack、Queue、Deque）を使うと、各盤面についてそれまでに訪れたnコの盤面とイチイチ比較を行うことを意味する。実際に作ってみると耐え難いほどの遅さだ。membership checkがO(1)であるように設計されたデータ構造に切り替えると、それだけで経験的には数十倍も早くなる。
Membership checkの用途のために、有限集合を表すSet、あるいはその集合の各要素をキーとして値を紐付けたMapを導入する。Mapの最も典型的な実装であるハッシュテーブル（Hash Table）は、要素の参照、追加、削除がすべて平均的にはO(1)で行なえるという、あまりにも強力な性能を持っている。そのため、ハッシュテーブルはプログラムのあらゆる局面で使われており、「とりあえずハッシュテーブルを使えば何とかなる」と冗談を言うシニアプログラマーを見たこともあるほどだ。ハッシュテーブルは確率的な現象を活用したデータ構造であり、1953年頃には既にIBMのコンピュータ上で利用されていたらしい。ボードゲームに限らず、さまざまな分野で高速な情報処理を支えているクールな発明である。
しかし、最強に見えたそのハッシュテーブルでさえも万能ではなく、他のデータ構造と併用していく必要がある。ハッシュテーブルは、特化した各種の問い合わせ(query)については素早く対応できない。例えば、以下の２つの操作だ。
- 3を入力として与えられたときに、3より大きい中で最小の数値を返すnext-largestクエリ
- {fri}という3文字が与えられたときに、その接頭辞で始まる全ての単語、fridayやfridgeなどを素早く表示するクエリ操作（Google検索が行う自動補完を想起しよう）
コーディングインタビューにおいて、前者は平衡二分探索木、後者はプレフィックス木（Prefix Tree、あるいはトライ木とも呼ばれる）というデータ構造で対応することになる。問題によっては、ハッシュテーブルに用いられる仕組みを単純化することで、ビットマップ（Bit MapまたはBit Array）のような、時間的にも空間的にも更に切り詰めたデータ構造が考えられる。
平衡二分探索木（Self-balancing Binary Search Tree）は、参照、追加、削除がすべて平均的にO(log n)であり、それら全てが平均的にO(1)であるハッシュテーブルに劣るが、一つには前述の柔軟性を理由として現代でも生き延びている*1。一方で「木の深さを均等にする操作」が必要になり、それが行われていない傾いた木は、最悪の場合には双方向連結リスト（Doubly Linked List）のような状態になってしまう。この場合には参照、追加、削除がすべてO(n)になる。木の高さのrebalanceは複雑な操作であるため、コーディングインタビューで扱われることはまずないと思われるが、与えられた木が偏っていた場合のedge caseの対処は重要である。書籍『みんなのデータ構造』に取り組んだ人は、平衡二分木としてスケープゴート木やTreapを想起するかもしれないが、それらは難易度からしてコーディングインタビューではおよそ問われることはない。
さらに、子ノードが格子状に並んだ1か0の値を取るマス目（白黒画像を保持している配列など）を訪れて、1で構成される島を数えるような問題では、探索木は2つ以上の子ノードを持っても不思議ではない（タテ・ヨコで4つの子ノードなど）。そのため、時に木を一般化したグラフを扱う問題が扱われることもある（Connected Componentsの数を数える問題など）。グラフについては長くなるので、各自で整理してほしい。
以上のような思考回路を一度作ると、コーディングインタビューにおけるデータ構造の選択はほとんどの場合において容易となる。
データ構造の概念地図を見るときの注意点
上図には、更にいくつか形式上の批判ができる。例えばハッシュテーブルのルックアップの計算量がO(1)というのは雑な説明で、最悪計算量がO(n)で償却計算量がO(1)などとするのが正しい。ただしコーディングインタビューにおいては、この程度の雑さで問題ない。
唯一、雑に扱うとまずいのは、ヒープからの削除がO(1)ではなくO(logn)であることだ。比較に基づくソートの計算量の下限が理論的にO(n logn)であることから、仮に平均がO(1)だとすると、合計O(n)でソートできてしまうことになる。この点を誤るだけで、比較に基づくソートについての理解が怪しいことが判断できる。
「あれ、君いま理論的な限界超えてなかった？」
「気のせいです」
更に面倒なことに、与えられた配列をmin/max heapにするheapifyの操作自体は、驚いたことにO(n)で出来る。何故か興味を持った場合はこのStack Overflowを参照のこと。作るのはO(n)でできるのに、いざ全部使おうとするとO(n logn)かかってしまう（nが1億なら27倍くらいの手数がかかる？）というのは何とも、もどかしくて印象的だ。ヒープは「雑然と積み上げたもの」という語義を持ち、最良のもの以外の位置をかなり緩く決めたデータ構造である。その適当さの負債を、実行時間として後払いしているようなものかもしれない。
データ構造に関する知識は上記のように、多少の罠があるものの大して量がない。これだけで済むならば、そこらの資格試験より簡単だろう。むしろコーディングインタビューにおける難関は、そのデータ構造の上で動くアルゴリズムの方である。
コーディングインタビューに必要なアルゴリズムの知識
コーディングインタビューという特殊な問題設定において、いちばん候補者の間で理解度の差が際立つのはアルゴリズムの知識だろう。これらは即座に思いつくことが極めて難しく、数が多く、なおかつ習得も一度見ればできるという類のものではない。
特に大変なのは連結リスト（Linked List）に関するアルゴリズムである。連結リストは、前述した二分ヒープやハッシュテーブルと比べると極めて単純な構造をしていることから、「学ぶことなどあるのか？」という印象を持つかもしれない。
だが侮ってはいけない。実際のコーディングインタビューであなたを叩きのめすのは、この一見すると人畜無害な連結リストかもしれないのだ。
連結リストの問題においては、細かな技法がものを言う。「リストを反転させる際には、前の要素と次の要素をprevとnxtとして一時変数に保持しておく」、あるいは「dummyノードをheadノードの前に付けることで、場合分けを減らす」、また「リストの真ん中に存在する要素を効率的に見つけるには、2コずつ要素を飛ぶfastとその半分の速度で動くslowを定義し、fastが動けなくなるまで前進を続ける」などと言った、初心者からすれば摩訶不思議でとても思いつかない技法が多用される。99.5%の人にとって、これらの技法は、数年の実務を積んだとしても自然と身に付く代物ではない。このギャップがコーディングインタビューを事前に訓練しないと解けないものにしている。仮にあなたがこれらの技法を何も知らずに臨んだ場合、待っているのは何も出来ず逃げ出したくなるような30分間だろう。
連結リストに対するアルゴリズムと並んで顕著な例が、ソートされた配列のbinary searchにおける２つの繰り返し変数、lowとhighの管理である。二分探索（Binary Search）は、与えられたnコの数値の列がソートされていることを活用して、問題サイズをあれよあれよという間に半分、また半分と縮小していくことで、O(log_2 n)の時間で目的の値を探すアルゴリズムである。設計パラダイムとしては分割統治法（Divide and Conquer）に分類され、部分問題の数が常に1なので、Decrease and Conquerと呼ぶ人たちもいる。
このアルゴリズムを実装すると、候補者は以下の極めて実務的な問題に答える必要が生じる。そして面接官は恐らくこれらへの対応速度と精度から、訓練量や思考の強度を見極めようとしている。
- ループする条件は while low < high か while low <= high か？
- high は n - 1 で初期化するか、それとも n か？
- そもそも low と high がいいのか、それとも競プロで使われているみたいに ok と ng と名付けるべきか？
- midのアップデートは low + (high - low) / 2 したあと、繰り下げるか繰り上げるか？
- アップデートは low = mid か、それとも low = mid + 1 か？
- アップデートは high = mid か、それとも high = mid - 1 か？
- このwhile ループは 要素数が 0, 1, あるいは 2 のときも動くか？
- 以上の設計を踏まえると、このwhileループは必ず終了するか？それはなぜか？
（細かい議論にウンザリしてきたという読者は、ここで一度休憩を取って、元気なときにまた読むほうが良いかもしれない。）
候補者は、自分が扱いやすい流儀を決めて、それをもとに考えを素早くかつ正確なものにする。筆者の場合は、
- ループの条件をwhile low < high
- highの初期値をn
- midの更新式をlow + floor((high - low) / 2)
- low = mid + 1
- high = mid （-1を付けない）
の組合せが最も好みである。
この組合せだと、
- lowとhighが隣り合わせの要素をポイントしたときに、midはfloor操作のおかげでlowと同じ要素をポイントするため、low = mid + 1またはhigh = midにより、lowがhighと同一になって必ず終了する。
- whileループでhighとlowは一緒になっていないので、midが更新直後にhighを指すことは絶対にない。そのため、highが不正な要素を指していてもmidで指定された要素の参照は安全となる。なので、安心してhighの初期値を（仮に参照したらout of indexエラーになる）nとして設定できる。これにより、nを特別な意味を持つ値として返り値に活用できる。
この設計の組合せは、Wikipediaでは、「数値に重複がありうるリストにおいて、目的の値が存在していればその一番左のもののindexを返す、そうでなければその目的の値より大きい値が配列内にいくつあるかを返す（0 または n）」アルゴリズムとして紹介されている。イメージとしては「左に偏った」アルゴリズムである。これを理解しておくと、例えばFind First and Last Position of Element in Sorted Arrayの問題は、その「左に偏っている」midのアップデートを「右に」偏らせて、２回binary searchをやるだけで解ける。このような応用ができる柔軟さが、上記の組み合わせを筆者が気に入っている理由である。
このような地道な思考の訓練を積み上げていくのが、コーディングインタビューにおけるアルゴリズムの準備となる。「再帰や基本的なパターンがsecond nature（深く身に付いた習慣）となるまで訓練しろ」とかつて友人に言われたが、まさにそのとおりである。union-find木を瞬間で思いついたり、複雑なイテレーターを使い出せる境地には至らなくてよい。そこはもはや異世界である。しかし一般的な問いを自然に効率よく解けるぐらいまではたどり着ける必要がある。そして、それは時間を多く投資した地道な訓練以外では難しい。
モチベーションと実務との関わり
「なぜこんな引っかけパズルや発想一発勝負のような問題に就職を左右されねばならないのか…」と考えると辛いかもしれない。筆者もそうだった。しかし、ある程度の問題を解いたところで大体「一回目にどれくらいの真剣さで向き合えばよいのか」が掴め、かなり楽になった。
どれほど真剣に向かおうが、パターンを知らなければ短時間では効率的に解けない問題が山ほどある。そういう問題はサクサク復習に回してしまうことで、パターンをより早く見つけられるようになったと思う。何事もそうだが、地図を手に入れれば、難所の攻略法も掴めるものだ。
最初のうちは、「こんな初期化、思いつかないだろう」と感じる問題もあるだろう。たとえば、「subarray sum equals kでcacheというハッシュテーブルを{0: 1}で初期化するとエッジケースが解ける」といったケースだ。このような問題の初期化も、3問ぐらい似たものを見れば、意外と苦もなく思いつくようになる。大事なのは、そのような自分の中でのパラダイムシフトを練習中にあらかじめ起こしておくことであり、決して本番の面接中のひらめきに期待してはいけない。
練習に際して心の支えになる事実もある。それは、上記で説明したような思考訓練が実務にも役立つということだ。著名なソフトウェアエンジニアであるMichael Feathers氏は、入力データを「都合のよい性質を持つ新しい入力データの集合」に拡張することで場合分けを劇的に減らす、ひいてはバグを減らすテクニックに繋がると言っている（この動画の16分から20分あたり）。この動画中の例は、連結リストでdummyノードを付けるテクニックに似ている。ソフトウェアエンジニアは複雑性と向き合う職業であり、要素1つ分だけのメモリを使うだけで複雑性を減らせるならば、それは設計上の優れた選択肢だと言える。
コーディングインタビュー最中の思考
あなたが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、「フロイドの解き直し」の章より引用）
（ロバート・フロイドは、ワーシャル・フロイド法を考案した人物である）
コーディングインタビューが得意な人は、「それがあれば与えられた問題に最も効果的な方法ではじめから接近できるというようなルール」を自然に把握して真っ先に使うことが多い。インタビューの練習の際は、ぜひこのような汎用的な視点で臨んでみてほしい。最初はうまく行かなくて悔しくても、続けていくうちに、いつか自分でも驚くほどの解法発想力が身に付くはずだ。
まとめ
この記事では、コーディングインタビューに必要なデータ構造とアルゴリズムの知識を概観し、それらの知識を使った思考過程が汎用的な問題解決の過程の一例であることを主張した。その中で特に、エンジニアの実務に応用できる訓練としての側面の特定に努めた。
あと１年以内にインタビュワーとして働き始めることは十分にありうるし、そのときには考えもまた変わっているかもしれない。なんにせよ「どうしてこのコーディングインタビューという制度が使われているのか？」と考えてみるのは、効用や限界を理解する上でとてもよい機会になった。
*1:形式的には、ハッシュテーブルが実装する抽象データ型はUnsortedSet、二分探索木が実装する抽象データ型はSortedSetという明確な違いがある。UnsortedSetは要素の大小比較ができないかもしれない（要素が「異なっているか」だけは定義されている）集合であるのに対し、SortedSetは全順序集合、すなわち全ての要素のペアについて大小比較が可能な集合を表す。平衡二分探索木は、実行速度が対数時間になるという犠牲を払って、大小比較を前提とするnext-largestなどの追加機能を実現したものであるとも言える。この議論は『みんなのデータ構造』では1.2節にまとまっている。
