実務で私が使っているデータ構造とアルゴリズム

(blog.pragmaticengineer.com)

20 ポイント投稿者 xguru 2020-07-17 | 3件のコメント | WhatsAppで共有

面接でよく聞かれるアルゴリズムの質問は、実務では使われないと言われることがありますが、

筆者が実際にSkypeやUberなどで働きながら頻繁に使っていたものを、例とともに整理し、基礎として読むべきものも勧めています。

グラフとグラフ探索：Skype & Uber

重み付きグラフと最短距離：SkyScanner

ソート：Skype

ハッシュテーブルとハッシング：あらゆる場所

スタックとキュー：ときどき

暗号化（Crypto）、確率理論と推測、Hexagonal Grid と階層インデックス：Uber

人気のあるアルゴリズムや珍しいデータ構造を知っていることは重要ではありません。

アルゴリズムとは何かを理解し、Greedyアルゴリズムのような単純なアルゴリズムは自分で考えられるべきです。

ハッシュテーブル、キュー&スタックのような基本的なデータ構造は知っておくべきですが、DijkstraやA*のような特殊なアルゴリズムを暗記する必要はありません。

私がソートを超えるアルゴリズムについて行ってきた作業の大半は、調べて理解しようと努める程度です。

Red-BlackやAVL木のような特殊なデータ構造も同様です。

実際にこうしたデータ構造を使うことはありませんでしたし、必要になったとしても改めて検索して調べるでしょう。

シリコンバレーでは、動的計画法や特殊なデータ構造を尋ねる質問がますます一般的になっています。

こうした質問は優れたエンジニアを採用するのには役立つかもしれませんが、実際には高度なアルゴリズム知識を必要としない仕事を非常にうまくこなす人を採れなくなります。

本当に必要なのは、最も一般的なデータ構造を認識し、問題を解決するための最も単純なアルゴリズムを道具として使う能力です。

データ構造とアルゴリズムは、単なるツールセットにすぎません。

ソフトウェア開発をするときに、自信を持って使うべき道具です。

こうした道具をよく知っていれば、それらを使ったコードを見ることにも慣れていくでしょう。

また、難しい問題を解くソリューションを実装することにも、より自信が持てるようになるでしょう。

基礎を知るために、次のものを勧めます。（リンクはコメント欄にあります）

GeekforGeeks の Data Structures Overview（オンライン記事集）
HackerRank の DataStructure Collection（問題を解きながら学ぶ）
Grokking Algorithms：図で概念を理解するアルゴリズム（翻訳書）
The Algorithm Design Manual と Algorithms: Fourth Edition は、あまりに無味乾燥で、日々の実務で使うにはあまり向いていません。