コーディングインタビュー本番に、最も血湧き肉躍り、そして最も意義深い瞬間は、そのような「初見だが既知の知識が応用できる」問題が出たときだと私は思う。有望な道筋（"You're on the right track"）を見つけ出すには、質の高い思考力とコミュニケーション能力が必要になる。手持ちの知識と、面接官（＝経験を積んだ同僚や上司）が与えてくれるかもしれないヒントや反応、あるいは自分が今から数分間の考察のあいだに段々と気づくかも知れない洞察を、有機的に組み合わせる力が必要になる。それらは会社にとっても、候補者個人にとっても、価値がある優れた力だ。ハッシュテーブルや二分探索は具体例に過ぎない。具体的すぎるほどの具体例を通して、汎用な課題解決能力を鍛えるものがコーディングインタビューだというのは、あまりに飛躍が過ぎる解釈だろうか。
たとえばSearch in Rotated Sorted Arrayの問題は、sorted arrayなのでbinary searchをすることは分かる。問題はdivide and conquerをどう設計するかであり、「どこでrotationが起きているのか」がmidより左なのか右なのかが分かると、片方はもうrotationが起きておらず、普通のbinary searchが使えることに気づけるかも知れない。
この図を見るうえでは、いくつか注意点がある。「集合の要素として含まれる」ことを表す記号 ∈ は雑に提示しているので深く解釈しなくてよい（例えば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）で次に訪れるノードはキューで表現できるし、数値の列を順に見ていく際のある時点における最小値はスタックとして記録できる。
連結リストに対するアルゴリズムと並んで顕著な例が、ソートされた配列のbinary searchにおける２つの繰り返し変数、lowとhighの管理である。二分探索（Binary Search）は、与えられたnコの数値の列がソートされていることを活用して、問題サイズをあれよあれよという間に半分、また半分と縮小していくことで、O(log_2 n)の時間で目的の値を探すアルゴリズムである。設計パラダイムとしては分割統治法（Divide and Conquer）に分類され、部分問題の数が常に1なので、Decrease and Conquerと呼ぶ人たちもいる。
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をやるだけで解ける。このような応用ができる柔軟さが、上記の組み合わせを筆者が気に入っている理由である。
最初のうちは、「こんな初期化、思いつかないだろう」と感じる問題もあるだろう。たとえば、「subarray sum equals kでcacheというハッシュテーブルを{0: 1}で初期化するとエッジケースが解ける」といったケースだ。このような問題の初期化も、3問ぐらい似たものを見れば、意外と苦もなく思いつくようになる。大事なのは、そのような自分の中でのパラダイムシフトを練習中に「あらかじめ」起こしておくことであり、決して本番の面接中のひらめきに期待してはいけない。
・交通ルールが想像以上に異なる。単に右側通行と左側通行の違いという話ではない。この方の記事にも書かれているが、赤信号でも一度停止したあとはタイミングを見て右折していいとか、そのルールに慣れたいまでも心のどこか奥底で信じられない。何なんだそのルールは。そのうえ、赤色の右矢印は「絶対に行くな」のサイン（単なる赤信号だと上記のルールでみんな進んでしまうため？）だとか、どう考えても認知に反している。極めつけは普通の赤信号に添えられたNO TURN ON REDである。この記載があると右折してはいけない…のだがそれって赤矢印と同じ意味では？？？なぜお前は赤矢印じゃないのだ？？？Youtubeで探してみたら他の州だと赤矢印の意味は違うとか出てきて頭が痛くなってきたのでこの話題はここで止める。かつ、赤信号で右折を待っている際はUターンする車に注意すべきだが、青信号になると対向車線からの左折車に注意を払う必要が生じる、また赤信号であっても独立した右折用のレーンが存在する場合は停止ではなく徐行で良くなるなど、事前にケーススタディをしておかないと、とてもじゃないが即座には判断できないケースが多すぎる。
左折するときに両車線で共有するCenter Left Turn Lanesは衝撃的ではあるが別に大して難しくないと思う。むしろ、本当に難しいのは4-Way Stopと2-Way Stopを瞬時に見分けることだと思う。ALL WAYやCROSS TRAFIC DOES NOT STOPと親切に書いてあればカンタンなのだが、それがない上に木が茂っていると泣きたくなる。この２つは停止後の操作が全く異なるため、正しく見分けないとその時点でクリティカルエラーとなる。
How to fail at almost everything and still win big（未訳）: 風刺作家Scott Adamsによる自伝。意志決定のうち、決定はしても実行が難しいタイプの事項というものがある（ダイエット、筋トレ、語学など）。それをgoalの設定ではなくsystemの導入という点で解決する、という極めて効果的なアプローチを提唱している。この本を読んだあとだと、村上春樹が『職業としての小説家』で語っている長編小説執筆のための日常（５時間執筆し、あとは走るなどして回復にあてる、を半年間繰り返す）は、一種のシステムとして解釈できる。
選択の科学：自分があまり納得できないような他人の意志決定の論理を知る上で参考になる本。原題はThe art of choosing。著者の両親は敬虔なシク教徒であり、結婚式の当日に初めてお互いの顔を見た。結婚相手のような重大な意志決定をなぜ顔も見ずに済ませるのか。実はそこには科学的に検証できるいくつかの社会的・心理的メカニズムが働いていた、ということを明らかにしている良書。他にも、「ジャムの試食コーナーを作る際に、ジャムの種類が増えるほど本当に細かなユーザーニーズにも対応できて顧客は幸せになるのか」という問題設定から、選択肢の数と幸福の関係を考察する。京都大学の学生にとっては、彼女の「砂糖入り緑茶」の話はとても興味深いでしょう。
Oh, my Ganesha: とあるショッキングな事件が起きたときにカーラが発した言葉。彼女は熱心なヒンドゥー教徒で、シーズン１の初回話ではヒンドゥー教の神であるガネーシャ象の前で供物を捧げるシーンが出てきたりする。彼女は別の場面ではOh, my godも使うので、何らかの感情の差があるのかと思われるが、よく分からない。ただ英語がグローバル化していることを示唆する決定的な表現だと感じた。
make the world a more equal and just place: 西海岸のスタートアップを描いたSilicon ValleyというTVドラマでは、スタートアップはどいつもこいつも宣伝文でmake the world better placeと使いまくっている、たかが日常の些事を数秒短くするだけのプロダクトでも、と批判されるシーンが出てくる。それと比べると、強盗や殺人が蔓延るナイロビでのこの発言は、たった３語の違いでも遥かに重く社会状況を反映している。
it's a little dull : 「この鉈はすこし刃が鈍い」 殺人や恐喝に使われる錆びた鉈の形容。
prank: からかい、悪ふざけ。嘘を付いて相手を騙すシーンが多発する。
thug: 悪党
I speak good English: カフィアスの台詞。日本でこんなことを言う人を聞いたことがない。ナイロビでの英語は、韓国やインドでの英語と同様に非常に癖の強いものなのだが、非常に感情は篭って聞こえる。何に起因するのかは分からない。
リト（メキシコ）
メキシコのスーパースタークラスの俳優。ゲイであることを隠して恋人と生活している。
We are on the location of Even Angels Must Earn Their Wings: 「映画〜の撮影現場 location に来ています」レポーターがリトとのインタビューで発した言葉。
be on a clock: 「時間がない」。捕われている仲間を早く助けるぞとノミが主張したときに使われた表現。We don't have timeとかを使わないところあたりがネイティブの語感という感触があり印象に残った。
Tell me about it: （同情して）「わかるよ」。ノミの恋人が口癖のように使う表現。たぶん彼女以外は作中で誰も使っていない気がする。
I'm kind of getting the hang of it: 「まあ慣れてきた」。感覚を共有しながら過ごすのは最初は気持ち悪いらしいが、だいぶ時間が経ってきたところでノミが言った表現。get the hang ofは「機械や道具の扱い方を実際に使って覚える」She got the hang of that software very quicklyのように使われる言葉。作中では「感覚共有は言語というツールよりも優れているか？」という問題提起がなされることがあるが、ノミがこの能力をツールとみなしていることを端的に示した表現。
Drama queen: もうウィズダムの説明をそのまま貼り付けるしか無い：「｟くだけて非難して｠ドラマクイーン, 悲劇のヒロイン〘注目を集めるために自己をドラマ化する人; 女性および同性愛者の男性に用いる〙」。リトは映画俳優のせいか感情の起伏が激しいのだが、そのリトと感覚を共有していると、どうにも…というちょっとした批難のシーンで使われた。
