|
|
# コーディング面接の大学
|
|
|
|
|
|
>私はもともとこれをソフトウェアエンジニアになるための短いトピックリストとして作成しましたが、
|
|
|
>今日それは大きなリストに成長しました。この学習計画を経て、[私はAmazonで
|
|
|
> ソフトウェアエンジニアとして雇われました！！](https://startupnextdoor.com/ive-been-acquired-by-amazon/?src=ciu)
|
|
|
>おそらく、あなたは私ほど勉強する必要はないでしょう。とにかく、必要なものはすべてここにあります。
|
|
|
> 私は数ヶ月間、1日約8〜12時間勉強しました。これが私のストーリーです: [Google の面接のために8か月間フルタイムで勉強した理由](https://www.freecodecamp.org/news/why-i-studied-full-time-for-8-months-for-a-google-interview-cc662ce9bb13)
|
|
|
>注意してください: あなたは私ほど勉強する必要はありません。私は、知る必要のないことに多くの時間を無駄にしました。詳細については、以下をご覧ください。貴重な時間を無駄にすることなく、必要なことを勉強するのを手伝います。
|
|
|
>ここに掲載されている項目を学べば、Amazon、Facebook、Google、Microsoftなど
|
|
|
>大手企業を含む、ほぼすべてのソフトウェア会社の面接に備えることができます。
|
|
|
>
|
|
|
> *あなたに最高の幸運がありますように!*
|
|
|
|
|
|
翻訳：
|
|
|
- [简体中文](translations/README-cn.md)
|
|
|
- [TiếngViệt - ベトナム語](translations/README-vi.md)
|
|
|
- [Español](translations/README-es.md)
|
|
|
|
|
|
翻訳中：
|
|
|
- [हिन्दी](https://github.com/jwasham/coding-interview-university/issues/81)
|
|
|
- [עברית](https://github.com/jwasham/coding-interview-university/issues/82)
|
|
|
- [インドネシア語](https://github.com/jwasham/coding-interview-university/issues/101)
|
|
|
- [アラビア語](https://github.com/jwasham/coding-interview-university/issues/98)
|
|
|
- [トルコ語](https://github.com/jwasham/coding-interview-university/issues/90)
|
|
|
- [French](https://github.com/jwasham/coding-interview-university/issues/89)
|
|
|
- [ロシア語](https://github.com/jwasham/coding-interview-university/issues/87)
|
|
|
- [ウクライナ](https://github.com/jwasham/coding-interview-university/issues/106)
|
|
|
- [ブラジルのポルトガル語](https://github.com/jwasham/coding-interview-university/issues/113)
|
|
|
- [韓国語](https://github.com/jwasham/coding-interview-university/issues/118)
|
|
|
- [Telugu](https://github.com/jwasham/coding-interview-university/issues/117)
|
|
|
- [Polish](https://github.com/jwasham/coding-interview-university/issues/122)
|
|
|
- [ドイツ語](https://github.com/jwasham/coding-interview-university/issues/135)
|
|
|
- [Urdu](https://github.com/jwasham/coding-interview-university/issues/140)
|
|
|
- [タイ語](https://github.com/jwasham/coding-interview-university/issues/156)
|
|
|
- [ギリシャ語](https://github.com/jwasham/coding-interview-university/issues/166)
|
|
|
|
|
|
<div align="center">
|
|
|
<hr />
|
|
|
<p>
|
|
|
<a href="https://github.com/sponsors/jwasham"><strong>Become a sponsor</strong> and support Coding Interview University!</a>
|
|
|
</p>
|
|
|
<hr />
|
|
|
</div>
|
|
|
|
|
|
## これは何？
|
|
|
|
|
|
|
|
|
|
|
|
これは、大企業のソフトウェア エンジニアになるための私の数か月にわたる学習計画です。
|
|
|
|
|
|
**必須：**
|
|
|
|
|
|
- コーディングの経験 (変数、ループ、メソッド/関数など)
|
|
|
- 忍耐
|
|
|
- 時間
|
|
|
|
|
|
これは**ソフトウェア エンジニアリング**の学習計画であり、フロントエンド エンジニアリングやフルスタック開発ではないことに注意してください。
|
|
|
他の場所でのキャリア パスのスーパー ロードマップとコースワーク (詳細については https://roadmap.sh/ を参照)。
|
|
|
|
|
|
大学のコンピューター サイエンス プログラムでは学ぶべきことがたくさんありますが、面接には 75% 程度知っていれば十分なので、ここではそれについて説明します。
|
|
|
完全な CS 独学プログラムについては、私の学習計画のリソースがカムラン アーメッドのコンピューター サイエンス ロードマップに含まれています: https://roadmap.sh/computer-science
|
|
|
|
|
|
---
|
|
|
|
|
|
## 目次
|
|
|
|
|
|
### 学習計画
|
|
|
|
|
|
- [なぜこれを使用するのか](#なぜこれを使用するのか)
|
|
|
- [使い方](#使い方)
|
|
|
- [自信を無くさないでください](#自信を無くさないでください)
|
|
|
- [ビデオリソースに関する注意](#ビデオリソースに関する注意)
|
|
|
- [プログラミング言語を選択してください](#プログラミング言語を選択してください)
|
|
|
- [データ構造とアルゴリズムに関する書籍](#データ構造とアルゴリズムに関する書籍)
|
|
|
- [面接対策本](#面接対策本)
|
|
|
- [私と同じ間違いを犯さないでください](#私と同じ間違いを犯さないでください)
|
|
|
- [取り上げられていないもの](#取り上げられていないもの)
|
|
|
- [日次計画](#日次計画)
|
|
|
- [コーディングに関する質問の練習](#コーディングに関する質問の練習)
|
|
|
- [コーディングの問題](#コーディングの問題)
|
|
|
|
|
|
### 研究のテーマ
|
|
|
|
|
|
- [アルゴリズムの複雑さ / Big-O / 漸近分析](#アルゴリズムの複雑さ/Big-O/漸近分析)
|
|
|
- [データ構造](#データ構造)
|
|
|
- [配列](#配列)
|
|
|
- [連結リスト](#連結リスト)
|
|
|
- [スタック](#スタック)
|
|
|
- [キュー](#キュー)
|
|
|
- [ハッシュテーブル](#ハッシュテーブル)
|
|
|
- [その他の知識](#その他の知識)
|
|
|
- [二分探索](#二分探索)
|
|
|
- [ビット演算](#ビット演算)
|
|
|
- [ツリー](#ツリー)
|
|
|
- [ツリーとは](#ツリーとは)
|
|
|
- [二分探索木：BST](#二分探索木：BST)
|
|
|
- [ヒープ/優先度つきキュー/二分ヒープ](#ヒープ/優先度つきキュー/二分ヒープ)
|
|
|
- バランスの取れた検索ツリー (詳細ではなく一般的な概念)
|
|
|
- トラバーサル: プレオーダー、インオーダー、 postorder、BFS、DFS
|
|
|
- [ソート](#ソート)
|
|
|
- 選択
|
|
|
- 挿入
|
|
|
- ヒープソート
|
|
|
- クイック
|
|
|
ソート - マージソート
|
|
|
- [グラフ](#グラフ)
|
|
|
- 有向
|
|
|
- 無向
|
|
|
- 隣接行列
|
|
|
- 隣接リスト
|
|
|
- 走査: BFS、DFS
|
|
|
- [さらに多くの知識](#さらに多くの知識)
|
|
|
- [再帰](#再帰)
|
|
|
- [動的プログラミング](#動的プログラミング)
|
|
|
- [デザインパターン](#デザインパターン)
|
|
|
- [組み合わせ論(nからkを選択)と確率](#組み合わせ論(nからkを選択)と確率)
|
|
|
- [NP、NP-完全/近似アルゴリズム](#NP、NP-完全/近似アルゴリズム)
|
|
|
- [コンピューターがプログラムを処理する仕組み](#コンピューターがプログラムを処理する仕組み)
|
|
|
- [キャッシュ](#キャッシュ)
|
|
|
- [プロセスとスレッド](#プロセスとスレッド)
|
|
|
- [テスト](#テスト)
|
|
|
- [文字列の検索と操作](#文字列の検索と操作)
|
|
|
- [トライ](#トライ)
|
|
|
- [浮動小数点数](#浮動小数点数)
|
|
|
- [Unicode](#unicode)
|
|
|
- [エンディアン](#エンディアン)
|
|
|
- [ネットワーキング](#ネットワーキング)
|
|
|
- [最終レビュー](#最終レビュー)
|
|
|
|
|
|
## なぜこれを使用するのか
|
|
|
|
|
|
大企業でソフトウェア エンジニアとして働きたいのであれば、これらのことを知っておく必要があります。
|
|
|
|
|
|
私のようにコンピューター サイエンスの学位を取得できなかった場合は、これで人生の 4 年間取り戻すことができます。
|
|
|
|
|
|
このプロジェクトを始めたとき、私はヒープからのスタックのことも、Big-O のことも、木についても、何も知りませんでした。
|
|
|
グラフを横断します。もし私が並べ替えアルゴリズムをコーディングしなければならなかったとしたら、それは酷いことになるでしょう。
|
|
|
私がこれまで使用してきたデータ構造はすべて言語に組み込まれており、それがどのように機能するのかわかりませんでした。
|
|
|
ボンネットの下にはまったくありません。実行しているプロセスで「不足」が発生しない限り、メモリを管理する必要はありませんでした。
|
|
|
「memory」エラーが発生した場合は、回避策を見つける必要があります。私は人生でいくつかの多次元配列を使用しましたが、
|
|
|
何千もの連想配列を作成しましたが、データ構造を最初から作成したことはありません。
|
|
|
|
|
|
長い計画ですね。何か月もかかるかもしれません。しかし、すでにこの内容の多くに精通している場合は、時間ははるかに短くなります。
|
|
|
|
|
|
## 使い方
|
|
|
|
|
|
以下はすべて概要であり、順に項目に取り組む必要があります。
|
|
|
|
|
|
私は進捗状況を追跡するためのタスク リストを含む、GitHub 風マークダウン を使用しています。
|
|
|
|
|
|
- [GitHub 風マークダウンの詳細](https://guides.github.com/features/mastering-markdown/#GitHub-flavored-markdown)
|
|
|
|
|
|
### git を使用したくない場合
|
|
|
|
|
|
このページで、上部近くの「Code」ボタンをクリックし、「Download ZIP」をクリックします。ファイルを解凍すると、テキスト ファイルを操作できるようになります。
|
|
|
|
|
|
マークダウンを理解できるコード エディターで開いている場合は、すべてが適切にフォーマットされていることを確認できます。
|
|
|
|
|
|
|
|
|
|
|
|
### git に慣れている場合
|
|
|
|
|
|
新しいブランチを作成して、次のような項目を確認できるようにします。括弧内に x を入力するだけです: [x]
|
|
|
|
|
|
1. **_GitHub リポジトリ:_** `https://github.com/jwasham/coding-interview-university` をフォーク ボタンをクリックしてフォークします。
|
|
|
|
|
|
|
|
|
|
|
|
1. ローカル リポジトリにクローンを作成します。
|
|
|
|
|
|
```bash
|
|
|
git clone https://github.com/<YOUR_GITHUB_USERNAME>/coding-interview-university.git
|
|
|
cd coding-interview-university
|
|
|
git remote add upstream https://github.com/jwasham/coding-interview-university.git
|
|
|
git remote set-url --push upstream DISABLE # 個人の進捗を元のレポにプッシュバックしないようにするため
|
|
|
```
|
|
|
|
|
|
1. 変更を完了したら、すべてのボックスに X を付けます。
|
|
|
|
|
|
```bash
|
|
|
git commit -am "Marked personal progress"
|
|
|
git pull upstream main # 元のレポからの変更でフォークを最新に保つ
|
|
|
|
|
|
git push # フォークにプッシュするだけ
|
|
|
```
|
|
|
|
|
|
## 自信を無くさないでください
|
|
|
|
|
|
- 成功した多くのソフトウェア エンジニアは自分が十分に賢くないのではないかという不安を抱えています。
|
|
|
- 次のビデオは、この不安を解消するのに役立ちます。
|
|
|
- [天才プログラマーの神話](https://www.youtube.com/watch?v=0SARbwvhupQ)
|
|
|
- [一人で行動するのは危険です: テクノロジーにおける目に見えないモンスターとの戦い](https://www.youtube.com/watch?v=1i8ylq4j_EY)
|
|
|
|
|
|
---
|
|
|
|
|
|
## ビデオリソースに関する注意
|
|
|
|
|
|
一部のビデオは、Coursera または EdX クラスに登録することによってのみ視聴できます。
|
|
|
これらは MOOC と呼ばれます。
|
|
|
場合によっては、クラスが開催されていないため、数か月待たなければならず、アクセスできないこともあります。
|
|
|
|
|
|
オンラインコースのリソースを、YouTube ビデオ (できれば大学の講義) など、いつでも利用できる無料の公開ソースに置き換えて、特定のオンラインコースの開催中だけでなく、いつでも学習できるようにするのは素晴らしいことです。
|
|
|
|
|
|
## プログラミング言語を選択してください
|
|
|
|
|
|
コーディング面接に使用するプログラミング言語を選択する必要がありますが、コンピューターサイエンスの概念を学習するために使用できる言語も見つける必要があります。
|
|
|
|
|
|
できれば、どちらか 1 つの言語に習熟するだけで済むように、言語が同じであることが望ましいです。
|
|
|
|
|
|
### この学習計画について
|
|
|
|
|
|
学習計画を立てたとき、そのほとんどで C と Python の 2 つの言語を使用しました。
|
|
|
|
|
|
* C: 非常に低いレベル。ポインタとメモリの割り当て / 割り当て解除を処理できるため、データ構造を実感できます。
|
|
|
そしてアルゴリズムが骨の中に組み込まれています。Python や Java などの高水準言語では、これらは表示されません。日々の仕事ではそれは素晴らしいことですが、これらの低レベルのデータ構造がどのように構築されるかを学んでいるときは、実際に近いと感じるのは素晴らしいことです。
|
|
|
- C はどこにでもあります。勉強していると、書籍、講義、ビデオなど、*あらゆる場所*で例を見ることができます。
|
|
|
- [C プログラミング言語 第 2 版](https://www.amazon.com/Programming-Language-Brian-W-Kernighan/dp/0131103628)
|
|
|
- これは短い本ですが、少し練習すれば C 言語をうまく扱えるようになります。
|
|
|
すぐに上達します。C を理解すると、プログラムとメモリがどのように機能するかを理解するのに役立ちます。
|
|
|
- 本を深く読み込む必要はありません（読み終える必要さえありません）。C で快適に読み書きできるところまで進んでください。
|
|
|
* Python: 現代的で表現力が非常に豊かです。非常に便利で、面接で記述するコードの量も少なくて済むため、私はこれを学びました。
|
|
|
|
|
|
これが私の好みです。もちろん、好きなことをしてください。
|
|
|
必要ないかもしれませんが、新しい言語を学習するためのサイトをいくつか紹介します。
|
|
|
- [exercism](https://exercism.org/tracks)
|
|
|
- [codewars](http://www.codewars.com)
|
|
|
- [HackerEarth](https://www.hackerearth.com/for-developers/)
|
|
|
- [SCALER Topics (Java、C++)](https://www.scaler.com/topics/)
|
|
|
|
|
|
### コーディング面接用
|
|
|
|
|
|
面接のコーディング部分には、使い慣れた言語を使用できますが、大企業の場合は、次の言語を選択するのが確実です。
|
|
|
|
|
|
- C++
|
|
|
- Java
|
|
|
- Python
|
|
|
|
|
|
これらを使用することもできますが、最初に読んでください。注意事項がある場合があります:
|
|
|
|
|
|
- JavaScript
|
|
|
- Ruby
|
|
|
|
|
|
面接の言語の選択について私が書いた記事は次のとおりです:
|
|
|
[Pick One Language for the Coding Interview](https://startupnextdoor.com/important-pick-one-language-for-the-coding-interview/).
|
|
|
|
|
|
これは私の投稿の元の記事です:
|
|
|
[Choosing a Programming Language for Interviews](https://web.archive.org/web/20210516054124/http://blog.codingforinterviews.com/best-programming-language-jobs/)
|
|
|
|
|
|
言語に非常に慣れており、知識が豊富である必要があります。
|
|
|
|
|
|
選択肢について詳しくは、次を参照してください。
|
|
|
- [Choose the Right Language for Your Coding Interview](http://www.byte-by-byte.com/choose-the-right-language-for-your-coding-interview/)
|
|
|
|
|
|
[ここで言語固有のリソースを参照してください](programming-language-resources.md)
|
|
|
|
|
|
## データ構造とアルゴリズムに関する書籍
|
|
|
|
|
|
### C
|
|
|
|
|
|
- [Algorithms in C, Parts 1-5 (Bundle), 3rd Edition](https://www.amazon.com/Algorithms-Parts-1-5-Bundle-Fundamentals/dp/0201756080)
|
|
|
- 基礎、データ構造、並べ替え、検索、およびグラフのアルゴリズム
|
|
|
|
|
|
### Python
|
|
|
|
|
|
- [Data Structures and Algorithms in Python](https://www.amazon.com/Structures-Algorithms-Python-Michael-Goodrich/dp/1118290275/)
|
|
|
- グッドリッチ、タマッシア、ゴールドワッサー著
|
|
|
- この本が大好きでした。それはすべてを網羅し、それ以上のものでした。
|
|
|
- Python コード
|
|
|
- 私の素晴らしい本のレポート: https://startupnextdoor.com/book-report-data-structions-and-algorithms-in-python/
|
|
|
|
|
|
### Java
|
|
|
|
|
|
- Goodrich、Tamassia、Goldwasser
|
|
|
- [Data Structures and Algorithms in Java](https://www.amazon.com/Data-Structures-Algorithms-Michael-Goodrich/dp/1118771338/)
|
|
|
- セッジウィックとウェイン:
|
|
|
- [Algorithms](https://www.amazon.com/Algorithms-4th-Robert-Sedgewick/dp/032157351X/)
|
|
|
- この本をカバーする無料の Coursera コース (著者が教えます!):
|
|
|
- [Algorithms I](https://www.coursera.org/learn/algorithms-part1)
|
|
|
- [Algorithms II](https://www.coursera.org/learn/algorithms-part2)
|
|
|
|
|
|
### C++
|
|
|
|
|
|
- Goodrich、Tamassia、および Mount
|
|
|
- [Data Structures and Algorithms in C++, 2nd Edition](https://www.amazon.com/Data-Structures-Algorithms-Michael-Goodrich/dp/0470383275)
|
|
|
- Sedgewick と Wayne
|
|
|
- [Algorithms in C++, Parts 1-4: Fundamentals, Data Structure, Sorting, Searching](https://www.amazon.com/Algorithms-Parts-1-4-Fundamentals-Structure/dp/0201350882/)
|
|
|
- [Algorithms in C++ Part 5: Graph Algorithms](https://www.amazon.com/Algorithms-Part-Graph-3rd-Pt-5/dp/0201361183/)
|
|
|
|
|
|
## 面接対策本
|
|
|
|
|
|
たくさん買う必要はありません。正直なところ、「コーディング面接の攻略」で十分だと思いますが、さらに練習するためにさらに購入しました。しかし、私はいつもやりすぎます。
|
|
|
|
|
|
これを両方購入しました。彼らは私にたくさんの練習をさせてくれました。
|
|
|
|
|
|
- [Programming Interviews Exposed: Coding Your Way Through the Interview, 4th Edition](https://www.amazon.com/Programming-Interviews-Exposed-Through-Interview/dp/111941847X/)
|
|
|
- C++ および Java での回答
|
|
|
- これコーディング面接を突破するための良いウォーミングアップです
|
|
|
- それほど難しいことではありません。ほとんどの問題は、インタビューで見られるものよりも簡単かもしれません (私が読んだ内容によると)
|
|
|
- [Cracking the Coding Interview, 6th Edition](http://www.amazon.com/Cracking-Coding-Interview-6th-Programming/dp/0984782850/)
|
|
|
- Java での回答
|
|
|
|
|
|
### 時間がたくさんある場合:
|
|
|
|
|
|
1 つ選択してください:
|
|
|
|
|
|
- [Elements of Programming Interviews (C++ version)](https://www.amazon.com/Elements-Programming-Interviews-Insiders-Guide/dp/1479274836)
|
|
|
- [Elements of Programming Interviews in Python](https://www.amazon.com/Elements-Programming-Interviews-Python-Insiders/dp/1537713949/)
|
|
|
- [Elements of Programming Interviews (Java version)](https://www.amazon.com/Elements-Programming-Interviews-Java-Insiders/dp/1517435803/)
|
|
|
- [Companion Project - Method Stub and Test Cases for Every Problem in the Book](https://github.com/gardncl/elements-of-programming-interviews)
|
|
|
|
|
|
## 私と同じ間違いを犯さないでください
|
|
|
|
|
|
このリストは何か月もかけて大きくなり、はい、手に負えなくなりました。
|
|
|
|
|
|
より良い経験をしていただくために、私が犯したいくつかの間違いを以下に示します。そして、何か月も時間を節約できます。
|
|
|
|
|
|
### 1. すべてを覚えているわけではない
|
|
|
|
|
|
時間もビデオを見て大量のメモを取りましたが、数か月後には覚えていないことがたくさんありました。
|
|
|
3日間かけてメモを見直し、フラッシュカードを作成して復習しましたが、そんな知識は必要ありませんでした。
|
|
|
|
|
|
私と同じ間違いを犯さないように、
|
|
|
|
|
|
[Retaining Computer Science Knowledge](https://startupnextdoor.com/retaining-computer-science-knowledge/) を読んでください。
|
|
|
|
|
|
### 2. フラッシュカードを使用する
|
|
|
|
|
|
この問題を解決するために、一般とコードの 2 種類のフラッシュカードを追加できる小さなフラッシュカード サイトを作成しました。
|
|
|
各カードには異なる形式があります。どこにいても携帯電話やタブレットでレビューできるように、モバイルファーストのウェブサイトを作成しました。
|
|
|
|
|
|
無料で独自に作成します。
|
|
|
|
|
|
- [Flashcards site repo](https://github.com/jwasham/computer-science-flash-cards)
|
|
|
|
|
|
**フラッシュカードの使用はお勧めしません。** フラッシュカードが多すぎて、ほとんどがトリビアです。必要ありません。
|
|
|
|
|
|
しかし、私の言うことを聞きたくない場合は、ここからどうぞ:
|
|
|
- [My flash cards database (1200 cards)](https://github.com/jwasham/computer-science-flash-cards/blob/main/cards-jwasham.db):
|
|
|
- [My flash cards database (extreme - 1800 cards)](https://github.com/jwasham/computer-science-flash-cards/blob/main/cards-jwasham-extreme.db):
|
|
|
|
|
|
やりすぎて、アセンブリ言語や Python のトリビアから機械学習や統計まで、あらゆるものをカバーするカードがあることに注意してください。
|
|
|
必要なものが多すぎます。
|
|
|
|
|
|
**フラッシュカードに関する注意:** 初めて答えを知っていると気づいたときは、その答えを既知としてマークしないでください。
|
|
|
本当に理解するには、同じカードを見て何度か正しく答える必要があります。
|
|
|
繰り返すことで知識が脳に深く定着します。
|
|
|
|
|
|
私のフラッシュカード サイトを使用する代わりに、[Anki](http://ankisrs.net/) が私に何度も勧められてきました。
|
|
|
繰り返しシステムを使用しているので、覚えやすくなります。ユーザーフレンドリーで、すべてのプラットフォームで利用でき、クラウド同期システムを備えています。
|
|
|
iOS では 25 ドルかかりますが、他のプラットフォームでは無料です。
|
|
|
|
|
|
Anki 形式のフラッシュカード データベース: https://ankiweb.net/shared/info/25173560 (thanks [@xiewenya](https://github.com/xiewenya)).
|
|
|
|
|
|
一部の学生は、空白に関する書式の問題について次の手順を実行することで修正できると述べています。デッキを開いて、カードを編集し、カードをクリックし、「スタイル」ラジオ ボタンを選択して、メンバー「white-space: pre;」を追加します。カードクラスへ。
|
|
|
|
|
|
### 3. 学習中にコーディング面接の質問をする
|
|
|
|
|
|
これは非常に重要です。
|
|
|
|
|
|
データ構造とアルゴリズムを学習しながら、コーディング面接の質問に答え始めます。
|
|
|
|
|
|
問題を解決するには、学んだことを応用する必要があります。そうしないと忘れてしまいます。私はこの間違いを犯しました。
|
|
|
|
|
|
トピックを学習し、**リンク リスト** などにある程度慣れたら:
|
|
|
1. [面接対策本](#面接対策本)のいずれかを開きます(または、以下にリストされているコーディングに関する問題の Web サイト)
|
|
|
1. 次の学習トピックに進みます。
|
|
|
1. その後、戻って別の 2 つまたは 3 つのリンク リストの問題を解きます。
|
|
|
1. 新しいトピックを学ぶたびにこれを行います。
|
|
|
|
|
|
**学習後ではなく、学習している間も問題を解き続けてください。**
|
|
|
|
|
|
あなたは知識のために雇われているのではなく、その知識をどのように応用するかによって雇われているのです。
|
|
|
|
|
|
以下に示すように、これに関する多くのリソースがあります。続けて。
|
|
|
|
|
|
### 4. 集中する
|
|
|
|
|
|
気を散らすものがたくさんあり、貴重な時間が奪われてしまう可能性があります。集中力と集中力は難しいです。歌詞のない音楽をかける
|
|
|
と、かなり集中できるようになります。
|
|
|
|
|
|
## 取り上げられていないもの
|
|
|
|
|
|
以下は一般的なテクノロジですが、この学習計画には含まれていません:
|
|
|
|
|
|
- Javascript
|
|
|
- HTML、CSS、およびその他のフロントエンドテクノロジ
|
|
|
- SQL
|
|
|
|
|
|
## 日次計画
|
|
|
|
|
|
このコースでは多くの主題について説明します。おそらくそれぞれに数日、場合によっては 1 週間以上かかる場合があります。それはあなたのスケジュール次第です。
|
|
|
|
|
|
毎日、リストの次の主題を取り上げ、その主題に関するビデオをいくつか見てから、
|
|
|
このコース用に選択した言語でそのデータ構造またはアルゴリズムの実装を作成します。
|
|
|
|
|
|
私のコードはここで見ることができます:
|
|
|
- [C](https://github.com/jwasham/practice-c)
|
|
|
- [C++](https://github.com/jwasham/practice-cpp)
|
|
|
- [Python]( https://github.com/jwasham/practice-python)
|
|
|
|
|
|
すべてのアルゴリズムを覚える必要はありません。独自の実装を作成できる程度に理解できれば十分です。
|
|
|
|
|
|
## コーディングに関する質問の練習
|
|
|
|
|
|
なぜこれがここにあるのでしょうか? 面接する準備ができていません。
|
|
|
|
|
|
[その後、戻ってこれを読んでください。](#学習中にコーディング面接の質問をする)
|
|
|
|
|
|
プログラミングの問題を練習する必要がある理由:
|
|
|
- 問題の認識、および適切なデータ構造とアルゴリズムがどこに適合するか
|
|
|
- 問題の要件を収集する
|
|
|
- 面接で行うのと同じように、問題について自分なりに説明する
|
|
|
- コンピューターではなく、ホワイトボードまたは紙にコーディングする
|
|
|
- 解決策のための時間と空間の複雑さを考え出す (下記の Big-O を参照)
|
|
|
- テストあなたの解決策
|
|
|
|
|
|
面接で体系的かつコミュニケーション的に問題を解決するための素晴らしい入門書があります。これはプログラミングのインタビュー本からもわかります
|
|
|
が、私はこれが素晴らしいと思いました:
|
|
|
[Algorithm design canvas](http://www.hiredintech.com/algorithm-design/)
|
|
|
|
|
|
コードを紙ではなく、ホワイトボードまたは紙に書きます。コンピューター。いくつかのサンプル入力を使用してテストします。次に、それを入力してコンピュータでテストします。
|
|
|
|
|
|
家にホワイトボードがない場合は、画材店で大きな描画パッドを購入してください。ソファに座って練習することもできます。
|
|
|
こちらは私の「ソファホワイトボード」です。写真ではスケールを調整するためにペンを追加しました。ペンを使っていると、消せたらいいのにと思うでしょう。
|
|
|
すぐに散らかります。**鉛筆と消しゴムを使用します。**
|
|
|
|
|
|
|
|
|
|
|
|
**コーディングの問題の練習は、プログラミングの問題の答えを覚えることではありません。**
|
|
|
|
|
|
## コーディングの問題
|
|
|
|
|
|
[ここ](#面接対策本) の主要なコーディング インタビュー ブックを忘れないでください。
|
|
|
|
|
|
問題の解決:
|
|
|
- [How to Find a Solution](https://www.topcoder.com/thrive/articles/How%20To%20Find%20a%20Solution)
|
|
|
- [How to Dissect a Topcoder Problem Statement](https://www.topcoder.com/thrive/articles/How%20To%20Dissect%20a%20Topcoder%20Problem%20Statement%20Content)
|
|
|
|
|
|
コーディング インタビューの質問ビデオ:
|
|
|
- [IDeserve (88 videos)](https://www.youtube.com/playlist?list=PLamzFoFxwoNjPfxzaWqs7cZGsPYy0x_gI)
|
|
|
- [Tushar Roy (5 playlists)](https://www.youtube.com/user/tusharroy2525/playlists?shelf_id=2&view=50&sort=dd)
|
|
|
- 問題解決策のウォークスルーに最適
|
|
|
- [Nick White - LeetCode Solutions (187 Videos)](https://www.youtube.com/playlist?list=PLU_sdQYzUj2keVENTP0a5rdykRSgg9Wp-)
|
|
|
- ソリューションとコードの適切な説明
|
|
|
- 短時間で何本も視聴できる
|
|
|
- [FisherCoder - LeetCode Solutions](https://youtube.com/FisherCoder)
|
|
|
|
|
|
チャレンジ/練習サイト:
|
|
|
- [LeetCode](https://leetcode.com/)
|
|
|
- 私のお気に入りのコーディングの問題サイト。おそらく準備する 1 ～ 2 か月分の購読料を払う価値があります。
|
|
|
- コードのウォークスルーについては、上記の Nick White と FisherCoder のビデオを参照してください。
|
|
|
- [HackerRank](https://www.hackerrank.com/)
|
|
|
- [TopCoder](https://www.topcoder.com/)
|
|
|
- [Codeforces](https://codeforces.com/)
|
|
|
- [Codility](https://codility.com/programmers/)
|
|
|
- [Geeks for Geeks](https://practice.geeksforgeeks.org/explore/?page=1)
|
|
|
- [AlgoExpert](https://www.algoexpert.io/product)
|
|
|
- Google のエンジニアによって作成されたこれは、スキルを磨くための優れたリソースでもあります。
|
|
|
- [Project Euler](https://projecteuler.net/)
|
|
|
- 非常に数学に重点が置かれており、コーディング面接にはあまり適していません
|
|
|
|
|
|
## 始めましょう
|
|
|
|
|
|
さて、話は十分です、学びましょう！
|
|
|
|
|
|
ただし、学習中に上記のコーディング問題に取り組むことを忘れないでください。
|
|
|
|
|
|
## アルゴリズムの複雑さ/Big-O/漸近分析
|
|
|
|
|
|
- ここでは何も実装する必要はありません。ビデオを見てメモを取るだけです。わーい！
|
|
|
- ここにはたくさんのビデオがあります。理解できるまで十分に見てください。いつでも戻ってレビューすることができます。
|
|
|
- 背後にある数学がすべて理解できなくても心配する必要はありません。
|
|
|
- Big-O の観点からアルゴリズムの複雑さを表現する方法を理解する必要があるだけです。
|
|
|
- [ ] [ハーバード CS50 - 漸近記法 (動画)](https://www.youtube.com/watch?v=iOq5kSKqeR4)
|
|
|
- [ ] [Big O Notations (一般的なクイック チュートリアル) (動画)](https://www.youtube.com/watch?v=V6mKVRU1evU)
|
|
|
- [ ] [Big O Notation (およびオメガとシータ) - 最良の数学的説明 (動画)](https://www.youtube.com/watch?v=ei-A_wy5Yxw&index=2&list=PL1BaGV1cIH4UhkL8a9bJGG356covJ76qN)
|
|
|
- [ ] [スキエナ](https://www.youtube.com/watch?v=z1mkCe3kVUA)
|
|
|
- [ ] [カリフォルニア大学バークレー校ビッグオー (動画)](https://archive.org/details/ucberkeley_webcast_VIS4YDpuP98)
|
|
|
- [ ] [償却分析 (動画)](https://www.youtube.com/watch?v=B3SpQZaAZP4&index=10&list=PL1BaGV1cIH4UhkL8a9bJGG356covJ76qN)
|
|
|
- [ ] TopCoder (漸化式とマスター定理を含む):
|
|
|
- [計算の複雑さ: セクション 1](https://www.topcoder.com/thrive/articles/Computational%20Complexity%20part%20one)
|
|
|
- [計算の複雑さ: セクション 2](https://www.topcoder.com/thrive/articles/Computational%20Complexity%20part%20two)
|
|
|
- [ ] [チートシート](http://bigocheatsheet.com/)
|
|
|
- [ ] [[Review] Analyzing Algorithms (playlist) in 18 minutes (video)](https://www.youtube.com/playlist?list=PL9xmBV_5YoZMxejjIyFHWa-4nKg6sdoIv)
|
|
|
|
|
|
|
|
|
まあ、それだけで十分です。
|
|
|
|
|
|
「コーディング インタビューの解読」を進めると、これに関する章があり、最後に、さまざまなアルゴリズムの実行時の複雑さを特定できるかどうかを確認するクイズがあります。それはスーパーレビューとテストです。
|
|
|
|
|
|
## データ構造
|
|
|
|
|
|
- ### 配列
|
|
|
- [ ] 配列について:
|
|
|
- [アレイ CS50 ハーバード大学](https://www.youtube.com/watch?v=tI_tIZFyKBw&t=3009s)
|
|
|
- [配列 (動画)](https://www.coursera.org/lecture/data-structures/arrays-OsBSF)
|
|
|
- [UC Berkeley CS61B - Linear and Multi-Dim Arrays (動画) (15 分 32 秒から視聴開始)](https://archive.org/details/ucberkeley_webcast_Wp8oiO_CZZE) (Start watching from 15m 32s)
|
|
|
- [動的配列 (動画)](https://www.coursera.org/lecture/data-structures/dynamic-arrays-EwbnV)
|
|
|
- [ギザギザ配列 (動画)](https://www.youtube.com/watch?v=1jtrQqYpt7g)
|
|
|
- [ ] ベクトルを実装します (自動サイズ変更を備えた可変配列):
|
|
|
- [ ] 配列とポインターを使用したコーディングと、インデックスを使用する代わりにインデックスにジャンプするポインターの計算を練習します。
|
|
|
- [ ] メモリが割り当てられた新しい生データ配列
|
|
|
- 内部で int 配列を割り当てることができますが、その機能は使用できません
|
|
|
- 16 から開始するか、開始番号がそれより大きい場合は、2 のべき乗 - 16、32、64、128 を使用します。
|
|
|
- [ ] size() - アイテムの数
|
|
|
- [ ] Capacity() - 保持できるアイテムの数
|
|
|
- [ ] is_empty()
|
|
|
- [ ] at(index) - 指定されたインデックスにある項目を返します。インデックスが範囲外の場合は爆発します。
|
|
|
- [ ] プッシュ(アイテム)
|
|
|
- [ ] insert(index, item) - インデックスに項目を挿入し、そのインデックスの値と末尾の要素を右にシフトします
|
|
|
- [ ] prepend(item) - インデックス 0 の上に挿入を使用できます
|
|
|
- [ ] Pop() - 末尾から削除し、値を返します
|
|
|
- [ ] delete(index) - インデックスにある項目を削除し、末尾の要素をすべて左にシフトします
|
|
|
- [ ]remove(item) - 値を検索し、それを保持するインデックスを削除します (複数の場所にある場合でも)
|
|
|
- [ ] find(item) - 値を検索し、その値を持つ最初のインデックスを返します。見つからない場合は -1 を返します。
|
|
|
- [ ]size(new_capacity) // プライベート関数
|
|
|
- 容量に達したら、サイズを 2 倍に変更します
|
|
|
- アイテムをポップするとき、サイズが容量の 1/4 の場合、サイズを半分に変更します
|
|
|
- [ ] 時間
|
|
|
- O(1) は、最後に追加/削除 (より多くの領域の割り当てのために償却)、インデックス付け、または更新を行います。
|
|
|
- O(n) は他の場所に挿入/削除します
|
|
|
- [ ] 空間
|
|
|
- メモリ内で連続しているため、近接性によりパフォーマンスが向上します
|
|
|
- 必要なスペース = (配列の容量、>= n) * 項目のサイズ、ただし 2n であっても O(n)
|
|
|
|
|
|
- ### 連結リスト
|
|
|
- [ ] 説明：
|
|
|
- [ ] [単独連結されたリスト(動画)](https://www.coursera.org/learn/data-structures/lecture/kHhgK/singly-linked-lists)
|
|
|
- [ ] [CS 61B - 連結リスト1(動画)](https://www.youtube.com/watch?v=htzJdKoEmO0&list=PL4BBB74C7D2A1049C&index=7)
|
|
|
- [ ] [CS 61B - 連結リスト2(動画)](https://www.youtube.com/watch?v=-c4I3gFYe3w&index=8&list=PL4BBB74C7D2A1049C)
|
|
|
- [ ] [[レビュー] 4 分でわかるリンクリスト (動画)](https://youtu.be/F8AbOfQwl1c)
|
|
|
- [ ] [Cコード(動画)](https://www.youtube.com/watch?v=QN6FPiD0Gzo)
|
|
|
- ビデオ全体ではなく、ノード構造とメモリ割り当てに関する部分のみ
|
|
|
- [ ] 連結リストと配列：
|
|
|
- [コア連結リストと配列 (動画)](https://www.coursera.org/learn/data-structures-optimizing-performance/lecture/rjBs9/core-linked-lists-vs-arrays)
|
|
|
- [現実世界の連結リストと配列 (動画)](https://www.coursera.org/learn/data-structures-optimizing-performance/lecture/quaUd/in-the-real-world-lists-vs)
|
|
|
- [ ] [連結リスト(動画)を避けるべき理由](https://www.youtube.com/watch?v=YQs6IC-vgmo)
|
|
|
- [ ] 注意事項: ポインタからポインタへの知識が必要です: (ポインタが指すアドレスを変更する可能性のある関数にポインタを渡すときのため) このページは、ptr から ptr への理解だけを目的としています。このリスト走査スタイルはお勧めしません。賢いため、可読性と保守性が低下します。
|
|
|
- [ポインターへのポインター](https://www.eskimo.com/~scs/cclass/int/sx8.html)
|
|
|
- [ ] 実装する(私はテールポインタ＆なしで行った)：
|
|
|
- [ ] size() - リスト内のデータ要素の数を返す
|
|
|
- [ ] empty() - 空の場合はboolを返します
|
|
|
- [ ] value_at(index) - n番目の項目の値を返します(最初は0から始まります)
|
|
|
- [ ] push_front(value) - リストの先頭に項目を追加します
|
|
|
- [ ] pop_front() - 前面アイテムを削除してその値を返します
|
|
|
- [ ] push_back(value) - 最後に項目を追加する
|
|
|
- [ ] pop_back() - 終了アイテムを削除し、その値を返します
|
|
|
- [ ] front() - フロントアイテムの値を取得する
|
|
|
- [ ] back() - 終了項目の値を取得する
|
|
|
- [ ] insert(index、value) - インデックスに値を挿入するので、そのインデックスの現在のアイテムはインデックスの新しいアイテムによってポイントされます
|
|
|
- [ ] erase(index) - 指定したインデックスのノードを削除する
|
|
|
- [ ] value_n_from_end(n) - リストの最後からn番目のノードの値を返します
|
|
|
- [ ] reverse() - リストを反転する
|
|
|
- [ ] remove_value(value) - この値を持つリストの最初の項目を削除します。
|
|
|
- [ ] 二重連結リスト
|
|
|
- [説明(動画)](https://www.coursera.org/learn/data-structures/lecture/jpGKD/doubly-linked-lists)
|
|
|
- 実装する必要はありません
|
|
|
|
|
|
- ### スタック
|
|
|
- [ ] [スタック (動画)](https://www.coursera.org/learn/data-structures/lecture/UdKzQ/stacks)
|
|
|
- [ ] [【復讐】3分でわかるスタック（動画）](https://youtu.be/KcT3aVgrrpU)
|
|
|
- [ ] 実装しません。配列を使った実装は簡単です
|
|
|
|
|
|
- ### キュー
|
|
|
- [ ] [キュー(動画)](https://www.coursera.org/learn/data-structures/lecture/EShpq/queue)
|
|
|
- [ ] [環状バッファ/ FIFO](https://en.wikipedia.org/wiki/Circular_buffer)
|
|
|
- [ ] [【復習】3分でわかるキュー（動画）](https://youtu.be/D6gu-_tmEpQ)
|
|
|
- [ ] テールポインタ付き連結リストを使って実装する：
|
|
|
- enqueue(value) - テールの位置に値を追加する
|
|
|
- dequeue() - 値を返し、少なくとも最近追加された要素を削除する(前面)
|
|
|
- empty()
|
|
|
- [ ] 固定長配列を使って実装する：
|
|
|
- enqueue(value) - 利用可能なストレージの最後にアイテムを追加する
|
|
|
- dequeue() - 値を返し、最近追加された要素のうち最も古い要素を削除します
|
|
|
- empty()
|
|
|
- full()
|
|
|
- [ ] コスト：
|
|
|
- 先頭でエンキューし、末尾でデキューするリンク リストを使用した悪い実装では、最後から 2 番目の要素が必要になるため、O(n) となり、各デキューの完全な走査が発生します。
|
|
|
- enqueue：O(1)(償却、連結リストと配列[プロービング])
|
|
|
- dequeue：O(1)(連結リストと配列)
|
|
|
- empty：O(1)(連結リストと配列)
|
|
|
|
|
|
- ### ハッシュテーブル
|
|
|
- [ ] 動画：
|
|
|
- [ ] [チェーンを使用したハッシュ (動画)](https://www.youtube.com/watch?v=0M_kIqhwbFo&list=PLUl4u3cNGP61Oq3tWYp6V_F-5jb5L2iHb&index=8)
|
|
|
- [ ] [テーブルダブリング、Karp-Rabin (動画)](https://www.youtube.com/watch?v=BRO7mVIFt08&index=9&list=PLUl4u3cNGP61Oq3tWYp6V_F-5jb5L2iHb)
|
|
|
- [ ] [公開アドレス指定、暗号化ハッシング(動画)](https://www.youtube.com/watch?v=rvdJDijO2Ro&index=10&list=PLUl4u3cNGP61Oq3tWYp6V_F-5jb5L2iHb)
|
|
|
- [ ] [PyCon 2010: 強力な辞書 (動画)](https://www.youtube.com/watch?v=C4Kc8xzcA68)
|
|
|
- [ ] [PyCon 2017: 辞書がさらに強力に (動画))](https://www.youtube.com/watch?v=66P5FMkWoVU)
|
|
|
- [ ] [(上級)Randomization：ユニバーサル＆完全 ハッシング(動画)](https://www.youtube.com/watch?v=z0lJ2k0sl1g&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp&index=11)
|
|
|
- [ ] [(高度)完全ハッシング(動画)](https://www.youtube.com/watch?v=N0COwN14gt0&list=PL2B4EEwhKD-NbwZ4ezj7gyc_3yNrojKM9&index=4)
|
|
|
- [ ] [【復習】4分でわかるハッシュテーブル（動画）](https://www.youtube.com/watch?v=knV86FlSXJ8)
|
|
|
|
|
|
- [ ] オンラインコース：
|
|
|
- [ ] [コアハッシュテーブル(動画)](https://www.coursera.org/learn/data-structures-optimizing-performance/lecture/m7UuP/core-hash-tables)
|
|
|
- [ ] [データ構造(動画)](https://www.coursera.org/learn/data-structures/home/week/3)
|
|
|
- [ ] [電話帳の問題(動画)](https://www.coursera.org/learn/data-structures/lecture/NYZZP/phone-book-problem)
|
|
|
- [ ] 分散ハッシュテーブル：
|
|
|
- [Dropbox でのインスタント アップロードとストレージの最適化 (動画)](https://www.coursera.org/learn/data-structures/lecture/DvaIb/instant-uploads-and-storage-optimization-in-dropbox)
|
|
|
- [分散ハッシュテーブル(動画)](https://www.coursera.org/learn/data-structures/lecture/tvH8H/distributed-hash-tables)
|
|
|
|
|
|
- [ ] 線形プロービングを使用して配列で実装する
|
|
|
- hash(k、m) - mはハッシュテーブルのサイズです
|
|
|
- add(key、value) - キーがすでに存在する場合は、値を更新します。
|
|
|
- exists(キー)
|
|
|
- get(key)
|
|
|
- remove(キー)
|
|
|
|
|
|
## その他の知識
|
|
|
|
|
|
- ### 二分探索
|
|
|
- [ ] [二分探索(動画)](https://www.youtube.com/watch?v=D5SrAga1pno)
|
|
|
- [ ] [二分探索(動画)](https://www.khanacademy.org/computing/computer-science/algorithms/binary-search/a/binary-search)
|
|
|
- [ ] [詳細](https://www.topcoder.com/community/data-science/data-science-tutorials/binary-search/)
|
|
|
- [ ] [ブループリント](https://leetcode.com/discuss/general-discussion/786126/python-powerful-ultimate-binary-search-template-solved-many-problems)
|
|
|
- [ ] [【復習】4分でわかる二分探索（動画）](https://youtu.be/fDKIpRe8GW4)
|
|
|
- [ ] 実装：
|
|
|
- 二分探索(ソートされた整数の配列)
|
|
|
- 再帰を利用した二分探索
|
|
|
|
|
|
- ### ビット演算
|
|
|
- [ ] [ビットチートシート](https://github.com/jwasham/coding-interview-university/blob/main/extras/cheat%20sheets/bits-cheat-sheet.pdf)
|
|
|
- (2^1 から 2^16 および 2^32) までの 2 のべき乗の多くを知っておく必要があります
|
|
|
- [ ] ＆、|、^、〜、>>、<<を使ってビットを操作することについての本当の理解を得る
|
|
|
- [ ] [言語](https://en.wikipedia.org/wiki/Word_(computer_architecture))
|
|
|
- [ ] [良いイントロ：ビット操作(動画)](https://www.youtube.com/watch?v=7jkIUgLC29I)
|
|
|
- [ ] [Cプログラミングチュートリアル2-10：ビット演算子(動画)](https://www.youtube.com/watch?v=d0AwjSpNXR0)
|
|
|
- [ ] [ビット操作](https://en.wikipedia.org/wiki/Bit_manipulation)
|
|
|
- [ ] [ビット演算](https://en.wikipedia.org/wiki/Bitwise_operation)
|
|
|
- [ ] [Bithacks](https://graphics.stanford.edu/~seander/bithacks.html)
|
|
|
- [ ] [The Bit Twiddler](http://bits.stephan-brumme.com/)
|
|
|
- [ ] [インタラクティブなBit Twiddler](http://bits.stephan-brumme.com/interactive.html)
|
|
|
- [ ] 2と1の補数
|
|
|
- [バイナリ：Plusses＆Minuses(なぜ2の補数を使うのか)(動画)](https://www.youtube.com/watch?v=lKTsv6iVxV4)
|
|
|
- [1の補数](https://en.wikipedia.org/wiki/Ones%27_complement)
|
|
|
- [2の補数](https://en.wikipedia.org/wiki/Two%27s_complement)
|
|
|
- [ ] カウントセットビット
|
|
|
- [1バイトのビットを数える4つの方法(動画)](https://youtu.be/Hzuzo9NJrlc)
|
|
|
- [カウントビット](https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan)
|
|
|
- [セットビットの数を32ビット整数で数える方法](http://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32ビット整数)
|
|
|
- [ ] カウントセットビット:
|
|
|
- [バイト内のビットを数える 4 つの方法 (動画)](https://youtu.be/Hzuzo9NJrlc)
|
|
|
- [ビットをカウントする](https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan)
|
|
|
- [32 ビット整数のセットビット数を数える方法](http://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer)
|
|
|
- [ ] スワップ値：
|
|
|
- [スワップ](http://bits.stephan-brumme.com/swap.html)
|
|
|
- [ ] 絶対値：
|
|
|
- [絶対整数](http://bits.stephan-brumme.com/absInteger.html)
|
|
|
|
|
|
## ツリー
|
|
|
|
|
|
- ### ツリーとは
|
|
|
- [ ] [ツリーの紹介 (動画)](https://www.coursera.org/lecture/data-structures/trees-95qda)
|
|
|
- [ ] [ツリートラバーサル (動画)](https://www.coursera.org/lecture/data-structures/tree-traversal-fr51b)
|
|
|
- [ ] [BFS (幅優先検索) および DFS (深さ優先検索) (動画)](https://www.youtube.com/watch?v=uWL6FJhq5fM)
|
|
|
- BFS のメモ:
|
|
|
- レベル順序 (BFS、キューを使用)
|
|
|
- 時間計算量: O(n)
|
|
|
- 空間の複雑さ: 最良: O(1)、最悪: O(n/2)=O(n)
|
|
|
- DFS のメモ:
|
|
|
- 時間計算量: O(n)
|
|
|
- 空間複雑さ: 最良: O(log n)
|
|
|
- 平均 最高の木の高さ: O(n)
|
|
|
best: O(log n)
|
|
|
- 平均 最低の木の高さ: O(n)
|
|
|
worst: O(n)
|
|
|
- 順序 (DFS: 左、自分、右)
|
|
|
- 事後順序 (DFS: 左、右、自己)
|
|
|
- 予約注文 (DFS: 自分、左、右)
|
|
|
- [ ] [【復習】4分でわかる幅優先検索（動画）](https://youtu.be/HZ5YTanv5QE)
|
|
|
- [ ] [【復習】4分で深さ優先検索（動画）](https://youtu.be/Urx87-NMm6c)
|
|
|
- [ ] [【復習】11 分でわかるツリー トラバーサル (プレイリスト) (動画)](https://www.youtube.com/playlist?list=PL9xmBV_5YoZO1JC2RgEi04nLy6D-rKk6b)
|
|
|
|
|
|
- ### 二分探索木：BST
|
|
|
- [ ] [二分探索木の復習 (動画)](https://www.youtube.com/watch?v=x6At0nzX92o&index=1&list=PLA5Lqm4uh9Bbq-E0ZnqTIa8LRaL77ica6)
|
|
|
- [ ] [はじめに（動画）](https://www.coursera.org/learn/data-structures/lecture/E7cXP/introduction)
|
|
|
- [ ] [MIT (動画)](https://www.youtube.com/watch?v=76dhtgZt38A&ab_channel=MITOpenCourseWare)
|
|
|
- C / C ++：
|
|
|
- [ ] [二分探索木 - C / C ++での実装(動画)](https://www.youtube.com/watch?v=COZK7NATh4k&list=PL2_aWCzGMAwI3W_JlcBbtYTwiQSsOTa6P&index=28)
|
|
|
- [ ] [BSTの実装 - スタックとヒープのメモリ割り当て(動画)](https://www.youtube.com/watch?v=hWokyBoo0aI&list=PL2_aWCzGMAwI3W_JlcBbtYTwiQSsOTa6P&index=29)
|
|
|
- [ ] [二分探索木(動画)の最小要素と最大要素を検索](https://www.youtube.com/watch?v=Ut90klNN264&index=30&list=PL2_aWCzGMAwI3W_JlcBbtYTwiQSsOTa6P)
|
|
|
- [ ] [二分木の高さを見つける(動画)](https://www.youtube.com/watch?v=_pnqMz5nrRs&list=PL2_aWCzGMAwI3W_JlcBbtYTwiQSsOTa6P&index=31)
|
|
|
- [ ] [二分木トラバース - 幅優先戦略(動画)](https://www.youtube.com/watch?v=9RHO6jU--GU&list=PL2_aWCzGMAwI3W_JlcBbtYTwiQSsOTa6P&index=32)
|
|
|
- [ ] [二分木：レベルオーダートラバーサル(動画)](https://www.youtube.com/watch?v=86g8jAQug04&index=33&list=PL2_aWCzGMAwI3W_JlcBbtYTwiQSsOTa6P)
|
|
|
- [ ] [二分木トラバーサル：Preorder、Inorder、Postorder(video)](https://www.youtube.com/watch?v=gm8DUJJhmY4&index=34&list=PL2_aWCzGMAwI3W_JlcBbtYTwiQSsOTa6P)
|
|
|
- [ ] [二分木が二分探索木かどうかを確認する(動画)](https://www.youtube.com/watch?v=yEwSGhSsT0U&index=35&list=PL2_aWCzGMAwI3W_JlcBbtYTwiQSsOTa6P)
|
|
|
- [ ] [二分探索木(動画)からノードを削除](https://www.youtube.com/watch?v=gcULXE7ViZw&list=PL2_aWCzGMAwI3W_JlcBbtYTwiQSsOTa6P&index=36)
|
|
|
- [ ] [二分探索木(動画)のInorder Successor](https://www.youtube.com/watch?v=5cPbNCrdotA&index=37&list=PL2_aWCzGMAwI3W_JlcBbtYTwiQSsOTa6P)
|
|
|
- [ ] 実装：
|
|
|
- [ ] [insert // ツリーに値を挿入します](https://leetcode.com/problems/insert-into-a-binary-search-tree/submissions/987660183/)
|
|
|
- [ ] get_node_count //格納された値の数を取得する
|
|
|
- [ ] print_values //最小値から最大値まで木の値を出力します
|
|
|
- [ ] delete_tree
|
|
|
- [ ] is_in_tree //与えられた値が木に存在する場合はtrueを返します
|
|
|
- [ ] [get_height // ノード単位の高さを返します (単一ノードの高さは 1)](https://www.geeksforgeeks.org/find-the-maximum-depth-or-height-of-a-tree/)
|
|
|
- [ ] get_min //木に格納されている最小値を返します
|
|
|
- [ ] get_max //木に格納されている最大値を返します
|
|
|
- [ ] [is_binary_search_tree](https://leetcode.com/problems/validate-binary-search-tree/)
|
|
|
- [ ] delete_value
|
|
|
- [ ] get_successor //指定された値の後に木の次に高い値を返し、存在しなければ-1を返します
|
|
|
|
|
|
- ### ヒープ/優先度つきキュー/二分ヒープ
|
|
|
- 木として可視化されますが、通常はストレージ内で線形です(配列、連結リスト)
|
|
|
- [ ] [ヒープ](https://en.wikipedia.org/wiki/Heap_(data_structure))
|
|
|
- [ ] [はじめに(動画)](https://www.coursera.org/learn/data-structures/lecture/2OpTs/introduction)
|
|
|
- [ ] [ナイーブな実装(動画)](https://www.coursera.org/learn/data-structures/lecture/z3l9N/naive-implementations)
|
|
|
- [ ] [二分木(動画)](https://www.coursera.org/learn/data-structures/lecture/GRV2q/binary-trees)
|
|
|
- [ ] [木の高さ備考(動画)](https://www.coursera.org/learn/data-structures/supplement/S5xxz/tree-height-remark)
|
|
|
- [ ] [基本的な操作(動画)](https://www.coursera.org/learn/data-structures/lecture/0g1dl/basic-operations)
|
|
|
- [ ] [完全な二分木(動画)](https://www.coursera.org/learn/data-structures/lecture/gl5Ni/complete-binary-trees)
|
|
|
- [ ] [疑似コード(動画)](https://www.coursera.org/learn/data-structures/lecture/HxQo9/pseudocode)
|
|
|
- [ ] [ヒープソート - ジャンプして開始(動画)](https://youtu.be/odNJmw5TOEE?list=PLFDnELG9dpVxQCxuD-9BSy2E7BWY3t5Sm&t=3291)
|
|
|
- [ ] [ヒープソート(動画)](https://www.coursera.org/learn/data-structures/lecture/hSzMO/heap-sort)
|
|
|
- [ ] [ヒープを作る(動画)](https://www.coursera.org/learn/data-structures/lecture/dwrOS/building-a-heap)
|
|
|
- [ ] [MIT：ヒープとヒープソート(動画)](https://www.youtube.com/watch?v=B7hVxCmfPtM&index=4&list=PLUl4u3cNGP61Oq3tWYp6V_F-5jb5L2iHb)
|
|
|
- [ ] [CS 61B講義24：優先度つきキュー(動画)](https://www.youtube.com/watch?v=yIUFT6AKBGE&index=24&list=PL4BBB74C7D2A1049C)
|
|
|
- [ ] [線形時間ビルドヒープ (最大ヒープ)](https://www.youtube.com/watch?v=MiyLo8adrWw)
|
|
|
- [ ] [【復習】13分でヒープ（プレイリスト）（動画）](https://www.youtube.com/playlist?list=PL9xmBV_5YoZNsyqgPW-DNwUeT8F8uhWc6)
|
|
|
- [ ] 最大ヒープを実装する：
|
|
|
- [ ] insert
|
|
|
- [ ] sift_up - 挿入に必要
|
|
|
- [ ] get_max - 最大項目を削除せずに返します
|
|
|
- [ ] get_size() - 格納された要素の数を返す
|
|
|
- [ ] is_empty() - ヒープに要素が含まれていない場合はtrueを返します。
|
|
|
- [ ] extract_max - 最大アイテムを返し、それを削除します。
|
|
|
- [ ] sift_down - extract_maxに必要です
|
|
|
- [ ] remove(x) - インデックスxのアイテムを削除する
|
|
|
- [ ] heapify - heap_sortに必要な要素の配列からヒープを作成する
|
|
|
- [ ] heap_sort() - ソートされていない配列を取得し、最大ヒープまたは最小ヒープを使用してその場でソートされた配列に変換します。
|
|
|
|
|
|
## ソート
|
|
|
|
|
|
- [ ] ノート：
|
|
|
- ソートを実装し、最良のケース/最悪のケース、それぞれの平均的な複雑さを知る：
|
|
|
- バブルソートなし - ひどいです - O(n^2) (n <= 16 の場合を除く)
|
|
|
- ソートアルゴリズムの安定性( "Quicksortは安定していますか？")
|
|
|
- [ソートアルゴリズムの安定性](https://en.wikipedia.org/wiki/Sorting_algorithm#Stability)
|
|
|
- [ソートアルゴリズムの安定性](http://stackoverflow.com/questions/1517793/stability-in-sorting-algorithms)
|
|
|
- [ソートアルゴリズムの安定性](http://www.geeksforgeeks.org/stability-in-sorting-algorithms/)
|
|
|
- [ソートアルゴリズム - 安定性](http://homepages.math.uic.edu/~leon/cs-mcs401-s08/handouts/stability.pdf)
|
|
|
- [ ] 連結リストで使用できるアルゴリズムはどれですか？どの配列ですか？両方でどちら？
|
|
|
- 連結リストのソートはお勧めしませんが、マージソートは実行可能です。
|
|
|
- [連結リストのマージソート](http://www.geeksforgeeks.org/merge-sort-for-linked-list/)
|
|
|
|
|
|
- ヒープソートについては、上記のヒープデータ構造を参照してください。ヒープソートは素晴らしいですが、安定していません。
|
|
|
|
|
|
- [ ] [セッジウィック - マージソート (5動画)](https://www.coursera.org/learn/algorithms-part1/home/week/3)
|
|
|
- [ ] [1. マージソート](https://www.coursera.org/lecture/algorithms-part1/mergesort-ARWDq)
|
|
|
- [ ] [2. ボトムアップ マージソート](https://www.coursera.org/learn/algorithms-part1/lecture/PWNEl/bottom-up-mergesort)
|
|
|
- [ ] [3. 並べ替えの複雑さ](https://www.coursera.org/lecture/algorithms-part1/sorting-complexity-xAltF)
|
|
|
- [ ] [4. コンパレーター](https://www.coursera.org/lecture/algorithms-part1/comparators-9FYhS)
|
|
|
- [ ] [5. 安定性](https://www.coursera.org/learn/algorithms-part1/lecture/pvvLZ/stability)
|
|
|
|
|
|
- [ ] [セッジウィック - クイックソート (4動画)](https://www.coursera.org/learn/algorithms-part1/home/week/3)
|
|
|
- [ ] [1. クイックソート](https://www.coursera.org/lecture/algorithms-part1/quicksort-vjvnC)
|
|
|
- [ ] [2. セレクション](https://www.coursera.org/lecture/algorithms-part1/selection-UQxFT)
|
|
|
- [ ] [3. 重複キー](https://www.coursera.org/lecture/algorithms-part1/duplicate-keys-XvjPd)
|
|
|
- [ ] [4. システムソート](https://www.coursera.org/lecture/algorithms-part1/system-sorts-QBNZ7)
|
|
|
|
|
|
- [ ] カリフォルニア大学バークレー校:
|
|
|
- [ ] [CS 61B 講義 29: 並べ替え I (動画)](https://archive.org/details/ucberkeley_webcast_EiUvYS2DT6I)
|
|
|
- [ ] [CS 61B 講義 30: 並べ替え II (動画)](https://archive.org/details/ucberkeley_webcast_2hTY3t80Qsk)
|
|
|
- [ ] [CS 61B 講義 32: 分類 III (動画)](https://archive.org/details/ucberkeley_webcast_Y6LOLpxg6Dc)
|
|
|
- [ ] [CS 61B レクチャー 33: 並べ替え V (動画)](https://archive.org/details/ucberkeley_webcast_qNMQ4ly43p4)
|
|
|
- [ ] [CS 61B 2014-04-21: 基数ソート (動画)](https://archive.org/details/ucberkeley_webcast_pvbBMd-3NoI)
|
|
|
|
|
|
- [ ] [バブルソート(動画)](https://www.youtube.com/watch?v=P00xJgWzz2c&index=1&list=PL89B61F78B552C1AB)
|
|
|
- [ ] [バブルソートの分析(動画)](https://www.youtube.com/watch?v=ni_zk257Nqo&index=7&list=PL89B61F78B552C1AB)
|
|
|
- [ ] [挿入ソート、マージソート(動画)](https://www.youtube.com/watch?v=Kg4bqzAqRBM&index=3&list=PLUl4u3cNGP61Oq3tWYp6V_F-5jb5L2iHb)
|
|
|
- [ ] [挿入ソート(動画)](https://www.youtube.com/watch?v=c4BRHC7kTaQ&index=2&list=PL89B61F78B552C1AB)
|
|
|
- [ ] [マージソート(動画)](https://www.youtube.com/watch?v=GCae1WNvnZM&index=3&list=PL89B61F78B552C1AB)
|
|
|
- [ ] [クイックソート(動画)](https://www.youtube.com/watch?v=y_G9BkAm6B8&index=4&list=PL89B61F78B552C1AB)
|
|
|
- [ ] [選択ソート(動画)](https://www.youtube.com/watch?v=6nDMgr0-Yyo&index=8&list=PL89B61F78B552C1AB)
|
|
|
|
|
|
- [ ] ソート コードを結合:
|
|
|
- [ ] [出力配列 (C) の使用](http://www.cs.yale.edu/homes/aspnes/classes/223/examples/sorting/mergesort.c)
|
|
|
- [ ] [出力配列の使用 (Python)](https://github.com/jwasham/practice-python/blob/master/merge_sort/merge_sort.py)
|
|
|
- [ ] [インプレース (C++)](https://github.com/jwasham/practice-cpp/blob/master/merge_sort/merge_sort.cc)
|
|
|
- [ ] クイックソートコード:
|
|
|
- [ ] [実装 (C)](http://www.cs.yale.edu/homes/aspnes/classes/223/examples/randomization/quick.c)
|
|
|
- [ ] [実装 (C)](https://github.com/jwasham/practice-c/blob/master/quick_sort/quick_sort.c)
|
|
|
- [ ] [実装 (Python)](https://github.com/jwasham/practice-python/blob/master/quick_sort/quick_sort.py)
|
|
|
|
|
|
|
|
|
- [ ] [【復習】18分で分かるソート(プレイリスト](https://www.youtube.com/playlist?list=PL9xmBV_5YoZOZSbGAXAPIq1BeUf4j20pl)
|
|
|
- [ ] [4 分で簡単ソート (動画)](https://youtu.be/Hoixgm4-P4M)
|
|
|
- [ ] [4 分でヒープソート (動画)](https://youtu.be/2DmK_H7IdTo)
|
|
|
- [ ] [3 分で並べ替えをマージする (動画)](https://youtu.be/4VqmGXwpLqc)
|
|
|
- [ ] [2 分でわかるバブルソート (動画)](https://youtu.be/xli_FI7CuzA)
|
|
|
- [ ] [3分でわかる選択ソート(動画)](https://youtu.be/g-PGLbMth_g)
|
|
|
- [ ] [2分で挿入ソート(動画)](https://youtu.be/JU767SDMDvA)
|
|
|
|
|
|
|
|
|
- [ ] 実装
|
|
|
- [ ] マージソート: O(n log n) 平均および最悪の場合
|
|
|
- [ ] クイックソート O(n log n) の平均ケース
|
|
|
- 選択ソートと挿入ソートは両方とも O(n^2) 平均および最悪の場合です
|
|
|
- ヒープソートについては、上記のヒープ データ構造を参照してください。
|
|
|
|
|
|
- [ ] 必須ではありませんが、お勧めします:
|
|
|
- [ ] [Sedgewick - 基数ソート (6動画)](https://www.coursera.org/learn/algorithms-part2/home/week/3)
|
|
|
- [ ] [1. Java の文字列](https://www.coursera.org/learn/algorithms-part2/lecture/vGHvb/strings-in-java)
|
|
|
- [ ] [2. キーのインデックス付きカウント](https://www.coursera.org/lecture/algorithms-part2/key-indexed-counting-2pi1Z)
|
|
|
- [ ] [3. 最下位桁の最初の文字列基数ソート](https://www.coursera.org/learn/algorithms-part2/lecture/c1U7L/lsd-radix-sort)
|
|
|
- [ ] [4. 最上位桁の最初の文字列基数ソート](https://www.coursera.org/learn/algorithms-part2/lecture/gFxwG/msd-radix-sort)
|
|
|
- [ ] [5. 3 ウェイ基数クイックソート](https://www.coursera.org/lecture/algorithms-part2/3-way-radix-quicksort-crkd5)
|
|
|
- [ ] [6. サフィックス配列](https://www.coursera.org/learn/algorithms-part2/lecture/TH18W/suffix-arrays)
|
|
|
- [ ] [基数ソート](http://www.cs.yale.edu/homes/aspnes/classes/223/notes.html#radixSort)
|
|
|
- [ ] [基数ソート (動画)](https://www.youtube.com/watch?v=xhr26ia4k38)
|
|
|
- [ ] [基数ソート、カウンティング ソート (線形時間指定制約) (動画)](https://www.youtube.com/watch?v=Nz1KZXbghj8&index=7&list=PLUl4u3cNGP61Oq3tWYp6V_F-5jb5L2iHb)
|
|
|
- [ ] [ランダム化: 行列乗算、クイックソート、フライヴァルドのアルゴリズム (動画)](https://www.youtube.com/watch?v=cNB2lADK3_s&index=8&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp)
|
|
|
- [ ] [線形時間でのソート (動画)](https://www.youtube.com/watch?v=pOKy3RZbSws&list=PLUl4u3cNGP61hsJNdULdudlRL493b-XZf&index=14)
|
|
|
|
|
|
概要として、[15のソートアルゴリズム](https://www.youtube.com/watch?v=kPRA0W1kECg) を視覚的に表したものを次に示します。
|
|
|
この主題についてさらに詳細が必要な場合は、[一部の主題に関する追加の詳細](#一部の主題に関する追加の詳細) の「並べ替え」セクションを参照してください。
|
|
|
|
|
|
|
|
|
## グラフ
|
|
|
|
|
|
グラフはコンピューター サイエンスの多くの問題を表すために使用できるため、このセクションはツリーや並べ替えと同様に長くなります。
|
|
|
|
|
|
- ノート：
|
|
|
- メモリ内でグラフを表現するには 4 つの基本的な方法があります。
|
|
|
- オブジェクトとポインタ
|
|
|
- 隣接行列
|
|
|
- 隣接リスト
|
|
|
- 隣接マップ
|
|
|
- それぞれの表現とその長所と短所をよく理解する
|
|
|
- BFS と DFS - 計算の複雑さ、トレードオフ、および実際のコードでの実装方法を理解しています。
|
|
|
- 質問されたら、まずグラフベースの解決策を探し、見つからない場合は次に進みます。
|
|
|
|
|
|
- [ ] MIT(ビデオ):
|
|
|
- [ ] [幅優先検索](https://www.youtube.com/watch?v=oFVYVzlvk9c&t=14s&ab_channel=MITOpenCourseWare)
|
|
|
- [ ] [深さ優先検索](https://www.youtube.com/watch?v=IBfWDYSffUU&t=32s&ab_channel=MITOpenCourseWare)
|
|
|
|
|
|
- [ ] スキエナ講義 - 素晴らしい導入部:
|
|
|
- [ ] [CSE373 2020 - レクチャー 10 - グラフ データ構造 (動画)](https://www.youtube.com/watch?v=Sjk0xqWWPCc&list=PLOtl7M3yp-DX6ic0HGT0PUX_wiNmkWkXx&index=10)
|
|
|
- [ ] [CSE373 2020 - レクチャー 11 - グラフ トラバーサル (動画)](https://www.youtube.com/watch?v=ZTwjXj81NVY&list=PLOtl7M3yp-DX6ic0HGT0PUX_wiNmkWkXx&index=11)
|
|
|
- [ ] [CSE373 2020 - レクチャー 12 - 深さ優先検索 (動画)](https://www.youtube.com/watch?v=KyordYB3BOs&list=PLOtl7M3yp-DX6ic0HGT0PUX_wiNmkWkXx&index=12)
|
|
|
- [ ] [CSE373 2020 - レクチャー 13 - 最小スパニング ツリー (動画)](https://www.youtube.com/watch?v=oolm2VnJUKw&list=PLOtl7M3yp-DX6ic0HGT0PUX_wiNmkWkXx&index=13)
|
|
|
- [ ] [CSE373 2020 - レクチャー 14 - 最小スパニング ツリー (続き) (動画)](https://www.youtube.com/watch?v=RktgPx0MarY&list=PLOtl7M3yp-DX6ic0HGT0PUX_wiNmkWkXx&index=14)
|
|
|
- [ ] [CSE373 2020 - レクチャー 15 - グラフ アルゴリズム (続き 2) (動画)](https://www.youtube.com/watch?v=MUe5DXRhyAo&list=PLOtl7M3yp-DX6ic0HGT0PUX_wiNmkWkXx&index=15)
|
|
|
|
|
|
- [ ] グラフ (レビューなど):
|
|
|
- [ ] [6.006 単一ソース最短パス問題 (動画)](https://www.youtube.com/watch?v=Aa2sqUhIn-E&index=15&list=PLUl4u3cNGP61Oq3tWYp6V_F-5jb5L2iHb)
|
|
|
- [ ] [6.006 ダイクストラ (動画)](https://www.youtube.com/watch?v=NSHizBK9JD8&t=1731s&ab_channel=MITOpenCourseWare)
|
|
|
- [ ] [6.006 ベルマン-フォード (動画)](https://www.youtube.com/watch?v=f9cVS_URPc0&ab_channel=MITOpenCourseWare)
|
|
|
- [ ] [6.006 ディクストラの高速化 (動画)](https://www.youtube.com/watch?v=CHvQ3q_gJ7E&list=PLUl4u3cNGP61Oq3tWYp6V_F-5jb5L2iHb&index=18)
|
|
|
- [ ] [Aduni: グラフ アルゴリズム I - トポロジカル ソート、最小スパニング ツリー、プリムのアルゴリズム - 講義 6 (動画)](https://www.youtube.com/watch?v=i_AQT_XfvD8&index=6&list=PLFDnELG9dpVxQCxuD-9BSy2E7BWY3t5Sm)
|
|
|
- [ ] [Aduni: グラフ アルゴリズム II - DFS、BFS、クラスカルのアルゴリズム、Union Find データ構造 - 講義 7 (動画)]( https://www.youtube.com/watch?v=ufj5_bppBsA&list=PLFDnELG9dpVxQCxuD-9BSy2E7BWY3t5Sm&index=7 )
|
|
|
- [ ] [Aduni: グラフ アルゴリズム III: 最短パス - レクチャー 8 (動画)](https://www.youtube.com/watch?v=DiedsPsMKXc&list=PLFDnELG9dpVxQCxuD-9BSy2E7BWY3t5Sm&index=8)
|
|
|
- [ ] [Aduni: グラフ Alg. IV: 幾何学的アルゴリズムの概要 - レクチャー 9 (動画)](https://www.youtube.com/watch?v=XIAQRlNkJAw&list=PLFDnELG9dpVxQCxuD-9BSy2E7BWY3t5Sm&index=9)
|
|
|
- [ ] [CS 61B 2014: 加重グラフ (動画)](https://archive.org/details/ucberkeley_webcast_zFbq8vOZ_0k)
|
|
|
- [ ] [貪欲なアルゴリズム: 最小スパニング ツリー (動画)](https://www.youtube.com/watch?v=tKwnms5iRBU&index=16&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp)
|
|
|
- [ ] [強結合コンポーネント コサラジュのアルゴリズム グラフ アルゴリズム (動画)](https://www.youtube.com/watch?v=RpgcYiky7uw)
|
|
|
- [ ] [[復習] 16 分でわかる最短経路アルゴリズム (プレイリスト) (動画)](https://www.youtube.com/playlist?list=PL9xmBV_5YoZO-Y-H3xIC9DGSfVYJng9Yw)
|
|
|
- [ ] [[復習] 4 分でわかる最小スパニング ツリー (プレイリスト) (動画)](https://www.youtube.com/playlist?list=PL9xmBV_5YoZObEi3Hf6lmyW-CBfs7nkOV)
|
|
|
|
|
|
- フルcourseraコース：
|
|
|
- [ ] [グラフのアルゴリズム(動画)](https://www.coursera.org/learn/algorithms-on-graphs/home/welcome)
|
|
|
|
|
|
- 次のことを実装します。
|
|
|
- [ ] 隣接リストを含む DFS (再帰的)
|
|
|
- [ ] 隣接リストを使用した DFS (スタックによる反復)
|
|
|
- [ ] 隣接行列を使用した DFS (再帰的)
|
|
|
- [ ] 隣接行列を使用した DFS (スタックによる反復)
|
|
|
- [ ] 隣接リストを含む BFS
|
|
|
- [ ] 隣接マトリックスを使用した BFS
|
|
|
- [ ] 単一ソースの最短パス (ダイクストラ)
|
|
|
- [ ] 最小スパニングツリー
|
|
|
- DFSベースのアルゴリズム(上記のAduniの動画を参照)：
|
|
|
- [ ] サイクルをチェックする(トポロジカルソートに必要．開始前にサイクルをチェックする)
|
|
|
- [ ] トポロジカルソート
|
|
|
- [ ] グラフ内の接続されたコンポーネントをカウントする
|
|
|
- [ ] 強く接続されたコンポーネントを一覧表示する
|
|
|
- [ ] 二部グラフをチェックする
|
|
|
|
|
|
## さらに多くの知識
|
|
|
|
|
|
- ### 再帰
|
|
|
- [ ] 再帰とバックトラッキングに関するスタンフォードの講義:
|
|
|
- [ ] [講義 8 | プログラミングの抽象化 (動画)](https://www.youtube.com/watch?v=gl3emqCuueQ&list=PLFE6E58F856038C69&index=8)
|
|
|
- [ ] [講義 9 | プログラミングの抽象化 (動画)](https://www.youtube.com/watch?v=uFJhEPrbycQ&list=PLFE6E58F856038C69&index=9)
|
|
|
- [ ] [講義 10 | プログラミングの抽象化 (動画)](https://www.youtube.com/watch?v=NdF1QDTRkck&index=10&list=PLFE6E58F856038C69)
|
|
|
- [ ] [講義 11 | プログラミングの抽象化 (動画)](https://www.youtube.com/watch?v=p-gpaIGRCQI&list=PLFE6E58F856038C69&index=11)
|
|
|
- いつ使用するのが適切ですか?
|
|
|
- 末尾再帰をしない場合と比べて、どのような点が優れているのでしょうか?
|
|
|
- [ ] [末尾再帰とは何ですか、なぜそれほど悪いのですか?](https://www.quora.com/What-is-tail-recursion-Why-is-it-so-bad)
|
|
|
- [ ] [末尾再帰 (動画)](https://www.coursera.org/lecture/programming-langages/tail-recursion-YZic1)
|
|
|
- [ ] [再帰的問題を解決するための 5 つの簡単なステップ (動画)](https://youtu.be/ngCos392W4w)
|
|
|
バックトラッキング ブループリント: [Java](https://leetcode.com/problems/combination-sum/discuss/16502/A-general-approach-to-backtracking-questions-in-Java-(Subsets-Permutations-Combination-Sum-回文分割)) [Python](https://leetcode.com/problems/combination-sum/discuss/429538/General-Backtracking-questions-solutions-in-Python-for-reference-%3A)
|
|
|
|
|
|
- ### 動的プログラミング
|
|
|
- おそらく面接では動的プログラミングの問題は見られないでしょうが、問題を認識できるようにしておくことは価値があります。
|
|
|
動的計画法の候補としての問題。
|
|
|
- それぞれの DP 解決問題は再帰関係として定義する必要があり、それを思いつくのは難しい場合があるため、このテーマはかなり難しい場合があります。
|
|
|
- 関連するパターンをしっかりと理解するまで、DP 問題の多くの例を検討することをお勧めします。
|
|
|
- [ ] 動画：
|
|
|
- [ ] [Skiena: CSE373 2020 - レクチャー 19 - 動的プログラミング入門 (動画)](https://www.youtube.com/watch?v=wAA0AMfcJHQ&list=PLOtl7M3yp-DX6ic0HGT0PUX_wiNmkWkXx&index=18)
|
|
|
- [ ] [Skiena: CSE373 2020 - レクチャー 20 - 距離の編集 (動画)](https://www.youtube.com/watch?v=T3A4jlHlhtA&list=PLOtl7M3yp-DX6ic0HGT0PUX_wiNmkWkXx&index=19)
|
|
|
- [ ] [Skiena: CSE373 2020 - レクチャー 20 - 距離の編集 (続き) (動画)](https://www.youtube.com/watch?v=iPnPVcZmRbE&list=PLOtl7M3yp-DX6ic0HGT0PUX_wiNmkWkXx&index=20)
|
|
|
- [ ] [Skiena: CSE373 2020 - レクチャー 21 - 動的プログラミング (動画)](https://www.youtube.com/watch?v=2xPE4Wq8coQ&list=PLOtl7M3yp-DX6ic0HGT0PUX_wiNmkWkXx&index=21)
|
|
|
- [ ] [Skiena: CSE373 2020 - レクチャー 22 - 動的プログラミングとレビュー (動画)](https://www.youtube.com/watch?v=Yh3RzqQGsyI&list=PLOtl7M3yp-DX6ic0HGT0PUX_wiNmkWkXx&index=22)
|
|
|
- [ ] [Simonson: 動的プログラミング 0 (59:18 から開始) (動画)](https://youtu.be/J5aJEcOr6Eo?list=PLFDnELG9dpVxQCxuD-9BSy2E7BWY3t5Sm&t=3558)
|
|
|
- [ ] [Simonson: 動的プログラミング I - 講義 11 (動画)](https://www.youtube.com/watch?v=0EzHjQ_SOeU&index=11&list=PLFDnELG9dpVxQCxuD-9BSy2E7BWY3t5Sm)
|
|
|
- [ ] [サイモンソン: 動的プログラミング II - 講義 12 (動画)](https://www.youtube.com/watch?v=v1qiRwuJU7g&list=PLFDnELG9dpVxQCxuD-9BSy2E7BWY3t5Sm&index=12)
|
|
|
- [ ] 個々の DP 問題のリスト (それぞれ短い): [ダイナミック プログラミング (動画)](https://www.youtube.com/playlist?list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr)
|
|
|
- [ ] イェール講義ノート：
|
|
|
- [ ] [動的プログラミング](http://www.cs.yale.edu/homes/aspnes/classes/223/notes.html#dynamicプログラミング)
|
|
|
- [ ] Coursera：
|
|
|
- [ ] [RNA二次構造の問題(動画)](https://www.coursera.org/learn/algorithmic-thinking-2/lecture/80RrW/the-rna-secondary-structure-problem)
|
|
|
- [ ] [動的プログラミングのアルゴリズム(動画)](https://www.coursera.org/learn/algorithmic-thinking-2/lecture/PSonq/a-dynamic-programming-algorithm)
|
|
|
- [ ] [DPアルゴリズムの説明(動画)](https://www.coursera.org/learn/algorithmic-thinking-2/lecture/oUEK2/illustrating-the-dp-algorithm)
|
|
|
- [ ] [DPアルゴリズムの実行時間(動画)](https://www.coursera.org/learn/algorithmic-thinking-2/lecture/nfK2r/running-time-of-the-dp-algorithm)
|
|
|
- [ ] [DPと再帰的実装(動画)](https://www.coursera.org/learn/algorithmic-thinking-2/lecture/M999a/dp-vs-recursive-implementation)
|
|
|
- [ ] [グローバル対配列アライメント(動画)](https://www.coursera.org/learn/algorithmic-thinking-2/lecture/UZ7o6/global-pairwise-sequence-alignment)
|
|
|
- [ ] [ローカル対配列アライメント(動画)](https://www.coursera.org/learn/algorithmic-thinking-2/lecture/WnNau/local-pairwise-sequence-alignment)
|
|
|
|
|
|
- ### デザインパターン
|
|
|
- [ ] [UMLの簡単なレビュー(動画)](https://www.youtube.com/watch?v=3cmzqZzwNDM&list=PLGLfVvz_LVvQ5G-LdJ8RLqe-ndo7QITYc&index=3)
|
|
|
- [ ] これらのパターンを学ぶ：
|
|
|
- [ ] Strategy(戦略)
|
|
|
- [ ] Singleton(単一要素)
|
|
|
- [ ] Adapter(アダプタ)
|
|
|
- [ ] Prototype(原型)
|
|
|
- [ ] Decorator(装飾者)
|
|
|
- [ ] Visitor(訪問者)
|
|
|
- [ ] Factory,AbstractFactory(工場、抽象工場)
|
|
|
- [ ] Facade(外見)
|
|
|
- [ ] Observer(観察者)
|
|
|
- [ ] Proxy(代理)
|
|
|
- [ ] Delegate(委任)
|
|
|
- [ ] Command(命令)
|
|
|
- [ ] State(状態)
|
|
|
- [ ] Memento(記念品)
|
|
|
- [ ] Iterator(イテレータ)
|
|
|
- [ ] Composite(合成)
|
|
|
- [ ] Flyweight(フライ級)
|
|
|
- [ ] [一連の動画 (27 本)](https://www.youtube.com/playlist?list=PLF206E906175C7E07)
|
|
|
- [ ] [書籍: Head First Design Patterns](https://www.amazon.com/Head-First-Design-Patterns-Freeman/dp/0596007124)
|
|
|
- 正規の本は「デザインパターン: 再利用可能なオブジェクト指向ソフトウェアの要素」であることは知っていますが、「Head First」は OO の初心者に最適です。
|
|
|
- [便利なリファレンス: 開発者のための 101 のデザインパターンとヒント](https://sourcemaking.com/design-patterns-and-tips)
|
|
|
|
|
|
- ### 組み合わせ論(nからkを選択)と確率
|
|
|
- [ ] [数学スキル: 階乗、順列、組み合わせの求め方 (選択) (動画)](https://www.youtube.com/watch?v=8RRo6Ti9d0U)
|
|
|
- [ ] [Make School: 確率 (動画)](https://www.youtube.com/watch?v=sZkAAk9Wwa4)
|
|
|
- [ ] [Make School: さらなる確率とマルコフ連鎖 (動画)](https://www.youtube.com/watch?v=dNaJg-mLobQ)
|
|
|
- [ ] カーンアカデミー:
|
|
|
- コースレイアウト:
|
|
|
- [ ] [基本理論確率](https://www.khanacademy.org/math/probability/probability-and-combinatorics-topic)
|
|
|
- ビデオのみ - 41 (それぞれがシンプルで短い):
|
|
|
- [ ] [確率の説明 (動画)](https://www.youtube.com/watch?v=uzkc-qNVoOk&list=PLC58778F28211FA19)
|
|
|
|
|
|
- ### NP、NP-完全/近似アルゴリズム
|
|
|
- 巡回セールスマンやナップザック問題など、NP 完全問題の最も有名なクラスについて知っています。
|
|
|
インタビュアーが変装して質問したときに、それを見分けることができます。
|
|
|
- NP 完全の意味を理解する。
|
|
|
- [ ] [計算の複雑さ (動画)](https://www.youtube.com/watch?v=moPtwq_cVH8&list=PLUl4u3cNGP61Oq3tWYp6V_F-5jb5L2iHb&index=23)
|
|
|
- [ ] サイモンソン:
|
|
|
- [ ] [貪欲なアルグス。II および NP 完全性の紹介 (動画)](https://youtu.be/qcGnJ47Smlo?list=PLFDnELG9dpVxQCxuD-9BSy2E7BWY3t5Sm&t=2939)
|
|
|
- [ ] [NP 完全性 II と削減 (動画)](https://www.youtube.com/watch?v=e0tGC6ZQdQE&index=16&list=PLFDnELG9dpVxQCxuD-9BSy2E7BWY3t5Sm)
|
|
|
- [ ] [NP 完全性 III (動画)](https://www.youtube.com/watch?v=fCX1BGT3wjE&index=17&list=PLFDnELG9dpVxQCxuD-9BSy2E7BWY3t5Sm)
|
|
|
- [ ] [NP 完全性 IV (動画)](https://www.youtube.com/watch?v=NKLDp3Rch3M&list=PLFDnELG9dpVxQCxuD-9BSy2E7BWY3t5Sm&index=18)
|
|
|
- [ ]スキエナ:
|
|
|
- [ ] [CSE373 2020 - レクチャー 23 - NP の完全性 (動画)](https://www.youtube.com/watch?v=ItHp5laE1VE&list=PLOtl7M3yp-DX6ic0HGT0PUX_wiNmkWkXx&index=23)
|
|
|
- [ ] [CSE373 2020 - レクチャー 24 - 満足度 (動画)](https://www.youtube.com/watch?v=inaFJeCzGxU&list=PLOtl7M3yp-DX6ic0HGT0PUX_wiNmkWkXx&index=24)
|
|
|
- [ ] [CSE373 2020 - レクチャー 25 - NP 完全性の詳細(動画)](https://www.youtube.com/watch?v=B-bhKxjZLlc&list=PLOtl7M3yp-DX6ic0HGT0PUX_wiNmkWkXx&index=25)
|
|
|
- [ ] [CSE373 2020 - レクチャー 26 - NP 完全性チャレンジ (動画)](https://www.youtube.com/watch?v=_EzetTkG_Cc&list=PLOtl7M3yp-DX6ic0HGT0PUX_wiNmkWkXx&index=26)
|
|
|
- [ ] [複雑さ: P、NP、NP 完全性、削減 (動画)](https://www.youtube.com/watch?v=eHZifpgyH_4&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp&index=22)
|
|
|
- [ ] [複雑さ: 近似アルゴリズム (ビ動画デオ)](https://www.youtube.com/watch?v=MEz1J9wY2iM&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp&index=24)
|
|
|
- [ ] [複雑さ: 固定パラメーター アルゴリズム (動画)](https://www.youtube.com/watch?v=4q-jmGrmxKs&index=25&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp)
|
|
|
- Peter Norvig は、巡回セールスマンの問題に対する最適に近い解決策について説明します。
|
|
|
- [Jupyter Notebook](http://nbviewer.jupyter.org/url/norvig.com/ipython/TSP.ipynb)
|
|
|
- CLRS のページ 1048 ～ 1140 (お持ちの場合)。
|
|
|
|
|
|
- ### コンピューターがプログラムを処理する仕組み
|
|
|
- [ ] [CPU がプログラムを実行する仕組み (動画)](https://www.youtube.com/watch?v=XM4lGflQFvA)
|
|
|
- [ ] [コンピューターの計算方法 - ALU (動画)](https://youtu.be/1I5ZMmrOfnA)
|
|
|
- [ ] [レジスタとRAM (動画)](https://youtu.be/fpnE6UAfbtU)
|
|
|
- [ ] [中央処理装置 (CPU) (動画)](https://youtu.be/FZGugFqdr60)
|
|
|
- [ ] [説明書とプログラム (動画)](https://youtu.be/zltgXvg6r3k)
|
|
|
|
|
|
- ### キャッシュ
|
|
|
- [ ] LRU キャッシュ:
|
|
|
- [ ] [LRU キャッシュの魔法 (Google 開発の 100 日間) (動画)](https://www.youtube.com/watch?v=R5ON3iwx78M)
|
|
|
- [ ] [LRU の実装 (動画)](https://www.youtube.com/watch?v=bq6N7Ym81iI)
|
|
|
- [ ] [LeetCode - 146 LRU キャッシュ (C++) (動画)](https://www.youtube.com/watch?v=8-FZRAjR7qU)
|
|
|
- [ ] CPU キャッシュ:
|
|
|
- [ ] [MIT 6.004 L15: メモリ階層 (動画)](https://www.youtube.com/watch?v=vjYF_fAZI5E&list=PLrRW1w6CGAcXbMtDFj205vALOGmiRc82-&index=24)
|
|
|
- [ ] [MIT 6.004 L16: キャッシュの問題 (動画)](https://www.youtube.com/watch?v=ajgC3-pyGlk&index=25&list=PLrRW1w6CGAcXbMtDFj205vALOGmiRc82-)
|
|
|
|
|
|
- ### プロセスとスレッド
|
|
|
- [ ] コンピュータサイエンス162 - オペレーティングシステム(25ビデオ)：
|
|
|
- プロセスとスレッドのためのビデオ表示1-11
|
|
|
- [オペレーティングシステムとシステムプログラミング(動画)](https://www.youtube.com/playlist?list=PL-XXv-cvA_iBDyz-ba4yDskqMDY6A1w_c)
|
|
|
- [プロセスとスレッドの違いは何ですか？](https://www.quora.com/What-is-the-difference-between-a-process-and-thread)
|
|
|
- カバー：
|
|
|
- プロセス、スレッド、並行性の問題
|
|
|
- プロセスとスレッドの違い
|
|
|
- プロセス
|
|
|
- スレッド
|
|
|
- ロック
|
|
|
- ミューテックス
|
|
|
- セマフォ
|
|
|
- モニタ(同期)
|
|
|
- 動作の仕方
|
|
|
- デッドロック
|
|
|
- ライブロック
|
|
|
- CPU アクティビティ、割り込み、コンテキスト切り替え
|
|
|
- マルチコアプロセッサを使用した最新の同時実行構造
|
|
|
- [ページング、セグメンテーション、仮想メモリ (動画)](https://youtu.be/O4nwUqQodAg)
|
|
|
- [中断（動画）](https://youtu.be/iKlAWIKEyuw)
|
|
|
- プロセス リソースのニーズ (メモリ: コード、静的ストレージ、スタック、ヒープ、およびファイル記述子、I/O)
|
|
|
- スレッド リソースのニーズ (同じプロセス内の他のスレッドと上記 (マイナススタック) を共有しますが、それぞれに独自の PC、スタック カウンター、レジスタ、およびスタックがあります)
|
|
|
- フォークは実際には、新しいプロセスがメモリに書き込むまではコピーオンライト (読み取り専用) であり、その後完全コピーが実行されます。
|
|
|
- コンテキストの切り替え
|
|
|
- [オペレーティングシステムと基盤となるハードウェアによってコンテキストスイッチングがどのように開始されるか?](https://www.javatpoint.com/what-is-the-context-switching-in-the-operating-system)
|
|
|
- [ ] [C++ のスレッド (シリーズ - 10 本の動画)](https://www.youtube.com/playlist?list=PL5jc9xFGsL8E12so1wlMS0r0hTQoJL74M)
|
|
|
- [ ] [CS 377 Spring '14: マサチューセッツ大学のオペレーティングシステム](https://www.youtube.com/playlist?list=PLacuG5pysFbDQU8kKxbUh4K5c1iL5_k7k)
|
|
|
- Python の同時実行性 (動画):
|
|
|
- [ ] [スレッドに関する短編シリーズ](https://www.youtube.com/playlist?list=PL1H1sBF1VAKVMONJWJkmUh6_p8g4F2oy1)
|
|
|
- [ ] [Python スレッド](https://www.youtube.com/watch?v=Bs7vPNbB9JM)
|
|
|
- [ ] [Python GIL を理解する (2010)](https://www.youtube.com/watch?v=Obt-vMVdM8s)
|
|
|
- [参考](http://www.dabeaz.com/GIL)
|
|
|
- [ ] [David Beazley - Python 同時実行性を基礎からライブで解説します! - PyCon 2015](https://www.youtube.com/watch?v=MCs5OvhV9S4)
|
|
|
- [ ] [基調講演 David Beazley - 注目のトピック (Python Asyncio)](https://www.youtube.com/watch?v=ZzfHjytDceU)
|
|
|
- [ ] [Python のミューテックス](https://www.youtube.com/watch?v=0zaPs8OtyKY)
|
|
|
|
|
|
- ### テスト
|
|
|
- カバーするために：
|
|
|
- 単体テストの仕組み
|
|
|
- モックオブジェクトとは何ですか
|
|
|
- 統合テストとは何ですか
|
|
|
- 依存性注入とは何ですか
|
|
|
- [ ] [James Bach によるアジャイル ソフトウェア テスト (動画)](https://www.youtube.com/watch?v=SAhJf36_u5U)
|
|
|
- [ ] [ソフトウェア テストに関する James Bach による公開講義 (動画)](https://www.youtube.com/watch?v=ILkT_HV9DVU)
|
|
|
- [ ] [Steve Freeman - テスト駆動開発 (それは私たちが言いたかったことではありません) (動画)](https://vimeo.com/83960706)
|
|
|
- [スライド](http://gotocon.com/dl/goto-berlin-2013/slides/SteveFreeman_TestDrivenDevelopmentThatsNotWhatWeMeant.pdf)
|
|
|
- [ ] 依存性の注入:
|
|
|
- [ ] [動画](https://www.youtube.com/watch?v=IKD2-MAkXyQ)
|
|
|
- [ ] [テストのTAO](http://jasonpolites.github.io/tao-of-testing/ch3-1.1.html)
|
|
|
- [ ] [テストの書き方](http://jasonpolites.github.io/tao-of-testing/ch4-1.1.html)
|
|
|
|
|
|
- ### 文字列の検索と操作
|
|
|
- [ ] [Sedgewick - サフィックス配列 (動画)](https://www.coursera.org/learn/algorithms-part2/lecture/TH18W/suffix-arrays)
|
|
|
- [ ] [Sedgewick - 部分文字列検索 (動画)](https://www.coursera.org/learn/algorithms-part2/home/week/4)
|
|
|
- [ ] [1. 部分文字列検索の概要](https://www.coursera.org/lecture/algorithms-part2/introduction-to-substring-search-n3ZpG)
|
|
|
- [ ] [2. ブルートフォース部分文字列検索](https://www.coursera.org/learn/algorithms-part2/lecture/2Kn5i/brute-force-substring-search)
|
|
|
- [ ] [3. クヌース・モリス・プラット](https://www.coursera.org/learn/algorithms-part2/lecture/TAtDr/knuth-morris-pratt)
|
|
|
- [ ] [4. ボイヤー・ムーア](https://www.coursera.org/learn/algorithms-part2/lecture/CYxOT/boyer-moore)
|
|
|
- [ ] [5. ラビン・カープ](https://www.coursera.org/lecture/algorithms-part2/rabin-karp-3KiqT)
|
|
|
- [ ] [テキスト内のパターンの検索 (動画)](https://www.coursera.org/learn/data-Structures/lecture/tAfHI/search-pattern-in-text)
|
|
|
|
|
|
この件についてさらに詳細が必要な場合は、[一部の件名に関する追加の詳細](#Additional-detail-on-some-subjects) の「文字列マッチング」セクションを参照してください。
|
|
|
|
|
|
- ### トライ
|
|
|
- さまざまな種類のトライがあることに注意してください。プレフィックスを持つものと持たないもの、そしてビットの代わりに文字列を使用してパスを追跡するものもあります
|
|
|
- コードは一通り読みましたが、実装はしません
|
|
|
- [ ] [Sedgewick - Trys (3動画)](https://www.coursera.org/learn/algorithms-part2/home/week/4)
|
|
|
- [ ] [1. R Way Tries](https://www.coursera.org/learn/algorithms-part2/lecture/CPVdr/r-way-tries)
|
|
|
- [ ] [2. 三項探索トライズ](https://www.coursera.org/learn/algorithms-part2/lecture/yQM8K/ternary-search-tries)
|
|
|
- [ ] [3. 文字ベースの操作](https://www.coursera.org/learn/algorithms-part2/lecture/jwNmV/character-based-operations)
|
|
|
- [ ] [データ構造とプログラミング技術に関するメモ](http://www.cs.yale.edu/homes/aspnes/classes/223/notes.html#Tries)
|
|
|
- [ ] ショートコースビデオ:
|
|
|
- [ ] [トライの概要 (動画)](https://www.coursera.org/learn/data-structions-optimizing-performance/lecture/08Xyf/core-introduction-to-tries)
|
|
|
- [ ] [トライのパフォーマンストライ (動画)](https://www.coursera.org/learn/data-Structures-optimizing-performance/lecture/PvlZW/core-performance-of-tries)
|
|
|
- [ ] [トライの実装 (動画)]( https://www.coursera.org/learn/data-Structures-optimizing-performance/lecture/DFvd3/core-implementing-a-trie)
|
|
|
- [ ] [トライ: 無視されたデータ構造](https://www.toptal.com/java/the-trie-a-neglected-data-struction)
|
|
|
- [ ] [TopCoder - トライの使用](https://www.topcoder.com/thrive/articles/Using%20Tries)
|
|
|
- [ ] [スタンフォード講義 (実際の使用例) (動画)](https://www.youtube.com/watch?v=TJ8SkcUSdbU)
|
|
|
- [ ] [MIT、高度なデータ構造、文字列 (途中でかなりわかりにくくなる可能性があります) ) (動画)](https://www.youtube.com/watch?v=NinWEPPrkDQ&index=16&list=PLUl4u3cNGP61hsJNdULdudlRL493b-XZf)
|
|
|
|
|
|
- ### 浮動小数点数
|
|
|
- [ ] 単純な 8 ビット: [浮動小数点数の表現 - 1 (ビデオ - 計算に誤りがあります - ビデオの説明を参照してください)](https://www.youtube.com/watch?v=ji3SfClm8TU)
|
|
|
|
|
|
- ### Unicode
|
|
|
- [ ] [すべてのソフトウェア開発者の絶対最小値、絶対にUnicodeと文字セットについて必ず知っておくべきこと]( http://www.joelonsoftware.com/articles/Unicode.html)
|
|
|
- [ ] [すべてのプログラマがテキストを扱うためにエンコーディングと文字セットについて絶対に、必ず知っておくべきこと]( http://kunststube.net/encoding/)
|
|
|
|
|
|
- ### エンディアン
|
|
|
- [ ] [ビッグ エンディアンとリトル エンディアン](https://web.archive.org/web/20180107141940/http://www.cs.umd.edu:80/class/sum2003/cmsc311/Notes/Data/endian.html)
|
|
|
- [ ] [ビッグ エンディアンとリトル エンディアン (動画)](https://www.youtube.com/watch?v=JrNF0KRAlyo)
|
|
|
- [ ] [Big And Little Endian Inside/Out (動画)](https://www.youtube.com/watch?v=oBSuXP-1Tc0)
|
|
|
- カーネル開発者向けの非常に技術的な話。ほとんどのことが頭から離れていても心配する必要はありません。
|
|
|
- 前半だけで十分です。
|
|
|
|
|
|
- ### ネットワーキング
|
|
|
- **ネットワーキングの経験がある場合、または信頼性エンジニアまたは運用エンジニアになりたい場合は、質問をお待ちください** -
|
|
|
それ以外の場合、これは知っておくと良いでしょう
|
|
|
- [ ] [カーン アカデミー](https://www.khanacademy.org/computing/code-org/computers-and-the-internet)
|
|
|
- [ ] [UDP と TCP: トランスポート プロトコルの比較 (動画)](https://www.youtube.com/watch?v=Vdc8TCESIg8)
|
|
|
- [ ] [TCP/IP と OSI モデルについて説明します! (動画)](https://www.youtube.com/watch?v=e5DEVa9eSN0)
|
|
|
- [ ] [インターネットを介したパケット送信。ネットワークと TCP/IP のチュートリアル。(動画)](https://www.youtube.com/watch?v=nomyRJehhnM)
|
|
|
- [ ] [HTTP (動画)](https://www.youtube.com/watch?v=WGJrLqtX7As)
|
|
|
- [ ] [SSL および HTTPS (動画)](https://www.youtube.com/watch?v=S2iBR2ZlZf0)
|
|
|
- [ ] [SSL/TLS (動画)](https://www.youtube.com/watch?v=Rp3iZUvXWlM)
|
|
|
- [ ] [HTTP 2.0 (動画)](https://www.youtube.com/watch?v=E9FxNzv1Tr8)
|
|
|
- [ ] [ビデオ シリーズ (21 動画) (動画)](https://www.youtube.com/playlist?list=PLEbnTDJUr_IegfoqO4iPnPYQui46QqT0j)
|
|
|
- [ ] [サブネットの謎を解く - パート 5 CIDR表記法 (動画)](https://www.youtube.com/watch?v=t5xYI0jzOf4)
|
|
|
- [ ] ソケット:
|
|
|
- [ ] [Java - ソケット - 概要 (動画)](https://www.youtube.com/watch?v=6G_W54zuadg&t=6s)
|
|
|
- [ ] [ソケット プログラミング (動画)](https://www.youtube.com/watch?v=G75vN2mnJeQ)
|
|
|
|
|
|
---
|
|
|
|
|
|
## 最終レビュー
|
|
|
|
|
|
このセクションには短いビデオが含まれます。非常にすぐに見て、重要な概念のほとんどを確認できます。
|
|
|
頻繁にリフレッシュしたい場合に便利です。
|
|
|
|
|
|
- [ ] 2 ～ 3 分の短い主題ビデオ シリーズ (23 動画)
|
|
|
- [ビデオ](https://www.youtube.com/watch?v=r4r1DZcx1cM&list=PLmVb1OknmNJuC5POdcDv5oCS7_OUkDgpj&index=22)
|
|
|
- [ ] 2 ～ 5 分のシリーズ短い主題のビデオ - Michael Sambol (動画 48 件):
|
|
|
- [ビデオ](https://www.youtube.com/@MichaelSambol)
|
|
|
- [コード例](https://github.com/msambol/dsa)
|
|
|
- [ ] [セッジウィック ビデオ - アルゴリズム I](https://www.coursera.org/learn/algorithms-part1)
|
|
|
- [ ] [セッジウィック ビデオ - アルゴリズム II](https://www.coursera.org/learn/algorithms-part2)
|
|
|
|
|
|
---
|
|
|
|
|
|
## 履歴書を更新する
|
|
|
|
|
|
- 書籍の履歴書準備情報を参照してください: 『コーディング面接の攻略』 「番組インタビュー暴露」
|
|
|
- [「良い履歴書はこうあるべきだ」 Gayle McDowell (『Cracking thecoding Interview』の著者) 著](https://www.careercup.com/resume)、
|
|
|
- 著者による注: 「これは米国に焦点を当てた履歴書用です。インドと他の国の履歴書では、多くの点は同じですが、期待される内容は異なります。」
|
|
|
- [「ステップバイステップの履歴書ガイド」 by Tech Interview Handbook](https://www.techinterviewhandbook.org/resume/guide)
|
|
|
- 履歴書を最初から設定し、効果的な履歴書の内容を作成し、最適化し、履歴書をテストする方法に関する詳細なガイド
|
|
|
|
|
|
## 面接プロセスと面接一般的な面接の準備
|
|
|
|
|
|
- [ ] [2021 年のエンジニアリング面接に合格する方法](https://davidbyttow.medium.com/how-to-pass-the-engineering-interview-in-2021-45f1b389a1)
|
|
|
- [ ] [テクノロジー採用の謎を解く](https://www.youtube.com/watch?v=N233T0epWTs)
|
|
|
- [ ] ビッグ 4 に就職する方法:
|
|
|
- [ ] [ビッグ 4 で仕事を得る方法 - Amazon、Facebook、Google、およびMicrosoft (ビデオ)](https://www.youtube.com/watch?v=YJZCUhxNCv8)
|
|
|
- [ ] [Big 4.1 で仕事を得る方法 (フォローアップ ビデオ)](https://www.youtube.com/watch?v=6790FVXWBw8&feature=youtu.be)
|
|
|
- [ ] コーディング インタビュー セット 1 を解読:
|
|
|
- [ ] [ゲイル L マクダウェル - コーディング インタビューのクラッキング (ビデオ)](https://www.youtube.com/watch?v=rEJzOhC5ZtQ)
|
|
|
- [ ] [著者ゲイル・ラークマン・マクダウェル氏のコーディングインタビューを解読 (ビデオ)](https://www.youtube.com/watch?v=aClxtDcdpsQ)
|
|
|
- [ ] Facebook コーディングのインタビューを解読:
|
|
|
- [ ] [アプローチ](https://www.youtube.com/watch?v=wCl9kvQGHPI)
|
|
|
- [ ] [問題のチュートリアル](https://www.youtube.com/watch?v=4UWDyJq8jZg)
|
|
|
- 準備コース:
|
|
|
- [データ構造、アルゴリズム、インタビューのための Python (有料コース)](https://www.udemy.com/python-for-data-structions-algorithms-and-interviews/):
|
|
|
- データ構造、アルゴリズム、模擬面接などをカバーする Python 中心の面接準備コース。
|
|
|
- [Python を使用したデータ構造とアルゴリズムの紹介 (Udacity 無料コース)](https://www.udacity.com/course/data-structures-and-algorithms-in-python--ud513):
|
|
|
- Python 中心のデータ構造とアルゴリズムの無料コース。
|
|
|
- [【データ構造とアルゴリズムをナノレベルで解説！ (Udacity 有料 Nanodegree)](https://www.udacity.com/course/data-structions-and-algorithms-nanodegree--nd256):
|
|
|
- 100 を超えるデータ構造とアルゴリズムの演習と、面接や実務シナリオの準備に役立つ専任のメンターからのガイダンスによる実践的な練習を行います。
|
|
|
- [行動面接のグロッキング (無料教育コース)](https://www.educative.io/courses/grokking-the-behavioral-interview):
|
|
|
- 多くの場合、夢の仕事に就くのを妨げているのは技術的能力ではなく、行動面接での成績です。
|
|
|
- [AlgoMonster (無料コンテンツ付きの有料コース)](https://algo.monster/?utm_campaign=jwasham&utm_medium=referral&utm_content=coding-interview-university&utm_source=github):
|
|
|
- LeetCode の短期集中コース。数千の質問から凝縮されたすべてのパターンを網羅。
|
|
|
|
|
|
模擬面接:
|
|
|
- [Gainlo.co: 大企業の面接官を模擬](http://www.gainlo.co/#!/) - これを使用したところ、電話での画面やオンサイトの面接に向けてリラックスするのに役立ちました
|
|
|
- [Pramp: ピアとの模擬面接](https://www.pramp.com/) - 面接を練習するためのピアツーピア モデル
|
|
|
- [interviewing.io: 上級エンジニアとの模擬面接の練習](https://interviewing.io) - FAANG の上級エンジニアとのアルゴリズム/システム設計匿名インタビュー
|
|
|
- [Meetapro: FAANG トップ面接官との模擬面接](https://meetapro.com/?utm_source=ciu) - Airbnb スタイルの模擬面接/コーチング プラットフォーム。
|
|
|
- [Hello Interview: Expert Coaches and AI との模擬面接](https://www.hellointerview.com/?utm_source=ciu) - AI または FAANG スタッフのエンジニアやマネージャーと直接面接します。
|
|
|
|
|
|
## 面接が来るときのことを考えてください
|
|
|
|
|
|
面接で聞かれる約 20 の質問と、以下の項目の内容を考えてください。それぞれに対して少なくとも 1 つの回答を用意してください。
|
|
|
達成したことについて、単なるデータではなくストーリーを作成します。
|
|
|
|
|
|
- なぜあなたはこの仕事をしたいです？
|
|
|
- あなたが解決した難しい問題は何ですか?
|
|
|
- 直面した最大の課題は何ですか?
|
|
|
- 見た中で最高/最悪のデザインは何ですか?
|
|
|
- 既存の製品を改善するためのアイデア
|
|
|
- 個人としても、チームの一員としても、どのようにすれば最も効果的に働くことができますか?
|
|
|
- あなたのスキルや経験のうち、その役割において資産となるものはどれですか、またその理由は何ですか?
|
|
|
- [ジョブ x / プロジェクト y] で一番楽しかったことは何ですか?
|
|
|
- [ジョブ x / プロジェクト y] で直面した最大の課題は何ですか?
|
|
|
- [ジョブ x / プロジェクト y] で直面した最も困難なバグは何ですか?
|
|
|
- [ジョブ x / プロジェクト y] で何を学びましたか?
|
|
|
- [ジョブ x / プロジェクト y] でもっと良くできたことは何ですか?
|
|
|
|
|
|
## 面接官に質問があります
|
|
|
|
|
|
私の意見の一部 (答えはすでに知っているかもしれませんが、彼らの意見やチームの視点が欲しいです):
|
|
|
|
|
|
- チームの規模はどれくらいですか?
|
|
|
- 開発サイクルはどのような感じですか?ウォーターフォール/スプリント/アジャイルをやっていますか?
|
|
|
- 締め切りに追われるのはよくあることですか?それとも柔軟性があるのでしょうか？
|
|
|
- チーム内での意思決定はどのように行われますか?
|
|
|
- 週に何回会議がありますか?
|
|
|
- 職場環境は集中力を高めますか？
|
|
|
-何に取り組んでいますか？
|
|
|
- 何が気に入っていますか？
|
|
|
- 仕事生活はどのような感じですか？
|
|
|
- ワークライフバランスはどうですか？
|
|
|
|
|
|
## 仕事に就いたら
|
|
|
|
|
|
おめでとう！
|
|
|
|
|
|
学び続けます。
|
|
|
|
|
|
本当に終わったことはありません。
|
|
|
|
|
|
---
|
|
|
|
|
|
************************************************* ************************************************* *
|
|
|
************************************************* ************************************************* *
|
|
|
|
|
|
これより下はすべてオプションです。初心者レベルの面接には必要ありません。
|
|
|
ただし、これらを学習することで、より多くの CS 概念に詳しくなり、より適切な準備が整います。
|
|
|
ソフトウェアエンジニアリングの仕事なら何でも。あなたは、より総合的なソフトウェア エンジニアになるでしょう。
|
|
|
|
|
|
************************************************* ************************************************* *
|
|
|
************************************************* ************************************************* *
|
|
|
|
|
|
---
|
|
|
|
|
|
## 追加の書籍
|
|
|
|
|
|
これらは、興味のあるトピックに飛び込むことができるようにここにあります。
|
|
|
|
|
|
- [Unix プログラミング環境](https://www.amazon.com/dp/013937681X)
|
|
|
- 懐かしいけどおいしい
|
|
|
- [Linux コマンドライン: 完全な紹介](https://www.amazon.com/dp/1593273894/)
|
|
|
- 現代的なオプション
|
|
|
- [TCP/IP 図解シリーズ](https://en.wikipedia.org/wiki/TCP/IP_図解)
|
|
|
- [ヘッドファーストデザインパターン](https://www.amazon.com/gp/product/0596007124/)
|
|
|
- デザインパターンへの優しい入門書
|
|
|
- [デザインパターン: 再利用可能なオブジェクト指向ソフトウェアの要素](https://www.amazon.com/Design-Patterns-Elements-Reusable-Object-Oriented/dp/0201633612)
|
|
|
- 別名「ギャング・オブ・フォー」本またはGOF
|
|
|
- 正規のデザインパターンブック
|
|
|
- [アルゴリズム設計マニュアル](http://www.amazon.com/Algorithm-Design-Manual-Steven-Skiena/dp/1849967202) (Skiena)
|
|
|
- 振り返りと問題認識として
|
|
|
- アルゴリズム カタログの部分は、面接で得られる難易度の範囲をはるかに超えています。
|
|
|
- この本は 2 つの部分から構成されています。
|
|
|
- データ構造とアルゴリズムに関する授業用教科書
|
|
|
- 長所:
|
|
|
- アルゴリズムの教科書と同様に、良いレビューです
|
|
|
- 産業界や学界の問題を解決した彼の経験からの素敵な話
|
|
|
- C でのコード例
|
|
|
- 短所:
|
|
|
- CLRS と同じくらい高密度または透過不可能である可能性があり、場合によっては、一部の被験者にとっては CLRS の方が優れた代替手段になる可能性があります。
|
|
|
- 第 7 章、第 8 章、および第 9 章は、いくつかの項目が十分に説明されていなかったり、私よりも多くの頭を必要としたりするため、理解しようとすると苦痛になる可能性があります。
|
|
|
- 誤解しないでください。私はスキエナと彼の教え方、マナーが好きですが、ストーニー ブルックの材料ではないかもしれません。
|
|
|
- アルゴリズムカタログ:
|
|
|
- これがこの本を購入する本当の理由です。
|
|
|
- この本はアルゴリズムのリファレンスとして優れており、最初から最後まで読むものではありません。
|
|
|
- Kindleでレンタルできる
|
|
|
- 答え:
|
|
|
- [ソリューション](https://web.archive.org/web/20150404194210/http://www.algorithm.cs.sunysb.edu/algowiki/index.php/The_Algorithms_Design_Manual_(Second_Edition))
|
|
|
- [正誤表](http://www3.cs.stonybrook.edu/~skiena/algorist/book/errata)
|
|
|
- [アルゴリズム](http://jeffe.cs.illinois.edu/teaching/algorithms/) (ジェフ エリクソン)
|
|
|
- [素晴らしいコードを書く: 第 1 巻: マシンを理解する](https://www.amazon.com/Write-Great-Code-Understanding-Machine/dp/1593270038)
|
|
|
- この本は 2004 年に出版されており、やや古いですが、コンピュータを簡単に理解するのに最適なリソースです。
|
|
|
- 著者は [HLA](https://en.wikipedia.org/wiki/High_Level_Assembly) を発明したものであるため、HLA での言及と例については、話半分に聞いてください。広く使用されていませんが、アセンブリがどのようなものかを示す適切な例
|
|
|
- これらの章は、優れた基礎を築くために読む価値があります。
|
|
|
- 第 2 章 - 数値表現
|
|
|
- 第 3 章 - 2 進数演算とビット演算
|
|
|
- 第 4 章 - 浮動小数点表現
|
|
|
- 第 5 章 - キャラクター表現
|
|
|
- 第 6 章 - メモリの構成とアクセス
|
|
|
- 第 7 章 - 複合データ型とメモリ オブジェクト
|
|
|
- 第 9 章 - CPU アーキテクチャ
|
|
|
- 第 10 章 - 命令セットのアーキテクチャ
|
|
|
- 第 11 章 - メモリのアーキテクチャと構成
|
|
|
- [アルゴリズム入門](https://www.amazon.com/Introduction-Algorithms-fourth-Thomas-Cormen/dp/026204630X)
|
|
|
- **重要:** この本を読む価値は限られています。この本はアルゴリズムとデータ構造についての優れたレビューですが、優れたコードの書き方については教えてくれません。適切なソリューションを効率的にコーディングできなければなりません
|
|
|
- スタインがゲームに遅刻したため、別名 CLR、場合によっては CLRS
|
|
|
- [コンピュータ アーキテクチャ、第 6 版: 定量的アプローチ](https://www.amazon.com/dp/0128119055)
|
|
|
- より充実した、より最新の (2017) が、より長い治療期間を必要とする場合
|
|
|
|
|
|
## システム設計、スケーラビリティ、データ処理
|
|
|
|
|
|
**4 年以上の経験がある場合は、システム設計に関する質問が予想されます。**
|
|
|
|
|
|
- スケーラビリティとシステム設計は、多くのトピックとリソースを含む非常に大きなトピックです。
|
|
|
拡張可能なソフトウェア/ハードウェア システムを設計する際には、考慮すべきことがたくさんあります。
|
|
|
これにはかなりの時間を費やすことが予想されます
|
|
|
- 考慮事項:
|
|
|
- スケーラビリティ
|
|
|
- 大きなデータセットを単一の値に抽出します
|
|
|
- あるデータセットを別のデータセットに変換する
|
|
|
- 異常に大量のデータを扱うこと
|
|
|
- システムデザイン
|
|
|
- 機能セット
|
|
|
- インターフェース
|
|
|
- クラス階層
|
|
|
- 特定の制約の下でシステムを設計する
|
|
|
- シンプルさと堅牢性
|
|
|
- トレードオフ
|
|
|
- パフォーマンスの分析と最適化
|
|
|
- [ ] **ここから始めてください**: [システム設計入門](https://github.com/donnemartin/system-design-primer)
|
|
|
- [ ] [HiredInTech のシステム設計](http://www.hiredintech.com/system-design/)
|
|
|
- [ ] [技術面接で設計に関する質問に答える準備はどのようにすればよいですか?](https://www.quora.com/How-do-I-prepare-to-answer-design-questions-in-a-technical-interview?redirected_qid=1500023)
|
|
|
- [ ] [システム設計面接に合格するための 8 つのステップ ガイド](https://javascript.plainenglish.io/8-steps-guide-to-ace-a-system-design-interview-7a5a797f4d7d)
|
|
|
- [ ] [データベースの正規化 - 1NF、2NF、3NF、および 4NF (ビデオ)](https://www.youtube.com/watch?v=UrYLYV7WSHM)
|
|
|
- [ ] [システム設計インタビュー](https://github.com/checkcheckzz/system-design-interview) - これには多くのリソースがあります。記事と例を確認してください。その一部を以下に載せておきます
|
|
|
- [ ] [システム設計面接に合格する方法](https://web.archive.org/web/20120716060051/http://www.palantir.com/2011/10/how-to-rock-a-systems-design-interview/)
|
|
|
- [ ] [誰もが知っておくべき数字](http://everythingisdata.wordpress.com/2009/10/17/numbers-everyone-Should-know/)
|
|
|
- [ ] [コンテキストスイッチを行うのにどのくらい時間がかかりますか?](http://blog.tsunanet.net/2010/11/how-long-does-it-take-to-make-context.html)
|
|
|
- [ ] [データセンター間のトランザクション (ビデオ)](https://www.youtube.com/watch?v=srOgpXECblk)
|
|
|
- [ ] [CAP 定理のわかりやすい英語の紹介](http://ksat.me/a-plain-english-introduction-to-cap-theorem)
|
|
|
- [ ] [MIT 6.824: 分散システム、2020 年春 (ビデオ 20 本)](https://www.youtube.com/watch?v=cQP8WApzIQQ&list=PLrw6a1wE39_tb2fErI4-WkMbsvGQk9_UB)
|
|
|
- [ ] コンセンサスアルゴリズム:
|
|
|
- [ ] Paxos - [Paxos 契約 - コンピューター愛好家 (ビデオ)](https://www.youtube.com/watch?v=s8JqcZtvnsM)
|
|
|
- [ ] Raft - [Raft 分散型コンセンサス アルゴリズムの概要 (ビデオ)](https://www.youtube.com/watch?v=P9Ydif5_qvE)
|
|
|
- [ ] [読みやすい論文](https://raft.github.io/)
|
|
|
- [ ] [インフォグラフィック](http://thesecretlivesofdata.com/raft/)
|
|
|
- [ ] [一貫したハッシュ](http://www.tom-e-white.com/2007/11/consistent-hashing.html)
|
|
|
- [ ] [NoSQL パターン](http://horicky.blogspot.com/2009/11/nosql-patterns.html)
|
|
|
- [ ] スケーラビリティ:
|
|
|
- これらすべてが必要なわけではありません。興味のあるものをいくつか選んでください。
|
|
|
- [ ] [素晴らしい概要 (ビデオ)](https://www.youtube.com/watch?v=-W9F__D3oY4)
|
|
|
- [ ] 短編シリーズ:
|
|
|
- [クローン](http://www.lecloud.net/post/7295452622/scalability-for-dummies-part-1-clones)
|
|
|
- [データベース](http://www.lecloud.net/post/7994751381/scalability-for-dummies-part-2-database)
|
|
|
- [キャッシュ](http://www.lecloud.net/post/9246290032/scalability-for-dummies-part-3-cache)
|
|
|
- [非同期](http://www.lecloud.net/post/9699762917/scalability-for-dummies-part-4-asynchronism)
|
|
|
- [ ] [スケーラブルな Web アーキテクチャと分散システム](http://www.aosabook.org/en/distsys.html)
|
|
|
- [ ] [分散コンピューティングの誤った説明](https://pages.cs.wisc.edu/~zuyu/files/fallacies.pdf)
|
|
|
- [ ] [Jeff Dean - Google でのソフトウェア システムの構築と得られた教訓 (ビデオ)](https://www.youtube.com/watch?v=modXC5IWTJI)
|
|
|
- [ ] [大規模なシステムの設計入門](http://lethain.com/introduction-to-architecting-systems-for-scale/)
|
|
|
- [ ] [App Engine と Cloud Datastore を使用してモバイル ゲームを世界中の視聴者に拡張する (ビデオ)](https://www.youtube.com/watch?v=9nWyWwY2Onc)
|
|
|
- [ ] [Google が地球規模のインフラ向けに惑星規模のエンジニアリングを行う方法 (ビデオ)](https://www.youtube.com/watch?v=H4vMcD7zKM0)
|
|
|
- [ ] [アルゴリズムの重要性](https://www.topcoder.com/thrive/articles/The%20Importance%20of%20Algorithms)
|
|
|
- [ ] [シャーディング](http://highscalability.com/blog/2009/8/6/an-unorthodox-approach-to-database-design-the-coming-of-the.html)
|
|
|
- [ ] [長期戦に向けたエンジニアリング - アストリッド アトキンソン基調講演 (ビデオ)](https://www.youtube.com/watch?v=p0jGmgIrf_M&list=PLRXxvay_m8gqVlExPC5DG3TGWJTaBgqSA&index=4)
|
|
|
- [ ] [30 分でわかる YouTube のスケーラビリティに関する 7 年間のレッスン](http://highscalability.com/blog/2012/3/26/7-years-of-youtube-scalability-lessons-in-30-minutes.html)
|
|
|
- [ビデオ](https://www.youtube.com/watch?v=G-lGCC4KKok)
|
|
|
- [ ] [PayPal がわずか 8VM を使用して毎日数十億のトランザクションに拡張した方法](http://highscalability.com/blog/2016/8/15/how-paypal-scaled-to-billions-of-transactions-daily-using-ju.html)
|
|
|
- [ ] [大規模なデータセット内の重複を削除する方法](https://blog.clevertap.com/how-to-remove-duplicates-in-large-datasets/)
|
|
|
- [ ] [Jon Cowie による Etsy の規模とエンジニアリング文化の内部を見る (ビデオ)](https://www.youtube.com/watch?v=3vV4YiqKm1o)
|
|
|
- [ ] [Amazon を独自のマイクロサービス アーキテクチャに導いたもの](http://thenewstack.io/led-amazon-microservices-architecture/)
|
|
|
- [ ] [圧縮するかしないか、それは Uber の質問でした](https://eng.uber.com/trip-data-squeeze/)
|
|
|
- [ ] [近似クエリ処理はどのような場合に使用する必要がありますか?](http://highscalability.com/blog/2016/2/25/when-Should-estimate-query-processing-be-used.html)
|
|
|
- [ ] [単一データセンターからフェイルオーバー、ネイティブ マルチホーム アーキテクチャへの Google の移行]( http://highscalability.com/blog/2016/2/23/googles-transition-from-single-datacenter-to-failover-to-a-n.html)
|
|
|
- [ ] [1 日に何百万ものリクエストに対応する画像最適化テクノロジー](http://highscalability.com/blog/2016/6/15/the-image-optimization-technology-that-serves-millions-of-re.html)
|
|
|
- [ ] [Patreon アーキテクチャの短編](http://highscalability.com/blog/2016/2/1/a-patreon-architecture-short.html)
|
|
|
- [ ] [Tinder: 最大規模のレコメンデーション エンジンの 1 つは、次に会う人をどのように決定しますか?](http://highscalability.com/blog/2016/1/27/tinder-how-does-one-最大の推奨エンジンのde.html)
|
|
|
- [ ] [最新のキャッシュの設計](http://highscalability.com/blog/2016/1/25/design-of-a-modern-cache.html)
|
|
|
- [ ] [Facebook 規模のライブ ビデオ ストリーミング](http://highscalability.com/blog/2016/1/13/live-video-streaming-at-facebook-scale.html)
|
|
|
- [ ] [Amazon の AWS で 1,100 万人以上のユーザーに拡張するための初心者ガイド](http://highscalability.com/blog/2016/1/11/a-beginners-guide-to-amazons.htmlで1,100万ユーザーに拡大)
|
|
|
- [ ] [Netflix スタック全体の 360 度ビュー](http://highscalability.com/blog/2015/11/9/a-360-degree-view-of-the-entire-netflix-stack.html )
|
|
|
- [ ] [レイテンシはどこにでも存在し、売上にコストがかかります - それを解消する方法](http://highscalability.com/latency-everywhere-and-it-costs-you-sales-how-crush-it)
|
|
|
- [ ] [Instagram を動かすもの: 数百のインスタンス、数十のテクノロジー](http://instagram-engineering.tumblr.com/post/13649370142/what-powers-instagram-hunreds-of-instances)
|
|
|
- [ ] [Salesforce アーキテクチャ - 1 日あたり 13 億トランザクションを処理する方法](http://highscalability.com/blog/2013/9/23/salesforce-architecture-how-they-handle-13-billion-transacti.html )
|
|
|
- [ ] [ESPN の大規模なアーキテクチャ - 毎秒 100,000 Duh Nuh Nuhs で動作](http://highscalability.com/blog/2013/11/4/espns-architecture-at-scale-operating-at-100000-duh-nuh-nuhs.html)
|
|
|
- [ ] 「メッセージング、シリアル化、およびキュー システム」を参照してください。サービスを結合できるいくつかのテクノロジーについては、以下を参照してください。
|
|
|
- [ ] ツイッター：
|
|
|
- [O'MySQL CE 2011: Jeremy Cole、「@Twitter におけるビッグ データとスモール データ」」 (ビデオ)](https://www.youtube.com/watch?v=5cKTP36HVgI)
|
|
|
- [大規模なタイムライン](https://www.infoq.com/presentations/Twitter-Timeline-Scalability)
|
|
|
- さらに詳しくは、「大規模なデータセットのマイニング」を参照してください。 [ビデオ シリーズ](#video-series) セクションのビデオ シリーズ
|
|
|
- [ ] システム設計プロセスの練習: ここでは、紙の上で取り組んでみるいくつかのアイデアを示します。それぞれのアイデアには、現実世界でどのように処理されたかについてのドキュメントが含まれています。
|
|
|
- レビュー: [システム設計入門](https://github.com/donnemartin/system-design-primer)
|
|
|
- [HiredInTech のシステム設計](http://www.hiredintech.com/system-design/)
|
|
|
- [チートシート](https://github.com/jwasham/coding-interview-university/blob/main/extras/cheat%20sheets/system-design.pdf)
|
|
|
- 流れ：
|
|
|
1. 問題と範囲を理解します。
|
|
|
- 面接官の助けを借りてユースケースを定義する
|
|
|
- 追加機能を提案する
|
|
|
- 面接官が範囲外と判断した項目は削除します。
|
|
|
- 高可用性が必要であると想定し、ユースケースとして追加します
|
|
|
2. 制約について考えます。
|
|
|
- 月あたりのリクエスト数を尋ねる
|
|
|
- 1 秒あたりのリクエスト数を尋ねます (ボランティアで依頼したり、計算させたりすることもあります)
|
|
|
- 読み取りと書き込みの割合を見積もる
|
|
|
- 見積もりの際は 80/20 ルールを念頭に置いてください
|
|
|
- 1秒あたりに書き込まれるデータ量
|
|
|
- 5 年間に必要な合計ストレージ
|
|
|
- 1秒あたりに読み取られるデータ量
|
|
|
3. 抽象的なデザイン:
|
|
|
- レイヤー (サービス、データ、キャッシュ)
|
|
|
- インフラストラクチャ: 負荷分散、メッセージング
|
|
|
- サービスを推進する主要なアルゴリズムの大まかな概要
|
|
|
- ボトルネックを検討し、解決策を決定します
|
|
|
- 演習:
|
|
|
- [ランダムな固有 ID 生成システムを設計する](https://blog.twitter.com/2010/payment-snowflake)
|
|
|
- [キーと値のデータベースを設計する](http://www.slideshare.net/dvirsky/introduction-to-redis)
|
|
|
- [写真共有システムを設計する](http://highscalability.com/blog/2011/12/6/instagram-architecture-14-million-users-terabytes-of-photos.html)
|
|
|
- [推奨システムの設計](http://ijcai13.org/files/tutorial_slides/td3.pdf)
|
|
|
- [URL 短縮システムの設計: 上記からコピー](http://www.hiredintech.com/system-design/the-system-design-process/)
|
|
|
- [キャッシュ システムの設計](https://web.archive.org/web/20220217064329/https://adayinthelifeof.nl/2011/02/06/memcache-internals/)
|
|
|
|
|
|
## 追加の学習
|
|
|
|
|
|
これらは、あなたが総合的なソフトウェア エンジニアになるのに役立ち、次の点に注意するために追加しました。
|
|
|
テクノロジーとアルゴリズムを活用できるため、より大きなツールボックスが手に入ります。
|
|
|
|
|
|
- ### コンパイラ
|
|
|
- [約 1 分でわかるコンパイラーの仕組み (ビデオ)](https://www.youtube.com/watch?v=IhC7sdYe-Jg)
|
|
|
- [ハーバード CS50 - コンパイラー (ビデオ)](https://www.youtube.com/watch?v=CSZLNYF4Klo)
|
|
|
- [C++ (ビデオ)](https://www.youtube.com/watch?v=twodd1KFfGk)
|
|
|
- [コンパイラの最適化を理解する (C++) (ビデオ)](https://www.youtube.com/watch?v=FnGCDLhaxKU)
|
|
|
|
|
|
- ### Emacs と vi(m)
|
|
|
- UNIX ベースのコード エディターに慣れる
|
|
|
- ヴィ(男):
|
|
|
- [Vim による編集 01 - インストール、セットアップ、およびモード (ビデオ)](https://www.youtube.com/watch?v=5givLEMcINQ&index=1&list=PL13bz4SHGmRxlZVmWQ9DvXo1fEg4UdGkr)
|
|
|
- [VIM アドベンチャー](http://vim-adventures.com/)
|
|
|
- 4 つのビデオのセット:
|
|
|
- [vi/vim エディター - レッスン 1](https://www.youtube.com/watch?v=SI8TeVMX8pk)
|
|
|
- [vi/vim エディタ - レッスン 2](https://www.youtube.com/watch?v=F3OO7ZIOaJE)
|
|
|
- [vi/vim エディター - レッスン 3](https://www.youtube.com/watch?v=ZYEccA_nMaI)
|
|
|
- [vi/vim エディター - レッスン 4](https://www.youtube.com/watch?v=1lYD5gwgZIA)
|
|
|
- [Emacs の代わりに Vi を使用する](http://www.cs.yale.edu/homes/aspnes/classes/223/notes.html#Using_Vi_instead_of_Emacs)
|
|
|
- emacs:
|
|
|
- [基礎 Emacs チュートリアル (ビデオ)](https://www.youtube.com/watch?v=hbmV1bnQ-i0)
|
|
|
- 3 個セット (ビデオ):
|
|
|
- [Emacs チュートリアル (初心者向け) -その 1- ファイルコマンド、カット/コピー/ペースト、カーソルコマンド](https://www.youtube.com/watch?v=ujODL7MD04Q)
|
|
|
- [Emacs チュートリアル (初心者向け) -パート 2- バッファ管理、検索、M-x grep および rgrep モード](https://www.youtube.com/watch?v=XWpsRupJ4II)
|
|
|
- [Emacs チュートリアル (初心者向け) -パート 3- 式、ステートメント、~/.emacs ファイル、およびパッケージ](https://www.youtube.com/watch?v=paSgzPso-yc)
|
|
|
- [悪のモード: あるいは、心配をやめて Emacs を愛する方法を学んだ方法 (ビデオ)](https://www.youtube.com/watch?v=JWD1Fpdd4Pc)
|
|
|
- [Emacs を使用した C プログラムの作成](http://www.cs.yale.edu/homes/aspnes/classes/223/notes.html#Writing_C_programs_with_Emacs)
|
|
|
- [Emacs の完全初心者ガイド (David Wilson によるビデオ)](https://www.youtube.com/watch?v=48JlgiBpw_I&t=0s)
|
|
|
- [Emacs の完全初心者ガイド (David Wilson によるメモ)](https://systemcrafters.net/emacs-essentials/absolute-beginners-guide-to-emacs/)
|
|
|
|
|
|
- ### Unix コマンドライン ツール
|
|
|
- 優れたツールから以下のリストを記入しました。
|
|
|
- バッシュ
|
|
|
- 猫
|
|
|
- grep
|
|
|
- セド
|
|
|
- ああ
|
|
|
- カールまたはウィジェット
|
|
|
- 選別
|
|
|
- tr
|
|
|
- ユニーク
|
|
|
- [strace](https://en.wikipedia.org/wiki/Strace)
|
|
|
- [tcpdump](https://danielmiessler.com/study/tcpdump/)
|
|
|
|
|
|
- ### 情報理論 (ビデオ)
|
|
|
- [カーンアカデミー](https://www.khanacademy.org/computing/computer-science/informationtheory)
|
|
|
- マルコフ過程の詳細:
|
|
|
- [コアマルコフテキスト生成](https://www.coursera.org/learn/data-structions-optimizing-performance/lecture/waxgx/core-markov-text-generation)
|
|
|
- [マルコフ テキスト生成のコア実装](https://www.coursera.org/learn/data-structors-optimizing-performance/lecture/gZhiC/core-implementing-markov-text-generation)
|
|
|
- [プロジェクト = マルコフ テキスト生成ウォークスルー](https://www.coursera.org/learn/data-structions-optimizing-performance/lecture/EUjrq/project-markov-text-generation-walk-through)
|
|
|
- 詳細については、以下の MIT 6.050J 情報とエントロピー シリーズを参照してください。
|
|
|
|
|
|
- ### パリティとハミングコード (ビデオ)
|
|
|
- [紹介](https://www.youtube.com/watch?v=q-3BctoUpHE)
|
|
|
- [パリティ](https://www.youtube.com/watch?v=DdMcAUlxh1M)
|
|
|
- ハミングコード:
|
|
|
- [エラー検出](https://www.youtube.com/watch?v=1A_NcXxdoCc)
|
|
|
- [誤り訂正](https://www.youtube.com/watch?v=JAMLuxdHH8o)
|
|
|
- [エラーチェック](https://www.youtube.com/watch?v=wbH2VxzmoZk)
|
|
|
|
|
|
- ### エントロピー
|
|
|
- 以下のビデオもご覧ください
|
|
|
- 最初に情報理論のビデオを必ず視聴してください
|
|
|
- [情報理論、クロード シャノン、エントロピー、冗長性、データ圧縮とデータ圧縮ビッツ（ビデオ）](https://youtu.be/JnJq3Py0dyM?t=176)
|
|
|
|
|
|
- ### 暗号化
|
|
|
- 以下のビデオもご覧ください
|
|
|
- 最初に情報理論のビデオを必ず視聴してください
|
|
|
- [カーン アカデミー シリーズ](https://www.khanacademy.org/computing/computer-science/cryptography)
|
|
|
- [暗号化: ハッシュ関数](https://www.youtube.com/watch?v=KqqOXndnvic&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp&index=30)
|
|
|
- [暗号化: 暗号化](https://www.youtube.com/watch?v=9TNI2wHmaeI&index=31&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp)
|
|
|
|
|
|
- ### 圧縮
|
|
|
- 最初に情報理論のビデオを必ず視聴してください
|
|
|
- コンピューターマニア (ビデオ):
|
|
|
- [圧縮](https://www.youtube.com/watch?v=Lto-ajuqW3w)
|
|
|
- [圧縮におけるエントロピー](https://www.youtube.com/watch?v=M5c_RFKVkko)
|
|
|
- [逆さまの木 (ハフマンの木)](https://www.youtube.com/watch?v=umTbivyJoiI)
|
|
|
- [おまけ/トリッツ - ハフマン ツリー](https://www.youtube.com/watch?v=DV8efuB3h2g)
|
|
|
- [テキストのエレガントな圧縮 (LZ 77 メソッド)](https://www.youtube.com/watch?v=goOa3DGezUA)
|
|
|
- [テキスト圧縮と確率の両立](https://www.youtube.com/watch?v=cCDCfoHTsaU)
|
|
|
- [コンプレッサーヘッドビデオ](https://www.youtube.com/playlist?list=PLOU2XLYxmsIJGErt5rrCqaSGTMyyqNt2H)
|
|
|
- [(オプション) Google Developers Live: GZIP だけでは十分ではありません!](https://www.youtube.com/watch?v=whGwm0Lky2s)
|
|
|
|
|
|
- ### コンピュータセキュリティ
|
|
|
- [MIT (23 ビデオ)](https://www.youtube.com/playlist?list=PLUl4u3cNGP62K2DjQLRxDNRi0z2IRWnNh)
|
|
|
- [概要、脅威モデル](https://www.youtube.com/watch?v=GqmQg-cszw4&index=1&list=PLUl4u3cNGP62K2DjQLRxDNRi0z2IRWnNh)
|
|
|
- [コントロールハイジャック攻撃](https://www.youtube.com/watch?v=6bwzNg5qQ0o&list=PLUl4u3cNGP62K2DjQLRxDNRi0z2IRWnNh&index=2)
|
|
|
- [バッファ オーバーフローの悪用と防御](https://www.youtube.com/watch?v=drQyrzRoRiA&list=PLUl4u3cNGP62K2DjQLRxDNRi0z2IRWnNh&index=3)
|
|
|
- [権限の分離](https://www.youtube.com/watch?v=6SIJmoE9L9g&index=4&list=PLUl4u3cNGP62K2DjQLRxDNRi0z2IRWnNh)
|
|
|
- [機能](https://www.youtube.com/watch?v=8VqTSY-11F4&index=5&list=PLUl4u3cNGP62K2DjQLRxDNRi0z2IRWnNh)
|
|
|
- [サンドボックス ネイティブ コード](https://www.youtube.com/watch?v=VEV74hwASeU&list=PLUl4u3cNGP62K2DjQLRxDNRi0z2IRWnNh&index=6)
|
|
|
- [Web セキュリティ モデル](https://www.youtube.com/watch?v=chkFBigodIw&index=7&list=PLUl4u3cNGP62K2DjQLRxDNRi0z2IRWnNh)
|
|
|
- [Web アプリケーションの保護](https://www.youtube.com/watch?v=EBQIGy1ROLY&index=8&list=PLUl4u3cNGP62K2DjQLRxDNRi0z2IRWnNh)
|
|
|
- [シンボリック実行](https://www.youtube.com/watch?v=yRVZPvHYHzw&index=9&list=PLUl4u3cNGP62K2DjQLRxDNRi0z2IRWnNh)
|
|
|
- [ネットワーク セキュリティ](https://www.youtube.com/watch?v=SIEVvk3NVuk&index=11&list=PLUl4u3cNGP62K2DjQLRxDNRi0z2IRWnNh)
|
|
|
- [ネットワーク プロトコル](https://www.youtube.com/watch?v=QOtA76ga_fY&index=12&list=PLUl4u3cNGP62K2DjQLRxDNRi0z2IRWnNh)
|
|
|
- [サイドチャネル攻撃](https://www.youtube.com/watch?v=PuVMkSEcPiI&index=15&list=PLUl4u3cNGP62K2DjQLRxDNRi0z2IRWnNh)
|
|
|
|
|
|
- ### ガベージ コレクション
|
|
|
- [Python での GC (ビデオ)](https://www.youtube.com/watch?v=iHVs_HkjdmI)
|
|
|
- [Java の詳細: ガベージ コレクションは優れています!](https://www.infoq.com/presentations/garbage-collection-benefits)
|
|
|
- [Python の詳細: CPython のガベージ コレクション (ビデオ)](https://www.youtube.com/watch?v=P-8Z0-MhdQs&list=PLdzf4Clw0VbOEWOS_sLhT_9zaiQDrS5AR&index=3)
|
|
|
|
|
|
- ### 並列プログラミング
|
|
|
- [Coursera (Scala)](https://www.coursera.org/learn/parprog1/home/week/1)
|
|
|
- [高性能並列コンピューティングのための効率的な Python (ビデオ)](https://www.youtube.com/watch?v=uY85GkaYzBk)
|
|
|
|
|
|
- ### メッセージング、シリアル化、およびキューイング システム
|
|
|
- [スリフト](https://thrift.apache.org/)
|
|
|
- [チュートリアル](http://thrift-tutorial.readthedocs.io/en/latest/intro.html)
|
|
|
- [プロトコル バッファ](https://developers.google.com/protocol-buffers/)
|
|
|
- [チュートリアル](https://developers.google.com/protocol-buffers/docs/tutorials)
|
|
|
- [gRPC](http://www.grpc.io/)
|
|
|
- [Java 開発者のための gRPC 101 (ビデオ)](https://www.youtube.com/watch?v=5tmPvSe7xXQ&list=PLcTqM9n_dieN0k1nSeN36Z_ppKnvMJoly&index=1)
|
|
|
- [Redis](http://redis.io/)
|
|
|
- [チュートリアル](http://try.redis.io/)
|
|
|
- [Amazon SQS (キュー)](https://aws.amazon.com/sqs/)
|
|
|
- [Amazon SNS (pub-sub)](https://aws.amazon.com/sns/)
|
|
|
- [RabbitMQ](https://www.rabbitmq.com/)
|
|
|
- [はじめる](https://www.rabbitmq.com/getstarted.html)
|
|
|
- [セロリ](http://www.celeryproject.org/)
|
|
|
- [Celery を使用した最初のステップ](http://docs.celeryproject.org/en/latest/getting-started/first-steps-with-celery.html)
|
|
|
- [ZeroMQ](http://zeromq.org/)
|
|
|
- [はじめに - マニュアルを読む](http://zeromq.org/intro:read-the-manual)
|
|
|
- [ActiveMQ](http://activemq.apache.org/)
|
|
|
- [Kafka](http://kafka.apache.org/documentation.html#introduction)
|
|
|
- [メッセージパック](http://msgpack.org/index.html)
|
|
|
- [アブロ](https://avro.apache.org/)
|
|
|
|
|
|
- ### A*
|
|
|
- [検索アルゴリズム](https://en.wikipedia.org/wiki/A*_search_algorithm)
|
|
|
- [A* Pathfinding (E01: アルゴリズムの説明) (ビデオ)](https://www.youtube.com/watch?v=-L-WgKMFuhE)
|
|
|
|
|
|
- ### 高速フーリエ変換
|
|
|
- [フーリエ変換の対話型ガイド](https://betterexplained.com/articles/an-interactive-guide-to-the-fourier-transform/)
|
|
|
- [フーリエ変換とは何ですか?それは何に使われますか?](http://www.askamathematician.com/2012/09/q-what-is-a-fourier-transform-what-is-it-used-for/)
|
|
|
- [フーリエ変換とは何ですか? (ビデオ)](https://www.youtube.com/watch?v=Xxut2PN-V8Q)
|
|
|
- [分割＆分割 制覇: FFT (ビデオ)](https://www.youtube.com/watch?v=iTMn0Kt18tg&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp&index=4)
|
|
|
- [FFT を理解する](http://jakevdp.github.io/blog/2013/08/28/Understanding-the-fft/)
|
|
|
|
|
|
- ### ブルームフィルター
|
|
|
- m ビットと k 個のハッシュ関数を持つブルーム フィルターを指定すると、挿入テストとメンバーシップ テストの両方が O(k) になります。
|
|
|
- [ブルームフィルター (ビデオ)](https://www.youtube.com/watch?v=-SuTGoFYjZs)
|
|
|
- [ブルームフィルター |大規模なデータセットのマイニング |スタンフォード大学 (ビデオ)](https://www.youtube.com/watch?v=qBTdukbzc78)
|
|
|
- [チュートリアル](http://billmill.org/bloomfilter-tutorial/)
|
|
|
- [ブルーム フィルター アプリの書き方](http://blog.michaelschmatz.com/2016/04/11/how-to-write-a-bloom-filter-cpp/)
|
|
|
|
|
|
- ### ハイパーログログ
|
|
|
- [わずか 1.5KB のメモリを使用して 10 億個の異なるオブジェクトを数える方法](http://highscalability.com/blog/2012/4/5/big-data-counting-how-to-count-a-billion-distinct-objects-us.html)
|
|
|
|
|
|
- ### 局所性を考慮したハッシュ
|
|
|
- 文書の類似性を判断するために使用されます
|
|
|
- 2 つのドキュメント/文字列がまったく同じかどうかを判断するために使用される MD5 または SHA の逆です。
|
|
|
- [Simhashing (できれば) シンプルに](http://ferd.ca/simhashing-hopefull-made-simple.html)
|
|
|
|
|
|
- ### ファン・エムデ・ボアスの木
|
|
|
- [分割＆分割 征服: ファン エムデ ボアスの木 (ビデオ)](https://www.youtube.com/watch?v=hmReJCupbNU&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp&index=6)
|
|
|
- [MIT 講義ノート](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-design-and-analysis-of-algorithms-spring-2012/lecture-notes/MIT6_046JS12_lec15.pdf)
|
|
|
|
|
|
- ### 拡張データ構造
|
|
|
- [CS 61B 講義 39: データ構造の拡張](https://archive.org/details/ucberkeley_webcast_zksIj9O8_jc)
|
|
|
|
|
|
- ### バランスのとれた検索ツリー
|
|
|
- 少なくとも 1 つのタイプのバランスのとれたバイナリ ツリーを知っています (そして、それがどのように実装されているかを知っています):
|
|
|
- 「バランスの取れた検索ツリーの中で、AVL と 2/3 ツリーは時代遅れになり、赤黒ツリーの方が人気があるようです。」
|
|
|
特に興味深い自己組織化データ構造は、回転を使用するスプレイ ツリーです。
|
|
|
アクセスされたキーをルートに移動します。」 - スキエナ
|
|
|
- このうち、私はスプレイツリーを実装することにしました。私が読んだ限りでは、
|
|
|
インタビューでのバランスの取れた検索ツリー。しかし、コーディングをもう一段階体験したかったのです
|
|
|
はっきり言って、枝分かれした木はミツバチの膝です。赤黒ツリーのコードをたくさん読みました
|
|
|
- スプレイツリー: 挿入、検索、削除機能
|
|
|
赤/黒のツリーを実装することになった場合は、次のことを試してください。
|
|
|
- 検索および挿入機能、削除のスキップ
|
|
|
- B-Tree は非常に大規模なデータセットで広く使用されているため、B-Tree について詳しく知りたい
|
|
|
- [自己平衡二分探索木](https://en.wikipedia.org/wiki/Self-balancing_binary_search_tree)
|
|
|
|
|
|
- **AVL ツリー**
|
|
|
- 実際には：
|
|
|
私の知る限り、これらは実際にはあまり使用されていませんが、どのような場所にあるのかはわかりました。
|
|
|
AVL ツリーは、O(log n) の検索、挿入、削除をサポートする別の構造です。より厳格です
|
|
|
赤黒の木よりもバランスが取れているため、挿入と削除は遅くなりますが、取得は速くなります。これでできます
|
|
|
言語など、一度構築すれば再構築せずにロードできるデータ構造にとって魅力的
|
|
|
辞書 (またはアセンブラやインタプリタのオペコードなどのプログラム辞書)
|
|
|
- [MIT AVL ツリー / AVL ソート (ビデオ)](https://www.youtube.com/watch?v=FNeL18KsWPc&list=PLUl4u3cNGP61Oq3tWYp6V_F-5jb5L2iHb&index=6)
|
|
|
- [AVL ツリー (ビデオ)](https://www.coursera.org/learn/data-structures/lecture/Qq5E0/avl-trees)
|
|
|
- [AVL ツリーの実装 (ビデオ)](https://www.coursera.org/learn/data-structures/lecture/PKEBC/avl-tree-implementation)
|
|
|
- [分割とマージ](https://www.coursera.org/learn/data-structures/lecture/22BgE/split-and-merge)
|
|
|
- [[レビュー] 19 分でわかる AVL ツリー (プレイリスト) (ビデオ)](https://www.youtube.com/playlist?list=PL9xmBV_5YoZOUFgdIeOPuH6cfSnNRMau-)
|
|
|
|
|
|
- **スプレーツリー**
|
|
|
- 実際には：
|
|
|
スプレイ ツリーは通常、キャッシュ、メモリ アロケータ、ルーター、ガベージ コレクター、
|
|
|
データ圧縮、ロープ (長いテキスト文字列に使用される文字列の置換)、Windows NT (仮想メモリ内、
|
|
|
ネットワークおよびファイル システム コード) など
|
|
|
- [CS 61B: スプレイ ツリー (ビデオ)](https://archive.org/details/ucberkeley_webcast_G5QIXywcJlY)
|
|
|
- MIT 講義: スプレー ツリー:
|
|
|
- 非常に数学的になりますが、最後の 10 分を必ず見てください。
|
|
|
- [ビデオ](https://www.youtube.com/watch?v=QnPl_Y6EqMo)
|
|
|
|
|
|
- **赤/黒の木**
|
|
|
- これらは 2-3 ツリーの翻訳です (下記を参照)。
|
|
|
- 実際には：
|
|
|
赤黒ツリーは、挿入時間、削除時間、および検索時間について最悪の場合の保証を提供します。
|
|
|
これにより、リアルタイム アプリケーションなどの時間に敏感なアプリケーションで価値が高まるだけでなく、
|
|
|
しかし、それは、最悪の場合の保証を提供する他のデータ構造の貴重な構成要素になります。
|
|
|
たとえば、計算幾何学で使用される多くのデータ構造は、赤黒ツリーに基づくことができます。
|
|
|
現在の Linux カーネルで使用されている Completely Fair Scheduler は、赤黒ツリーを使用します。 Java のバージョン 8 では、
|
|
|
コレクション ハッシュマップは、LinkedList を使用する代わりに、同じ要素を低品質で保存するように変更されました。
|
|
|
ハッシュコード、赤黒ツリーが使用されます
|
|
|
- [Aduni - アルゴリズム - レクチャー 4 (リンクは開始点にジャンプします) (ビデオ)](https://youtu.be/1W3x0f_RmUo?list=PLFDnELG9dpVxQCxuD-9BSy2E7BWY3t5Sm&t=3871)
|
|
|
- [Aduni - アルゴリズム - レクチャー 5 (ビデオ)](https://www.youtube.com/watch?v=hm2GHwyKF1o&list=PLFDnELG9dpVxQCxuD-9BSy2E7BWY3t5Sm&index=5)
|
|
|
- [赤黒の木](https://en.wikipedia.org/wiki/Red%E2%80%93black_tree)
|
|
|
- [二分探索と Red Black Tree の概要](https://www.topcoder.com/thrive/articles/An%20Introduction%20to%20Binary%20Search%20and%20Red-Black%20Trees)
|
|
|
- [[レビュー] 30 分でわかる Red-Black Trees (プレイリスト) (ビデオ)](https://www.youtube.com/playlist?list=PL9xmBV_5YoZNqDI8qfOZgzbqahCUmUEin)
|
|
|
|
|
|
- **2-3 検索ツリー**
|
|
|
- 実際には：
|
|
|
2 ～ 3 個のツリーでは、検索は遅くなりますが、挿入は高速になります (AVL ツリーと比較して高さが高いため)。
|
|
|
- 実装にはさまざまなタイプのノードが含まれるため、2 ～ 3 個のツリーを使用することはほとんどありません。代わりに、人々は赤黒の木を使います。
|
|
|
- [23 ツリーの直感と定義 (ビデオ)](https://www.youtube.com/watch?v=C3SsdUqasD4&list=PLA5Lqm4uh9Bbq-E0ZnqTIa8LRaL77ica6&index=2)
|
|
|
- [23 ツリーのバイナリ ビュー](https://www.youtube.com/watch?v=iYvBtGKsqSg&index=3&list=PLA5Lqm4uh9Bbq-E0ZnqTIa8LRaL77ica6)
|
|
|
- [2-3 Trees (学生朗読) (ビデオ)](https://www.youtube.com/watch?v=TOb1tuEZ2X4&index=5&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp)
|
|
|
|
|
|
- **2-3-4 ツリー (別名 2-4 ツリー)**
|
|
|
- 実際には：
|
|
|
2 ～ 4 個のツリーごとに、同じ順序でデータ要素を持つ対応する赤と黒のツリーがあります。挿入と削除
|
|
|
2 ～ 4 個のツリーに対する操作は、赤黒ツリーの色の反転と回転にも相当します。これにより、2 ～ 4 本の木が作成されます。
|
|
|
これは、赤黒ツリーの背後にあるロジックを理解するための重要なツールであり、これが、多くのアルゴリズム入門書で紹介されている理由です。
|
|
|
**実際には 2 ～ 4 本の木はあまり使用されません**が、赤黒の木の直前に 2 ～ 4 本の木。
|
|
|
- [CS 61B レクチャー 26: バランスのとれた検索ツリー (ビデオ)](https://archive.org/details/ucberkeley_webcast_zqrqYXkth6Q)
|
|
|
- [Bottom Up 234-Trees (ビデオ)](https://www.youtube.com/watch?v=DQdMYevEyE4&index=4&list=PLA5Lqm4uh9Bbq-E0ZnqTIa8LRaL77ica6)
|
|
|
- [トップダウン 234-Trees (ビデオ)](https://www.youtube.com/watch?v=2679VQ26Fp4&list=PLA5Lqm4uh9Bbq-E0ZnqTIa8LRaL77ica6&index=5)
|
|
|
|
|
|
- **N 配列 (K 配列、M 配列) ツリー**
|
|
|
- 注: N または K は分岐係数 (最大分岐) です。
|
|
|
- 二分木は、分岐係数 = 2 の 2 分木です。
|
|
|
- 2 ～ 3 本の木は 3 分木です
|
|
|
- [K-Ary Tree](https://en.wikipedia.org/wiki/K-ary_tree)
|
|
|
|
|
|
- **B ツリー**
|
|
|
- 面白い事実: それは謎ですが、B はボーイング、バランスド、またはバイエル (共同発明者) を表す可能性があります。
|
|
|
- 実際には：
|
|
|
B ツリーはデータベースで広く使用されています。最新のファイルシステムのほとんどは B ツリー (またはバリアント) を使用します。に加えて
|
|
|
B ツリーはデータベースで使用されるだけでなく、ファイル システムでも使用され、任意のファイルへの迅速なランダム アクセスを可能にします。
|
|
|
特定のファイル内のブロック。基本的な問題は、ファイル ブロック アドレスをディスク ブロックに変換することです。
|
|
|
(またはおそらくシリンダーヘッドセクターへの) アドレス
|
|
|
- [B-Tree](https://en.wikipedia.org/wiki/B-tree)
|
|
|
- [B ツリー データ構造](http://btechsmartclass.com/data_structs/b-trees.html)
|
|
|
- [B-Tree の紹介 (ビデオ)](https://www.youtube.com/watch?v=I22wEC1tTGo&list=PLA5Lqm4uh9Bbq-E0ZnqTIa8LRaL77ica6&index=6)
|
|
|
- [B ツリーの定義と挿入 (ビデオ)](https://www.youtube.com/watch?v=s3bCdZGrgpA&index=7&list=PLA5Lqm4uh9Bbq-E0ZnqTIa8LRaL77ica6)
|
|
|
- [B ツリーの削除 (ビデオ)](https://www.youtube.com/watch?v=svfnVhJOfMc&index=8&list=PLA5Lqm4uh9Bbq-E0ZnqTIa8LRaL77ica6)
|
|
|
- [MIT 6.851 - メモリ階層モデル (ビデオ)](https://www.youtube.com/watch?v=V3omVLzI0WE&index=7&list=PLUl4u3cNGP61hsJNdULdudlRL493b-XZf)
|
|
|
- キャッシュを意識しない B ツリー、非常に興味深いデータ構造をカバーします
|
|
|
- 最初の 37 分は非常に専門的なため、スキップされる可能性があります (B はブロック サイズ、キャッシュ ライン サイズ)
|
|
|
- [[レビュー] 26 分でわかる B-Trees (プレイリスト) (ビデオ)](https://www.youtube.com/playlist?list=PL9xmBV_5YoZNFPPv98DjTdD9X6UI9KMHz)
|
|
|
|
|
|
- ### k-D ツリー
|
|
|
- 長方形または高次元のオブジェクト内の多数の点を見つけるのに最適です
|
|
|
- k 最近傍に適切に適合
|
|
|
- [kNN K-d ツリー アルゴリズム (ビデオ)](https://www.youtube.com/watch?v=Y4ZgLlDfKDg)
|
|
|
|
|
|
- ### リストをスキップする
|
|
|
- 「これらはややカルト的なデータ構造です。」 - スキエナ
|
|
|
- [ランダム化: スキップ リスト (ビデオ)](https://www.youtube.com/watch?v=2g9OSRKJuzM&index=10&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp)
|
|
|
- [アニメーションともう少し詳細については](https://en.wikipedia.org/wiki/Skip_list)
|
|
|
|
|
|
- ### ネットワーク フロー
|
|
|
- [5 分でわかるフォード対フルカーソン — ステップバイステップの例 (ビデオ)](https://www.youtube.com/watch?v=Tl90tNtKvxs)
|
|
|
- [フォード・フルカーソンアルゴリズム (ビデオ)](https://www.youtube.com/watch?v=v1VgJmkEJW0)
|
|
|
- [ネットワーク フロー (ビデオ)](https://www.youtube.com/watch?v=2vhN4Ice5jI)
|
|
|
|
|
|
- ### 素セットとユニオン検索
|
|
|
- [UCB 61B - 素セット;並べ替えと整理セレクション (ビデオ)](https://archive.org/details/ucberkeley_webcast_MAEGXTwmUsI)
|
|
|
- [Sedgewick アルゴリズム - Union-Find (6 ビデオ)](https://www.coursera.org/learn/algorithms-part1/home/week/1)
|
|
|
|
|
|
- ### 高速処理のための数学
|
|
|
- [整数算術、からつばかけ算（動画）](https://www.youtube.com/watch?v=eCaXlAaN2uE&index=11&list=PLUl4u3cNGP61Oq3tWYp6V_F-5jb5L2iHb)
|
|
|
- [中国剰余定理 (暗号化で使用) (ビデオ)](https://www.youtube.com/watch?v=ru7mWZJlRQg)
|
|
|
|
|
|
- ### トレプ
|
|
|
- 二分探索木とヒープの組み合わせ
|
|
|
- [Treap](https://en.wikipedia.org/wiki/Treap)
|
|
|
- [データ構造: Treaps の説明 (ビデオ)](https://www.youtube.com/watch?v=6podLUyingH8)
|
|
|
- [集合演算でのアプリケーション](https://www.cs.cmu.edu/~scandal/papers/treaps-spaa98.pdf)
|
|
|
|
|
|
- ### 線形計画法 (ビデオ)
|
|
|
- [線形計画法](https://www.youtube.com/watch?v=M4K6HYLHREQ)
|
|
|
- [最低コストを調べる](https://www.youtube.com/watch?v=2ACJ9ewUC6U)
|
|
|
- [最大値を見つける](https://www.youtube.com/watch?v=8AA_81xI3ik)
|
|
|
- [Python で線形方程式を解く - シンプレックス アルゴリズム](https://www.youtube.com/watch?v=44pAWI7v5Zk)
|
|
|
|
|
|
- ### ジオメトリ、凸包 (ビデオ)
|
|
|
- [グラフアルゴリズムIV: 幾何学的アルゴリズムの概要 - レクチャー 9](https://youtu.be/XIAQRlNkJAw?list=PLFDnELG9dpVxQCxuD-9BSy2E7BWY3t5Sm&t=3164)
|
|
|
- [幾何アルゴリズム: Graham &ジャービス - 講義 10](https://www.youtube.com/watch?v=J5aJEcOr6Eo&index=10&list=PLFDnELG9dpVxQCxuD-9BSy2E7BWY3t5Sm)
|
|
|
- [分割＆分割 征服: 凸包、中央値の検出](https://www.youtube.com/watch?v=EzeYI7p9MjU&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp&index=2)
|
|
|
|
|
|
- ### 離散数学
|
|
|
- [コンピューター サイエンス 70,001 - 2015 年春 - 離散数学と確率理論](http://www.infocobuild.com/education/audio-video-courses/computer-science/cs70-spring2015-berkeley.html)
|
|
|
- [シャイ・サイモンソンによる離散数学 (19 ビデオ)](https://www.youtube.com/playlist?list=PLWX710qNZo_sNlSWRMVIh6kfTjolNaZ8t)
|
|
|
- [IIT Ropar NPTEL による離散数学](https://nptel.ac.in/courses/106/106/106106183/)
|
|
|
|
|
|
---
|
|
|
|
|
|
## 一部の主題に関する追加の詳細
|
|
|
|
|
|
これらは、上ですでに示したいくつかのアイデアを補強するために追加しましたが、含めたくはありませんでした
|
|
|
あまりにも多すぎるため、上記で説明しました。あるテーマについてやりすぎるのは簡単です。
|
|
|
今世紀中に採用されたいですよね？
|
|
|
|
|
|
- **固体**
|
|
|
- [ ] [Bob Martin オブジェクト指向とアジャイル設計の SOLID 原則 (ビデオ)](https://www.youtube.com/watch?v=TMuno5RZNeE)
|
|
|
- [ ] S - [単一責任の原則](http://www.oodesign.com/single-responsibility-principle.html) | [各オブジェクトに対する単一の責任](http://www.javacodegeeks.com/2011/11/solid-single-responsibility-principle.html)
|
|
|
- [その他のフレーバー](https://docs.google.com/open?id=0ByOwmqah_nuGNHEtcU5OekdDMkk)
|
|
|
- [ ] O - [オープン/クローズの原則](http://www.oodesign.com/open-close-principle.html) | [運用レベルでは、オブジェクトは拡張の準備ができていますが、変更の準備はできません](https://en.wikipedia.org/wiki/Open/closed_principle)
|
|
|
- [その他のフレーバー](http://docs.google.com/a/cleancoder.com/viewer?a=v&pid=explorer&chrome=true&srcid=0BwhCYaYDn8EgN2M5MTkwM2EtNWFkZC00ZTI3LWFjZTUtNTFhZGZiYmUzODc1&hl=en)
|
|
|
- [ ] L - [リスコフ置換原則](http://www.oodesign.com/liskov-s-substitution-principle.html) | [基本クラスと派生クラスは「IS A」原則に従います](http://stackoverflow.com/questions/56860/what-is-the-liskov-substitution-principle)
|
|
|
- [その他のフレーバー](http://docs.google.com/a/cleancoder.com/viewer?a=v&pid=explorer&chrome=true&srcid=0BwhCYaYDn8EgNzAzZjA5ZmItNjU3NS00MzQ5LTkwYjMtMDJhNDU5ZTM0MTlh&hl=en)
|
|
|
- [ ] I - [インターフェイス分離の原則](http://www.oodesign.com/interface-segregation-principle.html) |クライアントは、使用しないインターフェイスの実装を強制されるべきではありません
|
|
|
- [5 分でわかるインターフェース分離の原則 (ビデオ)](https://www.youtube.com/watch?v=3CtAfl7aXAQ)
|
|
|
- [その他のフレーバー](http://docs.google.com/a/cleancoder.com/viewer?a=v&pid=explorer&chrome=true&srcid=0BwhCYaYDn8EgOTViYjJhYzMtMzYxMC00MzFjLWJjMzYtOGJiMDc5N2JkYmJi&hl=ja)
|
|
|
- [ ] D -[依存性反転の原則](http://www.oodesign.com/dependency-inversion-principle.html) |オブジェクトの構成における依存関係を軽減します。
|
|
|
- [依存関係逆転の原則とその重要性](http://stackoverflow.com/questions/62539/what-is-the-dependency-inversion-principle-and-why-is-it-important)
|
|
|
- [その他のフレーバー](http://docs.google.com/a/cleancoder.com/viewer?a=v&pid=explorer&chrome=true&srcid=0BwhCYaYDn8EgMjdlMWIzNGUtZTQ0NC00ZjQ5LTkwYzQtZjRhMDRlNTQ3ZGMz&hl=en)
|
|
|
|
|
|
- **ユニオン検索**
|
|
|
- [概要](https://www.coursera.org/learn/data-structures/lecture/JssSY/overview)
|
|
|
- [単純な実装](https://www.coursera.org/learn/data-structures/lecture/EM5D0/naive-implementations)
|
|
|
- [木](https://www.coursera.org/learn/data-structures/lecture/Mxu0w/trees)
|
|
|
- [ランク別ユニオン](https://www.coursera.org/learn/data-structures/lecture/qb4c2/union-by-rank)
|
|
|
- [パス圧縮](https://www.coursera.org/learn/data-structures/lecture/Q9CVI/path-compression)
|
|
|
- [分析オプション](https://www.coursera.org/learn/data-structures/lecture/GQQLN/analysis-optional)
|
|
|
|
|
|
- **さらに動的プログラミング** (ビデオ)
|
|
|
- [6.006: 動的計画法 I: フィボナッチ、最短経路](https://www.youtube.com/watch?v=r4-cftqTcdI&ab_channel=MITOpenCourseWare)
|
|
|
- [6.006: 動的プログラミング II: テキストの位置調整、ブラックジャック](https://www.youtube.com/watch?v=KLBCUx1is2c&ab_channel=MITOpenCourseWare)
|
|
|
- [6.006: DP III: 括弧、編集距離、ナップザック](https://www.youtube.com/watch?v=TDo3r5M1LNo&ab_channel=MITOpenCourseWare)
|
|
|
- [6.006: DP IV: ギターの運指、テトリス、スーパーマリオブラザーズ](https://www.youtube.com/watch?v=i9OAOk0CUQE&ab_channel=MITOpenCourseWare)
|
|
|
- [6.046: 動的プログラミングとアドバンスト DP](https://www.youtube.com/watch?v=Tw1k46ywN6E&index=14&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp)
|
|
|
- [6.046: 動的プログラミング: 全ペアの最短パス](https://www.youtube.com/watch?v=NzgFUwOaoIw&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp&index=15)
|
|
|
- [6.046: 動的プログラミング (学生の暗唱)](https://www.youtube.com/watch?v=krZI60lKPek&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp&index=12)
|
|
|
|
|
|
- **高度なグラフ処理** (ビデオ)
|
|
|
- [同期分散アルゴリズム: 対称性の破壊。最短パス スパニング ツリー](https://www.youtube.com/watch?v=mUBmcbbJNf4&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp&index=27)
|
|
|
- [非同期分散アルゴリズム: 最短パス スパニング ツリー](https://www.youtube.com/watch?v=kQ-UQAzcnzA&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp&index=28)
|
|
|
|
|
|
- MIT **確率** (数学的で、ゆっくり進めてください。これは数学的なことに適しています) (ビデオ):
|
|
|
- [MIT 6.042J - 確率の概要](https://www.youtube.com/watch?v=SmFwFdESMHI&index=18&list=PLB7540DEDD482705B)
|
|
|
- [MIT 6.042J - 条件付き確率](https://www.youtube.com/watch?v=E6FbvM-FGZ8&index=19&list=PLB7540DEDD482705B)
|
|
|
- [MIT 6.042J - 独立](https://www.youtube.com/watch?v=l1BCv3qqW4A&index=20&list=PLB7540DEDD482705B)
|
|
|
- [MIT 6.042J - 確率変数](https://www.youtube.com/watch?v=MOfhhFaQdjw&list=PLB7540DEDD482705B&index=21)
|
|
|
- [MIT 6.042J - 期待 I](https://www.youtube.com/watch?v=gGlMSe7uEkA&index=22&list=PLB7540DEDD482705B)
|
|
|
- [MIT 6.042J - 期待 II](https://www.youtube.com/watch?v=oI9fMUqgfxY&index=23&list=PLB7540DEDD482705B)
|
|
|
- [MIT 6.042J - 大きな逸脱](https://www.youtube.com/watch?v=q4mwO2qS2z4&index=24&list=PLB7540DEDD482705B)
|
|
|
- [MIT 6.042J - ランダム ウォーク](https://www.youtube.com/watch?v=56iFMY8QW2k&list=PLB7540DEDD482705B&index=25)
|
|
|
|
|
|
- [Simonson: 近似アルゴリズム (ビデオ)](https://www.youtube.com/watch?v=oDniZCmNmNw&list=PLFDnELG9dpVxQCxuD-9BSy2E7BWY3t5Sm&index=19)
|
|
|
|
|
|
- **文字列のマッチング**
|
|
|
- ラビン・カープ (ビデオ):
|
|
|
- [Rabin Karps アルゴリズム](https://www.coursera.org/lecture/data- Structures/rabin-karps-algorithm-c0Qkw)
|
|
|
- [事前計算](https://www.coursera.org/learn/data-structures/lecture/nYrc8/optimization-precomputation)
|
|
|
- [最適化: 実装と分析](https://www.coursera.org/learn/data- Structures/lecture/h4ZLc/optimization-implementation-and-analysis)
|
|
|
- [テーブル ダブリング、カープラビン](https://www.youtube.com/watch?v=BRO7mVIFt08&list=PLUl4u3cNGP61Oq3tWYp6V_F-5jb5L2iHb&index=9)
|
|
|
- [ローリング ハッシュ、償却分析](https://www.youtube.com/watch?v=w6nuXg0BISo&list=PLUl4u3cNGP61Oq3tWYp6V_F-5jb5L2iHb&index=32)
|
|
|
- クヌース・モリス・プラット (KMP):
|
|
|
- [Knuth-Morris-Pratt (KMP) 文字列マッチング アルゴリズム](https://www.youtube.com/watch?v=5i7oKodCRJo)
|
|
|
- Boyer-Moore 文字列検索アルゴリズム
|
|
|
- [Boyer-Moore 文字列検索アルゴリズム](https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm)
|
|
|
- [Boyer-Moore-Horspool アルゴリズムによる高度な文字列検索 (ビデオ)](https://www.youtube.com/watch?v=QDZpzctPf10)
|
|
|
- [Coursera: 文字列上のアルゴリズム](https://www.coursera.org/learn/algorithms-on-strings/home/week/1)
|
|
|
- 最初は素晴らしいですが、KMP を超えるまでに必要以上に複雑になります
|
|
|
- トライの素晴らしい説明
|
|
|
- スキップ可能
|
|
|
|
|
|
- **並べ替え**
|
|
|
|
|
|
- スタンフォード大学の分類に関する講義:
|
|
|
- [講義 15 |プログラミングの抽象化 (ビデオ)](https://www.youtube.com/watch?v=ENp00xylP7c&index=15&list=PLFE6E58F856038C69)
|
|
|
- [講義 16 |プログラミングの抽象化 (ビデオ)](https://www.youtube.com/watch?v=y4M9IVgrVKo&index=16&list=PLFE6E58F856038C69)
|
|
|
- シャイ・サイモンソン:
|
|
|
- [アルゴリズム - 並べ替え - レクチャー 2 (ビデオ)](https://www.youtube.com/watch?v=odNJmw5TOEE&list=PLFDnELG9dpVxQCxuD-9BSy2E7BWY3t5Sm&index=2)
|
|
|
- [アルゴリズム - 並べ替え II - 講義 3 (ビデオ)](https://www.youtube.com/watch?v=hj8YKFTFKEE&list=PLFDnELG9dpVxQCxuD-9BSy2E7BWY3t5Sm&index=3)
|
|
|
- スティーブン・スキーナが分類について講義します:
|
|
|
- [CSE373 2020 - マージソート/クイックソート (ビデオ)](https://www.youtube.com/watch?v=jUf-UQ3a0kg&list=PLOtl7M3yp-DX6ic0HGT0PUX_wiNmkWkXx&index=8)
|
|
|
- [CSE373 2020 - 線形並べ替え (ビデオ)](https://www.youtube.com/watch?v=0ksyQKmre84&list=PLOtl7M3yp-DX6ic0HGT0PUX_wiNmkWkXx&index=9)
|
|
|
|
|
|
- NAND からテトリスへ: [第一原理から最新のコンピューターを構築する](https://www.coursera.org/learn/build-a-computer)
|
|
|
|
|
|
## ビデオ シリーズ
|
|
|
|
|
|
座って楽しんでください。
|
|
|
|
|
|
- [動的計画法の問題の個別リスト (それぞれ短い)](https://www.youtube.com/playlist?list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr)
|
|
|
|
|
|
- [x86 アーキテクチャ、アセンブリ、アプリケーション (11 ビデオ)](https://www.youtube.com/playlist?list=PL038BE01D3BAEFDB0)
|
|
|
|
|
|
- [MIT 18.06 線形代数、2005 年春 (35 ビデオ)](https://www.youtube.com/playlist?list=PLE7DDD91010BC51F8)
|
|
|
|
|
|
- [優れた - MIT 微積分再考: 単一変数微積分](https://www.youtube.com/playlist?list=PL3B08AE665AB9002A)
|
|
|
|
|
|
- [アルゴリズム設計マニュアルからの Skiena 講義 - CSE373 2020 - アルゴリズムの分析 (26 ビデオ)](https://www.youtube.com/watch?v=22hwcnXIGgk&list=PLOtl7M3yp-DX6ic0HGT0PUX_wiNmkWkXx&index=1)
|
|
|
|
|
|
- [UC Berkeley 61B (Spring 2014): データ構造 (25 ビデオ)](https://archive.org/details/ucberkeley-webcast-PL-XXv-cvA_iAlnI-BQr9hjqADPBtujFJd)
|
|
|
|
|
|
- [UC Berkeley 61B (2006 年秋): データ構造 (39 ビデオ)](https://archive.org/details/ucberkeley-webcast-PL4BBB74C7D2A1049C)
|
|
|
|
|
|
- [UC Berkeley 61C: 機械構造 (26 ビデオ)](https://archive.org/details/ucberkeley-webcast-PL-XXv-cvA_iCl2-D-FS5mk0jFF6cYSJs_)
|
|
|
|
|
|
- [OOSE: UML と Java を使用したソフトウェア開発 (21 ビデオ)](https://www.youtube.com/playlist?list=PLJ9pm_Rc9HesnkwKlal_buSIHA-jTZMpO)
|
|
|
|
|
|
- [MIT 6.004: 計算構造 (ビデオ 49 件)](https://www.youtube.com/playlist?list=PLDSlqjcPpoL64CJdF0Qee5oWqGS6we_Yu)
|
|
|
|
|
|
- [カーネギー メロン - コンピューター アーキテクチャの講義 (ビデオ 39 件)](https://www.youtube.com/playlist?list=PL5PHm2jkkXmi5CxxI7b3JCL1TWybTDtKq)
|
|
|
|
|
|
- [MIT 6.006: アルゴリズムの紹介 (47 ビデオ)](https://www.youtube.com/watch?v=HtSuA80QTyo&list=PLUl4u3cNGP61Oq3tWYp6V_F-5jb5L2iHb&nohtml5=False)
|
|
|
|
|
|
- [MIT 6.033: コンピューター システム エンジニアリング (22 ビデオ)](https://www.youtube.com/watch?v=zm2VP0kHl1M&list=PL6535748F59DCA484)
|
|
|
|
|
|
- [MIT 6.034 人工知能、2010 年秋 (30 ビデオ)](https://www.youtube.com/playlist?list=PLUl4u3cNGP63gFHB6xb-kVBiQHYe_4hSi)
|
|
|
|
|
|
- [MIT 6.042J: コンピューター サイエンスのための数学、2010 年秋 (25 ビデオ)](https://www.youtube.com/watch?v=L3LMbpZIKhQ&list=PLB7540DEDD482705B)
|
|
|
|
|
|
- [MIT 6.046: アルゴリズムの設計と分析 (ビデオ 34 件)](https://www.youtube.com/watch?v=2P-yW7LQr08&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp)
|
|
|
|
|
|
- [MIT 6.824: 分散システム、2020 年春 (ビデオ 20 本)](https://www.youtube.com/watch?v=cQP8WApzIQQ&list=PLrw6a1wE39_tb2fErI4-WkMbsvGQk9_UB)
|
|
|
|
|
|
- [MIT 6.851: 高度なデータ構造 (22 ビデオ)](https://www.youtube.com/watch?v=T0yzrZL1py0&list=PLUl4u3cNGP61hsJNdULdudlRL493b-XZf&index=1)
|
|
|
|
|
|
- [MIT 6.854: 高度なアルゴリズム、2016 年春 (24 動画eos)](https://www.youtube.com/playlist?list=PL6ogFv-ieghdoGKGg2Bik3Gl1glBTEu8c)
|
|
|
|
|
|
- [Harvard COMPSCI 224: 高度なアルゴリズム (25 ビデオ)](https://www.youtube.com/playlist?list=PL2SOU6wwxB0uP4rJgf5ayhHWgw7akUWSf)
|
|
|
|
|
|
- [MIT 6.858 コンピューター システム セキュリティ、2014 年秋](https://www.youtube.com/watch?v=GqmQg-cszw4&index=1&list=PLUl4u3cNGP62K2DjQLRxDNRi0z2IRWnNh)
|
|
|
|
|
|
- [スタンフォード: プログラミング パラダイム (27 ビデオ)](https://www.youtube.com/playlist?list=PL9D558D49CA734A02)
|
|
|
|
|
|
- [クリストフ・パールによる暗号入門](https://www.youtube.com/playlist?list=PL6N5qY2nvvJE8X75VkXglSrVhLv1tVcfy)
|
|
|
- [スライドと問題セットを含むコース Web サイト](http://www.crypto-textbook.com/)
|
|
|
|
|
|
- [大規模なデータセットのマイニング - スタンフォード大学 (94 ビデオ)](https://www.youtube.com/playlist?list=PLLssT5z_DsK9JDLcT8T62VtzwyW9LNepV)
|
|
|
|
|
|
- [Sarada Herke によるグラフ理論 (67 ビデオ)](https://www.youtube.com/user/DrSaradaHerke/playlists?shelf_id=5&view=50&sort=dd)
|
|
|
|
|
|
## コンピューター サイエンス コース
|
|
|
|
|
|
- [オンライン CS コースのディレクトリ](https://github.com/open-source-society/computer-science)
|
|
|
- [CS コースのディレクトリ (オンライン講義を含む多くのコース)](https://github.com/prakhar1989/awesome-courses)
|
|
|
|
|
|
## アルゴリズムの実装
|
|
|
|
|
|
- [プリンストン大学による複数のアルゴリズムの実装](https://algs4.cs.princeton.edu/code)
|
|
|
|
|
|
## 論文
|
|
|
|
|
|
- [古典的な論文は好きですか?](https://www.cs.cmu.edu/~cry/819-f09/)
|
|
|
- [1978: 逐次プロセスの通信](http://spinroot.com/courses/Summer/Papers/hoare_1978.pdf)
|
|
|
- [Go で実装](https://godoc.org/github.com/thomas11/csp)
|
|
|
- [2003: Google ファイル システム](http://static.googleusercontent.com/media/research.google.com/en//archive/gfs-sosp2003.pdf)
|
|
|
- 2012 年に Colossus に置き換えられました
|
|
|
- [2004: MapReduce: 大規模クラスターでのデータ処理の簡素化](http://static.googleusercontent.com/media/research.google.com/en//archive/mapreduce-osdi04.pdf)
|
|
|
- ほとんどが Cloud Dataflow に置き換えられましたか?
|
|
|
- [2006: Bigtable: 構造化データの分散ストレージ システム](https://static.googleusercontent.com/media/research.google.com/en//archive/bigtable-osdi06.pdf)
|
|
|
- [2006: 疎結合分散システム用の Chubby Lock サービス](https://research.google.com/archive/chubby-osdi06.pdf)
|
|
|
- [2007: Dynamo: Amazon の高可用性 Key-Value ストア](http://s3.amazonaws.com/AllThingsDistributed/sosp/amazon-dynamo-sosp2007.pdf)
|
|
|
- Dynamo の論文が NoSQL 革命のきっかけとなった
|
|
|
- [2007: What Every Programmer Should Know About Memory (非常に長いため、著者は一部のセクションをスキップすることを推奨しています)](https://www.akkadia.org/drepper/cpumemory.pdf)
|
|
|
- 2012: AddressSanitizer: 高速アドレス健全性チェッカー:
|
|
|
- [論文](http://static.googleusercontent.com/media/research.google.com/en//pubs/archive/37752.pdf)
|
|
|
- [ビデオ](https://www.usenix.org/conference/atc12/technical-sessions/presentation/serebryany)
|
|
|
- 2013: Spanner: Google の世界的に分散されたデータベース:
|
|
|
- [論文](http://static.googleusercontent.com/media/research.google.com/en//archive/spanner-osdi2012.pdf)
|
|
|
- [ビデオ](https://www.usenix.org/node/170855)
|
|
|
- [2015: Google の継続的なパイプライン](http://static.googleusercontent.com/media/research.google.com/en//pubs/archive/43790.pdf)
|
|
|
- [2015: 大規模な高可用性: Google の広告用データ インフラストラクチャの構築](https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/44686.pdf)
|
|
|
- [2015: 開発者がコードを検索する方法: ケーススタディ](http://static.googleusercontent.com/media/research.google.com/en//pubs/archive/43835.pdf)
|
|
|
- その他の論文: [1,000 件の論文](https://github.com/0voice/computer_expert_paper)
|
|
|
|
|
|
## ライセンス
|
|
|
|
|
|
[CC-BY-SA-4.0](./LICENSE.txt)
|