leetcode

やってみた

ときおわると解説があるのがよい

LeetCode とかに問題がさらされていますが、あれは、たいてい入り口で倒れているので、本体に到達していないんです。そういった足を踏み入れると深みがあるような問題が好まれます。

解答にひらめきがいるように思われていますが、だいたいの場合は、人類の100年近い情報科学の歴史の中で類題が解かれているので、それを思い出すだけで解ける話ばかりです。そのようにしなくてはいけない制限が随所にあって、それらは、いくらかは合意、いくらかは人類の技術的理由、いくらかはこの宇宙の数学的物理学的制限から来ているものです。

「何をどれくらい知っていなくてはいけないのか」と聞かれたので、ちょっと考えてから、右手を前に突き出しました。手を開いた状態で右手を伸ばしたあとに、「手を握ります」と宣言してからゆっくりと手を握ってみせました。「いま、手を握ろうと思ってから握るまでのあいだに起きたことをできるだけ詳細に説明してください。」

いままで鉄門を何人か教えてきたので、医師にはこれが一番通じると思ったのです。

前頭前野。運動野。頚椎。腕神経叢。ミオシン。アクチン。

「そうですね。H-H方程式やイオンチャンネル、骨や筋肉の名称の話をしてもいいでしょうし、答えが足りなかったら追加で聞いてきます。では、頚椎損傷で今の動きができなくなったとしたら、Cいくつの損傷を考えますか。医師でも結構忘れているので答えられなくてもいいのですが、この答えられなかったときに感じる答えられて当然という感覚を覚えていてください。その番号で人生が大きく変わった人はたくさんいますよね。」

「ヘモクロマトーシスの患者さん、いままでどれくらい見たことありますか。要するにプロというのは、数年に一度見るくらいのことは当然に知っているんです。いままで仕事で書いたダイクストラの数覚えてますか。」

同僚の8,9割が知っていることを8,9割知っていることがどの世界でも求められるのだと思います。

知っていて当然な知識かどうかの判断をする際には、同僚のエンジニア同士が夕食時などに雑談をして、まあ、そこにいる8-9割方が知っていることならば、出題ミスではないよねとなり、それが常識とされるわけです。

Google の入社試験は、そういう意味では田舎初段では難しい

囲碁や将棋には田舎初段という言葉があって、正規の訓練を受けた人からは相手にされるほど強くないが、素人になら無双できるレベルというのがあるんです。レベル5くらい、と私は時々表現します。人

多くの能力について、初級のときに身につけるスキルとその後にずれがあります。たとえば、数学をするにしてもはじめは九九の暗唱をします。それが得意であれば、レベル5くらいまでにはなります。それをよしとするかあしとするかはともかく、大学受験までは芸大でもなければ、田舎初段で通ってしまうというのが日本の水準です。東大でも数学が得意だと名乗って証明と称するグロテスクな画像をネットにあげている人いますよね。受験数学は好きだったが数学者とカジュアルにお話をしない法学部文学部医学部あたりではよく見ますし、理学部でさえもたまにいますね。

レベルが10あれば通る可能性がでてきて、レベルが30くらいあれば余裕というのが私の感覚です。

どの分野であれ、ここからここまでは常識という範囲があり、特にある程度体系化された学問はそれがはっきりしています。たとえば、ACM と IEEE-CS は Computing Curricula を出しているので、それを参考にするのでもいいですし、関係する学科のカリキュラムを参考にして、その授業でどのような書籍が参考に挙げられているかを見るのもいいでしょう。

情報科学は、「作ってみた」「現実はこう」「理論的制限」の本を読むとよいと思います。たとえば、交通ルールを考えてみましょう。標識の形が各国違うように、その標識の形自体はただの約束として作られたもので、さまざまな歴史的な経緯の集積の末にできあがったものです。ただ、まったく無作為に作られるものではなく、たとえば、左側通行と右側通行が同じ道で混在すると問題を起こすことであったり、見通しが悪ければ一旦停止が必要であることであったり、速すぎる速度でカーブに突入すれば曲がりきれないから速度制限がいることであったり、さまざまな数学的物理的技術的制限がかかってきて、それ自体も知る価値があります。そして、それらを分かっている人が無人島を借り切って箱庭で交通システムを作ってみることがあり、その記録を読むと、何が起きているかとてもよく分かります。作ってみた系は意外と現実についても最低限の言及がありますね。

「作ってみた」系の本として、CPU やメモリーの構造が分かりますので、このレイヤーを俯瞰するのによいでしょう。

古い本ですが、このあたりで現在のマルチタスク OS をサポートする CPU が完成しますので、アーキテクチャについて、知っているべきことについてだいたいカバーしていると思います。欠けているものがあるとすれば、高速化や仮想化のための技法くらいでしょうか。興味があれば「プロセッサを支える技術」あたりがそれを埋めるでしょう。

3ウェイハンドシェイクと輻輳制御が書かれているとなると、ほとんど選択肢がありませんでした。逆に、Tier 1 network とかは知らなくていいんじゃないでしょうか。

・岩波講座 ソフトウェア科学 オペレーティングシステム

オペレーティングシステムについての本はこれでよかったかはまだ迷いがあります。

一緒にタネンバウムも紹介していました。

REST にこだわりが強い本ですが、そこは軽く流すようにと伝えました。

コンパイラの大まかな原理は聞かれることがあるかと思います。言語に特有のことは出てこないので、そこは別で補ってください。

高速化の技法の部分は過剰かもしれません。

この本はたしか本屋では名前が挙がっていました。OS を作ってみようという本なのですが、周辺の技術、たとえば、ハードディスクのフォーマットである FAT16 の仕様が載っているのがいいですね。

アルゴリズムが苦手だったら入れていたでしょう。最近の模擬面接ではコードがおぼつかない感じだと思うと、なんでもいいんですが、AtCoder の ABC 4問時代の C 問題くらいを埋めることをおすすめしています。あと、コードは書けたら終わりではなくて、どの行をどう変えたらどうなるのか、どういう場合に動かなくなるのか、どう書いたらより洗練されるのか、を考えるといいと思います。

・C++ Templates: The Complete Guide

この辺は私の趣味ですが、関数型言語はなにか触っておいたほうがいいと思いますし、C++ テンプレートはやらかしでチューリング完全なので一回目を合わせておくべきですし、純粋関数型データ構造は見ておいて、いいんじゃないでしょうか。

・エキスパートCプログラミング―知られざるCの深層

・Modern C++ Design

・Effective C++

・Exceptional C++

競技プログラミングの始祖のあたりの人たちは、C++ 使うならばこのあたり読んでいた気がします。最近の C++ はちょっと違うものですが、大切なのは、見慣れていて使役しているものが本性はおぞましいという感覚じゃないでしょうか。

言語は何でもいいと思うのです。たとえば、従妹にはじめてプログラミングを教えたときは C++ でしたが、妹には Perl + SQLite という構成で教えました。Perl は、たとえばレキシカルスコープとダイナミックスコープが両方あるなど、とても教育的にいい言語です。ただ、とにかく表層的にしか理解していない人や本であふれていて、社会的なノイズのせいできちんと理解するのが大変です。私は、大学の同期を問い詰めるまで、振る舞いが分かりませんでした。なお、その人も合宿のメンバーで Google の同僚になりました。

・入門 コンピュータ科学　ITを支える技術と理論の基礎知識

これは、最近見つけたんですが、広く書かれていて、とりあえず、これもいいんじゃないでしょうか。