私はもともとこれをソフトウェアエンジニアになるための短いトピックリストとして作成しましたが、 今日それは大きなリストに成長しました。この学習計画を経て、私はAmazonで ソフトウェアエンジニアとして雇われました！！ おそらく、あなたは私ほど勉強する必要はないでしょう。とにかく、必要なものはすべてここにあります。 私は数ヶ月間、1日約8〜12時間勉強しました。これが私のストーリーです: Google の面接のために8か月間フルタイムで勉強した理由 注意してください: あなたは私ほど勉強する必要はありません。私は、知る必要のないことに多くの時間を無駄にしました。詳細については、以下をご覧ください。貴重な時間を無駄にすることなく、必要なことを勉強するのを手伝います。 ここに掲載されている項目を学べば、Amazon、Facebook、Google、Microsoftなど 大手企業を含む、ほぼすべてのソフトウェア会社の面接に備えることができます。
あなたに最高の幸運がありますように!
翻訳：
翻訳中：
これは、大企業のソフトウェア エンジニアになるための私の数か月にわたる学習計画です。
必須：
- コーディングの経験 (変数、ループ、メソッド/関数など)
- 忍耐
- 時間
これはソフトウェア エンジニアリングの学習計画であり、フロントエンド エンジニアリングやフルスタック開発ではないことに注意してください。 他の場所でのキャリア パスのスーパー ロードマップとコースワーク (詳細については https://roadmap.sh/ を参照)。
大学のコンピューター サイエンス プログラムでは学ぶべきことがたくさんありますが、面接には 75% 程度知っていれば十分なので、ここではそれについて説明します。 完全な CS 独学プログラムについては、私の学習計画のリソースがカムラン アーメッドのコンピューター サイエンス ロードマップに含まれています: https://roadmap.sh/computer-science
- なぜこれを使用するのか
- 使い方
- 自信を無くさないでください
- ビデオリソースに関する注意
- プログラミング言語を選択してください
- データ構造とアルゴリズムに関する書籍
- 面接対策本
- 私と同じ間違いを犯さないでください
- 取り上げられていないもの
- 日次計画
- コーディングに関する質問の練習
- コーディングの問題
- アルゴリズムの複雑さ / Big-O / 漸近分析
- データ構造
- その他の知識
- ツリー
- ツリーとは
- 二分探索木：BST
- ヒープ/優先度つきキュー/二分ヒープ
- バランスの取れた検索ツリー (詳細ではなく一般的な概念)
- トラバーサル: プレオーダー、インオーダー、 postorder、BFS、DFS
- ソート
- 選択
- 挿入
- ヒープソート
- クイック ソート - マージソート
- グラフ
- 有向
- 無向
- 隣接行列
- 隣接リスト
- 走査: BFS、DFS
- さらに多くの知識
- 最終レビュー
大企業でソフトウェア エンジニアとして働きたいのであれば、これらのことを知っておく必要があります。
私のようにコンピューター サイエンスの学位を取得できなかった場合は、これで人生の 4 年間取り戻すことができます。
このプロジェクトを始めたとき、私はヒープからのスタックのことも、Big-O のことも、木についても、何も知りませんでした。 グラフを横断します。もし私が並べ替えアルゴリズムをコーディングしなければならなかったとしたら、それは酷いことになるでしょう。 私がこれまで使用してきたデータ構造はすべて言語に組み込まれており、それがどのように機能するのかわかりませんでした。 ボンネットの下にはまったくありません。実行しているプロセスで「不足」が発生しない限り、メモリを管理する必要はありませんでした。 「memory」エラーが発生した場合は、回避策を見つける必要があります。私は人生でいくつかの多次元配列を使用しましたが、 何千もの連想配列を作成しましたが、データ構造を最初から作成したことはありません。
長い計画ですね。何か月もかかるかもしれません。しかし、すでにこの内容の多くに精通している場合は、時間ははるかに短くなります。
以下はすべて概要であり、順に項目に取り組む必要があります。
私は進捗状況を追跡するためのタスク リストを含む、GitHub 風マークダウン を使用しています。
このページで、上部近くの「Code」ボタンをクリックし、「Download ZIP」をクリックします。ファイルを解凍すると、テキスト ファイルを操作できるようになります。
マークダウンを理解できるコード エディターで開いている場合は、すべてが適切にフォーマットされていることを確認できます。
新しいブランチを作成して、次のような項目を確認できるようにします。括弧内に x を入力するだけです: [x]
-
GitHub リポジトリ:
https://github.com/jwasham/coding-interview-universityをフォーク ボタンをクリックしてフォークします。 -
ローカル リポジトリにクローンを作成します。
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 # 個人の進捗を元のレポにプッシュバックしないようにするため
-
変更を完了したら、すべてのボックスに X を付けます。
git commit -am "Marked personal progress" git pull upstream main # 元のレポからの変更でフォークを最新に保つ git push # フォークにプッシュするだけ
- 成功した多くのソフトウェア エンジニアは自分が十分に賢くないのではないかという不安を抱えています。
- 次のビデオは、この不安を解消するのに役立ちます。
一部のビデオは、Coursera または EdX クラスに登録することによってのみ視聴できます。 これらは MOOC と呼ばれます。 場合によっては、クラスが開催されていないため、数か月待たなければならず、アクセスできないこともあります。
オンラインコースのリソースを、YouTube ビデオ (できれば大学の講義) など、いつでも利用できる無料の公開ソースに置き換えて、特定のオンラインコースの開催中だけでなく、いつでも学習できるようにするのは素晴らしいことです。
コーディング面接に使用するプログラミング言語を選択する必要がありますが、コンピューターサイエンスの概念を学習するために使用できる言語も見つける必要があります。
できれば、どちらか 1 つの言語に習熟するだけで済むように、言語が同じであることが望ましいです。
学習計画を立てたとき、そのほとんどで C と Python の 2 つの言語を使用しました。
- C: 非常に低いレベル。ポインタとメモリの割り当て / 割り当て解除を処理できるため、データ構造を実感できます。
そしてアルゴリズムが骨の中に組み込まれています。Python や Java などの高水準言語では、これらは表示されません。日々の仕事ではそれは素晴らしいことですが、これらの低レベルのデータ構造がどのように構築されるかを学んでいるときは、実際に近いと感じるのは素晴らしいことです。
- C はどこにでもあります。勉強していると、書籍、講義、ビデオなど、あらゆる場所で例を見ることができます。
- C プログラミング言語 第 2 版
- これは短い本ですが、少し練習すれば C 言語をうまく扱えるようになります。 すぐに上達します。C を理解すると、プログラムとメモリがどのように機能するかを理解するのに役立ちます。
- 本を深く読み込む必要はありません（読み終える必要さえありません）。C で快適に読み書きできるところまで進んでください。
- Python: 現代的で表現力が非常に豊かです。非常に便利で、面接で記述するコードの量も少なくて済むため、私はこれを学びました。
これが私の好みです。もちろん、好きなことをしてください。 必要ないかもしれませんが、新しい言語を学習するためのサイトをいくつか紹介します。
面接のコーディング部分には、使い慣れた言語を使用できますが、大企業の場合は、次の言語を選択するのが確実です。
- C++
- Java
- Python
これらを使用することもできますが、最初に読んでください。注意事項がある場合があります:
- JavaScript
- Ruby
面接の言語の選択について私が書いた記事は次のとおりです: Pick One Language for the Coding Interview.
これは私の投稿の元の記事です: Choosing a Programming Language for Interviews
言語に非常に慣れており、知識が豊富である必要があります。
選択肢について詳しくは、次を参照してください。
- Algorithms in C, Parts 1-5 (Bundle), 3rd Edition
- 基礎、データ構造、並べ替え、検索、およびグラフのアルゴリズム
- Data Structures and Algorithms in Python
- グッドリッチ、タマッシア、ゴールドワッサー著
- この本が大好きでした。それはすべてを網羅し、それ以上のものでした。
- Python コード
- 私の素晴らしい本のレポート: https://startupnextdoor.com/book-report-data-structions-and-algorithms-in-python/
- Goodrich、Tamassia、Goldwasser
- セッジウィックとウェイン:
- Algorithms
- この本をカバーする無料の Coursera コース (著者が教えます!):
- Goodrich、Tamassia、および Mount
- Sedgewick と Wayne
たくさん買う必要はありません。正直なところ、「コーディング面接の攻略」で十分だと思いますが、さらに練習するためにさらに購入しました。しかし、私はいつもやりすぎます。
これを両方購入しました。彼らは私にたくさんの練習をさせてくれました。
- Programming Interviews Exposed: Coding Your Way Through the Interview, 4th Edition
- C++ および Java での回答
- これコーディング面接を突破するための良いウォーミングアップです
- それほど難しいことではありません。ほとんどの問題は、インタビューで見られるものよりも簡単かもしれません (私が読んだ内容によると)
- Cracking the Coding Interview, 6th Edition
- Java での回答
1 つ選択してください:
- Elements of Programming Interviews (C++ version)
- Elements of Programming Interviews in Python
- Elements of Programming Interviews (Java version) - Companion Project - Method Stub and Test Cases for Every Problem in the Book
このリストは何か月もかけて大きくなり、はい、手に負えなくなりました。
より良い経験をしていただくために、私が犯したいくつかの間違いを以下に示します。そして、何か月も時間を節約できます。
時間もビデオを見て大量のメモを取りましたが、数か月後には覚えていないことがたくさんありました。 3日間かけてメモを見直し、フラッシュカードを作成して復習しましたが、そんな知識は必要ありませんでした。
私と同じ間違いを犯さないように、
Retaining Computer Science Knowledge を読んでください。
この問題を解決するために、一般とコードの 2 種類のフラッシュカードを追加できる小さなフラッシュカード サイトを作成しました。 各カードには異なる形式があります。どこにいても携帯電話やタブレットでレビューできるように、モバイルファーストのウェブサイトを作成しました。
無料で独自に作成します。
フラッシュカードの使用はお勧めしません。 フラッシュカードが多すぎて、ほとんどがトリビアです。必要ありません。
しかし、私の言うことを聞きたくない場合は、ここからどうぞ:
やりすぎて、アセンブリ言語や Python のトリビアから機械学習や統計まで、あらゆるものをカバーするカードがあることに注意してください。 必要なものが多すぎます。
フラッシュカードに関する注意: 初めて答えを知っていると気づいたときは、その答えを既知としてマークしないでください。 本当に理解するには、同じカードを見て何度か正しく答える必要があります。 繰り返すことで知識が脳に深く定着します。
私のフラッシュカード サイトを使用する代わりに、Anki が私に何度も勧められてきました。 繰り返しシステムを使用しているので、覚えやすくなります。ユーザーフレンドリーで、すべてのプラットフォームで利用でき、クラウド同期システムを備えています。 iOS では 25 ドルかかりますが、他のプラットフォームでは無料です。
Anki 形式のフラッシュカード データベース: https://ankiweb.net/shared/info/25173560 (thanks @xiewenya).
一部の学生は、空白に関する書式の問題について次の手順を実行することで修正できると述べています。デッキを開いて、カードを編集し、カードをクリックし、「スタイル」ラジオ ボタンを選択して、メンバー「white-space: pre;」を追加します。カードクラスへ。
これは非常に重要です。
データ構造とアルゴリズムを学習しながら、コーディング面接の質問に答え始めます。
問題を解決するには、学んだことを応用する必要があります。そうしないと忘れてしまいます。私はこの間違いを犯しました。
トピックを学習し、リンク リスト などにある程度慣れたら:
- 面接対策本のいずれかを開きます(または、以下にリストされているコーディングに関する問題の Web サイト)
- 次の学習トピックに進みます。
- その後、戻って別の 2 つまたは 3 つのリンク リストの問題を解きます。
- 新しいトピックを学ぶたびにこれを行います。
学習後ではなく、学習している間も問題を解き続けてください。
あなたは知識のために雇われているのではなく、その知識をどのように応用するかによって雇われているのです。
以下に示すように、これに関する多くのリソースがあります。続けて。
気を散らすものがたくさんあり、貴重な時間が奪われてしまう可能性があります。集中力と集中力は難しいです。歌詞のない音楽をかける と、かなり集中できるようになります。
以下は一般的なテクノロジですが、この学習計画には含まれていません:
- Javascript
- HTML、CSS、およびその他のフロントエンドテクノロジ
- SQL
このコースでは多くの主題について説明します。おそらくそれぞれに数日、場合によっては 1 週間以上かかる場合があります。それはあなたのスケジュール次第です。
毎日、リストの次の主題を取り上げ、その主題に関するビデオをいくつか見てから、 このコース用に選択した言語でそのデータ構造またはアルゴリズムの実装を作成します。
私のコードはここで見ることができます:
すべてのアルゴリズムを覚える必要はありません。独自の実装を作成できる程度に理解できれば十分です。
なぜこれがここにあるのでしょうか? 面接する準備ができていません。
プログラミングの問題を練習する必要がある理由:
- 問題の認識、および適切なデータ構造とアルゴリズムがどこに適合するか
- 問題の要件を収集する
- 面接で行うのと同じように、問題について自分なりに説明する
- コンピューターではなく、ホワイトボードまたは紙にコーディングする
- 解決策のための時間と空間の複雑さを考え出す (下記の Big-O を参照)
- テストあなたの解決策
面接で体系的かつコミュニケーション的に問題を解決するための素晴らしい入門書があります。これはプログラミングのインタビュー本からもわかります が、私はこれが素晴らしいと思いました: Algorithm design canvas
コードを紙ではなく、ホワイトボードまたは紙に書きます。コンピューター。いくつかのサンプル入力を使用してテストします。次に、それを入力してコンピュータでテストします。
家にホワイトボードがない場合は、画材店で大きな描画パッドを購入してください。ソファに座って練習することもできます。 こちらは私の「ソファホワイトボード」です。写真ではスケールを調整するためにペンを追加しました。ペンを使っていると、消せたらいいのにと思うでしょう。 すぐに散らかります。鉛筆と消しゴムを使用します。
コーディングの問題の練習は、プログラミングの問題の答えを覚えることではありません。
ここ の主要なコーディング インタビュー ブックを忘れないでください。
問題の解決:
コーディング インタビューの質問ビデオ:
- IDeserve (88 videos)
- Tushar Roy (5 playlists)
- 問題解決策のウォークスルーに最適
- Nick White - LeetCode Solutions (187 Videos)
- ソリューションとコードの適切な説明
- 短時間で何本も視聴できる
- FisherCoder - LeetCode Solutions
チャレンジ/練習サイト:
- LeetCode
- 私のお気に入りのコーディングの問題サイト。おそらく準備する 1 ～ 2 か月分の購読料を払う価値があります。
- コードのウォークスルーについては、上記の Nick White と FisherCoder のビデオを参照してください。
- HackerRank
- TopCoder
- Codeforces
- Codility
- Geeks for Geeks
- AlgoExpert
- Google のエンジニアによって作成されたこれは、スキルを磨くための優れたリソースでもあります。
- Project Euler
- 非常に数学に重点が置かれており、コーディング面接にはあまり適していません
さて、話は十分です、学びましょう！
ただし、学習中に上記のコーディング問題に取り組むことを忘れないでください。
- ここでは何も実装する必要はありません。ビデオを見てメモを取るだけです。わーい！
- ここにはたくさんのビデオがあります。理解できるまで十分に見てください。いつでも戻ってレビューすることができます。
- 背後にある数学がすべて理解できなくても心配する必要はありません。
- Big-O の観点からアルゴリズムの複雑さを表現する方法を理解する必要があるだけです。
- ハーバード CS50 - 漸近記法 (動画)
- Big O Notations (一般的なクイック チュートリアル) (動画)
- Big O Notation (およびオメガとシータ) - 最良の数学的説明 (動画)
- スキエナ
- カリフォルニア大学バークレー校ビッグオー (動画)
- 償却分析 (動画)
- TopCoder (漸化式とマスター定理を含む):
- チートシート
- [Review] Analyzing Algorithms (playlist) in 18 minutes (video)
まあ、それだけで十分です。
「コーディング インタビューの解読」を進めると、これに関する章があり、最後に、さまざまなアルゴリズムの実行時の複雑さを特定できるかどうかを確認するクイズがあります。それはスーパーレビューとテストです。
-
- 配列について:
- アレイ CS50 ハーバード大学
- 配列 (動画)
- UC Berkeley CS61B - Linear and Multi-Dim Arrays (動画) (15 分 32 秒から視聴開始) (Start watching from 15m 32s)
- 動的配列 (動画)
- ギザギザ配列 (動画)
- アレイ CS50 ハーバード大学
- ベクトルを実装します (自動サイズ変更を備えた可変配列):
- 配列とポインターを使用したコーディングと、インデックスを使用する代わりにインデックスにジャンプするポインターの計算を練習します。
- メモリが割り当てられた新しい生データ配列
- 内部で 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)
- 配列について:
-
- 説明：
- Cコード(動画)
- ビデオ全体ではなく、ノード構造とメモリ割り当てに関する部分のみ
- 連結リストと配列：
- 連結リスト(動画)を避けるべき理由
- 注意事項: ポインタからポインタへの知識が必要です: (ポインタが指すアドレスを変更する可能性のある関数にポインタを渡すときのため) このページは、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) - この値を持つリストの最初の項目を削除します。
- 二重連結リスト
- 説明(動画)
- 実装する必要はありません
-
- スタック (動画)
- 【復讐】3分でわかるスタック（動画）
- 実装しません。配列を使った実装は簡単です
-
- キュー(動画)
- 環状バッファ/ FIFO
- 【復習】3分でわかるキュー（動画）
- テールポインタ付き連結リストを使って実装する：
- enqueue(value) - テールの位置に値を追加する
- dequeue() - 値を返し、少なくとも最近追加された要素を削除する(前面)
- empty()
- 固定長配列を使って実装する：
- enqueue(value) - 利用可能なストレージの最後にアイテムを追加する
- dequeue() - 値を返し、最近追加された要素のうち最も古い要素を削除します
- empty()
- full()
- コスト：
- 先頭でエンキューし、末尾でデキューするリンク リストを使用した悪い実装では、最後から 2 番目の要素が必要になるため、O(n) となり、各デキューの完全な走査が発生します。
- enqueue：O(1)(償却、連結リストと配列[プロービング])
- dequeue：O(1)(連結リストと配列)
- empty：O(1)(連結リストと配列)
-
-
動画：
-
オンラインコース：
-
線形プロービングを使用して配列で実装する
- hash(k、m) - mはハッシュテーブルのサイズです
- add(key、value) - キーがすでに存在する場合は、値を更新します。
- exists(キー)
- get(key)
- remove(キー)
-
-
- 二分探索(動画)
- 二分探索(動画)
- 詳細
- ブループリント
- 【復習】4分でわかる二分探索（動画）
- 実装：
- 二分探索(ソートされた整数の配列)
- 再帰を利用した二分探索
-
- ビットチートシート
- (2^1 から 2^16 および 2^32) までの 2 のべき乗の多くを知っておく必要があります
- ＆、|、^、〜、>>、<<を使ってビットを操作することについての本当の理解を得る
- 2と1の補数
- カウントセットビット
- カウントセットビット:
- スワップ値：
- 絶対値：
- ビットチートシート
-
- ツリーの紹介 (動画)
- ツリートラバーサル (動画)
- BFS (幅優先検索) および DFS (深さ優先検索) (動画)
- 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: 自分、左、右)
- BFS のメモ:
- 【復習】4分でわかる幅優先検索（動画）
- 【復習】4分で深さ優先検索（動画）
- 【復習】11 分でわかるツリー トラバーサル (プレイリスト) (動画)
-
- 二分探索木の復習 (動画)
- はじめに（動画）
- 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を返します
-
- 木として可視化されますが、通常はストレージ内で線形です(配列、連結リスト)
- ヒープ
- はじめに(動画)
- ナイーブな実装(動画)
- 二分木(動画)
- 木の高さ備考(動画)
- 基本的な操作(動画)
- 完全な二分木(動画)
- 疑似コード(動画)
- ヒープソート - ジャンプして開始(動画)
- ヒープソート(動画)
- ヒープを作る(動画)
- MIT：ヒープとヒープソート(動画)
- CS 61B講義24：優先度つきキュー(動画)
- 線形時間ビルドヒープ (最大ヒープ)
- 【復習】13分でヒープ（プレイリスト）（動画）
- 最大ヒープを実装する：
- 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は安定していますか？")
- 連結リストで使用できるアルゴリズムはどれですか？どの配列ですか？両方でどちら？
- 連結リストのソートはお勧めしませんが、マージソートは実行可能です。
- 連結リストのマージソート
- ソートを実装し、最良のケース/最悪のケース、それぞれの平均的な複雑さを知る：
-
ヒープソートについては、上記のヒープデータ構造を参照してください。ヒープソートは素晴らしいですが、安定していません。
-
カリフォルニア大学バークレー校:
-
ソート コードを結合:
-
クイックソートコード:
-
実装
- マージソート: O(n log n) 平均および最悪の場合
- クイックソート O(n log n) の平均ケース
- 選択ソートと挿入ソートは両方とも O(n^2) 平均および最悪の場合です
- ヒープソートについては、上記のヒープ データ構造を参照してください。
-
必須ではありませんが、お勧めします:
概要として、15のソートアルゴリズム を視覚的に表したものを次に示します。 この主題についてさらに詳細が必要な場合は、一部の主題に関する追加の詳細 の「並べ替え」セクションを参照してください。
グラフはコンピューター サイエンスの多くの問題を表すために使用できるため、このセクションはツリーや並べ替えと同様に長くなります。
-
ノート：
- メモリ内でグラフを表現するには 4 つの基本的な方法があります。
- オブジェクトとポインタ
- 隣接行列
- 隣接リスト
- 隣接マップ
- それぞれの表現とその長所と短所をよく理解する
- BFS と DFS - 計算の複雑さ、トレードオフ、および実際のコードでの実装方法を理解しています。
- 質問されたら、まずグラフベースの解決策を探し、見つからない場合は次に進みます。
- メモリ内でグラフを表現するには 4 つの基本的な方法があります。
-
MIT(ビデオ):
-
スキエナ講義 - 素晴らしい導入部:
-
グラフ (レビューなど):
- 6.006 単一ソース最短パス問題 (動画)
- 6.006 ダイクストラ (動画)
- 6.006 ベルマン-フォード (動画)
- 6.006 ディクストラの高速化 (動画)
- Aduni: グラフ アルゴリズム I - トポロジカル ソート、最小スパニング ツリー、プリムのアルゴリズム - 講義 6 (動画)
- Aduni: グラフ アルゴリズム II - DFS、BFS、クラスカルのアルゴリズム、Union Find データ構造 - 講義 7 (動画)
- Aduni: グラフ アルゴリズム III: 最短パス - レクチャー 8 (動画)
- Aduni: グラフ Alg. IV: 幾何学的アルゴリズムの概要 - レクチャー 9 (動画)
- CS 61B 2014: 加重グラフ (動画)
- 貪欲なアルゴリズム: 最小スパニング ツリー (動画)
- 強結合コンポーネント コサラジュのアルゴリズム グラフ アルゴリズム (動画)
- [復習] 16 分でわかる最短経路アルゴリズム (プレイリスト) (動画)
- [復習] 4 分でわかる最小スパニング ツリー (プレイリスト) (動画)
-
フルcourseraコース：
-
次のことを実装します。
- 隣接リストを含む DFS (再帰的)
- 隣接リストを使用した DFS (スタックによる反復)
- 隣接行列を使用した DFS (再帰的)
- 隣接行列を使用した DFS (スタックによる反復)
- 隣接リストを含む BFS
- 隣接マトリックスを使用した BFS
- 単一ソースの最短パス (ダイクストラ)
- 最小スパニングツリー
- DFSベースのアルゴリズム(上記のAduniの動画を参照)：
- サイクルをチェックする(トポロジカルソートに必要．開始前にサイクルをチェックする)
- トポロジカルソート
- グラフ内の接続されたコンポーネントをカウントする
- 強く接続されたコンポーネントを一覧表示する
- 二部グラフをチェックする
-
- 再帰とバックトラッキングに関するスタンフォードの講義:
- いつ使用するのが適切ですか?
- 末尾再帰をしない場合と比べて、どのような点が優れているのでしょうか?
- 再帰的問題を解決するための 5 つの簡単なステップ (動画) バックトラッキング ブループリント: Java Python
-
- おそらく面接では動的プログラミングの問題は見られないでしょうが、問題を認識できるようにしておくことは価値があります。 動的計画法の候補としての問題。
- それぞれの DP 解決問題は再帰関係として定義する必要があり、それを思いつくのは難しい場合があるため、このテーマはかなり難しい場合があります。
- 関連するパターンをしっかりと理解するまで、DP 問題の多くの例を検討することをお勧めします。
- 動画：
- Skiena: CSE373 2020 - レクチャー 19 - 動的プログラミング入門 (動画)
- Skiena: CSE373 2020 - レクチャー 20 - 距離の編集 (動画)
- Skiena: CSE373 2020 - レクチャー 20 - 距離の編集 (続き) (動画)
- Skiena: CSE373 2020 - レクチャー 21 - 動的プログラミング (動画)
- Skiena: CSE373 2020 - レクチャー 22 - 動的プログラミングとレビュー (動画)
- Simonson: 動的プログラミング 0 (59:18 から開始) (動画)
- Simonson: 動的プログラミング I - 講義 11 (動画)
- サイモンソン: 動的プログラミング II - 講義 12 (動画)
- 個々の DP 問題のリスト (それぞれ短い): ダイナミック プログラミング (動画)
- イェール講義ノート：
- Coursera：
- DPと再帰的実装(動画)
-
- UMLの簡単なレビュー(動画)
- これらのパターンを学ぶ：
- Strategy(戦略)
- Singleton(単一要素)
- Adapter(アダプタ)
- Prototype(原型)
- Decorator(装飾者)
- Visitor(訪問者)
- Factory,AbstractFactory(工場、抽象工場)
- Facade(外見)
- Observer(観察者)
- Proxy(代理)
- Delegate(委任)
- Command(命令)
- State(状態)
- Memento(記念品)
- Iterator(イテレータ)
- Composite(合成)
- Flyweight(フライ級)
- 一連の動画 (27 本)
- 書籍: Head First Design Patterns
- 正規の本は「デザインパターン: 再利用可能なオブジェクト指向ソフトウェアの要素」であることは知っていますが、「Head First」は OO の初心者に最適です。
- 便利なリファレンス: 開発者のための 101 のデザインパターンとヒント
-
- 数学スキル: 階乗、順列、組み合わせの求め方 (選択) (動画)
- Make School: 確率 (動画)
- Make School: さらなる確率とマルコフ連鎖 (動画)
- カーンアカデミー:
- コースレイアウト:
- ビデオのみ - 41 (それぞれがシンプルで短い):
-
- 巡回セールスマンやナップザック問題など、NP 完全問題の最も有名なクラスについて知っています。 インタビュアーが変装して質問したときに、それを見分けることができます。
- NP 完全の意味を理解する。
- 計算の複雑さ (動画)
- サイモンソン:
- [ ]スキエナ:
- 複雑さ: P、NP、NP 完全性、削減 (動画)
- 複雑さ: 近似アルゴリズム (ビ動画デオ)
- 複雑さ: 固定パラメーター アルゴリズム (動画)
- Peter Norvig は、巡回セールスマンの問題に対する最適に近い解決策について説明します。
- CLRS のページ 1048 ～ 1140 (お持ちの場合)。
-
- コンピュータサイエンス162 - オペレーティングシステム(25ビデオ)：
- プロセスとスレッドのためのビデオ表示1-11
- オペレーティングシステムとシステムプログラミング(動画)
- プロセスとスレッドの違いは何ですか？
- カバー：
- プロセス、スレッド、並行性の問題
- プロセスとスレッドの違い
- プロセス
- スレッド
- ロック
- ミューテックス
- セマフォ
- モニタ(同期)
- 動作の仕方
- デッドロック
- ライブロック
- CPU アクティビティ、割り込み、コンテキスト切り替え
- マルチコアプロセッサを使用した最新の同時実行構造
- ページング、セグメンテーション、仮想メモリ (動画)
- 中断（動画）
- プロセス リソースのニーズ (メモリ: コード、静的ストレージ、スタック、ヒープ、およびファイル記述子、I/O)
- スレッド リソースのニーズ (同じプロセス内の他のスレッドと上記 (マイナススタック) を共有しますが、それぞれに独自の PC、スタック カウンター、レジスタ、およびスタックがあります)
- フォークは実際には、新しいプロセスがメモリに書き込むまではコピーオンライト (読み取り専用) であり、その後完全コピーが実行されます。
- コンテキストの切り替え
- プロセス、スレッド、並行性の問題
- C++ のスレッド (シリーズ - 10 本の動画)
- CS 377 Spring '14: マサチューセッツ大学のオペレーティングシステム
- Python の同時実行性 (動画):
- コンピュータサイエンス162 - オペレーティングシステム(25ビデオ)：
-
- カバーするために：
- 単体テストの仕組み
- モックオブジェクトとは何ですか
- 統合テストとは何ですか
- 依存性注入とは何ですか
- James Bach によるアジャイル ソフトウェア テスト (動画)
- ソフトウェア テストに関する James Bach による公開講義 (動画)
- Steve Freeman - テスト駆動開発 (それは私たちが言いたかったことではありません) (動画)
- 依存性の注入:
- テストの書き方
- カバーするために：
-
この件についてさらに詳細が必要な場合は、一部の件名に関する追加の詳細 の「文字列マッチング」セクションを参照してください。
-
- さまざまな種類のトライがあることに注意してください。プレフィックスを持つものと持たないもの、そしてビットの代わりに文字列を使用してパスを追跡するものもあります
- コードは一通り読みましたが、実装はしません
- Sedgewick - Trys (3動画)
- データ構造とプログラミング技術に関するメモ
- ショートコースビデオ:
- トライ: 無視されたデータ構造
- TopCoder - トライの使用
- スタンフォード講義 (実際の使用例) (動画)
- MIT、高度なデータ構造、文字列 (途中でかなりわかりにくくなる可能性があります) ) (動画)
- さまざまな種類のトライがあることに注意してください。プレフィックスを持つものと持たないもの、そしてビットの代わりに文字列を使用してパスを追跡するものもあります
-
- ビッグ エンディアンとリトル エンディアン
- ビッグ エンディアンとリトル エンディアン (動画)
- Big And Little Endian Inside/Out (動画)
- カーネル開発者向けの非常に技術的な話。ほとんどのことが頭から離れていても心配する必要はありません。
- 前半だけで十分です。
-
- ネットワーキングの経験がある場合、または信頼性エンジニアまたは運用エンジニアになりたい場合は、質問をお待ちください - それ以外の場合、これは知っておくと良いでしょう
- カーン アカデミー
- UDP と TCP: トランスポート プロトコルの比較 (動画)
- TCP/IP と OSI モデルについて説明します! (動画)
- インターネットを介したパケット送信。ネットワークと TCP/IP のチュートリアル。(動画)
- HTTP (動画)
- SSL および HTTPS (動画)
- SSL/TLS (動画)
- HTTP 2.0 (動画)
- ビデオ シリーズ (21 動画) (動画)
- サブネットの謎を解く - パート 5 CIDR表記法 (動画)
- ソケット:
このセクションには短いビデオが含まれます。非常にすぐに見て、重要な概念のほとんどを確認できます。
頻繁にリフレッシュしたい場合に便利です。
- 2 ～ 3 分の短い主題ビデオ シリーズ (23 動画)
- 2 ～ 5 分のシリーズ短い主題のビデオ - Michael Sambol (動画 48 件):
- セッジウィック ビデオ - アルゴリズム I
- セッジウィック ビデオ - アルゴリズム II
- 書籍の履歴書準備情報を参照してください: 『コーディング面接の攻略』 「番組インタビュー暴露」
- 「良い履歴書はこうあるべきだ」 Gayle McDowell (『Cracking thecoding Interview』の著者) 著、
- 著者による注: 「これは米国に焦点を当てた履歴書用です。インドと他の国の履歴書では、多くの点は同じですが、期待される内容は異なります。」
- 「ステップバイステップの履歴書ガイド」 by Tech Interview Handbook
- 履歴書を最初から設定し、効果的な履歴書の内容を作成し、最適化し、履歴書をテストする方法に関する詳細なガイド
- 2021 年のエンジニアリング面接に合格する方法
- テクノロジー採用の謎を解く
- ビッグ 4 に就職する方法:
- コーディング インタビュー セット 1 を解読:
- Facebook コーディングのインタビューを解読:
- 準備コース:
- データ構造、アルゴリズム、インタビューのための Python (有料コース):
- データ構造、アルゴリズム、模擬面接などをカバーする Python 中心の面接準備コース。
- Python を使用したデータ構造とアルゴリズムの紹介 (Udacity 無料コース):
- Python 中心のデータ構造とアルゴリズムの無料コース。
- 【データ構造とアルゴリズムをナノレベルで解説！ (Udacity 有料 Nanodegree):
- 100 を超えるデータ構造とアルゴリズムの演習と、面接や実務シナリオの準備に役立つ専任のメンターからのガイダンスによる実践的な練習を行います。
- 行動面接のグロッキング (無料教育コース):
- 多くの場合、夢の仕事に就くのを妨げているのは技術的能力ではなく、行動面接での成績です。
- AlgoMonster (無料コンテンツ付きの有料コース):
- LeetCode の短期集中コース。数千の質問から凝縮されたすべてのパターンを網羅。
- データ構造、アルゴリズム、インタビューのための Python (有料コース):
模擬面接:
- Gainlo.co: 大企業の面接官を模擬 - これを使用したところ、電話での画面やオンサイトの面接に向けてリラックスするのに役立ちました
- Pramp: ピアとの模擬面接 - 面接を練習するためのピアツーピア モデル
- interviewing.io: 上級エンジニアとの模擬面接の練習 - FAANG の上級エンジニアとのアルゴリズム/システム設計匿名インタビュー
- Meetapro: FAANG トップ面接官との模擬面接 - Airbnb スタイルの模擬面接/コーチング プラットフォーム。
- Hello Interview: Expert Coaches and AI との模擬面接 - AI または FAANG スタッフのエンジニアやマネージャーと直接面接します。
面接で聞かれる約 20 の質問と、以下の項目の内容を考えてください。それぞれに対して少なくとも 1 つの回答を用意してください。 達成したことについて、単なるデータではなくストーリーを作成します。
- なぜあなたはこの仕事をしたいです？
- あなたが解決した難しい問題は何ですか?
- 直面した最大の課題は何ですか?
- 見た中で最高/最悪のデザインは何ですか?
- 既存の製品を改善するためのアイデア
- 個人としても、チームの一員としても、どのようにすれば最も効果的に働くことができますか?
- あなたのスキルや経験のうち、その役割において資産となるものはどれですか、またその理由は何ですか?
- [ジョブ x / プロジェクト y] で一番楽しかったことは何ですか?
- [ジョブ x / プロジェクト y] で直面した最大の課題は何ですか?
- [ジョブ x / プロジェクト y] で直面した最も困難なバグは何ですか?
- [ジョブ x / プロジェクト y] で何を学びましたか?
- [ジョブ x / プロジェクト y] でもっと良くできたことは何ですか?
私の意見の一部 (答えはすでに知っているかもしれませんが、彼らの意見やチームの視点が欲しいです):
- チームの規模はどれくらいですか?
- 開発サイクルはどのような感じですか?ウォーターフォール/スプリント/アジャイルをやっていますか?
- 締め切りに追われるのはよくあることですか?それとも柔軟性があるのでしょうか？
- チーム内での意思決定はどのように行われますか?
- 週に何回会議がありますか?
- 職場環境は集中力を高めますか？ -何に取り組んでいますか？
- 何が気に入っていますか？
- 仕事生活はどのような感じですか？
- ワークライフバランスはどうですか？
おめでとう！
学び続けます。
本当に終わったことはありません。
************************************************* ************************************************* *
************************************************* ************************************************* *
これより下はすべてオプションです。初心者レベルの面接には必要ありません。
ただし、これらを学習することで、より多くの CS 概念に詳しくなり、より適切な準備が整います。
ソフトウェアエンジニアリングの仕事なら何でも。あなたは、より総合的なソフトウェア エンジニアになるでしょう。
************************************************* ************************************************* *
************************************************* ************************************************* *
これらは、興味のあるトピックに飛び込むことができるようにここにあります。
- Unix プログラミング環境
- 懐かしいけどおいしい
- Linux コマンドライン: 完全な紹介
- 現代的なオプション
- TCP/IP 図解シリーズ
- ヘッドファーストデザインパターン
- デザインパターンへの優しい入門書
- デザインパターン: 再利用可能なオブジェクト指向ソフトウェアの要素
- 別名「ギャング・オブ・フォー」本またはGOF
- 正規のデザインパターンブック
- アルゴリズム設計マニュアル (Skiena)
- 振り返りと問題認識として
- アルゴリズム カタログの部分は、面接で得られる難易度の範囲をはるかに超えています。
- この本は 2 つの部分から構成されています。
- データ構造とアルゴリズムに関する授業用教科書
- 長所:
- アルゴリズムの教科書と同様に、良いレビューです
- 産業界や学界の問題を解決した彼の経験からの素敵な話
- C でのコード例
- 短所:
- CLRS と同じくらい高密度または透過不可能である可能性があり、場合によっては、一部の被験者にとっては CLRS の方が優れた代替手段になる可能性があります。
- 第 7 章、第 8 章、および第 9 章は、いくつかの項目が十分に説明されていなかったり、私よりも多くの頭を必要としたりするため、理解しようとすると苦痛になる可能性があります。
- 誤解しないでください。私はスキエナと彼の教え方、マナーが好きですが、ストーニー ブルックの材料ではないかもしれません。
- 長所:
- アルゴリズムカタログ:
- これがこの本を購入する本当の理由です。
- この本はアルゴリズムのリファレンスとして優れており、最初から最後まで読むものではありません。
- データ構造とアルゴリズムに関する授業用教科書
- Kindleでレンタルできる
- 答え:
- 正誤表
- アルゴリズム (ジェフ エリクソン)
- 素晴らしいコードを書く: 第 1 巻: マシンを理解する
- この本は 2004 年に出版されており、やや古いですが、コンピュータを簡単に理解するのに最適なリソースです。
- 著者は HLA を発明したものであるため、HLA での言及と例については、話半分に聞いてください。広く使用されていませんが、アセンブリがどのようなものかを示す適切な例
- これらの章は、優れた基礎を築くために読む価値があります。
- 第 2 章 - 数値表現
- 第 3 章 - 2 進数演算とビット演算
- 第 4 章 - 浮動小数点表現
- 第 5 章 - キャラクター表現
- 第 6 章 - メモリの構成とアクセス
- 第 7 章 - 複合データ型とメモリ オブジェクト
- 第 9 章 - CPU アーキテクチャ
- 第 10 章 - 命令セットのアーキテクチャ
- 第 11 章 - メモリのアーキテクチャと構成
- アルゴリズム入門
- 重要: この本を読む価値は限られています。この本はアルゴリズムとデータ構造についての優れたレビューですが、優れたコードの書き方については教えてくれません。適切なソリューションを効率的にコーディングできなければなりません
- スタインがゲームに遅刻したため、別名 CLR、場合によっては CLRS
- コンピュータ アーキテクチャ、第 6 版: 定量的アプローチ
- より充実した、より最新の (2017) が、より長い治療期間を必要とする場合
4 年以上の経験がある場合は、システム設計に関する質問が予想されます。
- スケーラビリティとシステム設計は、多くのトピックとリソースを含む非常に大きなトピックです。 拡張可能なソフトウェア/ハードウェア システムを設計する際には、考慮すべきことがたくさんあります。 これにはかなりの時間を費やすことが予想されます
- 考慮事項:
- スケーラビリティ
- 大きなデータセットを単一の値に抽出します
- あるデータセットを別のデータセットに変換する
- 異常に大量のデータを扱うこと
- システムデザイン
- 機能セット
- インターフェース
- クラス階層
- 特定の制約の下でシステムを設計する
- シンプルさと堅牢性
- トレードオフ
- パフォーマンスの分析と最適化
- スケーラビリティ
- ここから始めてください: システム設計入門
- HiredInTech のシステム設計
- 技術面接で設計に関する質問に答える準備はどのようにすればよいですか?
- システム設計面接に合格するための 8 つのステップ ガイド
- データベースの正規化 - 1NF、2NF、3NF、および 4NF (ビデオ)
- システム設計インタビュー - これには多くのリソースがあります。記事と例を確認してください。その一部を以下に載せておきます
- システム設計面接に合格する方法
- 誰もが知っておくべき数字
- コンテキストスイッチを行うのにどのくらい時間がかかりますか?
- データセンター間のトランザクション (ビデオ)
- CAP 定理のわかりやすい英語の紹介
- MIT 6.824: 分散システム、2020 年春 (ビデオ 20 本)
- コンセンサスアルゴリズム:
- 一貫したハッシュ
- NoSQL パターン
- スケーラビリティ:
- これらすべてが必要なわけではありません。興味のあるものをいくつか選んでください。
- 素晴らしい概要 (ビデオ)
- 短編シリーズ:
- スケーラブルな Web アーキテクチャと分散システム
- 分散コンピューティングの誤った説明
- Jeff Dean - Google でのソフトウェア システムの構築と得られた教訓 (ビデオ)
- 大規模なシステムの設計入門
- App Engine と Cloud Datastore を使用してモバイル ゲームを世界中の視聴者に拡張する (ビデオ)
- Google が地球規模のインフラ向けに惑星規模のエンジニアリングを行う方法 (ビデオ)
- アルゴリズムの重要性
- シャーディング
- 長期戦に向けたエンジニアリング - アストリッド アトキンソン基調講演 (ビデオ)
- 30 分でわかる YouTube のスケーラビリティに関する 7 年間のレッスン
- PayPal がわずか 8VM を使用して毎日数十億のトランザクションに拡張した方法
- 大規模なデータセット内の重複を削除する方法
- Jon Cowie による Etsy の規模とエンジニアリング文化の内部を見る (ビデオ)
- Amazon を独自のマイクロサービス アーキテクチャに導いたもの
- 圧縮するかしないか、それは Uber の質問でした
- 近似クエリ処理はどのような場合に使用する必要がありますか?
- 単一データセンターからフェイルオーバー、ネイティブ マルチホーム アーキテクチャへの Google の移行
- 1 日に何百万ものリクエストに対応する画像最適化テクノロジー
- Patreon アーキテクチャの短編
- Tinder: 最大規模のレコメンデーション エンジンの 1 つは、次に会う人をどのように決定しますか?
- 最新のキャッシュの設計
- Facebook 規模のライブ ビデオ ストリーミング
- Amazon の AWS で 1,100 万人以上のユーザーに拡張するための初心者ガイド
- Netflix スタック全体の 360 度ビュー
- レイテンシはどこにでも存在し、売上にコストがかかります - それを解消する方法
- Instagram を動かすもの: 数百のインスタンス、数十のテクノロジー
- Salesforce アーキテクチャ - 1 日あたり 13 億トランザクションを処理する方法
- ESPN の大規模なアーキテクチャ - 毎秒 100,000 Duh Nuh Nuhs で動作
- 「メッセージング、シリアル化、およびキュー システム」を参照してください。サービスを結合できるいくつかのテクノロジーについては、以下を参照してください。
- ツイッター：
- さらに詳しくは、「大規模なデータセットのマイニング」を参照してください。 ビデオ シリーズ セクションのビデオ シリーズ
- システム設計プロセスの練習: ここでは、紙の上で取り組んでみるいくつかのアイデアを示します。それぞれのアイデアには、現実世界でどのように処理されたかについてのドキュメントが含まれています。
- レビュー: システム設計入門
- HiredInTech のシステム設計
- チートシート
- 流れ：
- 問題と範囲を理解します。
- 面接官の助けを借りてユースケースを定義する
- 追加機能を提案する
- 面接官が範囲外と判断した項目は削除します。
- 高可用性が必要であると想定し、ユースケースとして追加します
- 制約について考えます。
- 月あたりのリクエスト数を尋ねる
- 1 秒あたりのリクエスト数を尋ねます (ボランティアで依頼したり、計算させたりすることもあります)
- 読み取りと書き込みの割合を見積もる
- 見積もりの際は 80/20 ルールを念頭に置いてください
- 1秒あたりに書き込まれるデータ量
- 5 年間に必要な合計ストレージ
- 1秒あたりに読み取られるデータ量
- 抽象的なデザイン:
- レイヤー (サービス、データ、キャッシュ)
- インフラストラクチャ: 負荷分散、メッセージング
- サービスを推進する主要なアルゴリズムの大まかな概要
- ボトルネックを検討し、解決策を決定します
- 問題と範囲を理解します。
- 演習:
- ランダムな固有 ID 生成システムを設計する
- キーと値のデータベースを設計する
- 写真共有システムを設計する
- 推奨システムの設計
- URL 短縮システムの設計: 上記からコピー
- キャッシュ システムの設計
これらは、あなたが総合的なソフトウェア エンジニアになるのに役立ち、次の点に注意するために追加しました。
テクノロジーとアルゴリズムを活用できるため、より大きなツールボックスが手に入ります。
-
- UNIX ベースのコード エディターに慣れる
- ヴィ(男):
- emacs:
- Emacs の完全初心者ガイド (David Wilson によるビデオ)
- Emacs の完全初心者ガイド (David Wilson によるメモ)
-
- カーンアカデミー
- マルコフ過程の詳細:
- 詳細については、以下の MIT 6.050J 情報とエントロピー シリーズを参照してください。
-
- 以下のビデオもご覧ください
- 最初に情報理論のビデオを必ず視聴してください
- 情報理論、クロード シャノン、エントロピー、冗長性、データ圧縮とデータ圧縮ビッツ（ビデオ）
-
- 以下のビデオもご覧ください
- 最初に情報理論のビデオを必ず視聴してください
- カーン アカデミー シリーズ
- 暗号化: ハッシュ関数
- 暗号化: 暗号化
-
- 最初に情報理論のビデオを必ず視聴してください
- コンピューターマニア (ビデオ):
- コンプレッサーヘッドビデオ
- (オプション) Google Developers Live: GZIP だけでは十分ではありません!
-
- m ビットと k 個のハッシュ関数を持つブルーム フィルターを指定すると、挿入テストとメンバーシップ テストの両方が O(k) になります。
- ブルームフィルター (ビデオ)
- ブルームフィルター |大規模なデータセットのマイニング |スタンフォード大学 (ビデオ)
- チュートリアル
- ブルーム フィルター アプリの書き方
-
- 文書の類似性を判断するために使用されます
- 2 つのドキュメント/文字列がまったく同じかどうかを判断するために使用される MD5 または SHA の逆です。
- Simhashing (できれば) シンプルに
-
-
少なくとも 1 つのタイプのバランスのとれたバイナリ ツリーを知っています (そして、それがどのように実装されているかを知っています):
-
「バランスの取れた検索ツリーの中で、AVL と 2/3 ツリーは時代遅れになり、赤黒ツリーの方が人気があるようです。」 特に興味深い自己組織化データ構造は、回転を使用するスプレイ ツリーです。 アクセスされたキーをルートに移動します。」 - スキエナ
-
このうち、私はスプレイツリーを実装することにしました。私が読んだ限りでは、 インタビューでのバランスの取れた検索ツリー。しかし、コーディングをもう一段階体験したかったのです はっきり言って、枝分かれした木はミツバチの膝です。赤黒ツリーのコードをたくさん読みました
- スプレイツリー: 挿入、検索、削除機能 赤/黒のツリーを実装することになった場合は、次のことを試してください。
- 検索および挿入機能、削除のスキップ
-
B-Tree は非常に大規模なデータセットで広く使用されているため、B-Tree について詳しく知りたい
-
AVL ツリー
- 実際には： 私の知る限り、これらは実際にはあまり使用されていませんが、どのような場所にあるのかはわかりました。 AVL ツリーは、O(log n) の検索、挿入、削除をサポートする別の構造です。より厳格です 赤黒の木よりもバランスが取れているため、挿入と削除は遅くなりますが、取得は速くなります。これでできます 言語など、一度構築すれば再構築せずにロードできるデータ構造にとって魅力的 辞書 (またはアセンブラやインタプリタのオペコードなどのプログラム辞書)
- MIT AVL ツリー / AVL ソート (ビデオ)
- AVL ツリー (ビデオ)
- AVL ツリーの実装 (ビデオ)
- 分割とマージ
- [レビュー] 19 分でわかる AVL ツリー (プレイリスト) (ビデオ)
-
スプレーツリー
- 実際には： スプレイ ツリーは通常、キャッシュ、メモリ アロケータ、ルーター、ガベージ コレクター、 データ圧縮、ロープ (長いテキスト文字列に使用される文字列の置換)、Windows NT (仮想メモリ内、 ネットワークおよびファイル システム コード) など
- CS 61B: スプレイ ツリー (ビデオ)
- MIT 講義: スプレー ツリー:
- 非常に数学的になりますが、最後の 10 分を必ず見てください。
- ビデオ
-
赤/黒の木
- これらは 2-3 ツリーの翻訳です (下記を参照)。
- 実際には： 赤黒ツリーは、挿入時間、削除時間、および検索時間について最悪の場合の保証を提供します。 これにより、リアルタイム アプリケーションなどの時間に敏感なアプリケーションで価値が高まるだけでなく、 しかし、それは、最悪の場合の保証を提供する他のデータ構造の貴重な構成要素になります。 たとえば、計算幾何学で使用される多くのデータ構造は、赤黒ツリーに基づくことができます。 現在の Linux カーネルで使用されている Completely Fair Scheduler は、赤黒ツリーを使用します。 Java のバージョン 8 では、 コレクション ハッシュマップは、LinkedList を使用する代わりに、同じ要素を低品質で保存するように変更されました。 ハッシュコード、赤黒ツリーが使用されます
- Aduni - アルゴリズム - レクチャー 4 (リンクは開始点にジャンプします) (ビデオ)
- Aduni - アルゴリズム - レクチャー 5 (ビデオ)
- 赤黒の木
- 二分探索と Red Black Tree の概要
- [レビュー] 30 分でわかる Red-Black Trees (プレイリスト) (ビデオ)
-
2-3 検索ツリー
- 実際には： 2 ～ 3 個のツリーでは、検索は遅くなりますが、挿入は高速になります (AVL ツリーと比較して高さが高いため)。
- 実装にはさまざまなタイプのノードが含まれるため、2 ～ 3 個のツリーを使用することはほとんどありません。代わりに、人々は赤黒の木を使います。
- 23 ツリーの直感と定義 (ビデオ)
- 23 ツリーのバイナリ ビュー
- 2-3 Trees (学生朗読) (ビデオ)
-
2-3-4 ツリー (別名 2-4 ツリー)
- 実際には： 2 ～ 4 個のツリーごとに、同じ順序でデータ要素を持つ対応する赤と黒のツリーがあります。挿入と削除 2 ～ 4 個のツリーに対する操作は、赤黒ツリーの色の反転と回転にも相当します。これにより、2 ～ 4 本の木が作成されます。 これは、赤黒ツリーの背後にあるロジックを理解するための重要なツールであり、これが、多くのアルゴリズム入門書で紹介されている理由です。 実際には 2 ～ 4 本の木はあまり使用されませんが、赤黒の木の直前に 2 ～ 4 本の木。
- CS 61B レクチャー 26: バランスのとれた検索ツリー (ビデオ)
- Bottom Up 234-Trees (ビデオ)
- トップダウン 234-Trees (ビデオ)
-
N 配列 (K 配列、M 配列) ツリー
- 注: N または K は分岐係数 (最大分岐) です。
- 二分木は、分岐係数 = 2 の 2 分木です。
- 2 ～ 3 本の木は 3 分木です
- K-Ary Tree
-
B ツリー
- 面白い事実: それは謎ですが、B はボーイング、バランスド、またはバイエル (共同発明者) を表す可能性があります。
- 実際には： B ツリーはデータベースで広く使用されています。最新のファイルシステムのほとんどは B ツリー (またはバリアント) を使用します。に加えて B ツリーはデータベースで使用されるだけでなく、ファイル システムでも使用され、任意のファイルへの迅速なランダム アクセスを可能にします。 特定のファイル内のブロック。基本的な問題は、ファイル ブロック アドレスをディスク ブロックに変換することです。 (またはおそらくシリンダーヘッドセクターへの) アドレス
- B-Tree
- B ツリー データ構造
- B-Tree の紹介 (ビデオ)
- B ツリーの定義と挿入 (ビデオ)
- B ツリーの削除 (ビデオ)
- MIT 6.851 - メモリ階層モデル (ビデオ)
- キャッシュを意識しない B ツリー、非常に興味深いデータ構造をカバーします
- 最初の 37 分は非常に専門的なため、スキップされる可能性があります (B はブロック サイズ、キャッシュ ライン サイズ)
- [レビュー] 26 分でわかる B-Trees (プレイリスト) (ビデオ)
-
-
- 長方形または高次元のオブジェクト内の多数の点を見つけるのに最適です
- k 最近傍に適切に適合
- kNN K-d ツリー アルゴリズム (ビデオ)
-
- 「これらはややカルト的なデータ構造です。」 - スキエナ
- ランダム化: スキップ リスト (ビデオ)
- アニメーションともう少し詳細については
-
- 二分探索木とヒープの組み合わせ
- Treap
- データ構造: Treaps の説明 (ビデオ)
- 集合演算でのアプリケーション
これらは、上ですでに示したいくつかのアイデアを補強するために追加しましたが、含めたくはありませんでした
あまりにも多すぎるため、上記で説明しました。あるテーマについてやりすぎるのは簡単です。
今世紀中に採用されたいですよね？
-
固体
- Bob Martin オブジェクト指向とアジャイル設計の SOLID 原則 (ビデオ)
- S - 単一責任の原則 | 各オブジェクトに対する単一の責任
- O - オープン/クローズの原則 | 運用レベルでは、オブジェクトは拡張の準備ができていますが、変更の準備はできません
- L - リスコフ置換原則 | 基本クラスと派生クラスは「IS A」原則に従います
- I - インターフェイス分離の原則 |クライアントは、使用しないインターフェイスの実装を強制されるべきではありません
- D -依存性反転の原則 |オブジェクトの構成における依存関係を軽減します。
-
ユニオン検索
-
さらに動的プログラミング (ビデオ)
-
高度なグラフ処理 (ビデオ)
-
MIT 確率 (数学的で、ゆっくり進めてください。これは数学的なことに適しています) (ビデオ):
-
文字列のマッチング
- ラビン・カープ (ビデオ):
- [Rabin Karps アルゴリズム](https://www.coursera.org/lecture/data- Structures/rabin-karps-algorithm-c0Qkw)
- 事前計算
- [最適化: 実装と分析](https://www.coursera.org/learn/data- Structures/lecture/h4ZLc/optimization-implementation-and-analysis)
- テーブル ダブリング、カープラビン
- ローリング ハッシュ、償却分析
- クヌース・モリス・プラット (KMP):
- Boyer-Moore 文字列検索アルゴリズム
- Coursera: 文字列上のアルゴリズム
- 最初は素晴らしいですが、KMP を超えるまでに必要以上に複雑になります
- トライの素晴らしい説明
- スキップ可能
- ラビン・カープ (ビデオ):
-
並べ替え
- スタンフォード大学の分類に関する講義:
- シャイ・サイモンソン:
- スティーブン・スキーナが分類について講義します:
-
NAND からテトリスへ: 第一原理から最新のコンピューターを構築する
座って楽しんでください。
- 古典的な論文は好きですか?
- 1978: 逐次プロセスの通信
- 2003: Google ファイル システム
- 2012 年に Colossus に置き換えられました
- 2004: MapReduce: 大規模クラスターでのデータ処理の簡素化
- ほとんどが Cloud Dataflow に置き換えられましたか?
- 2006: Bigtable: 構造化データの分散ストレージ システム
- 2006: 疎結合分散システム用の Chubby Lock サービス
- 2007: Dynamo: Amazon の高可用性 Key-Value ストア
- Dynamo の論文が NoSQL 革命のきっかけとなった
- 2007: What Every Programmer Should Know About Memory (非常に長いため、著者は一部のセクションをスキップすることを推奨しています)
- 2012: AddressSanitizer: 高速アドレス健全性チェッカー:
- 2013: Spanner: Google の世界的に分散されたデータベース:
- 2015: Google の継続的なパイプライン
- 2015: 大規模な高可用性: Google の広告用データ インフラストラクチャの構築
- 2015: 開発者がコードを検索する方法: ケーススタディ
- その他の論文: 1,000 件の論文