README-ja.md 148 KB
コーディング面接の大学
私はもともとこれをソフトウェアエンジニアになるための短いトピックリストとして作成しましたが、 今日それは大きなリストに成長しました。この調査計画を経て、私はAmazonで ソフトウェアエンジニアとして雇われました！！ おそらく、あなたは私ほど勉強する必要はないでしょう。とにかく、必要なものはすべてここにあります。
ここに掲載されている項目を学べば、Amazon、Facebook、Google、Microsoftなど 大手企業を含む、ほぼすべてのソフトウェア会社の面接に備えることができます。
あなたに最高の幸運がありますように!
翻訳：
翻訳中：
これは何？
これは、Webエンジニア(独学で、CS学位なし)から大企業のソフトウェアエンジニアを目指すための私の複数月の学習計画です。
これは、 新人ソフトウェアエンジニア 、またはソフトウェア/ Webエンジニアからソフトウェアエンジニア（CSの知識が必要な場合）に転職する人を対象にしています。 長年のソフトウェアエ開発経験をお持ちの場合は、より面白い面接を期待してください。
あなたに何年ものソフトウェア/Web開発経験がある場合、Google、Amazon、Facebook、Microsoftなどの大規模なソフトウェア会社は、ソフトウェア/Web開発力ではなくソフトウェア工学に関して見ており、そのためにはCSに関する知識が必要となることをご了承ください。
SREまたはシステムエンジニアになりたい場合は、オプションのリスト(ネットワーク、セキュリティ)から詳細を調べてください。
目次
- コーディング面接の大学
- これは何？
- 目次
- なぜこれを使用するのか
- それの使い方
- あなたは十分にスマートではないと感じないでください
- ビデオリソースについて
- 面接のプロセスと一般的な面接の準備
- 面接のための1つの言語を選ぶ
- ブックリスト
- 始める前に
- カバーされていないもの
- 日々の計画
- 前提知識
- アルゴリズムの複雑さ/ Big-O / Asymptotic解析
- データ構造
- その他の知識
- 木
- ソート
- グラフ
- さらに多くの知識
- システム設計、スケーラビリティ、データ処理
- 最終レビュー
- コーディングの質問練習
- コード演習/挑戦
- 面接に近づいたら
- あなたの履歴書
- 面接が来たときに考えてください
- 面接官に質問があります
- 一度あなたは仕事を得た
- その他の書籍
- その他の学習
- 追加科目の詳細
- ビデオシリーズ
- コンピュータサイエンスコース
なぜこれを使用するのか
私はこのプロジェクトを始めたとき、ヒープからスタックを知りませんでしたし、Big-O とは何か、木構造に関すること、グラフをたどる方法を知らなかったのです。 ソートアルゴリズムをコーディングしなければならない場合は、あまりうまくいきませんでした。 これまで使用してきたすべてのデータ構造は言語に組み込まれていて、どのようにしてそれらがどのようにして動作するのか分かりませんでした。 私が実行していたプロセスが "メモリ不足"エラーを出さない限り、メモリを管理する必要はありませんでしたが、回避策を見つけなければなりません。 私は人生で数多くの多次元配列を使用していましたが、何千もの連想配列を使用しましたが、データ構造を一から作成したことはありません。
それは長い計画です。あなたに数ヶ月かかるかもしれません。 すでに多くのことに慣れていれば、それほど時間がかかりません。
それの使い方
下のすべてがアウトラインです。 アイテムを上から下に順番に取り組まなければなりません。
私はGithubの特別なマークダウンフレーバーを使用しています。
新しいブランチを作成して、このような項目をチェックできるようにしてください．xを角かっこに入れてください：[x]
ブランチをフォークし、以下のコマンドに従ってください。
git checkout -b progress
git remote add jwasham https://github.com/jwasham/coding-interview-university
git fetch --all
変更を完了した後にXですべてのボックスにマークを付ける
git add .
git commit -m "マークされたx"
git rebase jwasham/main
git push --force
あなたは十分にスマートではないと感じないでください
- 成功したソフトウェアエンジニアはスマートですが、多くの人はスマートではないという不安があります。
- 天才プログラマーの神話
- 一人で行くのは危険だ：テクノロジーの見えない魔物と戦う
ビデオリソースについて
一部のビデオは、Coursera、EdX、またはLynda.comクラスに登録することによってのみ利用できます。 これらはMOOCと呼ばれています。 時にはクラスがセッションに入っていないので、数ヶ月待つ必要があるため、アクセス権がありません。 Lynda.comコースは有料です。
オンラインコースビデオに付随するYouTubeビデオなど、無料で常時利用可能なパブリックソースを追加することに感謝します。
私は大学の講義を使うのが好きです。
面接のプロセスと一般的な面接の準備
- ABC：常にコーディングする
- Whiteboarding
- プログラミング面接中の効果的なホワイトボード
- 技術職募集での謎解き
- クラッキングコーディング面接セット1：
- Gayle L McDowell - コーディング面接(ビデオ)
- Gayle Laakmann McDowell(ビデオ)とのコーディング面接をクラッキング
- ビッグ4で仕事を得る方法：
- 準備コース：
- Software Engineer Interview Unleashed(有料コース)：
- 以前のGoogle面接官からソフトウェアエンジニアの面接準備をする方法を学びます。
- データ構造、アルゴリズム、面接のためのPython! (有料コース)：
- データ構造、アルゴリズム、模擬面接などを扱うPython中心の面接の準備コース。
- Software Engineer Interview Unleashed(有料コース)：
面接のための1つの言語を選ぶ
面接のコーディングの部分に慣れ親しんだ言語を使用することはできますが、大企業にとってはこれらの選択肢が確実です。
- C ++
- Java
- Python
これらを使用することもできますが、最初に読んでください。注意が必要な場合があります：
- JavaScript
- Ruby
あなたは言語に非常に慣れて知識が必要です。
選択肢についてもっと読む：
- http://www.byte-by-byte.com/choose-the-right-language-for-your-coding-interview/
- http://blog.codingforinterviews.com/best-programming-language-jobs/
私は学習しているので、以下に含まれるC、C ++、Pythonの学習を見ることができます。 いくつかの本があります、下を参照してください。
ブックリスト
これは私が使ったものよりも短いリストです。これは時間を節約するために省略されています。
面接の準備
- プログラミング面接の公開：あなたの次の仕事への秘密、第2版
- C ++とJavaの回答
- コーディング面接をクラッキングするためのウォームアップが良い
- あまりにも難しくない、ほとんどの問題はあなたが面接で（私が読んだことから）見ることよりも簡単かもしれない
- Cracking the Coding Interview、第6版
- 日本語版(世界で闘うプログラミング力を鍛える本)
- Javaでの回答
もし余分な時間があれば：
- プログラミング面接の要素(C ++版)
- プログラミング面接の要素(Java版)
コンピュータアーキテクチャ
短期：
- グレートコードの作成：第1巻：マシンの理解
- 日本語版：Write Great Code〈Vol.1〉ハードウェアを知り、ソフトウェアを書く
- この本は2004年に出版され、幾分古いですが、コンピュータを簡単に理解するには素晴らしいリソースです。
- 作者はHLAを発明したので、塩の穀物でHLAの言及と例を取り上げます。広く使われているわけではありませんが、どのようなアセンブリのように見えますか？
- これらの章はあなたに素敵な基礎を与えるために読む価値があります：
- 第2章 - 数値表現
- 第3章 - 2進算術とビット演算
- 第4章 - 浮動小数点表現
- 第5章 - キャラクター表現
- 第6章 - メモリ構成とアクセス
- 第7章 - 複合データ型とメモリオブジェクト
- 第9章 - CPUアーキテクチャ
- 第10章 - 命令セットのアーキテクチャ
- 第11章 - メモリのアーキテクチャと構成
もっと時間があれば(私はこの本が欲しい)：
- Computer Architecture、第5版：定量的アプローチ
- 日本語最新版：コンピュータアーキテクチャ[第6版]定量的アプローチ
- お金がある人向け、より最新（2017（日本語版は2019））かつ歴史も長い
言語固有
面接の言語を選択する必要があります(上記参照)。 ここで私の推奨する言語です。私はすべての言語のためのリソースがありません。私は追加を歓迎する。
これらのうちの1つを読んだら、コーディングの問題を開始するために必要なすべてのデータ構造とアルゴリズムの知識が必要です。 あなたがレビューをしたくない場合は、このプロジェクトのビデオ講義をすべてスキップすることができます。
C++
私はこれらの2つを読んだことはありませんが、Sedgewickによって高く評価され書かれています。彼は素晴らしいです。
C++の推奨事項がある場合は、私に知らせてください。包括的なリソースを探しています。
Java
OR：
- Javaにおけるデータ構造とアルゴリズム
- Goodrich、Tamassia、Goldwasserによる
- UCバークレーのCSイントロコースのオプションテキストとして使用
- 下のPython版の私の本のレポートを見てください。この本は同じトピックを扱っています。
Python
- Pythonのデータ構造とアルゴリズム
- Goodrich、Tamassia、Goldwasserによる
- 私はこの本が好きだった。それはすべてをカバーしました。
- Pythonコード
- 私の輝く本のレポート：https://startupnextdoor.com/book-report-data-structures-and-algorithms-in-python/
始める前に
このリストは何ヶ月にもわたって成長しました。
ここで私が作ったいくつかの間違いがあります。 あなたはより良い経験をするでしょう。
1.あなたはそれをすべて覚えていない
私は数時間のビデオを見て、豊富なメモを取りました。 そして数ヶ月後に私は覚えていないほどでした。 私はメモを書き、フラッシュカードを作って見直すことができるように3日間過ごしました。
あなたが私と同じ間違いをしないように読んでください：
2.フラッシュカードを使用する
この問題を解決するために、私は2種類のフラッシュカード、一般とコードを追加できる小さなフラッシュカードサイトを作った。 各カードのフォーマットは異なります。
私はモバイル先のウェブサイトを作ったので、どこにいても電話とタブレットを見直すことができました。
あなた自身を無料で作る：
覚えておいてほしいのですが，私はやりすぎてしまい、アセンブリ言語，機械学習のためのPythonのトリビア，統計に至るまですべてのカードをカバーしています。 何が必要なのかはあまりにも大変です。
フラッシュカードについての注意： 最初に答えを知っているときは、それを既知のものとしてマークしないでください。 あなたは本当にそれを知る前に、同じカードを見て、それを正しく数回答えなければなりません。 繰り返すことで、その知識があなたの脳に深く浸透します。
私のフラッシュカードサイトを使用する代わりにAnkiが何度も私に勧められています。 繰り返しシステムを使用して覚えやすくなります。 ユーザーフレンドリーで、すべてのプラットフォームで利用でき、クラウド同期システムを備えています。 iOSでは25ドル、他のプラットフォームでは無料です。
Anki形式の私のフラッシュカードデータベース：https://ankiweb.net/shared/info/25173560(thanks @xiewenya)
3.レビュー、レビュー、評価
私は、ASCII、OSI参照モデル、Big-O記法などのチートシートを用意しています。私は余裕があるときに勉強します。
プログラミングの問題から30分ほど休み、フラッシュカードを通過してください。
4.フォーカス
貴重な時間を費やす可能性のある注意散漫がたくさんあります。集中と集中が難しい。
カバーされていないもの
これらは一般的な技術ですが、この調査計画の一部ではありません：
- SQL
- Javascript
- HTML、CSS、およびその他のフロントエンド技術
日々の計画
一部の科目は1日を要し、いくつかは複数日を要する。 いくつかは、何も実装することなく学習しているだけです。
毎日私は以下のリストから1つのテーマを取り上げ、そのテーマに関するビデオを見て、以下の実装を書いています：
- C - struct*と何か他のものをargsとする構造体と関数を使用する。
- C++ - 組み込み型を使用しない
- C++ - 連結リストのSTLのstd :: listのような組込み型の使用
- Python - 組み込み型を使用する(Pythonの練習を続ける)
- 簡単なassert（）文を使って、時には正しく動作することを保証するテストを書く
- あなたはJavaや他の何かをするかもしれませんが、これは私のことです。
あなたはこれらのすべてを必要としません。面接のために必要な言語は1つだけです。
なぜこれらすべてのコード？
- 私はそれが病気になるまで練習、練習、練習をし、何の問題もありません（忘れてはいけないことがいくつかあります）
- 生の制約内で作業する(ガベージコレクションの助けを借りずにメモリを割り当てる/解放する(Pythonを除く))
- 組み込みの型を利用して、実際の使用のために組み込みのツールを使用した経験を持ちます（本番環境で自分のリンクされたリストの実装を書くつもりはありません）
私はすべてのテーマでこれらのすべてをやる時間がないかもしれませんが、私は試してみます。
あなたは私のコードをここに見ることができます：
あなたはすべてのアルゴリズムの内容を暗記する必要はありません。
コンピューターではなく、ホワイトボードや紙にコードを書く。いくつかのサンプル入力でテストします。次に、コンピュータでテストします。
前提知識
[ ] Cを学ぶ
- Cはどこにでもあります。あなたは勉強している間、書籍、講義、ビデオ、*どこにでも*見ることができます。
- Cプログラミング言語、Vol 2
- これは短い本ですが、それはC言語の優れた処理方法を提供します。 少しでも練習すれば、すばやく習得できます。 Cを理解すると、プログラムやメモリの仕組みを理解するのに役立ちます。
- 質問への回答
[ ] コンピュータがプログラムをどのように処理するか：
アルゴリズムの複雑さ/ Big-O / Asymptotic解析
- 実装するものは何もない
- Harvard CS50 - 漸近表記(video)
- BigO記法(一般的なクイックチュートリアル)(ビデオ)
- BigO表記(とオメガとシータ) - 最良の数学的説明(ビデオ)
- Skiena：
- アルゴリズム複雑さ分析への穏やかな紹介
- 成長の命令(ビデオ)
- 漸近線(Asymptotics)(video)
- UCバークレー BigO(ビデオ)
- UCバークレー Big オメガ(ビデオ)
- 償却分析(ビデオ)
- 「Big Oを描く」(ビデオ)
- TopCoder(漸化関係とマスター定理を含む)：
- チートシート
講義の中には数学的にも余裕がある場合は、下にジャンプして 離散数学ビデオを見て、背景知識を得る。
データ構造
配列
- 自動的にサイズ変更ベクトルを実装する。
- 説明：
- ベクトルを実装する(自動サイズ変更可能な可変配列)：
- 配列とポインタを使用してコーディングを実践し、インデックスを使用する代わりにインデックスにジャンプするポインタ演算
- 割り当てられたメモリを持つ新しい生データ配列
- 内部で配列を割り当てることができますが、その機能は使用しません。
- 16で開始するか、開始番号が大きい場合は、2 - 16,32,64,128の出力を使用します
- size() - 項目数
- capacity() - 保持できるアイテムの数
- is_empty()
- at(index) - 指定されたインデックスでitemを返し、インデックスが範囲外であれば吹き飛ばす
- push(item)
- insert(index,item) - itemをindexに挿入し、そのインデックスの値と末尾の要素を右側にシフトする
- prepend(item) - インデックス0に上記の挿入を使用できます
- pop() - 最後から削除し、値を返す
- delete(index) - インデックスの項目を削除し、すべての末尾の要素を左にシフトする
- remove(item) - 値を探し、それを保持するインデックスを削除します(複数の場所であっても)
- find(item) - valueを検索し、その値を持つ最初のインデックスを返します。見つからなければ-1を返します。
- resize(new_capacity)//プライベート関数
- 容量に達すると、サイズを2倍に変更します
- アイテムをポップするとき、サイズが容量の1/4である場合、サイズを半分に変更
- 時間
- 最後に追加/削除するO(1)(スペースを増やすために償却される)、索引、または更新
- 他の場所に挿入/削除するO(n)
- 空間
- メモリ内で連続しているため、プロキシミティはパフォーマンスに役立ちます
- 必要なスペース=(配列の容量, > = n)*アイテムのサイズですが、2nでもO(n)
連結リスト
- 説明：
- Cコード(動画) ビデオ全体ではなく、ノード構造体とメモリ割り当てに関する部分だけです。
- 連結リスト Vs 配列：
- 連結リスト(ビデオ)を避けるべき理由
- 分かったぞ！：ポインタの知識へのポインタが必要です： (そのポインタが指すアドレスを変更する可能性のある関数へのポインタを渡すとき) このページはptrからptrまでを把握するためのものです。このリストトラバーサルスタイルはお勧めしません。読みやすさと保守性は巧みさのために苦しんでいます。
- 実装する(私はテールポインタ＆なしで行った)：
- 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) - この値を持つリストの最初の項目を削除します。
- 二重連結リスト
- 説明(ビデオ)
- 実装する必要はありません
スタック
- Stacks(video)
- スタックをの使用 Last-In First-Out(ビデオ)
- 実装されません。配列で実装するのは簡単です。
キュー
- キューの使用 First-In First-Out(ビデオ)
- キュー(video)
- 環状バッファ/ FIFO
- 優先度つきキュー(ビデオ)
- テールポインタ付き連結リストを使って実装する：
- enqueue(value) - テールの位置に値を追加する
- dequeue() - 値を返し、少なくとも最近追加された要素を削除する(前面) - empty()
- 固定長配列を使って実装する：
- enqueue(value) - 利用可能なストレージの最後にアイテムを追加する
- dequeue() - 値を返し、最近追加された要素のうち最も古い要素を削除します - empty()
- full()
- コスト：
- 最後の要素の次の要素が必要になるため、先頭にエンキューし、末尾をデキューするリンクリストを使用する悪い実装はO（n）になり、デキューごとに完全なトラバーサルが発生します
- enqueue：O(1)(償却、連結リストと配列[プロービング])
- dequeue：O(1)(連結リストと配列)
- empty：O(1)(連結リストと配列)
ハッシュテーブル
[ ] 動画：
[ ] オンラインコース：
[ ] 線形プロービングを使用して配列で実装する
- hash(k、m) - mはハッシュテーブルのサイズです
- add(key、value) - キーがすでに存在する場合は、値を更新します。
- exists(キー)
- get(key)
- remove(キー)
その他の知識
二分探索
ビット演算
- ビットチートシート- 2 ^ 1から2 ^ 16および2 ^ 32までの2の累乗の多くを知るべきです
- ＆、|、^、〜、>>、<<を使ってビットを操作することについての本当の理解を得る
- 2と1の補数
- カウントセットビット
- 2の次の累乗に丸めます：
- スワップ値：
- 絶対値：
木
木 - メモと背景
- シリーズ：Core Trees(ビデオ)
- シリーズ：木々(ビデオ)
- 基本的な木の構築
- トラバーサル
- 操作アルゴリズム
- BFS(幅優先検索)
- MIT(動画)
- レベルオーダー(BFS、キューを使用) 時間複雑度：O(n) 空間の複雑さ：最適：O(1)、最悪：O(n / 2)= O(n)
- DFS(深さ優先探索)
- MIT(動画) - メモ： 時間複雑度：O(n) 空間の複雑さ： 最良：O(log n) - 平均。木の高さ 最悪：O(n)
- inorder(DFS：left、self、right)
- postorder(DFS：left、right、self)
- preorder(DFS：自己、左、右)
二分探索木：BST
- 二分探索木レビュー(動画)
- シリーズ(ビデオ)
- シンボルテーブルから始まり、BSTアプリケーションを経由します
- はじめに(ビデオ)
- MIT(動画)
- C / C ++：
- 実装：
- insert //木に値を挿入する
- get_node_count //格納された値の数を取得する
- print_values //最小値から最大値まで木の値を出力します
- delete_tree
- is_in_tree //与えられた値が木に存在する場合はtrueを返します
- get_height //ノードの高さを返します(単一ノードの高さは1です)
- get_min //木に格納されている最小値を返します
- get_max //木に格納されている最大値を返します
- is_binary_search_tree
- delete_value
- get_successor //指定された値の後に木の次に高い値を返し、存在しなければ-1を返します
ヒープ/優先度つきキュー/二分ヒープ
- 木として可視化されますが、通常はストレージ内で線形です(配列、連結リスト)
- ヒープ
- はじめに(ビデオ)
- ナイーブな実装(video)
- 二分木(ビデオ)
- 木の高さ備考(ビデオ)
- 基本的な操作(ビデオ)
- 完全な二分木(ビデオ)
- 疑似コード(ビデオ)
- ヒープソート - ジャンプして開始(ビデオ)
- ヒープソート(ビデオ)
- ヒープを作る(ビデオ)
- MIT：ヒープとヒープソート(ビデオ)
- CS 61B講義24：優先度つきキュー(ビデオ)
- 線形時間BuildHeap(max-heap)
- 最大ヒープを実装する：
- insert
- sift_up - 挿入に必要
- get_max - 最大項目を削除せずに返します
- get_size() - 格納された要素の数を返す
- is_empty() - ヒープに要素が含まれていない場合はtrueを返します。
- extract_max - 最大アイテムを返し、それを削除します。
- sift_down - extract_maxに必要です
- remove(i) - インデックスxのアイテムを削除する
- heapify - heap_sortに必要な要素の配列からヒープを作成する
- heap_sort() - ソートされていない配列を取り出し、最大ヒープを使用してソート済みの配列に変換します
- 注意：代わりにminヒープを使用すると、操作が節約されますが、必要な領域が2倍になります(in-placeでは実行できません)。
ソート
[ ] note：
- ソートを実装し、最良のケース/最悪のケース、それぞれの平均的な複雑さを知る：
- バブルソートなし - ひどい - O(n ^ 2)、ただしn <= 16の場合を除く
- ソートアルゴリズムの安定性( "Quicksortは安定していますか？")
- 連結リストで使用できるアルゴリズムはどれですか？どの配列ですか？両方でどちら？
- 連結リストのソートはお勧めしませんが、マージソートは実行可能です。
- 連結リストのマージソート
- ソートを実装し、最良のケース/最悪のケース、それぞれの平均的な複雑さを知る：
ヒープソートについては、上記のヒープデータ構造を参照してください。ヒープソートは素晴らしいですが、安定していません。
[ ] バブルソート(動画)
[ ] バブルソートの分析(動画)
[ ] 挿入ソート、マージソート(動画)
[ ] 挿入ソート(動画)
[ ] マージソート(動画)
[ ] クイックソート(動画)
[ ] 選択ソート(動画)
[ ] マージソートコード：
[ ] クイックソートコード：
[ ] 実装：
- Mergesort：O(n log n)平均と最悪の場合
- Quicksort O(n log n)平均の場合
- 選択ソートと挿入ソートは両方ともO(n ^ 2)の平均と最悪の場合です
- ヒープソートについては、上記のヒープデータ構造を参照してください。
[ ] 必須ではありませんが、私はそれらをお勧めしました：
まとめとして、ここには15ソートアルゴリズムの視覚的表現があります。 このテーマの詳細が必要な場合は、[いくつかの科目の追加の詳細]の[ソート]の項を参照してください(#additional-detail-on-some-subjects)
グラフ
グラフはコンピュータサイエンスの多くの問題を表現するために使用することができるので、このセクションは木やソートのように長いです。
note：
- メモリにグラフを表示するには4つの基本的な方法があります：
- オブジェクトとポインタ
- 隣接行列
- 隣接リスト
- 隣接マップ
- それぞれの表現とその長所と短所を熟知してください
- BFSとDFS - 計算の複雑さとそのトレードオフ、そしてそれらを実際のコードに実装する方法を知っている
- 質問が表示されたら、まずグラフベースのソリューションを探し、それがなければ進んでください。
- メモリにグラフを表示するには4つの基本的な方法があります：
[ ] Skiena Lectures - 素晴らしいイントロ：
[ ] グラフ(レビューなど)：
- 6.006単一始点最短経路問題(ビデオ)
- 6.006 ダイクストラ(ビデオ)
- 6.006 ベルマン-フォード法(ビデオ)
- 6.006 ダイクストラ法のスピードアップ(ビデオ)
- Aduni：グラフアルゴリズムI - トポロジカルソート、最小スパニング木、プリムのアルゴリズム - 講演6(ビデオ)
- Aduni：グラフアルゴリズムII - DFS、BFS、クラスカル法のアルゴリズム、連合探索データ構造 - 講義7(ビデオ)
- Aduni：グラフアルゴリズムIII：最短経路 - レクチャー8(ビデオ)
- Aduni：グラフアルゴリズムIV：幾何学アルゴリズムの紹介 - 第9講(ビデオ)
- CS 61B 2014(58:09から開始)(ビデオ)
- CS 61B 2014：加重グラフ(ビデオ)
- 欲張りアルゴリズム：最小スパニング木(ビデオ)
- 強固に接続されたコサラジュのアルゴリズムグラフアルゴリズム(ビデオ)
フルcourseraコース：
私は実装します：
- 隣接リストを持つDFS(再帰的)
- 隣接リストを持つDFS(スタックで反復)
- 隣接行列を持つDFS(再帰的)
- 隣接行列を持つDFS(スタックで反復)
- 隣接リストを持つBFS
- 隣接行列を持つBFS
- 単一始点の最短経路(ダイクストラ)
- 最小スパニング木
- DFSベースのアルゴリズム(上記のAduniの動画を参照)：
- サイクルをチェックする(トポロジカルソートに必要．開始前にサイクルをチェックする)
- トポロジカルソート
- グラフ内の接続されたコンポーネントをカウントする
- 強く接続されたコンポーネントを一覧表示する
- 二部グラフをチェックする
Skienaの本(下記の書籍の節を参照)と面接の書籍
さらに多くの知識
再帰
- 再帰とバックトラックに関するスタンフォードの講義：
- それを使用するのが適切なとき
- 尾の再帰はどのように優れていないのですか？
動的プログラミング
- この問題はかなり難しいかもしれません。なぜなら、それぞれのDP可溶性問題は再帰関係として定義されなければならず、それを思い付くのは難しいかもしれないからです。
- DPの問題の多くの例を見て、あなたが関連するパターンをしっかりと理解するまでお勧めします。
- 動画：
- Skienaのビデオは、時には見ることができないほど小さすぎるホワイトボードを使用することがあるため、フォローするのが難しい場合があります
- Skiena：CSE373 2012 - 講義19 - 動的プログラミング入門(ビデオ)
- Skiena：CSE373 2012 - 講義20 - 編集距離(ビデオ)
- Skiena：CSE373 2012 - 講義21 - 動的プログラミング例(ビデオ)
- Skiena：CSE373 2012 - 講義22 - 動的プログラミングのアプリケーション(ビデオ)
- Simonson：動的プログラミング0(59:18から開始)(ビデオ)
- Simonson：動的プログラミングI - 講義11(ビデオ)
- Simonson：動的プログラミングII - 講演12(ビデオ)
- 個々のDP問題のリスト(それぞれ短い)： 動的プログラミング(動画)
- イェール講義ノート：
- Coursera：
オブジェクト指向プログラミング
- オプション：UML 2.0シリーズ(動画)
- オブジェクト指向ソフトウェアエンジニアリング：UMLとJavaを使ったソフトウェア開発(21ビデオ)：
- OOとOOの設計方法を十分に理解している場合は、これをスキップできます。
- OOSE：UMLとJavaを使用したソフトウェア開発
- SOLID OOP原則：
- Bob Martin SOLIDオブジェクト指向とアジャイルデザインの原則(ビデオ)
- SOLID原則(ビデオ)
- S - 単一責任の原則| 各オブジェクトへの単一責任
- O - オープン/クローズの原則l| プロダクションレベルではオブジェクトは拡張の準備ができていますが、変更はできません
- L - リスコフの置換原則| 基本クラスと派生クラスは
IS Aプリンシパルに従います - I - インタフェース分離の原則|クライアントは、使用しないインタフェースを強制的に実装するべきではありません
- D - 依存性逆転の原則|オブジェクトの構成における依存関係を減らす。
デザインパターン
- クイックUMLレビュー(ビデオ)
- これらのパターンを学ぶ：
- Strategy(戦略)
- Singleton(単一要素)
- Adapter(アダプタ)
- Prototype(原型)
- Decorator(装飾者)
- Visitor(訪問者)
- Factory,AbstractFactory(工場、抽象工場)
- Facade(外見)
- Observer(観察者)
- Proxy(代理)
- Delegate(委任)
- Command(命令)
- State(状態)
- Memento(記念品)
- Iterator(イテレータ)
- Composite(合成)
- Flyweight(フライ級)
- 第6章(パート1) - パターン(ビデオ)
- 第6章(パート2) - 抽象化 - 発生、一般階層、プレーヤーロール、シングルトン、オブザーバー、代表団(ビデオ)
- 第6章(パート3) - アダプタ、ファサード、変更不可、読み取り専用インターフェイス、プロキシ(ビデオ)
- ビデオシリーズ(27ビデオ)
- ヘッドファーストデザインパターン
- 正式な本は「デザインパターン：再利用可能なオブジェクト指向ソフトウェアの要素」であることは分かっていますが、ヘッドファーストはOOの初心者には最適です。
- 参考：開発者のための101のデザインパターンとヒント
- 人間のデザインパターン
組み合わせ(nCk)と確率
- 数学のスキル：階乗、順列、組み合わせの見つけ方(選択)(ビデオ)
- 学校を作る：確率(ビデオ)
- 学校を作る：確率とマルコフ連鎖(ビデオ)
- Khan Academy：
- コースのレイアウト：
- ちょうどビデオ - 41(それぞれ単純で、それぞれ短いです)：
NP、NP-完全/近似アルゴリズム
- 巡回セールスマン問題やナップザック問題など、NP完全問題の最も有名なクラスについて知りましょう。 そうすれば面接官がこれらについて偽装して尋ねるとき、それらを認識することができます。
- NP完全の意味を知る。
- 計算上の複雑さ(ビデオ)
- Simonson：
- スキナ：
- 複雑さ：P、NP、NP完全性、削減(ビデオ)
- 複雑さ：近似アルゴリズム(ビデオ)
- 複雑さ：固定パラメータアルゴリズム(ビデオ)
- ピーター・ノヴィグ(Peter Norvig)は、セールスマンの問題を解決するための最適なソリューションについて説明しています。
- あなたが持っているなら、CLRSの1048 - 1140ページ。
キャッシュ
プロセスとスレッド
- コンピュータサイエンス162 - オペレーティングシステム(25ビデオ)：
- プロセスとスレッドのためのビデオ表示1-11
- オペレーティングシステムとシステムプログラミング(ビデオ)
- プロセスとスレッドの違いは何ですか？
- カバー：
- プロセス、スレッド、並行性の問題
- プロセスとスレッドの違い
- プロセス
- スレッド
- ロック
- ミューテックス
- セマフォ
- モニタ(同期)
- 彼らの動作の仕方
- デッドロック
- ライブロック
- CPUの動作、割り込み、コンテキストの切り替え
- マルチコアプロセッサを使用した最新の並行構成
- ページング、セグメンテーション、仮想メモリ(動画)
- 割り込み(動画)
- スケジューリング(動画)
- プロセスリソースのニーズ(メモリ：コード、静的ストレージ、スタック、ヒープ、ファイル記述子、I/O)
- スレッドリソースの必要性(同じプロセス内の他のスレッドとの上の(マイナススタック)の共有、それぞれが独自のpc、スタックカウンタ、レジスタ、およびスタックを持つ)
- フォークは、新しいプロセスがメモリに書き込むまで、実際には書き込み時にコピー(読み取り専用)され、次に完全なコピーを行います。
- コンテキストスイッチ
- オペレーティングシステムとその基盤となるハードウェアによってコンテキスト切り替えが開始される仕組み
- プロセス、スレッド、並行性の問題
- C++のスレッド(シリーズ - 10ビデオ)
- Pythonでの並行性(ビデオ)：
- コンピュータサイエンス162 - オペレーティングシステム(25ビデオ)：
論文
- 完全に理解した上ですべてを読むことは、あなたが持っているより多くの時間がかかるでしょう。私は論文とそのセクションを選択することをお勧めします。
- 古典的な論文を愛する？
- 1978：順次プロセスの通信
- 2003：The Googleファイルシステム
- 2012年に巨像に置き換えられました
- 2004：MapReduce：大規模クラスタでのデータ処理の簡略化
- 主にCloud Dataflowに置き換えられましたか？
- 2006：Bigtable：構造化データ用分散ストレージシステム
- 2006：疎結合分散システムのChubby Lockサービス
- 2007：Dynamo：Amazonの高可用性 key valueストア
- Dynamo紙がNoSQL革命を開始
- すべてのプログラマーがメモリについて知っておくべきこと(非常に長く、著者はいくつかのセクションのスキップを奨励する)
- 2010：Dapper、大規模分散システム追跡基盤
- 2010：Dremel：Web-Scaleデータセットのインタラクティブ解析
- 2012：Googleの巨像
- 論文がありません
- 2012：AddressSanitizer：高速アドレス整合性チェッカー：
- 2013：スパナ：Googleのグローバル分散データベース：
- 2014年：機械学習：技術的負債の高利貸しクレジットカード
- 2015：Googleの継続的なパイプライン
- 2015年：大規模な高可用性：Googleの広告用データ基盤の構築
- 2015：TensorFlow：異種分散システムの大規模機械学習
- 2015年：開発者がコードを検索する方法：ケーススタディ
- 2016：Borg、Omega、Kubernetes
テスト
- カバーするために：
- ユニット(単体)テストの仕組み
- モックオブジェクトとは何ですか？
- 統合テストとは
- 依存性注入とは
- James Bachによるアジャイルソフトウェアテスト(ビデオ)
- ジェイムス・バッハによるソフトウェアテストの公開講座(ビデオ)
- Steve Freeman - テスト駆動開発(これは私たちが意味するものではありません)(ビデオ)
- TDDは死んでいます。長いライブテスト。
- TDDは死んでいますか？ (ビデオ)
- ビデオシリーズ(152ビデオ) - すべてではない(ビデオ)
- Pythonでテスト駆動型Web開発
- 依存性注入：
- テストの書き方
- カバーするために：
スケジューリング
- OSで、どのように動作するか
- オペレーティングシステムのビデオから収集できます
システムルーチンを実装する
- 使用するプログラミングAPIの下にあるものを理解する あなたはそれらを実装できますか？
文字列の検索と操作
このテーマについてさらに詳しく知りたい場合は、[いくつかの科目の追加の詳細]の「文字列のマッチング」の項を参照してください(#additional-detail-on-some-subjects)
トライ木
- さまざまなトライ木があることに注意してください。いくつかは接頭辞を持ち、あるものはパスを追跡するビットの代わりに文字列を使用します。
- 私はコードを読んだが、実装しないだろう。
- Sedgewick - 試してみる(3ビデオ)
- データ構造とプログラミング手法に関する注記
- 短期コースビデオ：
- Trie：無視されたデータ構造
- TopCoder - トライ木の使用
- スタンフォード講演(現実世界のユースケース)(ビデオ)
- MIT、高度なデータ構造、文字列(途中でかなり不明瞭になることがあります)
浮動小数点数
Unicode
バイト順(エンディアン)
- ビッグエンディアンとリトルエンディアン
- ビッグエンディアン Vs リトルエンディアン(ビデオ)
- ビッグエンディアンとリトルエンディアンの イン/アウト(ビデオ)
- カーネル開発者のための非常に技術的な話。ほとんどがあなたの頭の上にある場合は心配しないでください。
- 前半で十分です。
ネットワーキング
- ネットワーク経験がある、またはシステムエンジニアになりたい場合は、質問を期待してください
- そうでなければ、これは知っているだけでいいです
- Khan Academy
- UDPとTCP：トランスポートプロトコルの比較
- TCP / IPとOSIモデルの説明!
- インターネット経由のパケット伝送。ネットワーク＆TCP / IPチュートリアル
- HTTP
- SSLとHTTPS
- SSL / TLS
- HTTP 2.0
- ビデオシリーズ(21ビデオ)
- 詳解サブネット化 - 第5部CIDR表記
- ソケット：
システム設計、スケーラビリティ、データ処理
- 4年以上の経験があれば、システム設計の質問を期待できます。
- スケーラビリティとシステム設計は、多くのトピックとリソースを持つ非常に大きなトピックです。 スケーラビリティ(拡張可能)なソフトウェア/ハードウェアシステムを設計する際には、考慮すべき点がたくさんあります。 これにかなりの時間を費やすことを期待してください。
考慮事項：
- スケーラビリティ
- 大きなデータセットを単一の値に変換する
- あるデータセットを別のデータセットに変換する
- 莫大な量のデータを扱う
- システム設計
- 機能セット
- インターフェース
- クラス階層
- 一定の制約の下でシステムを設計する
- シンプルさと丈夫さ
- トレードオフ
- パフォーマンス分析と最適化
- スケーラビリティ
[ ] ここをクリック：システム設計入門
[ ] アルゴリズム設計
[ ] システム設計の面接 - この中には多くのリソースがあります。記事や例を見てください。私はそれらのいくつかを下に置いた。
[ ] システム設計面接の方法
[ ] 誰もが知っておくべき数字
[ ] データセンター間の取引(動画)
[ ] CAP定理の簡単な英語入門
[ ] Paxosアルゴリズム：
[ ] コンシステントハッシュ法
[ ] スケーラビリティ：
- 概要(動画)
- 短いシリーズ：
- スケーラブルなWebアーキテクチャと分散システム
- 分散コンピューティングの説明の誤り
- 実用的なプログラミングテクニック
- Jeff Dean - Googleのソフトウェアシステム構築と教訓(ビデオ)
- スケールのための設計システムの紹介
- App EngineとCloud Datastoreを使用してモバイルゲームを世界中の視聴者に拡大(ビデオ)
- Googleがプラネットスケールのインフラのプラネットスケールエンジニアリングを行う仕組み
- アルゴリズムの重要性
- シャーディング
- Facebook（2009）でスケール
- Facebook(2012年)、「10億ユーザー向けビルド(ビデオ)」
- ロングゲームのためのエンジニアリング - Astrid Atkinson Keynote(ビデオ)
- 7年間のYouTubeスケーラビリティレッスン30分
- ペイパルが毎日何十億ものトランザクションにスケーリングされる方法(8VMだけを使用)
- 大きなデータセットで重複を削除する方法
- Jon CowieによるEtsyのスケールとエンジニアリング文化の中の一見(ビデオ)
- Amazonは独自のマイクロサービスアーキテクチャをどのように導いたか
- 圧縮するか圧縮しないか、それはUberの質問でした
- Tarantoolの非同期キュー、キューに入れる
[ ] スパナ
[ ] 現代のキャッシュのデザイン
[ ] [アーキテクチャ - 40Mビジター、200Mダイナミックページビュー、30TBデータ]()
[ ] サービスを結合する技術の情報については、以下の「メッセージング、シリアライゼーション、およびキューイングシステム」を参照してください。
[ ] Twitter：
さらに詳しくは、ビデオシリーズセクションの「Mining Massive Datasets」ビデオシリーズを参照してください。
[ ] システム設計プロセスの練習：紙で作業しようとするいくつかのアイデアがあります。実際にどのように処理されたかについてのいくつかの文書があります。
- レビュー：システム設計入門
- HiredInTechのシステム設計
- チートシート
- 流れ：
- 問題と範囲を理解する：
- 面接官の助けを借りてユースケースを定義する
- 追加の機能を提案する
- 面接官が範囲外とみなすアイテムを削除する
- 高可用性が必要と仮定し、ユースケースとして追加する
- 制約について考える：
- 毎月のリクエスト数を尋ねる
- 毎秒どれくらいのリクエストをするか(彼らはボランティアでもよいし、あなたに数学をさせるかもしれない)
- 読み込みと書き込みの割合を見積もります
- 推定時に80/20ルールを守って下さい
- 1秒あたりに書き込まれるデータの量
- 5年間に必要な合計ストレージ
- 毎秒読み取られるデータの量
- 抽象的なデザイン：
- レイヤー(サービス、データ、キャッシング)
- インフラストラクチャ：負荷分散、メッセージング
- サービスを駆動する主要なアルゴリズムの概要
- ボトルネックを考慮し、解決策を決定する
- 問題と範囲を理解する：
- 面接官の助けを借りてユースケースを定義する
- 演習：
最終レビュー
このセクションでは、重要な概念のほとんどを見直すためにかなり短いビデオを見ることができます。 あなたが頻繁に再学習をしたいならいいですね。
コーディングの質問練習
上のすべてのコンピュータサイエンスのトピックを知ったので、コーディングの問題に答える練習をしましょう。
コーディング質問の練習は、プログラミング問題への回答を記憶することではありません。
プログラミングの問題を練習する必要がある理由
- 問題の認識、そして適切なデータ構造とアルゴリズムの適合
- 問題のための要件を集める
- 面接であなたのように問題をあなたの方法で話している
- コンピュータではなく、ホワイトボードや紙でのコーディング
- ソリューションの時間と空間の複雑さが増す
- ソリューションのテスト
面接では、体系的でコミュニケーション的な問題解決の素晴らしいイントロがあります。あなたはプログラミングの面接の本からもこれを手に入れるでしょうが、私はこの優れた発見しました： アルゴリズム設計キャンバス
自宅にホワイトボードはありませんか？それは理にかなっている。私は変わった人で、大きなホワイトボードを持っています。ホワイトボードの代わりに、 アートストアから大きなドローイングパッドを拾い上げます。あなたはソファに座って練習することができます。これが私の「ソファホワイトボード」です。 私はスケールの写真にペンを追加しました。ペンを使うと、あなたは消すことができます。すぐに厄介になる。
補足：
プログラミングの問題を読んでやる(この順番で)：
- プログラミング面接公開：あなたが次の仕事に着任する秘訣、第2版
- C、C ++、Javaの回答
- コーディング面接をクラッキング、第6版
- Javaでの回答
上記のブックリストを参照してください
コード演習/挑戦
あなたの脳を学んだら、脳を働かせてください。 できるだけ多く、毎日コーディングの課題に取り組んでください。
コーディング面接質問ビデオ：
チャレンジサイト：
- LeetCode
- TopCoder
- プロジェクトオイラー(Math-focused)
- コードワード
- HackerEarth
- HackerRank
- Codility
- InterviewCake
- Geeks for Geeks
- InterviewBit
- Sphere(Sphere)
チャレンジレポ：
疑似面接：
面接に近づいたら
- クラッキングコーディング面接セット2(ビデオ)：
あなたの履歴書
- クラッキングでの準備項目の再開を参照してください。コーディング面接とプログラミング面接の公開
面接が来たときに考えてください
あなたが得る20の面接の質問と、以下の項目の行を考えてみましょう。 それぞれ2-3の答えがあります。 あなたが達成したことについての物語だけでなく、データを持ってください。
- なぜあなたはこの仕事をしたいです？
- あなたが解決した厳しい問題は何ですか？
- 最大の課題に直面した？
- ベスト/最悪のデザインが見られる？
- 既存の製品を改善するためのアイデア。
- 個人として、そしてチームの一員として、どのようにベストを尽くしていますか？
- あなたのスキルや経験のうち、その役割の資産とその理由は？
- [job x / project y]で一番楽しかったことは何ですか？
- [job x / project y]に直面した最大の課題は何ですか？
- [job x / project y]で直面した最も難しいバグは何でしたか？
- [job x / project y]で何を学びましたか？
- あなたは[job x / project y]で何を良くしていますか？
面接官に質問があります
私の中には(私は既に知っているかもしれませんが、彼らの意見やチームの視点が必要です)：
あなたのチームはどれくらいの規模ですか？
- あなたの開発サイクルはどのように見えるのですか？あなたはウォーターフォール/スプリント/アジャイルをしますか？
- 締め切りまでのフローは共通ですか？それとも柔軟性はありますか？
- あなたのチームではどのように意思決定が行われますか？
- 週に何回会議がありますか？
- あなたの仕事環境が集中するのに役立つと思いますか？
- 何をしているの？
- それについて何が好きですか？
- 仕事の生活はどうですか？
一度あなたは仕事を得た
おめでとう!
学び続けます。
あなたは決して本当に終わらない。
*************************************************** *************************************************** * *************************************************** *************************************************** *
この点以下のものはすべてオプションです。 これらを勉強することで、より多くのCSコンセプトにさらされることになります。 任意のソフトウェアエンジニアリングジョブ。あなたはもっと豊富なソフトウェアエンジニアになるでしょう。
*************************************************** *************************************************** * *************************************************** *************************************************** *
その他の書籍
- Unixプログラミング環境
- 古き良き時代
- Linuxコマンドライン：完全な紹介
- 現代的な選択肢
- TCP / IP Illustrated Series
- ヘッドファーストデザインパターン
- デザインパターンへの穏やかな紹介
- デザインパターン：再利用可能なオブジェクト指向ソフトウェアの要素
- 別名「Gang Of Four」の本、またはGOF
- 正式なデザインパターンの本
- UNIXおよびLinuxシステム管理ハンドブック、第4版
その他の学習
これらの話題は面接では出てこないかもしれませんが、 特定のテクノロジとアルゴリズムを認識するためには、より大きなツールボックスが必要になります。
- アルゴリズム設計マニュアル(Skiena)
-
- レビューと問題認識として
- アルゴリズムのカタログ部分は、面接で得られる難易度の範囲をはるかに超えています。
- この本は2パートに分かれます：
- データ構造とアルゴリズムに関する教科書
- 長所：
- アルゴリズムの教科書はどんなものでも良いレビューです
- 業界および学界の問題を解決した経験から得た素敵な話
- Cのコード例
- 短所：
- Introduction to Algorithms(CLRS)と同様に密集しているか、侵入不可能な場合があります。場合によっては、CLRSが一部の科目にとってより良い選択肢になる可能性があります
- 7章、8章、9章では、いくつかの項目がうまく説明されていないか、私が持っているよりも多くの脳を必要とするため、追跡しようとすると痛いことがあります
- 誤解しないで：私はSkiena、彼の教え方、そしてマナーを好きですが、Stony Brookの教材ではないかもしれません。
- 長所：
- アルゴリズムカタログ：
- これがあなたがこの本を買う本当の理由です。
- この部分に近づきます。一度私がそれを通り抜けたら、ここで更新されます。
- データ構造とアルゴリズムに関する教科書
- Kindleで読むことが出来ます
- Half.comは教科書のための良いリソースです。
- 回答：
- 正誤表
[ ] アルゴリズムイントロダクション
-
- 重要： この本を読む価値は限られています。この本はアルゴリズムとデータ構造の素晴らしいレビューですが、良いコードを書く方法を教えてくれません。まともなソリューションを効率的にコーディングすることができなければなりません。
- Half.comは、良い価格で教科書のための素晴らしいリソースです。
- スタインはゲームに遅れていたので、別名CLR、ときにはCLRSと呼ばれている
-
- プログラミング上の問題（データテープを使っているものもあります）への巧妙な解決策を示していますが、これは単なるイントロです。 これはプログラムの設計とアーキテクチャに関するガイドブックです。 これはプログラムの設計とアーキテクチャに関するガイドブックです。Code Completeとよく似ていますが、はるかに短いものです。
シェンの "アルゴリズムとプログラミング：問題と解決策"- 良い本ですが、いくつかのページで問題を解決した後、私はPascalに悩まされ、whileループ、1つのインデックス付き配列、不確実な事後条件の満足度結果を得ました。
- むしろ別の本やオンラインのコーディングの問題からコーディングの問題に時間を費やすだろう
コンパイラ
Emacsとvi(m)
- UNIXベースのコードエディタに慣れましょう
- vi(m)：
- emacs：
Unixコマンドラインツール
情報理論(ビデオ)
- Khan Academy
- Markovプロセスの詳細：
- 下記のMIT 6.050J Information and Entropyシリーズを参照してください。
パリティ＆ハミングコード(ビデオ)
エントロピー
- 下記の動画もご覧ください
- 最初に情報理論ビデオを見てください
- 情報理論、Claude Shannon、エントロピー、冗長性、データ圧縮およびビット(ビデオ)
暗号化
- 下記の動画もご覧ください
- 最初に情報理論ビデオを見てください
- Khan Academy Series
- 暗号化：ハッシュ関数
- 暗号化：暗号化
圧縮
- 最初に情報理論ビデオを見てください
- Computerphile(ビデオ)：
- Compressor Head videos
- (オプション)Google Developers Live：GZIPでは不十分です!
コンピュータセキュリティ
ガベージコレクション
パラレルプログラミング
メッセージング、シリアライゼーション、およびキューイングシステム
A *
高速フーリエ変換
ブルームフィルター
- mビットとkハッシュ関数を持つBloomフィルタが与えられた場合、挿入とメンバーシップの両方のテストはO(k)
- Bloom Filters
- ブルームフィルター|大規模なデータセットのマイニング|スタンフォード大学
- チュートリアル
- Bloom Filter Appを書く方法
HyperLogLog
局所性に敏感なハッシング
- ドキュメントの類似性を判断するために使用されます。
- 2つの文書/文字列がまったく同じかどうかを判断するために使用されるMD5またはSHAの反対。
- Simhashing(うまくいけば)シンプルに
ヴァンEmde Boasの木
拡張データ構造
バランスの取れた検索木
- 少なくとも1つのタイプの平衡二分木を知っている(そしてそれがどのように実装されているか知っている)：
- "バランスの取れた探索木の中で、AVLと2/3の樹木が通過し、赤黒の木がより人気があるようです。
特に興味深い自己組織化データ構造は、スプレイ木であり、回転を使用します
アクセスされたキーをルートに移動する」 - Skiena
これらのうち、私はスプレイ木を実装することを選択しました。私が読んだことから、あなたは
あなたの面接でバランスの取れた検索木。しかし、私は1つのコーディングへの露出を望んでいた
そしてそれに直面しましょう、スプレーの木はミツバチの膝です。私は赤黒の木のコードをたくさん読んだ。
- スプレイ木：挿入、検索、削除機能 あなたが赤/黒の木の実装を終わらせるならば、これらを試してみてください：
- 検索と挿入機能、削除をスキップする B-Treeについては、非常に大規模なデータセットで非常に広く使用されているため、詳細を知りたい。
[ ] AVL木 - 実際には： 私が言うことから、これらは実際にはあまり使われていませんが、どこになるか分かります。 AVL木は、O(log n)検索、挿入、および削除をサポートする別の構造です。より厳格に 赤黒の木よりもバランスがとれているため、挿入と取り出しが遅くなりますが、検索が速くなります。これにより 一度構築され、再構成なしでロードされる、例えば言語 辞書(または、アセンブラまたはインタプリタのオペコードなどのプログラム辞書)を含む。
[ ] スプレッド木 - 実際には： スプレイ・木は、キャッシュ、メモリ・アロケータ、ルータ、ガベージ・コレクタ、 データ圧縮、ロープ(長いテキスト文字列に使用される文字列の置換)、Windows NT(仮想メモリ、 ネットワークおよびファイルシステムコードなど)
- CS 61B：Splay Trees(video)
- MIT講義：Splay Trees：
- 非常にマッシーになりますが、最後の10分を確かめてください。
- 動画
[ ] レッド/ブラックの木
- これらは2-3木の翻訳です(下記参照) - 実際には： 赤黒の木は、挿入時間、削除時間、および検索時間に対して最悪の場合の保証を提供します。 これは、リアルタイムアプリケーションなどの時間に敏感なアプリケーションでは、これらを貴重なものにするだけでなく、 それは最悪の場合の保証を提供する他のデータ構造における貴重なビルディングブロックになります。 例えば、計算幾何学で使用される多くのデータ構造は赤黒の木に基づくことができ、 現在のLinuxカーネルで使用されている完全に公正なスケジューラは赤黒の木を使用します。 Javaのバージョン8では、 Collection HashMapが変更され、LinkedListを使用して同一の要素を貧弱に保存する代わりに ハッシュコードでは、赤黒の木が使用されます。
- Aduni - アルゴリズム - 講義4(リンク先のジャンプ先)(ビデオ)
- Aduni - アルゴリズム - 講義5(ビデオ)
- 黒い木
- バイナリサーチとレッドブラック木の紹介
[ ] 2-3の検索木
実際には： 2〜3本の木は、検索が遅くなるため(AVL木よりも高さが高いため)、挿入が速くなります。
- 2-3の木は非常にまれにしか使用しませんが、実装にはさまざまなタイプのノードが含まれるためです。代わりに、人々はレッドブラックの木を使用します。
- 23木の直感と定義(ビデオ)
- 23-Treeのバイナリビュー
- 2-3木(学生の暗唱)(ビデオ)
[ ] 2-3-4木(別名2-4木) - 実際には： すべての2-4木には、同じ順序でデータ要素を持つ対応する赤黒の木があります。挿入と削除 2-4木の操作は、赤黒の木の色の反転と回転にも相当します。これは2-4の木を 赤黒の木の背後にある論理を理解するための重要なツールです。そのため、多くの導入アルゴリズムのテキストでは、 2〜4本の木は実用的ではありません**。
[ ] N-ary(K-ary、M-ary)木
- 注記：NまたはKは分岐因子(最大分岐)であり、
- 2分木は2分木であり、分岐因子= 2
- 2-3本の木は3本である
- K-Ary Tree
[ ] B-Tree
- 楽しい事実：それは謎ですが、Bはボーイング、バランスの取れた、またはバイエル(共同発明家)のために立つことができます。 - 実際には： B木はデータベースで広く使用されています。最近のファイルシステムのほとんどは、B-tree(またはVariants)を使用しています。に加えて B木はファイルシステムでも使用され、任意のデータベースへの迅速なランダムアクセスを可能にします 特定のファイル内のブロック基本的な問題は、ファイルブロックのiアドレスをディスクブロックに変換することです (またはおそらくシリンダーヘッドセクターへの)アドレスである。
- B-Tree
- B木(ビデオ)の紹介
- B木の定義と挿入(ビデオ)
- B木削除(動画)
- MIT 6.851 - メモリ階層モデル(ビデオ) - キャッシュに気付かないB木、非常に興味深いデータ構造 - 最初の37分は非常に技術的であり、スキップすることができます(Bはブロックサイズ、キャッシュラインサイズです)
k-D木
- 矩形または高次元のオブジェクトの点数を見つけるのに最適
- k最近接の隣人に適している
- Kd Trees(ビデオ)
- kNN K-d木アルゴリズム(ビデオ)
リストをスキップする
- 「これは多少のカルトデータ構造です」 - Skiena
- ランダム化：リストをスキップ(ビデオ)
- アニメーションともう少し詳しく
ネットワークの流れ
高速処理のための数学
Treap
- 二分探索木とヒープの組み合わせ
- Treap
- データ構造：Treaps説明(動画)
- セット操作のアプリケーション
リニアプログラミング(ビデオ)
幾何学、凸包(ビデオ)
離散数学
- 下のビデオを見る
機械学習
- なぜMLですか？
- Googleのクラウドマシン学習ツール(動画)
- Google Developers `Machine Learning Recipes(Scikit Learn＆Tensorflow)(ビデオ)
- Tensorflow(video)
- Tensorflowチュートリアル
- Pythonでニューラルネットワークを実装する実践ガイド(Theanoを使用)
- コース：
- グレートスターターコース：機械学習 - 動画のみ - 線形代数のレビューについてはビデオ12〜18を参照してください(14と15は重複しています)
- 機械学習のためのニューラルネットワーク
- GoogleのDeep Learning Nanodegree
- Google / Kaggle Machine Learning Engineer Nanodegree
- 自己運転車技術者Nanodegree
- リソース：
-
追加科目の詳細
私は既に上記のいくつかのアイデアを強化するためにこれらを追加しましたが、それらを含めたくありませんでした それはちょうどあまりにも多くのためです。それは科目にそれを過ごすのは簡単です。 あなたは今世紀に雇われたかったですね。
[ ] 連合検索
[ ] もっとダイナミックなプログラミング(ビデオ)
[ ] 高度なグラフ処理(ビデオ)
[ ] MIT 確率(mathy、ゆっくりと進み、数学的なことに良い)(ビデオ)：
[ ] 文字列マッチング
- Rabin-Karp(ビデオ)：
- クヌース・モリス・プラット(KMP)：
- Boyer-Moore文字列検索アルゴリズム
- Coursera：文字列のアルゴリズム
- すごく始まりますが、KMPを過ぎるまでには、必要以上に複雑になります
- 試行の良い説明
- スキップすることができます
[ ] ソート
- スタンフォードのソーティングに関する講義：
- Shai Simonson、Aduni.org：
- Steven Skienaのソーティングに関する講義：
ビデオシリーズ
座って楽しんでください。 「ネットフリックスとスキル」：P
[ ] CSE373 - アルゴリズムの分析(25ビデオ)