コーディングインタビューの対策とその意義 (1/2)
１．コーディングインタビューとは何か
コーディングインタビュー（Coding Interview、またはProgramming Interview）とは、1時間ほどの制限時間内に小さなプログラミング問題を解かせる面接形式のことをいう。プログラマー、またはデータサイエンティストなどの採用試験として、米国を含むいくつかの国で用いられている。「物理的なホワイトボード上にプログラムを書く」という形式で実施されることが多い。「オンライン上の共有エディタで書く」といった形式のこともある。Googleなどは自社のYoutubeチャンネル動画でも説明している。
出題される問題としては、例えば、「複数の数字numbersと整数kが与えられたとき、合計がkとなる数字の組を1つ出力せよ」といったものがある。この問題は有名なので通称が付いており、Two Sumと呼ばれる。
このTwo Sumという問題は一見すると余りにも簡単で、選抜するための問題として機能しないように思える。多くのプログラマは「２重のfor文を使うとTwo Sumが解ける」ことはすぐに思いつくだろう。だが実際に面接でその解法を説明すると、面接官は間違いなく「もっと効率的な方法で解いて下さい」と指示を返す。そしてコーディングインタビューの準備をしたことがないプログラマは、例え10年の実務経験があったとしてもそこで困ってしまうことだろう。Two Sumは２重のfor文よりも素早い実行時間のアルゴリズムで解くことができ、面接官は短時間にその解法を発想・概説・実装・検証できるかどうかを見ている。
具体的に検討してみよう。numbersの要素数をnとする。Two Sumは素朴に2重のfor文で解くとO(n^2)の時間がかかるが、ハッシュテーブルを用いて工夫するとO(n)の時間で済む。仮にn = 1億（10^8）とした場合、素朴なやり方だと数京（10^16）ほどの手数となるが、ハッシュテーブルを使うアプローチであればおよそ数億の手数で解ける。
乱暴に言えば、素朴なやり方だと10000秒、すなわち約2時間46分かかるものが、データ構造を工夫すると0.0001秒で解ける。いくら最近のコンピュータが高性能でも、数億倍の効率の悪さは無視できない。雇用する側にとって、両方の解法を思い付けて適切に取捨選択できる労働者のほうが魅力的なことは言うまでもないだろう。
このような課題は競技プログラミング（競プロ）と似ている。ただ競プロよりも必要な技法は少ない。なおかつ「binary searchせよ」など基本的な操作がそのまま課題になることが多く取り組みやすい。また競プロでは単に問題が解ければよいが、コーディングインタビューではコミュニケーションの側面が多分に含まれる。例えば、意図的に曖昧に示された問題に対して的確な質問をすることで仕様を正確に把握したり（「数字に重複は？」「入力は空ではない？」など）、プログラムを書き始める前に解法を簡潔に面接官に説明したり、正しいプログラムを書いたあとで適切な入力例を用いて動くことを検証したりと、意外とやることが多い。
以上の観察から言えるのは、
コーディングインタビューは、実務のプログラミングとも競技プログラミングとも少し異なる、独自の対策や訓練が必要なものである
ということだ。コーディングインタビューに必要なのは、実際のプログラミングの力というよりは、「コーディングインタビュー力」なのだ。
２．コーディングインタビューの意義・効用
コーディングインタビューは役に立たないという論評は多い。たとえばRuby on Railsの著者であるDHHは「私はなぞなぞはしない（"I don't do riddles"）」と言って、この面接形式を厳しく批判している。多くのプログラマが使っているHomebrewの開発者であるMax Howellが、二分木を反転できなかったからGoogleに落とされたと語った事実もある。
コーディングインタビューに批判的な人々の主張の大筋は次のようなものだ。
「やっかいなアルゴリズムを設計できる力が必要とされる部署も世界のどこかにはあるだろうが、情報システムを作る大多数のプログラマーにはホワイトボード上で効率の良い基礎的なプログラムを書くスキルなど必要ないだろう」
なるほど確かに、「マージソートやQuick Selectなんて、カリッカリに最適化された専用のライブラリがどうせ存在するだろう」という気持ちも分かる。一方で、システム設計のインタビューや「過去のプロジェクトについて話してください」といった形式の面接では、バグを作らないように細部のシミュレーションを行う受験者の姿は視認できないだろう。そのような側面を十分に代替する他の面接形式には未だ出会っていない。効率が数億倍のプログラムを書けるかどうかはもちろん、バグが少ないプログラムを書けるかどうかは採用する側にとって大いに重要な点だろう。バグはソフトウェアの将来の価値を損ない、時に人命に関わることもあるからだ。
例えば、
- 2014年にアメリカの警察緊急通報911の電話受付プログラムが6時間以上も応答不能になり、1,100万人以上が影響を受けた。原因は単純なバグだった。この事件はネットフリックスのコーディングに関するドキュメンタリーでも取り上げられている。
- 富士通の子会社が作った会計システムの中に多くのバグがあり、イギリスの郵便局で働く550人が「数字が合わない」と横領の濡れ衣を着せられた。中には自己破産に追い込まれ、最終的に最低賃金で働く状況にまで追い込まれる人もいた。裁判所は約8億3400万円の和解金の支払いを命じた。（出典）
３．これからコーディングインタビューを受ける人へ
以下では建設的な見方を深めるために、受ける前に知っているとよい知識と、インタビュー中の思考過程を考察する。コーディングインタビューなしで採用を行う有名企業も存在するが、業界全体からコーディングインタビューが消えることはないだろう。選抜という面だけでなく、訓練という面からも、従業員の質を高める上でまあまあ役に立つからだ。 労働者が自身の雇用流動性を高めるためにこの面接形式の対策をするのは、妥当な選択肢だといえる。
なお、読者の期待値を正しく設定するために言うと、筆者はコーディングインタビューが苦手である。競技プログラミングについてはサッパリだ。しかし、学生時代に面接対策として150問から200問くらいの問題を解いてきたので、平均的な問題に関しては対応ができる。以下の内容はそのようなエンジニアが書いたものとして読んでほしい。また、何か大きく見落としている点に気付いたら、ぜひ教えてほしい。筆者は面接官としての訓練を受けたことがないので、見方が未熟である可能性は高い。
４．コーディングインタビューに必要なデータ構造の知識
（この段落以降は、アルゴリズムとデータ構造の勉強をしたことがない人には読みにくい箇所が多々あるため、目的に応じて適宜飛ばしてもらえれば幸いである。）
筆者の理解では、およそ80%強のコーディングインタビュー問題を解く上で必要になるデータ構造の知識とその関係は、以下のようなデータ構造の概念地図として表せる。
青字がそのデータ構造が得意とする（＝効率的に行なえる）操作で、赤字がそのデータ構造が苦手とする操作を表す。全体として、青と赤が交互に配置され、たった１つ最強のデータ構造を使えば全て解決できる、と言った都合の良い状況ではないことが確認できる。
この図を見るうえでは、いくつか注意点がある。「集合の要素として含まれる」ことを表す記号 ∈ は雑に提示しているので深く解釈しなくてよい（例えばHyperLogLogはBit Map以外の構造も持つ）。また灰色の背景で塗られたデータ構造（Radix Tree, Red Black Tree, HyperLogLog, Bloom Filter, Bounded Priority Queue）はインタビューにはまず出ない。あくまで、どのような実務上のデータ構造に繋がっているか図示したのみである。大事なことは、灰色になっていないデータ構造とその性質はマニアックでも何でもなく、知らないとしたら単に準備不足だと判断されるということだ。順に見ていこう。
データ構造の概念地図は、左上の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などを素早く表示するprefixクエリ（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の対処は重要である。書籍『みんなのデータ構造』に取り組んだ人は、平衡二分探索木としてスケープゴート木などを想起するかもしれないが、それらは難易度からしてコーディングインタビューではおよそ問われることはない。
格子状に並んだ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つ分だけのメモリを使うだけで複雑性を減らせるならば、それは設計上の優れた選択肢だと言える。
８．まとめ
この記事では、コーディングインタビューに必要なデータ構造とアルゴリズムの知識を概観し、それらの知識を身に着けることでエンジニアの実務にも応用できることを主張した。
次の記事では、インタビューを控えている人向けに、コーディングインタビューの当日に何を考えるかについて考えてみる。
*1:形式的には、ハッシュテーブルが実装する抽象データ型はUnsortedSet、二分探索木が実装する抽象データ型はSortedSetという明確な違いがある。UnsortedSetは要素の大小比較ができないかもしれない（要素が「異なっているか」だけは定義されている）集合であるのに対し、SortedSetは全順序集合、すなわち全ての要素のペアについて大小比較が可能な集合を表す。平衡二分探索木は、実行速度が対数時間になるという犠牲を払って、大小比較を前提とするnext-largestなどの追加機能を実現したものであるとも言える。この議論は『みんなのデータ構造』では1.2節にまとまっている。
