コーディングインタビューの対策とその意義 (2/2):インタビュー本番中に何を考えるか
前回の記事(下のリンクを参照)では、コーディングインタビュー前日までに役立つ知識とインタビューの意義を考察した。
この記事では、コーディングインタビュー当日の思考過程について考えてみる。
コーディングインタビュー最中の思考
あなたがGoogleやFacebookといった、競争の激しいテック企業のコーディングインタビューを受ける状況を想像してほしい。
何ヶ月にも及ぶ練習を乗り越え、準備は万端だ。
だが、面接官が問題の設定を説明し始めると、自分の鼓動が速まっていくのを感じる。
なんてことだ、今までやったことない問題だ。
あれだけ解いたのに。
いったいどうアプローチすればよいのだろう?
どのデータ構造を使えば解けるのかも分からない。
動的計画法のような気も、単なる分割統治法の気もする。
それともgreedyに解けるのか?
どんな境界例が考えられるのか頭に思い浮かばない。
頭が真っ白だ。
このような心理状態に陥ることは、十分に想定される。なぜなら現実の問題は複雑であり、以前に解いた問題と全く同じではありえない。相当な数の問題が、過去問と類似性が見えない(あるいは、面接官は類似性を隠すように説明する)。コーディングインタビューで見たことのない問題を解くという、ミクロに危機的な状況で突破口を見つける方策は、より複雑な現実の問題に対処するときの方策でもある。
コーディングインタビュー本番に、最も血湧き肉躍り、そして最も意義深い瞬間は、そのような「初見だが既知の知識が応用できる」問題が出たときだと私は思う。有望な道筋("You're on the right track")を見つけ出すには、質の高い思考力とコミュニケーション能力が必要になる。手持ちの知識と、面接官(=経験を積んだ同僚や上司)が与えてくれるかもしれないヒントや反応、あるいは自分が今から数分間の考察のあいだに段々と気づくかも知れない洞察を、有機的に組み合わせる力が必要になる。それらは会社にとっても、候補者個人にとっても、価値がある優れた力だ。ハッシュテーブルや二分探索は具体例に過ぎない。具体的すぎるほどの具体例を通して、汎用な課題解決能力を鍛えるものがコーディングインタビューだというのは、あまりに飛躍が過ぎる解釈だろうか。
コーディングインタビューが単に無数の解答を覚えてなぞなぞを解く暗記運ゲー以上のものでありえるならば、それは「初見の問題を与えられた際に、どれだけ素早く、即ち会社にとって低コストで、ある程度効率の良いプログラムを正確に記述していけるのか」という問題解決能力にあるだろう。
人によって思考の手順は異なるので、一概に単純化できるものではないが(Interview Cakeのこの記事は興味深い)、そのような突破口を見つける方策として一般的に有効なものを以下に紹介する。
1.例の「動き」を分解する
多くの場合、インタビュワーは問題を説明するために入力例とその応答を実演する。例の動きを分解すると、以前に解いた類題との類似性が見えることがある。
- この動きはFIFOのキューじゃないか?
- いま最大値って頭をよぎったか?ということはPriority Queueか?
2.例を増やす
面接官は、「信頼できない語り手」である可能性がある。例を使って実演してくれた優しいその人は、もしかしたら本当に重要な例を避けているかもしれない。
- 要素が重複したらどうだろうか?
- 文字列が数万文字もあったら?
- 英語のアルファベットだけなのか、それともアスキーなら何でもありなのか?
- rootノードしか存在しない、あるいはそれすら存在しない?
- 反転しろとあるけど、もしかして全要素を反転するともとに戻る?
- rotatedされているとあるけど、もしかして最初の場所でrotateした場合は操作前と同一になる?
- 今、2つ目の要素を4と書いて、5に直さなかったか?
- もしかして偶数と奇数で扱いが違う?
- modの結果に何か意味がある?
また、low < highやlow = mid + 1などを書く際に、「等号あったっけ?」などと不安になったら、15秒程度でチェックできる小さな入力をその場で作り上げる。問題の入力とは別に、各行の入力と出力という部分問題については、この方策がよく効く。
3.データ構造をlinear scanする
上節で書いたようなデータ構造間の関係のメンタルマップが出来ていれば、以下の問いをlinear scanするだけで突破口が見つかることがある。
- Dequeを使うと解けるか?
- Priority Queueを使うと解けるか?
- Hash Tableを使うと解けるか?
- Binary Treeを使うと解けるか?
- ...
多くのデータ構造は瞬間で却下できる一方で、1つ2つ気にかかることがある。そうなったらチャンスだ。なぜそのデータ構造がうまくいきそうなのかを考察してみる。
4.アルゴリズムを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が使えることに気づけるかも知れない。
5.制約を緩める、前提を増やす
たとえばTwo Sumのような配列の要素を何らかの形で比べる問題で、入力が何かによってソートされていると仮定する。この際、全ての要素についての比較が必要なくなることに気がつけば、ソートするO(n log n)が実は全要素を比べるO(n^2)より効率の良いアプローチであることに気がつくかも知れない。Two SumはO(n)で解けるやり方があるのでソートして解くことはまずないが、「全比較してO(n^2)ではなく、ソートしてO(n logn)」が最適な計算量となる問題はいくつか存在する。
あるいは二分探索木において、探す要素が必ず存在すると仮定する。重複がないことを仮定する。これらの仮定は面接官への質問のなかで見つかることも多い。
6.自分の発想に対する面接官の言動に注意する
これが競技プログラミングと最も異なる点だと思うが、コーディングインタビューは独力での問題解決である一方で、時に面接官と2人での問題解決になる。
特に1問目と2問目をすんなりとこなした場合など、面接官は解けないことを前提として暴力的な3問目を尋ねてくる可能性がある。そうなると、いきなり正答例のアプローチを答えられる可能性はほぼない。むしろ、データ構造やアルゴリズムを声に出しながら検討する中で、面接官が何に反応しているかを探ったほうがいい。
大して親切でもないヒントのように聞こえても、実は多くの試行錯誤をカットできる強力な手がかりであったりもする。話の誘導の仕方、気を抜いて見ている瞬間の推測など、一人でコードを書いているときにはアクセスできなかった情報がかなり提供される。たまに全く反応しない熟練の面接官が居るが、そのときはそのときだ。
学習の指針
面接対策用の書籍”Cracking the Coding Interview”などでも、BCR(Best Conceivable Runtime、速さの上限からアプローチを逆算する)や、BUD(Bottleneck, Unnecessary work, Duplicated workという3つの最適化機会)と言った論理的な観点を用いて、プログラミングによる問題解決の過程をより汎用にすることを狙っているように思える。興味がある人は同書を読んでみて、自分にしっくり来る形にまとめ直してみるとよいだろう。
解けない問題を1時間も2時間も考え続けることを奨励する人が居るが、コーディングインタビューの問題に関してはそのような癖をつけるべきではないと思う。上記の思考過程は、3から7分程度で一巡しなければならない。それを過ぎたら、むしろヒントを見て、いまの7分間にそのヒントにたどり着ける道筋はあったか?答えでは優先度付きキューを使っていて、一瞬それを使うことを考えたのに、どうして使わなかったのだろうか?などを点検するほうが、よほど実践的で、なおかつ頭を使うと思う。
最後に、筆者の好きな計算機科学者、ロバート・フロイドがチューリング賞(計算機科学におけるノーベル賞に相当するもの)の講演原稿で述べた言葉を引用する。
「やっかいなアルゴリズムの設計を行ったときに味わった私自身の経験では、ある種の技術が自分の能力を高めるために非常に役立った。すなわち、意欲をそそる問題を1 つ解いた後で、そのときの『洞察』だけを頼りにして、同じ問題を再び最初から解く。この過程を解ができるかぎり明解かつ直接的になるまで繰り返す。そうして同様な問題を解くための、一般性があり、しかもそれがあれば与えられた問題に最も効果的な方法ではじめから接近できるというようなルールを探し出す。そのようなルールは永久に価値のあるものになることが多い」
(書籍『問題解決大全』の方策番号26、「フロイドの解き直し」の章より引用)
(ロバート・フロイドは、ワーシャル・フロイド法を考案した人物である)
コーディングインタビューが得意な人は、「それがあれば与えられた問題に最も効果的な方法ではじめから接近できるというようなルール」を自然に把握して真っ先に使うことが多い。インタビューの練習の際は、ぜひこのような汎用的な視点で臨んでみてほしい。最初はうまく行かなくて悔しくても、続けていくうちに、いつか自分でも驚くほどの解法発想力が身に付くはずだ。
コーディングインタビューの対策とその意義 (1/2)
1.コーディングインタビューとは何か
コーディングインタビュー(Coding Interview、またはProgramming Interview)とは、1時間ほどの制限時間内に小さなプログラミング問題を解かせる面接形式のことをいう。プログラマー、またはデータサイエンティストなどの採用試験として、米国を含むいくつかの国で用いられている。「物理的なホワイトボード上にプログラムを書く」という形式で実施されることが多い。「オンライン上の共有エディタで書く」といった形式のこともある。Googleなどは自社のYoutubeチャンネル動画でも説明している。
出題される問題としては、例えば、「複数の数字numbersと整数kが与えられたとき、合計がkとなる数字の組を1つ出力せよ」といったものがある。この問題は有名なので通称が付いており、Two Sumと呼ばれる。
このTwo Sumという問題は一見すると余りにも簡単で、選抜するための問題として機能しないように思える。多くのプログラマは「2重のfor文を使うとTwo Sumが解ける」ことはすぐに思いつくだろう。だが実際に面接でその解法を説明すると、面接官は間違いなく「もっと効率的な方法で解いて下さい」と指示を返す。そしてコーディングインタビューの準備をしたことがないプログラマは、例え10年の実務経験があったとしてもそこで困ってしまうことだろう。Two Sumは2重の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せよ」など基本的な操作がそのまま課題になることが多く取り組みやすい。また競プロでは単に問題が解ければよいが、コーディングインタビューではコミュニケーションの側面が多分に含まれる。例えば、意図的に曖昧に示された問題に対して的確な質問をすることで仕様を正確に把握したり(「数字に重複は?」「入力は空ではない?」など)、プログラムを書き始める前に解法を簡潔に面接官に説明したり、正しいプログラムを書いたあとで適切な入力例を用いて動くことを検証したりと、意外とやることが多い。
以上の観察から言えるのは、
コーディングインタビューは、実務のプログラミングとも競技プログラミングとも少し異なる、独自の対策や訓練が必要なものである
ということだ。コーディングインタビューに必要なのは、実際のプログラミングの力というよりは、「コーディングインタビュー力」なのだ。
2.コーディングインタビューの意義・効用
コーディングインタビューは役に立たないという論評は多い。たとえばRuby on Railsの著者であるDHHは「私はなぞなぞはしない("I don't do riddles")」と言って、この面接形式を厳しく批判している。多くのプログラマが使っているHomebrewの開発者であるMax Howellが、二分木を反転できなかったからGoogleに落とされたと語った事実もある。
コーディングインタビューに批判的な人々の主張の大筋は次のようなものだ。
「やっかいなアルゴリズムを設計できる力が必要とされる部署も世界のどこかにはあるだろうが、情報システムを作る大多数のプログラマーにはホワイトボード上で効率の良い基礎的なプログラムを書くスキルなど必要ないだろう」
なるほど確かに、「マージソートやQuick Selectなんて、カリッカリに最適化された専用のライブラリがどうせ存在するだろう」という気持ちも分かる。一方で、システム設計のインタビューや「過去のプロジェクトについて話してください」といった形式の面接では、バグを作らないように細部のシミュレーションを行う受験者の姿は視認できないだろう。そのような側面を十分に代替する他の面接形式には未だ出会っていない。効率が数億倍のプログラムを書けるかどうかはもちろん、バグが少ないプログラムを書けるかどうかは採用する側にとって大いに重要な点だろう。バグはソフトウェアの将来の価値を損ない、時に人命に関わることもあるからだ。
例えば、
- 2014年にアメリカの警察緊急通報911の電話受付プログラムが6時間以上も応答不能になり、1,100万人以上が影響を受けた。原因は単純なバグだった。この事件はネットフリックスのコーディングに関するドキュメンタリーでも取り上げられている。
- 富士通の子会社が作った会計システムの中に多くのバグがあり、イギリスの郵便局で働く550人が「数字が合わない」と横領の濡れ衣を着せられた。中には自己破産に追い込まれ、最終的に最低賃金で働く状況にまで追い込まれる人もいた。裁判所は約8億3400万円の和解金の支払いを命じた。(出典)
3.これからコーディングインタビューを受ける人へ
以下では建設的な見方を深めるために、受ける前に知っているとよい知識と、インタビュー中の思考過程を考察する。コーディングインタビューなしで採用を行う有名企業も存在するが、業界全体からコーディングインタビューが消えることはないだろう。選抜という面だけでなく、訓練という面からも、従業員の質を高める上でまあまあ役に立つからだ。 労働者が自身の雇用流動性を高めるためにこの面接形式の対策をするのは、妥当な選択肢だといえる。
なお、読者の期待値を正しく設定するために言うと、筆者はコーディングインタビューが苦手である。競技プログラミングについてはサッパリだ。しかし、学生時代に面接対策として150問から200問くらいの問題を解いてきたので、平均的な問題に関しては対応ができる。以下の内容はそのようなエンジニアが書いたものとして読んでほしい。また、何か大きく見落としている点に気付いたら、ぜひ教えてほしい。筆者は面接官としての訓練を受けたことがないので、見方が未熟である可能性は高い。
4.コーディングインタビューに必要なデータ構造の知識
(この段落以降は、アルゴリズムとデータ構造の勉強をしたことがない人には読みにくい箇所が多々あるため、目的に応じて適宜飛ばしてもらえれば幸いである。)
筆者の理解では、およそ80%強のコーディングインタビュー問題を解く上で必要になるデータ構造の知識とその関係は、以下のようなデータ構造の概念地図として表せる。
青字がそのデータ構造が得意とする(=効率的に行なえる)操作で、赤字がそのデータ構造が苦手とする操作を表す。全体として、青と赤が交互に配置され、たった1つ最強のデータ構造を使えば全て解決できる、と言った都合の良い状況ではないことが確認できる。
この図を見るうえでは、いくつか注意点がある。「集合の要素として含まれる」ことを表す記号 ∈ は雑に提示しているので深く解釈しなくてよい(例えば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)については素早く対応できない。例えば、以下の2つの操作だ。
- 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の数を数える問題など)。グラフについては長くなるので、各自で整理してほしい。
以上のような思考回路を一度作ると、コーディングインタビューにおけるデータ構造の選択はほぼ容易になる。
5.データ構造の概念地図を見るときの注意点
上図には、更にいくつか形式上の批判ができる。例えばハッシュテーブルのルックアップの計算量が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倍くらいの手数がかかる?)というのは、何とも、もどかしくて印象的だ。ヒープは「雑然と積み上げたもの」という語義を持ち、最良のもの以外の位置をかなり緩く決めたデータ構造である。その適当さの負債を、実行時間として後払いしているようなものかもしれない。
データ構造に関する知識は上記のように、多少の罠があるものの大して量がない。これだけで済むならば、そこらの資格試験より簡単だろう。むしろコーディングインタビューにおける難関は、そのデータ構造の上で動くアルゴリズムの方である。
6.コーディングインタビューに必要なアルゴリズムの知識
コーディングインタビューという特殊な問題設定において、いちばん候補者の間で理解度の差が際立つのはアルゴリズムの知識だろう。これらは即座に思いつくことが極めて難しく、数が多く、なおかつ習得も一度見ればできるという類のものではない。
特に大変なのは連結リスト(Linked List)に関するアルゴリズムである。連結リストは、前述した二分ヒープやハッシュテーブルと比べると極めて単純な構造をしていることから、「学ぶことなどあるのか?」という印象を持つかもしれない。
だが侮ってはいけない。実際のコーディングインタビューであなたを叩きのめすのは、この一見すると人畜無害な連結リストかもしれないのだ。
連結リストの問題においては、細かな技法がものを言う。「リストを反転させる際には、前の要素と次の要素をprevとnxtとして一時変数に保持しておく」、あるいは「dummyノードをheadノードの前に付けることで、場合分けを減らす」、また「リストの真ん中に存在する要素を効率的に見つけるには、2コずつ要素を飛ぶfastとその半分の速度で動くslowを定義し、fastが動けなくなるまで前進を続ける」などと言った、初心者からすれば摩訶不思議でとても思いつかない技法が多用される。99.5%の人にとって、これらの技法は、数年の実務を積んだとしても自然と身に付く代物ではない。このギャップがコーディングインタビューを事前に訓練しないと解けないものにしている。仮にあなたがこれらの技法を何も知らずに臨んだ場合、待っているのは何も出来ず逃げ出したくなるような30分間だろう。
連結リストに対するアルゴリズムと並んで顕著な例が、ソートされた配列のbinary searchにおける2つの繰り返し変数、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のアップデートを「右に」偏らせて、2回binary searchをやるだけで解ける。このような応用ができる柔軟さが、上記の組み合わせを筆者が気に入っている理由である。
このような地道な思考の訓練を積み上げていくのが、コーディングインタビューにおけるアルゴリズムの準備となる。「再帰や基本的なパターンがsecond nature(深く身に付いた習慣)となるまで訓練しろ」とかつて友人に言われたが、まさにそのとおりである。union-find木を瞬間で思いついたり、複雑なイテレーターを使い出せる境地には至らなくてよい。そこはもはや異世界である。しかし一般的な問いを自然に効率よく解けるぐらいまではたどり着ける必要がある。そして、それは時間を多く投資した地道な訓練以外では難しい。
7.モチベーションと実務との関わり
「なぜこんな引っかけパズルや発想一発勝負のような問題に就職を左右されねばならないのか…」と考えると辛いかもしれない。筆者もそうだった。しかし、ある程度の問題を解いたところで大体「一回目にどれくらいの真剣さで向き合えばよいのか」が掴め、かなり楽になった。
どれほど真剣に向かおうが、パターンを知らなければ短時間では効率的に解けない問題が山ほどある。そういう問題はサクサク復習に回してしまうことで、パターンをより早く見つけられるようになったと思う。何事もそうだが、地図を手に入れれば、難所の攻略法も掴めるものだ。
最初のうちは、「こんな初期化、思いつかないだろう」と感じる問題もあるだろう。たとえば、「subarray sum equals kでcacheというハッシュテーブルを{0: 1}で初期化するとエッジケースが解ける」といったケースだ。このような問題の初期化も、3問ぐらい似たものを見れば、意外と苦もなく思いつくようになる。大事なのは、そのような自分の中でのパラダイムシフトを練習中に「あらかじめ」起こしておくことであり、決して本番の面接中のひらめきに期待してはいけない。
練習に際して心の支えになる事実もある。それは、上記で説明したような思考訓練が実務にも役立つということだ。著名なソフトウェアエンジニアであるMichael Feathers氏は、入力データを「都合のよい性質を持つ新しい入力データの集合」に拡張することで場合分けを劇的に減らせる、ひいてはバグを減らせると言っている(この動画の16分から20分あたり)。この動画中の例は、連結リストでdummyノードを付けるテクニックに似ている。ソフトウェアエンジニアは複雑性と向き合う職業であり、要素1つ分だけのメモリを使うだけで複雑性を減らせるならば、それは設計上の優れた選択肢だと言える。
8.まとめ
この記事では、コーディングインタビューに必要なデータ構造とアルゴリズムの知識を概観し、それらの知識を身に着けることでエンジニアの実務にも応用できることを主張した。
次の記事では、インタビューを控えている人向けに、コーディングインタビューの当日に何を考えるかについて考えてみる。
*1:形式的には、ハッシュテーブルが実装する抽象データ型はUnsortedSet、二分探索木が実装する抽象データ型はSortedSetという明確な違いがある。UnsortedSetは要素の大小比較ができないかもしれない(要素が「異なっているか」だけは定義されている)集合であるのに対し、SortedSetは全順序集合、すなわち全ての要素のペアについて大小比較が可能な集合を表す。平衡二分探索木は、実行速度が対数時間になるという犠牲を払って、大小比較を前提とするnext-largestなどの追加機能を実現したものであるとも言える。この議論は『みんなのデータ構造』では1.2節にまとまっている。
カリフォルニア州の運転免許を取得するまで
学生として渡米し、およそ2年目にしてカリフォルニア州の免許を取得した。
最初に想定していたよりはるかに辛く長い道のりだったので、
今後免許を取得する予定の同じ境遇の人に向けていくつか気づいたことを書き記しておこうと思う。
なるべく正確に記すつもりだが、ルールはコロコロ変わるし私自身が思い違いをしている可能性もあるので、疑問点があれば個々人でDMVに問い合わせてほしい。
まず運転免許を最初に取ろうと思ったころの自分に一言アドバイスするならこれだ。
運転免許の取得は思ったほど簡単ではない
私はペーパードライバーだったものの、日本で運転免許を一発で取得していたし、ネットには大量に同じような状況から免許を取得した日本人の体験談が溢れていたので、免許取得というのは片手間にサクサクと済むようなものだと思っていた。片手間で済むのは確かなのだが、簡単かというとそうではない。実技試験で2回落ちても何ら不思議ではない、4回落ちたら流石に何かに呪われている、ぐらいの難易度であると言っていいと思う。少なくとも全員がほぼ1回で受かる日本の実技試験のようなザルでは全くない。
それにはかなり多くの理由がある。
・クリティカルエラーがかなり起きやすい。実技試験は15個(!)までミスが許されるが、それとは別に、一回ミスしたらその時点で失格となるクリティカルエラーと呼ばれるミスが多種存在する。このクリティカルエラーが結構キツく、特にImproper Speed(不適切なスピード)とToo cautious(過剰注意)は練習中に誰かに言ってもらわないと、自分がそれに該当していると気づけないと思われる。州や各DMVにもよるだろうが、私が聞いた限りでは各道路の制限速度から10mph上あるいは下にズレるとその時点で失格となる。ベイエリアでは大抵の住宅街は25mphで一般道は35mphなのだが、たまにまるで一般道のような住宅街やその逆があるため、そこで勘違いをするとそれでアウトになる(その上、結構な数の制限速度サインが木に隠れている。自分が受けたサンタクララの場合、(実際のテストで走ったか全く記憶にないが)Homestead Roadにおける40mphのサインがほぼ9割木に隠れていて、しかもそこから少し走ると30mphのサインが出てくるので、こんな配置をするなんて冗談かと思った)。
・交通ルールが想像以上に異なる。単に右側通行と左側通行の違いという話ではない。この方の記事にも書かれているが、赤信号でも一度停止したあとはタイミングを見て右折していいとか、そのルールに慣れたいまでも心のどこか奥底で信じられない。何なんだそのルールは。そのうえ、赤色の右矢印は「絶対に行くな」のサイン(単なる赤信号だと上記のルールでみんな進んでしまうため?)だとか、どう考えても認知に反している。極めつけは普通の赤信号に添えられたNO TURN ON REDである。この記載があると右折してはいけない…のだがそれって赤矢印と同じ意味では???なぜお前は赤矢印じゃないのだ???Youtubeで探してみたら他の州だと赤矢印の意味は違うとか出てきて頭が痛くなってきたのでこの話題はここで止める。かつ、赤信号で右折を待っている際はUターンする車に注意すべきだが、青信号になると対向車線からの左折車に注意を払う必要が生じる、また赤信号であっても独立した右折用のレーンが存在する場合は停止ではなく徐行で良くなるなど、事前にケーススタディをしておかないと、とてもじゃないが即座には判断できないケースが多すぎる。
左折するときに両車線で共有するCenter Left Turn Lanesは衝撃的ではあるが別に大して難しくないと思う。むしろ、本当に難しいのは4-Way Stopと2-Way Stopを瞬時に見分けることだと思う。ALL WAYやCROSS TRAFIC DOES NOT STOPと親切に書いてあればカンタンなのだが、それがない上に木が茂っていると泣きたくなる。この2つは停止後の操作が全く異なるため、正しく見分けないとその時点でクリティカルエラーとなる。
・一人暮らしの人は練習量が制限される。カリフォルニアで筆記試験を通ると貰える仮免許は、カリフォルニア州の免許保持者が同乗した状態でしか運転の練習を許可しない。そしてどうも国際免許証を持っていてもその制約は解除されないようで、パートナーがいる人や免許持ちのルームメイトがいる人は頼んで運転の練習に付き合ってもらうなどできるだろうが、僕のように免許持ちのルームメイトがいない人にとっては、これはかなり大きな制約となる。なお、一部の州においては国際免許証が通用する様子?
・DMVのシステムは基本的に不安定。筆記試験に初めて向かった日、1時間以上待たされたあとようやく窓口の人と話せると思ったら「今日は筆記試験用のシステムがダウンしてて再開の見込みが立たない。また別の日に来なさい」と告げられた。この日は、ああ、世の中には変えようのない理不尽というものがあるのだ、と思った。こちとらエンジニアなのでヤンワリと再起動してみましたかとか別のパソコンはありませんかとかしつこく聞いてみたが、そんなものが通じるDMVではなかった。なので私は筆記試験に落ちていないにも関わらず大切な平日の午前を二回筆記試験に使った。これがアメリカのDMVクオリティである。もちろん保障や謝罪は存在しない。
・試験官ごとの特質の分散が大きい。全くこちらに人間としての興味を示さない試験官というのが居る(同時に敬意も感じられなかった)。目を一度も合わさなかったし、名前も聞かれなかった。彼ら彼女らの判断が正当であるのかどうかは僕は経験不足で判断できない。
・路上で見かける車の運転が信用できない。カリフォルニア州の運転ルールをきちんと学んでわかったのは、以下に普段利用しているライドシェアアプリの運転手やあるいは街で見かける車が交通ルールを守らずに運転しているか、ということだった。もちろんいくつかのルールはかなりの違反者でも守る(自身に危害が加わるため)のだが、道行く車を眺めているとすぐに違反が目につく。なので、ノイズだらけの弱教師あり学習のようなマインドセットで望まないと遵法の作法が身につかない。
・近日の予約が取れない。9月の2週目ぐらいに予約して一番近くで取れたのが11月の3−4週目の月曜午前だった。どうもここにはおそらく何らかのハックがありそうなのだがついぞ調べる機会は無かった(なくてよかった)。
筆記試験について
ベイエリアではおそらく、サンノゼのDMV(住所が111番地で終わるもの)が唯一、予約なしでの筆記試験を受け付けている。休日は空いておらず平日は基本8時から空いているが、水曜日だけ9時なので要注意。テック系の会社は水曜日をノーミーティングデーとしていることが多いので、このトラップが地味に痛い人もいるのではないだろうか。
実技試験の練習について
私は前述のように練習の相手を頼める相手がおらず、仕方ないのでDriving Schoolの講師に同乗をお願いすることにした。お金はかかるが、それでも日本で免許を取ったときの費用と比べれば大幅に安かった。安全には代えられない。
最初はYelpでDriving Schoolで検索して、トップに出てきたスクールに頼もうと思ったのだが、どこも人気のようで数週間待ちだった。仕方ないので2ページ目ぐらいに出てきた若干二流みたいなスクールの先生と運転練習を行なったのだが、どうもイマイチだった。いや確かに学ぶことはあるのだが、練習中に鼻歌歌ってるし、録音しておけば罵倒と解釈してもいいのでは?みたいなフィードバックを返すこともあるし、非ネイティブの英語なので説明がたまに不十分に感じるしということで、お試しで仲良く別れた。
その後は、恐らく唯一の日本語対応の運転学校ということで、あまり期待せずにJoy Driving Schoolに依頼した。これが大当たりだった。Google Mapsの口コミでは低評価だったため警戒していたのだが、実際には期待以上の教育成果を与えてくれた。自分は2人の日本人講師に教わったのだが、どちらも完全にプロ意識に溢れている上、知識が豊富で(ワイパーが何秒ごとに動くのかすら当然のように答えていた)、議論の緻密さやトリックが僕の好みだった。そして自分の運転のどこに問題があるのか本当に常によく観察していた。右折や左折の各条件と対応、特殊な道路状況での対応など、運転がここまで奥深いものだとは全く想像もしていなかった。彼らから教わったあとはUber運転手の操作に不満を感じるようになった。
実技試験について
サンタクララのDMVで受けた。10時前半の予約で、10時には現地に付き、11時半頃には結果が出ていたように思う。サンタクララのDMVはこのサイトでは「人が少なく道がすっきりして走行しやすい」と評されているが、私のような未熟者からすれば初心者殺しの不可解な交通ルールに満ちた魔界であった。ようつべに上がっている動画は恐らくそのサイトのパターン3を通っている動画なのだろうが、私が実技で通ったルートはこのどれでもなかった気がしてならない。なので結果的に、単にDMVの周りを(これらのルートとは関係なく)何度も何度も練習したのが功を奏したと言える。そのうちに「この道からこの小道に右折した直後のサインがいつも見にくい」とか「このサインを初見で読んで正しく運転できる人間は尊敬に値する」ということに気づくので、エピソード記憶とともに道の攻略法が掴めてきた。
あと、一度だけDMVから少し離れたところでなんとなくグルッと回っていたときがあったのだが、結構交通ルールとして共通するパーツが多くて驚いた。あんな形をした道はてっきりあそこだけだと思っていたら、すぐ近くに類似形があったのである。道というのもパターン認識なのだなあとしみじみしていた。
なお、別の州で免許取得を試みた友人はカリフォルニアと比べると比較的試験がカンタンだったらしく、もしかしたら穴場の州というのがあるのかもしれない…。
最後に
Wikipediaによると、ラウンドアバウトや一方通行などの交通ルールを制定する契機となったのは、およそ110年前のウィリアム・フェルプス・イーノ(William Phelps Eno)という人物だそうだ。ニューヨーク生まれの彼は、9歳のときに交通渋滞に巻き込まれ、「なんでこれだけの馬車しかないのに交通が進まないのだろう」という原体験を持ち、その後いくつもの交通ルールを提案したとのこと。
私にとって運転というものは、そもそも何百キロもある鉄の塊をあれだけ近距離で走らせるという発想自体が恐ろしいし、面倒でも身につけなければならないことという側面が強いものだが、それでも一方である一定の規則のもとにまあまあの秩序が保たれていることには尊敬と関心を覚える。こういう記事を読む人は、恐らく私と同じく運転にさほど興味のない(しかし生活上取らざるをえない)という人が多いだろうが、世の中には運転ルールの細部まで理解して安全な運転を行ない更には伝授する人もいるし、またもっと振り返ればそのルール自体をゼロから生み出した人も居るわけである。そう思うと、運転というものの中に存在する人類の叡智が感じられて、練習が少し面白くなるかもしれない。私は結構それでノるタイプなので、なんでこの信号はこうなっているんだろう、と考えると退屈が紛らわせた。もちろん、非合理にしか思えない標識も多いんだけどね…
新大学生が早めに気づくとよい海外大学院という進路
この記事は、4月から日本国内において新大学生となる人たちが、自分に海外大学院という進路があると気付いたときには遅かったとなるのを防ぐための記事です。
自分は東大の文科3類に文学部志望として入学し、2年次の夏に理転して情報系の学科へ進学したのち、大学院としてニューヨーク市のコロンビア大学の計算機科学科(Computer Science学科)に進学、18年の春から情報系の学生にとって夢の地域であるカリフォルニア州シリコンバレーで新卒のプログラマーとして働くという、比較的珍しい進路を取っています。
過去を振り返ってみて、進路選択の部分で運に助けられた部分が多くあったことを深く自覚しました。そのため、新入生が早めに気がついていないとマズい部分について指摘を行い、運が絡む要素の最小化を手助けしたいと思い、この記事を書くことにしました。
要点を一言で言えば、理転を考える場合は入学直後、海外の大学院への進学を考える場合は、大学2年の夏には考え始めないと間に合わなくなります。大学院は博士課程に所属した場合で最長で6年ほど所属することになりますが、それぐらい長い期間に及ぶ決定を、入学して1年半後にはもう考え始めておいたほうが良いというわけです。ここで「間に合わなくなる」とは、出願書類が間に合わなくてやむなく1年留年する、あるいは国内で進学して仮面浪人の院バージョンをする羽目になる、などを指します。両親からの反対が強くなったりするかもしれません。道が途絶えるわけではありませんが、不必要に困難になることは間違いないでしょう。
弁護士になる、医者になるなども数年前から行動し始めないと達成できない類の進路でしょう。しかし僕はその分野に疎いため、大学院での留学という選択肢が最低でも2−3年前から計画する必要があるものだという主張に焦点をあてます。
日本には東大という素晴らしい大学があるのに、どうして調べるのが大変そうな海外に目を向ける必要があるのでしょうか?たった一回の大学と大学院の経験に基づいた意見なので誤っているかもしれませんが、しかしそれでもコンピューターサイエンスで博士課程の場合、アメリカの大学院はほぼ全てにおいて日本の大学院の上位互換です。そして僕が知らないだけで、他のほぼ全ての分野でそうなのでしょう(アメリカとは限らないですが)。
もっとわかりやすく言ってしまうならば、東大は二流の大学です。
率直に言って、一流の小学校、中学、高校、大学、大学院に行った方が良いです。初期に配られるカードが全く違うので。大人は、これははっきり教えた方が親切だと思います。すでにカードが配られている人に逆転の可能性を説くのはそれはそれで意味がありますが、これからの人に誤解を与えるのは罪です
— 瀧本哲史bot (@ttakimoto) November 4, 2013
いつだってリストには漏れがあるものなので、代ゼミの偏差値表で一番上だったからと東大を選ぶようには名の知れた海外の大学院を選んでほしくはありませんが(たとえば学部だとミネルヴァは今ほとんどのリストに載っていないでしょう)、しかし目線は常にできるだけ上を見ていてほしいと思います。あなた方がいま東大に受かったとか落ちたとかは問題ではなく(どうせもう一度試験をすれば合格者の3分の1は変わります)、今後10年間でまだまだ飛躍的に成長する可能性を秘めています。
僕が大学院で所属したコロンビア大学はコンピュータサイエンス(CS)においてトップ5にはどう考えても入りませんが、それでも教授は引用数2万超えの大家だったり有名なプログラミング言語を最初に立ち上げた人だったりがゴロゴロしていますし、そういう人たちと一対一で話す機会もあります(ちなみに、そのときにどんな英語を自分と相手が喋るか、想像が付きますか?)。チームメイトがAmazonシアトル本社のインターン生だった、Googleシリコンバレー本社に就職した、ということもしょっちゅう起きます。東大で学部生をしていたときの数倍刺激的かつ教育的な日々を過ごせました。
それはちょうど、地方の名も無き学校で暇をしていた高校生の僕が、国内ではトップとされる東大に進んで数倍刺激的かつ教育的な日々を過ごしたと感じたのと同じ構図になっています。コロンビア大学で出会った同級生たち、すなわち中国のトップ大学である清華大学卒の友人や、インドのトップ大学であるインド工科大学(IIT)卒の友人も、ひょっとしたら似たようなことを言うかもしれません。いつだって辺境にはリソースが欠乏しています。それは、コロンビア大学があるニューヨークからシリコンバレーに移って、現代最高峰のソフトウェア・エンジニアリングを目撃し始めた今もまた、感じ始めたことです。これから数年間で出会う世界に、ワクワクせずには居られません。それはかつて自分が初めて東大に来たときの高揚感にも似ています。大学を卒業してもなお、そのような期待感を持ちながら日々を過ごせることは、とても幸せなことだと思います。
参考: 大学院の第2学期感想
しかしその幸せは、決して自動的にはやってきません。
2年の夏というと、東大で言えば進学振り分け(=所属部門の決定)の希望先を提出した段階で、博士課程のことを考え始めないといけないわけです。
近年は博士課程に(僕は修士課程のみですが)進学した人たちによる極めて詳細かつ有益な出願準備ブログも存在するため、一読しておくと、受験が終わったあとの世界について想像力が広がるかと思います。際立った記事を以下に3つ紹介します。情報量がとても多いので、保存しておいて時間があるときに読んでみてください。これらを見ると、なぜ2年ぐらいもの準備期間が必要なのか感覚が掴めるかと思います。
思考実験
なおはじめに断っておきたいのですが、この例は特定の個人への攻撃を全く意図していません。実際にはあてはまる個人の存在しない藁人形とも言われかれない例であり、しかし、ややもすると大学生(特に「自分たちはもう安泰だ」と勘違いしている東大生)はこのモデルに近づきかねません。あくまで目的は、長期的/計画的かつ丹念に調べ考量して進路を決定することは、国内最高峰の大学に在籍していたとしても自動的に授業で学べることではないという重要な事実をしみじみと実感することにあります。
悪い例:
典型的なケースです。進路について考えるのは受動的、周りが騒ぎ出してからだけなので、二年生になった4月になって慌てて進学先のパンフレットを探し始めます。生物やってきたし生物系のA学科かな、となんとなく決め、あっでもサークル打ち込みすぎてて点数足りないからB学科にするかと変えます。決定までに10分もかからないでしょう。Nintendo Switchを買うか悩む時間のほうが長いかもしれません。「人間は難しい決定のほうがパッと決めてしまうミスを行いがち」と行動経済学が説くそのままです。本当は、生物かも、でも自分のやりたいこと/できること/やるべきことを考えたとき、本当に他の選択肢はないのかな、とそこから何段階にも検討を重ねるべきなのです。
自身の専攻変更について考える過程が抜けていることは、極めて大きな機会損失をもたらします。専攻は自分の世界観を決める、誰もがほぼ完全に制御できる数少ない変数の一つです。西洋史専攻は西洋映画を見るたび小道具の時代考証が気になって話に集中できないと言います。化学専攻は健康食品の説明を見るたびに???となると言います。僕は計算機科学専攻なので、人工知能に関する日本の報道を見ると大抵?となります。あなたは世界のどの詳細に注目するか、そのレンズを決めることになります。全てを知ることはできず、それは人脈が担当します。
興味をベースとして何らかの学科に進んだとします。たった2年間しかない専門課程では詰め込んだとしても授業として学べることがそんなにないため、「う〜んなんかあんまやってることは合わないけど、今更変えるのあれだし〜しかもここまでやったし〜」と多くは何となく現専攻の修士への進学を選びます。ここでも、自身の専攻変更について考える過程が失われています(僕の指導教官は学部が物理で院から情報系に移行しました)。とりわけ、海外の大学院への進学を検討していません。また、学部卒で働き始め、問題意識を持った段階で大学院に戻るという、最も意義の大きい大学院進学パターンの検討が抜けています。博士課程では、社会人博士という選択肢もあります。コロンビアには夜間の授業履修だけで学位取得をした社会人修士も何人か居ました。何となくで修士を取ると、そういう道がほぼ途絶えます。
大学院で修士論文を書き上げました。しかし修士1年から既に始まった就活で忙しく(そういえば学部では就活の情報集めすらしていなかったことにここで気付く)、あまり納得のいく成果とは言えません。就職先は学部時代の内容とはあまり関係のない、就活ランキングで上位に上がっていたコンサルティング企業です。大学で学んだことがどう活きたのかまるで不明瞭です。
そもそも、国内市場が縮小するなか海外で生き残りをかけるグローバル企業が増えている現代、製薬や土木などの専門性もなく日本語しか話せないだけの人材が企業支援の過程でどれだけの価値を持つのでしょうか?彼らにはインド人クライアントとの会議もプレゼンも任せられないし、かといって人と接しない資料収集・制作業務が特別秀でているわけでもない(そもそも英語の資料が読めて英語でまとめられないと、業務の幅は極端に狭まります)。大学6年間は人生を豊かにする教養のためにあったならば、今自分が直面している人間としてのこの貧しさはなんなのか。会社に不満があるのに、上司に不満をぶつけても首を切られないだけの「人としてのかけがえのなさ」はおろか、スキル要件を満たしておらず転職できない、毎日夜11時まで働いて家族との時間も取れない(人工知能ブームの真っ只中にいて多忙なはずのGoogleの子会社の社長ですら家族との時間を取っていますし、アメリカでのプログラマーの就業時間帯はかなり長いほうでも8時 - 6時といったところでしょう)、それではまるで会社ではなく、グローバル化が進む資本主義社会の中で、牢獄にいるようなものではないか。
一言で言えば思考停止に陥っており、効用を考慮せず多数派の進路を受動的に選び続ける羽目になります。
以上の例には、3箇所大きな意志決定の転換点が登場しました。
- 3年次以降の専攻の決定(今のあなたから見て、1年半後。考え始めるとしたら今)
- 学部卒業以降の進路(卒業の1年前には定めているとして、3年後。考え始めるとしたら1年半後)
- 修士卒業以降の進路(卒業の半年前には定まっているとして、5年半後。考え始めるとしたら3年後)
参考: 東大法学部卒、司法試験と就活に失敗、30歳フリーター(この手の記事は過度に絶望的な側面だけを切り取る傾向にあるので、批判的思考力よろしく、差し引いて読む必要があります。世の中は、30歳フリーターからでも、上記のような専門性のないコンサルタントからでも成功できない訳ではありません、ただ「ものすごく険しい」だけです)
さて、以上のような進路選択スゴロクを行なった場合、そもそも出願可能な程度にGPAを確保するとか英語力を底上げするとか教授に共同研究を持ちかける(海外で博士を取った人ならば、誰でも快く協力してくれます、どれだけ価値のある選択肢であるか知っているからです)と言った課題は頭に上りません。なぜならこれらは、数年前から進路を考えたときに浮かぶ長期投資的な論点だからです。
ではどうするか:
未来というものは、決して確定されて予定調和的に辿りつくものではなく、あなた自身の選択により全く異質なものにできます。戦略を決め、柔軟に計画し、行動を継続することによって、あなたの未来はまだあなたが想像をしたことがないものになりえます。大学1年のころ、まだプログラミングという言葉すら知らなかった僕は、数年後にシリコンバレーのIT企業で、世界各国から集まった同僚たちと英語で議論しながら、職業としてプログラムを書いているとはまったく想像しませんでした。
選択もまた、過去の先人から学ぶことにより、より正確な制御が可能になる対象のひとつです。次の記事では、漫然と進路を決めていては論点や選択肢にすら気づけないという観点から、意志決定、そして関連する分野として問題解決の力を磨くための資料を紹介します。興味のある人は覗いて見てください。
この日本は沈みかけており、あなたが沈まないとしたら、それはあなた自身にとっても、社会にとってもとても価値のあることです。先人のいない道を行くのは怖いかもしれませんが、同じように挑戦を続ける日本人は予想以上に多く居ます。あなたが自分にできる範囲で少しずつ、慣れてきたら大胆に、自分の未来を切り開いていけるよう願っています。
意志を決定する力を磨くための資料
選択肢の中から選ぶ(「選択」や「意志決定」と呼ばれる)というのは、学習可能なスキルです。原理を知れば知る程に、自分がより満足の行く選択を行なう可能性が高まります。
大学は知識を教える場所としては一流かもしれません。
しかし意志決定の方法論を教える場所としては間違いなく二流以下です。
以下では、自分が進路選択、住居選択、居住エリア選択、職業選択をする上で参考になった資料を紹介します。どれも新入生全員にオススメできる良質な知識が詰まっています。
はじめに読むことを薦める本
世界一やさしい問題解決の授業:まずはこれを読んで欲しい。外資系コンサルタント会社マッキンゼーで顧客企業の問題解決を手がけてきた著者が、子供向けに「問題を解決すると何が嬉しくて、どういう風に解決できるのか」を解説した本。問題解決(problem solving)という分野が存在することを知れる。最近「右脳」バージョンが出たらしいが、そちらは未読。
武器としての決断思考:論点(たとえば進路選択)を定め、それの利点と欠点を考量する方法をactionableに解説した書籍。何度も「日系企業であるXYZ社に22年新卒として入社すべきか?」という問いを立てて思考実験すれば、自分にとって重要な論点が次第に明確になってくるはずだ。
問題解決大全:上の薄い本2つで意志決定と問題解決についてなんとなく感覚を掴んだら、この本で問題解決の歴史的な全貌を知ろう。この本の最大の特徴は、「そもそも大抵の問題は解けない」「どれが現実的なコストで動きそうか知る」というそもそも論から始まり、「実は問題と原因という捉え方自体が、現実の一部をそういう枠組みとして歪曲して切り取ったものにすぎない」という俯瞰を行う。
そして第二章では「実際には問題と原因は相互フィードバックのシステムを作っており、根本原因は存在せず悪循環自体から脱出することが目的になる」という遥かに踏み込んだ考察を行なっている。実際、臨床心理学的なアプローチを知れば知るほど、「心理的な問題については、なぜこれで解決するのか分からないようなものが解決の糸口になる」ということは念頭に置いておいたほうがいいという感想を持つ。上記の二冊が論理的に解ける問題を対象としていたのに対し、こちらはもっと幅広い問題解決を扱っており、出典は文化人類学から、神学、政治学、社会学、計算機科学にまで渡る。これだけ包括的に問題解決について網羅している類書を僕は知らない。たとえば、かつてベストセラーになった『スーパーベター』で語られた方法論はこの本で述べられる「問題への相談」の類型に過ぎない。上掲の『世界一やさしい〜』で語られたロジックツリーもこの本では37コのうちの1つに過ぎない。木を見て森を見ずにならないために、一度は通読すべき本。
リスクや不確実性に対する感覚を養う
世界最強のエコノミストが教える お金を増やす一番知的なやり方 賢明なる投資家のためのパーソナル・ファイナンス読本
- 作者:ジョン・ケイ
- 発売日: 2018/08/09
- メディア: 単行本(ソフトカバー)
これは金融資産の投資に関する本だが、中盤に出てくる「リスク」と「不確実性」を分ける考え方は汎用的な上に、現代においておそらくトップクラスにバランスが取れている。「バランスが取れている」というのは、特定の欲しいなにか一つを確実に手に入れることはかなわないかもしれないが(むしろ、そのような不可能なことに拘ることは避ける)、長期で見れば他の人よりほとんど確実に多くを手にすることができる、そのような安定感と超然さを持っているという意味である。このようなバランス感覚があるのとないのとでは、選べる選択肢がまるで違ってくる。
各話題における実践論
How to fail at almost everything and still win big(未訳): 風刺作家Scott Adamsによる自伝。意志決定のうち、決定はしても実行が難しいタイプの事項というものがある(ダイエット、筋トレ、語学など)。それをgoalの設定ではなくsystemの導入という点で解決する、という極めて効果的なアプローチを提唱している。この本を読んだあとだと、村上春樹が『職業としての小説家』で語っている長編小説執筆のための日常(5時間執筆し、あとは走るなどして回復にあてる、を半年間繰り返す)は、一種のシステムとして解釈できる。
ゲーム開発プロジェクトマネジメント講座:自分ひとりだけならばScott Adamsのようにシステムを作れば課題は解決できるかもしれないが、現実は多くの人がメンバーとなったチームで何かを解決するということが多い。スクウェア・エニックスで数百人のチームをまとめて見事良質なゲームをこれまで作ってきたプロジェクト・マネージャーによる、どうすればプロジェクトは炎上しにくくなるのかを述べた貴重な資料。
ロジカル・プレゼンテーション:会議、プレゼンにおけるコミュニケーションの齟齬の解消法の各論。人と一緒に何かを決めるための方法論。
メンタルタフネス:用意してきたのに本番で成果が出せないというアスリートにありがちな問題の解決策を説いた良書。あるいは、ニューヨークの音楽学校では以下のような「本番での不安にどう対応するか」という授業が行われているらしい。
キャリアをデザインする際の3つのアプローチ :「やりたいことが見つからない」という問題を考察したニューヨーク在住の日本人の方による記事。著者がこれまで出会ってきた人たちがどのような認知を経て職業を選択してきたのかを考察しており、大変示唆深い。あなたはどれに分類されるだろうか。
選択の科学:自分があまり納得できないような他人の意志決定の論理を知る上で参考になる本。原題はThe art of choosing。著者の両親は敬虔なシク教徒であり、結婚式の当日に初めてお互いの顔を見た。結婚相手のような重大な意志決定をなぜ顔も見ずに済ませるのか。実はそこには科学的に検証できるいくつかの社会的・心理的メカニズムが働いていた、ということを明らかにしている良書。他にも、「ジャムの試食コーナーを作る際に、ジャムの種類が増えるほど本当に細かなユーザーニーズにも対応できて顧客は幸せになるのか」という問題設定から、選択肢の数と幸福の関係を考察する。京都大学の学生にとっては、彼女の「砂糖入り緑茶」の話はとても興味深いでしょう。
年収は住むところで決まる:住む都市に関する意志決定を行なう際に参考になる本。同じスキルを持っている人でも、住む都市によって年収が違う、もっと言うと都市Aの高卒者は都市Bの大卒者より稼いでいるという驚くべき事実を指摘しています。地方から東京・京都・名古屋・福岡などに移った実感と比べてみて下さい。そして、それが同書内で指摘されているニューヨークやシリコンバレーと比べた場合、どこに住むべきかという意志決定はどう変わるか考えて見て下さい。
米国大学院留学生による大企業ビッグデータ部署でのインターンの感想
プレゼン
センス8から見るグローバルな英語
互いの感情、感覚、能力を共有できる力を持った8人の主人公たちが協力しながら、それぞれの人生における苦境を解決していくという物語である。
特筆すべきは、8人の属性の選ばれ方の秀逸さである。主人公たち8人はそれぞれ、イギリス、カリフォルニア、シカゴ、メキシコ、インド、韓国(ソウル)、アフリカ(ナイロビ)、ドイツでそれぞれ全く異なる生活を営んでいる(中国を敢えて選ばなかった理由が気になる)。このような設定でもなければ絶対に出会わなかったような人たちばかりだ。
最初は明かされずに少しずつ明らかになっていくのだが、彼らそれぞれが持っている能力、そしてそれらが互いに補い合う様子もクリエイティビティに溢れている。全くもって21世紀ならではのチームを描いているようで、鑑賞していてワクワクする。
さて、この記事で取り上げたいのは、彼らが会話する媒体、英語である。自然な表現の身につけ方について英語が達者な留学生の友人(中国人)に尋ねた時に、このドラマを勧められた。「君の身につけたい英語かは分からないけれど、面白いよ」。劇中の彼らは現地語(ヒンディー語、ドイツ語、韓国語、スワヒリ語などなど)で会話しているが、全員が英語を喋ることができるという前提で進む。各自の現地でも現地語と英語を併用しながら進んでいくわけだが、その違いが面白かったのでここに書き記して考察してみる。彼らの属性はシーズン1の第1話で判明するものしか書き上げていないので、それほどのネタバレにはならないと思われる。
- ライリー(アイスランド、非ネイティブ?アイスランド語も話す)
ロンドンでDJをやっている白い髪の女性。ドラッグの名前やパーティー用語が乱発する。たとえばraveで「麻薬の使用を伴う可能性もあるパーティ」。DJがステージの上で音楽をかけながら聴衆がフロアで踊っているようなシーンを観た。
- サン(韓国)
父親の経営する会社で働く、元・格闘家の女性。単語はどれもネタバレになりそうなので避けておく。彼女とその取り巻きが使う英語は、特筆するほど特徴のある英語だとは思わなかった。ただしどの人物も発音が遅い。センス8はもともと綿密なストーリーを目指しているものではない、全く異なる他者がどう共感をしていくのかをただ想像力で描いていきたかったもの、と捉えているが、それにしても棒読みのような場面も散見され、サンの物語が最も茶番に見えてしまっている。ただ分かる。僕を含む、日中韓あるいは隣接アジア諸国から来たあまり英語が得意でない留学生は、こういう英語を話す。
- ヴォルフガング(ドイツ)
ドイツのマフィアの一員。彼とその取り巻きが話す英語はそれほど地域特有のものは無い気がした。ただしサンと異なり、どの人物の英語も自然に思えた(役者がネイティブなのかもしれない)。
- カーラ(インド)
結婚式を間近に控えたインド人の女性。
Oh, my Ganesha: とあるショッキングな事件が起きたときにカーラが発した言葉。彼女は熱心なヒンドゥー教徒で、シーズン1の初回話ではヒンドゥー教の神であるガネーシャ象の前で供物を捧げるシーンが出てきたりする。彼女は別の場面ではOh, my godも使うので、何らかの感情の差があるのかと思われるが、よく分からない。ただ英語がグローバル化していることを示唆する決定的な表現だと感じた。
作中のインド人の話す英語は、典型的な、一言聞いただけであっインド人だと分かる癖の強いものだが、彼らが極めて平凡な文法と単語で自由自在に自分たちの感情を表明しており、ドイツのヴォルフガングに近い自然さを覚えた。
- カフィアス(アフリカ)
ナイロビのバス運転手。前向きな性格で、多くのシーンで仲間たちを励ます役目を果たす。
make the world a more equal and just place: 西海岸のスタートアップを描いたSilicon ValleyというTVドラマでは、スタートアップはどいつもこいつも宣伝文でmake the world better placeと使いまくっている、たかが日常の些事を数秒短くするだけのプロダクトでも、と批判されるシーンが出てくる。それと比べると、強盗や殺人が蔓延るナイロビでのこの発言は、たった3語の違いでも遥かに重く社会状況を反映している。
it's a little dull : 「この鉈はすこし刃が鈍い」 殺人や恐喝に使われる錆びた鉈の形容。
prank: からかい、悪ふざけ。嘘を付いて相手を騙すシーンが多発する。
thug: 悪党
I speak good English: カフィアスの台詞。日本でこんなことを言う人を聞いたことがない。ナイロビでの英語は、韓国やインドでの英語と同様に非常に癖の強いものなのだが、非常に感情は篭って聞こえる。何に起因するのかは分からない。
- リト(メキシコ)
メキシコのスーパースタークラスの俳優。ゲイであることを隠して恋人と生活している。
We are on the location of Even Angels Must Earn Their Wings: 「映画〜の撮影現場 location に来ています」レポーターがリトとのインタビューで発した言葉。
Holy Communion: 和訳は「聖体拝領(せいたいはいりょう)」。「カトリック教会用語で,ミサ聖餐においてキリストのからだとなったとされるパンとぶどう酒を食すること」とブリタニカ百科事典。リトが恋人との出会いを自分にとってどれだけ劇的なものだったか表現する際に使われた。この単語に限らず、芸術、宗教関連の比喩で彼らの関係は説明されることが多い。
Toreador: 「闘牛士」。リトは映画俳優として様々な役を努めるので、このような職業の名前がよく出てくる。
box office: 映画が大当たりの
- ノミ(カリフォルニア、ネイティブ)
両親にほぼ勘当されているトランスジェンダー(男性→女性)。恋人の女性アマリータと二人暮らしをしている。リトとは真逆で、積極的に2人の関係を表明している。
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: もうウィズダムの説明をそのまま貼り付けるしか無い:「⦅くだけて非難して⦆ドラマクイーン, 悲劇のヒロイン〘注目を集めるために自己をドラマ化する人; 女性および同性愛者の男性に用いる〙」。リトは映画俳優のせいか感情の起伏が激しいのだが、そのリトと感覚を共有していると、どうにも…というちょっとした批難のシーンで使われた。
pot: マリファナ。
patriarchal: 男性上位の
- ウィル(シカゴ、ネイティブ)
正義感に溢れるシカゴの警察官。彼が同僚と話す英語は、警察用語あるいは俗語ばかりで非常に分かりにくい。例えば:
I'm going with a nine-millimeter tucked under my arm: ベルトの脇に警察官用の拳銃を携帯しているということ。tuckは「しまい込む」の意味。
B & E: Breaking & Entering (家宅不法侵入)
stakeout: 張り込み
boover: 日本の辞書には出てこないので和訳が不明。おそらく「甘ちゃん」とか「クズ野郎」ぐらいか。新人だったウィルに対して既存の警官が「どうせ典型的なシカゴのbooverだろうと思っていたら」と使われた。booverは語源上、人を侮蔑する時に使うassholeと同様なものと考えられる。
Bears & Packers : 「争い合っている二組織」。シカゴにはシカゴベアーズとグリーンベイ・パッカーズの2つのアメフトチームがあり、その戦いになぞらえたもの。
I'm beat: 「へとへとに疲れて切っている」。日本人だとexhaustedとでも言いそうだが、こちらのほうが口語的なのだろう。
そして単語としては知っていても卑語が入り砕けた表現ばかりで同僚と話すので、一体全体何について話しているのか判然としない。和訳を観て初めて「ああこれはさっきの事件のことを言っているのか」と気付くこともしばしばだ。
さて、こうやって書き並べてみると、明らかに理解する上で自分側の俗語力が足りていない主人公たちがいる。ノミとウィル、すなわちネイティブスピーカーたちが語る日常生活だ。リトは俳優、カフィアスは治安という部分で聞いたことがない表現がいくつか出て来るが、ネイティブの比ではない。あとの4人は更に少ない(いくつか地域固有ではない、標準的な表現が出て来るが)。ネイティブたちとのまだまだ埋まらない距離を感じる一方で、世界各地の英語(いわゆるブロークンイングリッシュ?)との近さを実感するような、そんな作品であった。