coding interview university
1.0.0
私はもともとこれを、ソフトウェア エンジニアになるための学習トピックの短い To-Do リストとして作成しましたが、今日見られるような大規模なリストに成長しました。この学習計画を実行した結果、Amazon でソフトウェア開発エンジニアとして採用されることができました。おそらく私ほど勉強する必要はないでしょう。とにかく、必要なものはすべてここにあります。
数か月間、1日約8〜12時間勉強しました。これは私のストーリーです: Google の面接のために 8 か月間フルタイムで勉強した理由
注意してください:私ほど勉強する必要はありません。知る必要のないことに多くの時間を無駄にしてしまいました。詳細については以下をご覧ください。あなたの貴重な時間を無駄にすることなく、目的地に到達できるようお手伝いいたします。
ここにリストされている項目は、Amazon、Facebook、Google、Microsoft などの大手企業を含む、ほぼすべてのソフトウェア会社での技術面接に備えるための準備として役立ちます。
幸運を祈ります！
インドネシア語
ブルガリア語
スペイン語
ドイツ語
日本語 (日本語)
マラーティー語
研磨
ポルトガル語 ブラジレイロ
ロシア
Tiếng Việt - ベトナム語
ウルドゥー語 - ウルドゥー語
ウズベク語
বাংলা - バングラ語
ខ្មែរ - クメール語
简体中文
繁体中文
アフリカーンス語
アラビア語
フランス語
ギリシャ語
イタリア語
韓国語(한국어)
マラヤーラム語
ペルシア語 - ペルシャ語
テルグ語
タイ語
トルコ語
Українська
イエス
हिन्दी
スポンサーになってコーディング面接大学を応援しましょう！
これは、大企業のソフトウェア エンジニアになるための私の数か月にわたる学習計画です。
必須：
コーディングの経験 (変数、ループ、メソッド/関数など)
忍耐
時間
これはソフトウェア エンジニアリングの学習計画であり、フロントエンド エンジニアリングやフルスタック開発ではないことに注意してください。これらのキャリア パスに関するスーパー ロードマップとコースワークは、他の場所にあります (詳細については、https://roadmap.sh/ を参照してください)。
大学のコンピューター サイエンス プログラムでは学ぶべきことがたくさんありますが、面接には 75% 程度知っていれば十分なので、ここではそれについて説明します。完全な CS 独学プログラムについては、私の学習計画のリソースがカムラン アーメッドのコンピューター サイエンス ロードマップに含まれています: https://roadmap.sh/computer-science
それは何ですか？
なぜそれを使うのでしょうか？
使い方
自分が十分に賢くないとは思わないでください
ビデオリソースに関する注意
プログラミング言語を選択してください
データ構造とアルゴリズムに関する書籍
面接対策本
私の間違いをしないでください
表示されない内容
毎日の計画
コーディングの質問の練習
コーディングの問題
アルゴリズムの複雑さ / Big-O / 漸近分析
データ構造
配列
リンクされたリスト
スタック
列
ハッシュテーブル
さらなる知識
二分探索
ビット単位の演算
木々
木 - イントロ
二分探索木: BST
ヒープ / プライオリティ キュー / バイナリ ヒープ
バランスの取れた検索ツリー (詳細ではなく一般的な概念)
トラバーサル: プレオーダー、インオーダー、ポストオーダー、BFS、DFS
仕分け
選択
挿入
ヒープソート
クイックソート
マージソート
グラフ
指示された
方向性のない
隣接行列
隣接リスト
トラバーサル:BFS、DFS
さらに多くの知識
再帰
動的プログラミング
デザインパターン
組み合わせ論 (n から k を選択) と確率
NP、NP-Complete、および近似アルゴリズム
コンピューターがプログラムを処理する仕組み
キャッシュ
プロセスとスレッド
テスト
文字列の検索と操作
試してみます
浮動小数点数
ユニコード
エンディアンネス
ネットワーキング
最終レビュー
履歴書を更新する
仕事を探す
面接プロセスと一般的な面接の準備
面接が来るときのことを考えておく
面接官に質問する
仕事を手に入れたら
---------------- これより下はすべてオプションです ----------------
追加の書籍
システム設計、スケーラビリティ、データ処理 (4 年以上の経験がある場合)
追加の学習
AVL ツリー
スプレーツリー
赤/黒の木
2～3本の検索ツリー
2-3-4 ツリー (別名 2-4 ツリー)
N 進 (K 進、M 進) ツリー
B ツリー
コンパイラ
Emacs と vi(m)
Unixコマンドラインツール
情報理論
パリティ&ハミングコード
エントロピ
暗号化
圧縮
コンピュータのセキュリティ
ガベージコレクション
並列プログラミング
メッセージング、シリアル化、およびキューイング システム
あ*
高速フーリエ変換
ブルームフィルター
ハイパーログログ
局所性を考慮したハッシュ
ファン・エムデ・ボアスの木
拡張されたデータ構造
バランスの取れた検索ツリー
kDツリー
スキップリスト
ネットワークフロー
素集合と和集合の検索
高速処理のための数学
トレプ
線形計画法
ジオメトリ、凸包
離散数学
一部の主題に関する追加の詳細
ビデオシリーズ
コンピュータサイエンスコース
論文
大企業でソフトウェア エンジニアとして働きたいのであれば、これらのことを知っておく必要があります。
私のようにコンピューター サイエンスの学位を取得できなかった場合は、これで取り戻せ、人生を 4 年間節約できます。
このプロジェクトを開始したとき、私はヒープからのスタックのことも、Big-O のことも、ツリーについても、グラフのトラバース方法も何も知りませんでした。もし私が並べ替えアルゴリズムをコーディングしなければならなかったとしたら、それはひどいことになるでしょう。私がこれまで使用してきたデータ構造はすべて言語に組み込まれており、それらが内部でどのように機能するのかまったく知りませんでした。実行中のプロセスで「メモリ不足」エラーが発生し、回避策を見つける必要がない限り、メモリを管理する必要はありませんでした。私はこれまでにいくつかの多次元配列と何千もの連想配列を使用しましたが、データ構造を最初から作成したことはありませんでした。
長い計画ですね。何か月もかかるかもしれません。すでにこの内容の多くに精通している場合は、時間ははるかに短くなります。
⬆トップに戻る
以下はすべて概要であり、上から下の順に項目に取り組む必要があります。
私は、進捗状況を追跡するためのタスク リストを含む、GitHub の特別なマークダウン フレーバーを使用しています。
GitHub 風味のマークダウンの詳細
このページで、上部近くの「コード」ボタンをクリックし、「ZIP をダウンロード」をクリックします。ファイルを解凍すると、テキスト ファイルを操作できるようになります。
マークダウンを理解できるコード エディターで開いている場合は、すべてが適切にフォーマットされていることを確認できます。
新しいブランチを作成して、次のような項目を確認できるようにします。括弧内に x を入力するだけです: [x]
「フォーク」ボタンをクリックして、 GitHub リポジトリhttps://github.com/jwasham/coding-interview-universityをフォークします。
ローカル リポジトリにクローンを作成します。
git clone https://github.com/<YOUR_GITHUB_USERNAME>/coding-interview-university.gitcdcoding-interview-university git リモート追加アップストリーム https://github.com/jwasham/coding-interview-university.git gitRemote set-url --pushupstream DISABLE #個人的な進行状況を元のリポジトリに戻さないようにする
変更を完了したら、すべてのボックスに X を付けます。
git commit -am "Markedpersonal progress"git pullupstreammain #元のリポジトリからの変更でフォークを最新の状態に保つ Push #フォークにプッシュするだけ
⬆トップに戻る
成功したソフトウェア エンジニアは賢いですが、多くの人は自分が十分に賢くないのではないかという不安を抱えています。
次のビデオは、この不安を克服するのに役立ちます。
天才プログラマーの神話
一人で行くのは危険: テクノロジー業界の目に見えないモンスターとの戦い
⬆トップに戻る
一部のビデオは、Coursera または EdX クラスに登録することによってのみ視聴できます。これらは MOOC と呼ばれます。場合によっては、クラスが開催されていないため、数か月待たなければならず、アクセスできないこともあります。
オンライン コースのリソースを、YouTube ビデオ (できれば大学の講義) など、いつでも利用できる無料の公開ソースに置き換えて、特定のオンライン コースの開催中だけでなく、いつでも学習できるようにするのは素晴らしいことです。
⬆トップに戻る
コーディング面接に使用するプログラミング言語を選択する必要がありますが、コンピューター サイエンスの概念を学習するために使用できる言語も見つける必要があります。
できれば、どちらか 1 つの言語に習熟するだけで済むように、言語が同じであることが望ましいです。
学習計画を立てたとき、そのほとんどで C と Python の 2 つの言語を使用しました。
C: 非常に低いレベル。ポインタやメモリの割り当て/割り当て解除を扱うことができるため、データ構造とアルゴリズムを骨の髄まで感じ取ることができます。 Python や Java などの高水準言語では、これらは表示されません。日常の仕事ではそれは素晴らしいことですが、これらの低レベルのデータ構造がどのように構築されるかを学んでいるときは、金属を身近に感じられるのは素晴らしいことです。
これは短い本ですが、C 言語をうまく扱うことができ、少し練習すればすぐに上達します。 C を理解すると、プログラムとメモリがどのように機能するかを理解するのに役立ちます。
本を深く読み込む必要はありません（あるいは読み終える必要さえありません）。 C で快適に読み書きできるところまで進んでください。
Cはどこにでもあります。勉強していると、書籍、講義、ビデオなど、あらゆるところで例を見ることができます。
C プログラミング言語、第 2 版
Python: モダンで表現力が非常に豊かです。非常に便利で、面接で記述するコードの量も少なくて済むため、私はこれを学びました。
これが私の好みです。もちろん、好きなことをしてください。
必要ないかもしれませんが、新しい言語を学習するためのサイトをいくつか紹介します。
運動
コードウォーズ
ハッカーアース
スケーラーのトピック (Java、C++)
Programiz PRO コミュニティ チャレンジ)
面接のコーディング部分には、使い慣れた言語を使用できますが、大企業の場合は、次の言語を選択するのが確実です。
C++
ジャワ
パイソン
これらを使用することもできますが、最初に読んでください。注意事項がある場合があります:
JavaScript
ルビー
面接の言語の選択について私が書いた記事は次のとおりです。「コーディング面接には言語を 1 つ選択してください」。これは私の投稿の元の記事です: 面接のためのプログラミング言語の選択
その言語に非常に慣れていて、知識が豊富である必要があります。
選択肢について詳しくは、以下をご覧ください。
コーディング面接に適切な言語を選択してください
ここで言語固有のリソースを参照してください
⬆トップに戻る
この本は、コンピューター サイエンスの基礎を築きます。
使いやすい言語を選択してください。大量の読書とコーディングを行うことになります。
C のアルゴリズム、パート 1 ～ 5 (バンドル)、第 3 版
基礎、データ構造、並べ替え、検索、グラフ アルゴリズム
Python のデータ構造とアルゴリズム
グッドリッチ、タマッシア、ゴールドワッサー著
この本が大好きでした。それはすべてを網羅し、それ以上のものでした。
Python コード
私の素晴らしい本のレポート: https://startupnextdoor.com/book-report-data-structurals-and-algorithms-in-python/
あなたの選択:
グッドリッチ、タマッシア、ゴールドワッサー
Java のデータ構造とアルゴリズム
セジウィックとウェイン：
アルゴリズム I
アルゴリズム II
アルゴリズム
この本をカバーする無料の Coursera コース (著者が教えます!):
あなたの選択:
グッドリッチ、タマッシア、マウント
C++ のデータ構造とアルゴリズム、第 2 版
セジウィックとウェイン
C++ のアルゴリズム、パート 1 ～ 4: 基礎、データ構造、並べ替え、検索
C++ のアルゴリズム パート 5: グラフ アルゴリズム
⬆トップに戻る
たくさん買う必要はありません。正直なところ、「コーディング面接の攻略」で十分だと思いますが、さらに練習するためにさらに購入しました。しかし、私はいつもやりすぎます。
これを両方購入しました。彼らは私にたくさんの練習をさせてくれました。
プログラミング面接の公開: 面接を通じたコーディング、第 4 版
C++ と Java での回答
これはコーディング面接を突破するための良いウォーミングアップです
それほど難しくありません。ほとんどの問題は、面接で見られるものよりも簡単かもしれません (私が読んだ情報によると)
コーディングインタビューの解読、第 6 版
Javaでの答え
1 つ選択してください:
プログラミング面接の要素（C++版）
Python でのプログラミング面接の要素
プログラミング インタビューの要素 (Java バージョン) - コンパニオン プロジェクト - 書籍内のすべての問題に対するメソッド スタブとテスト ケース
⬆トップに戻る
このリストは何か月もかけて増えていき、手に負えなくなりました。
より良い経験をしていただくために、私が犯したいくつかの間違いを以下に示します。そして、何か月も時間を節約できます。
何時間もビデオを見て大量のメモをとりましたが、数か月後には覚えていないことがたくさんありました。 3 日間かけてメモを見直し、フラッシュカードを作成して復習しました。そんな知識は必要ありませんでした。
私の間違いを犯さないように、読んでください。
コンピューターサイエンスの知識を保持する。
この問題を解決するために、一般とコードの 2 種類のフラッシュカードを追加できる小さなフラッシュカード サイトを作成しました。各カードには異なる形式があります。どこにいても携帯電話やタブレットでレビューできるように、モバイルファーストのウェブサイトを作成しました。
無料で独自に作成します。
フラッシュカード サイト リポジトリ
フラッシュカードの使用はお勧めしません。あまりにも多すぎて、そのほとんどは必要のない雑学です。
しかし、私の言うことを聞きたくない場合は、次のようにしてください。
私のフラッシュ カード データベース (1200 枚):
私のフラッシュ カード データベース (極端な - 1800 枚のカード):
やりすぎて、アセンブリ言語や Python のトリビアから機械学習や統計まで、あらゆるものをカバーしたカードがあることに注意してください。必要なものが多すぎます。
フラッシュカードに関する注意:初めて答えを知っていると気づいたときは、その答えを既知としてマークしないでください。本当に理解するには、同じカードを見て何度か正しく答える必要があります。繰り返すことで知識が脳に深く定着します。
私のフラッシュカード サイトを使用する代わりに、何度も勧められてきた Anki がおすすめです。繰り返しシステムを使用しているので、覚えやすくなります。ユーザーフレンドリーで、すべてのプラットフォームで利用でき、クラウド同期システムを備えています。 iOS では 25 ドルかかりますが、他のプラットフォームでは無料です。
Anki 形式のフラッシュカード データベース: https://ankiweb.net/shared/info/25173560 (@xiewenya に感謝)。
一部の学生は、空白に関する書式の問題について次の手順を実行することで修正できると述べています。デッキを開いて、カードを編集し、カードをクリックし、「スタイル」ラジオ ボタンを選択して、メンバー「white-space: pre;」を追加します。カードクラスへ。
これは非常に重要です。
データ構造とアルゴリズムを学習しながら、コーディング面接の質問に答え始めます。
問題を解決するには、学んだことを応用する必要があります。そうしないと忘れてしまいます。私はこの間違いを犯しました。
トピックを学習し、リンク リストなどにある程度慣れてきたら、次のようにします。
コーディングに関するインタビューブックのいずれかを開きます (または、以下にリストされているコーディングに関する問題の Web サイト)
リンクされたリストに関する質問を 2 つまたは 3 つ答えます。
次の学習トピックに進みます。
後で、戻って別の 2 つまたは 3 つのリンク リストの問題を解きます。
新しいトピックを学ぶたびにこれを行ってください。
これらすべてを学習した後ではなく、学習中に問題を解き続けてください。
あなたは知識のために雇われているのではなく、その知識をどのように応用するかによって雇われているのです。
以下に示すように、これに関する多くのリソースがあります。続けて。
気を散らすものがたくさんあり、貴重な時間が奪われてしまう可能性があります。集中力と集中力は難しいです。歌詞のない音楽をかけると、かなり集中できるようになります。
⬆トップに戻る
これらは普及しているテクノロジーですが、この調査計画には含まれていません。
JavaScript
HTML、CSS、その他のフロントエンドテクノロジー
SQL
⬆トップに戻る
このコースでは多くの科目を扱います。おそらくそれぞれに数日、場合によっては 1 週間以上かかる場合があります。それはあなたのスケジュール次第です。
毎日、リストの次の主題を取り上げ、その主題に関するビデオをいくつか見てから、このコース用に選択した言語でそのデータ構造またはアルゴリズムの実装を作成します。
私のコードはここで見ることができます:
C
C++
パイソン
すべてのアルゴリズムを覚える必要はありません。独自の実装を作成できる程度に理解できれば十分です。
⬆トップに戻る
Why is this here? I'm not ready to interview.
それから戻ってこれを読んでください。
プログラミングの問題を解く練習が必要な理由:
問題の認識、および適切なデータ構造とアルゴリズムがどこに適合するか
問題の要件を収集する
面接と同じように問題を解決する方法を話す
コンピューターではなく、ホワイトボードまたは紙にコーディングする
ソリューションの時間と空間の複雑さを考え出す (下記の Big-O を参照)
ソリューションをテストする
面接における系統的かつコミュニケーション的な問題解決のための素晴らしい導入部があります。これはプログラミングのインタビュー本からもわかりますが、私はこれが優れていると思いました: アルゴリズム デザイン キャンバス
コードはコンピューターではなくホワイトボードまたは紙に書きます。いくつかのサンプル入力を使用してテストします。次に、それを入力してコンピュータでテストします。
家にホワイトボードがない場合は、画材店で大きな描画パッドを購入してください。ソファに座って練習することもできます。こちらは私の「ソファホワイトボード」です。写真ではスケールを調整するためにペンを追加しました。ペンを使っていると、消せたらいいのにと思うでしょう。すぐに散らかります。私は鉛筆と消しゴムを使います。
コーディング問題の演習は、プログラミング問題の答えを暗記することではありません。
⬆トップに戻る
ここに重要なコーディングに関するインタビュー本を忘れないでください。
問題の解決:
解決策を見つける方法
トップコーダーの問題ステートメントを分析する方法
コーディング面接の質問ビデオ:
IDeserve (88 ビデオ)
トゥシャー・ロイ (5 プレイリスト)
問題解決策のウォークスルーに最適
Nick White - LeetCode ソリューション (187 ビデオ)
ソリューションとコードの適切な説明
短時間で何本も視聴できる
FisherCoder - LeetCode ソリューション
チャレンジ/練習サイト:
リートコード
私のお気に入りのコーディングの問題サイト。おそらく準備する 1 ～ 2 か月分の購読料を払う価値があります。
コードのウォークスルーについては、上記の Nick White と FisherCoder のビデオを参照してください。
ハッカーランク
トップコーダー
コードフォース
卑劣さ
オタクのためのオタク
アルゴエキスパート
Google のエンジニアによって作成されたこれは、スキルを磨くための優れたリソースでもあります。
プロジェクト・オイラー
非常に数学に重点が置かれており、コーディング面接にはあまり適していません
⬆トップに戻る
さて、話は十分です、学びましょう！
ただし、学習中に上記のコーディング問題に取り組むことを忘れないでください。
ここでは何も実装する必要はありません。ビデオを見てメモを取るだけです。わーい！
ここにはたくさんのビデオがあります。理解できるまで十分に見てください。いつでも戻ってレビューすることができます。
背後にある数学がすべて理解できなくても心配する必要はありません。
Big-O の観点からアルゴリズムの複雑さを表現する方法を理解する必要があるだけです。
ハーバード CS50 - 漸近記法 (ビデオ)
Big O Notations (一般的なクイック チュートリアル) (ビデオ)
Big O Notation (およびオメガとシータ) - 最良の数学的説明 (ビデオ)
スキエナ (ビデオ)
カリフォルニア大学バークレー校ビッグオー (ビデオ)
償却分析 (ビデオ)
TopCoder (漸化式とマスター定理を含む):
計算の複雑さ: セクション 1
計算の複雑さ: セクション 2
チートシート
[レビュー] 18 分でわかるアルゴリズム (プレイリスト) (動画)
まあ、それだけで十分です。
「コーディング インタビューの解読」を進めると、これに関する章があり、最後に、さまざまなアルゴリズムの実行時の複雑さを特定できるかどうかを確認するクイズがあります。それはスーパーレビューとテストです。
⬆トップに戻る
メモリ内で連続しているため、近接性によりパフォーマンスが向上します
必要なスペース = (配列の容量、つまり n 以上) * 項目のサイズ、ただし 2n であっても O(n)
O(1) は、最後に追加/削除 (より多くのスペースの割り当てのために償却)、インデックス付け、または更新を行います。
O(n) は他の場所に挿入/削除します
配列とポインターを使用したコーディングと、インデックスを使用する代わりにインデックスにジャンプするポインターの計算を練習します。
メモリが割り当てられた新しい生データ配列
size() - アイテムの数
Capacity() - 保持できるアイテムの数
is_empty()
at(index) - 指定されたインデックスにある項目を返します。インデックスが範囲外の場合は爆発します。
プッシュ(アイテム)
insert(index, item) - インデックスに項目を挿入し、そのインデックスの値と末尾の要素を右にシフトします
prepend(item) - インデックス 0 で上に挿入を使用できます
Pop() - 末尾から削除し、値を返す
delete(index) - インデックスにある項目を削除し、後続の要素をすべて左にシフトします
Remove(item) - 値を検索し、それを保持するインデックスを削除します (複数の場所にある場合でも)
find(item) - 値を検索し、その値を持つ最初のインデックスを返します。見つからない場合は -1 を返します。
size(new_capacity) // プライベート関数
内部で int 配列を割り当てることができますが、その機能は使用できません
16 から始まります。開始番号がそれより大きい場合は、2 - 16、32、64、128 の累乗を使用します。
容量に達したら、サイズを 2 倍に変更します
アイテムをポップするときに、サイズが容量の 1/4 の場合は半分にサイズ変更します
アレイ CS50 ハーバード大学
配列 (ビデオ)
UC Berkeley CS61B - Linear and Multi-Dim Arrays (ビデオ) (15 分 32 秒から視聴開始)
動的配列 (ビデオ)
ギザギザ配列 (ビデオ)
配列について:
ベクトル (自動サイズ変更機能を備えた可変配列) を実装します。
時間
空間
説明（ビデオ）
実装する必要はありません
size() - リスト内のデータ要素の数を返します。
empty() - ブール値は空の場合に true を返します。
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) - この値を持つリストの最初の項目を削除します
ポインタからポインタへ
コアリンクリストと配列 (ビデオ)
現実の世界では、リンクされたリストと配列 (ビデオ)
リンク リスト CS50 ハーバード大学 - これは直感を構築します。
単一リンクリスト (ビデオ)
CS 61B - リンクされたリスト 1 (ビデオ)
CS 61B - リンク リスト 2 (ビデオ)
【復習】4分でわかるリンクリスト（動画）
説明：
C コード (ビデオ) - ビデオ全体ではなく、ノード構造とメモリ割り当てに関する部分のみ
リンクされたリストと配列:
リンクされたリストを避けるべき理由 (ビデオ)
注意: ポインタからポインタへの知識が必要です: (ポインタが指すアドレスを変更する可能性のある関数にポインタを渡すときのため) このページは、ptr から ptr への理解だけを目的としています。このリスト走査スタイルはお勧めしません。賢いため、可読性と保守性が低下します。
実装します（私はテールポインタを使用して、および使用せずに実行しました）：
二重リンクリスト
スタック (ビデオ)
【レビュー】3分で積み上げる（動画）
実装しません。配列を使った実装は簡単です
先頭でエンキューし、末尾でデキューするリンク リストを使用した悪い実装では、最後から 2 番目の要素が必要になるため、O(n) となり、各デキューの完全な走査が発生します。
エンキュー: O(1) (償却済み、リンク リストおよび配列 [プローブ])
デキュー: O(1) (リンクされたリストと配列)
空: O(1) (リンクされたリストと配列)
enqueue(value) - 使用可能なストレージの最後に項目を追加します
dequeue() - 値を返し、最後に追加された要素を削除します
空の（）
満杯（）
enqueue(value) - 末尾の位置に値を追加します。
dequeue() - 値を返し、最後に追加された要素 (前部) を削除します。
空の（）
キュー（ビデオ）
循環バッファ/FIFO
【復習】3分でわかる行列（動画）
リンクリストとテールポインタを使用して実装します。
固定サイズの配列を使用して実装します。
料金：
hash(k, m) - m はハッシュ テーブルのサイズです
add(key, value) - キーがすでに存在する場合、値を更新します
存在します(キー)
取得(キー)
削除(キー)
コア ハッシュ テーブル (ビデオ)
データ構造 (ビデオ)
電話帳の問題 (ビデオ)
分散ハッシュテーブル:
Dropbox でのインスタント アップロードとストレージの最適化 (ビデオ)
分散ハッシュ テーブル (ビデオ)
チェーンを使用したハッシュ (ビデオ)
テーブルダブリング、Karp-Rabin (ビデオ)
オープン アドレッシング、暗号化ハッシュ (ビデオ)
PyCon 2010: 強力な辞書 (ビデオ)
PyCon 2017: 辞書がさらに強力に (ビデオ)
(上級) ランダム化: ユニバーサル & パーフェクト ハッシュ (ビデオ)
(上級) 完全ハッシュ化 (ビデオ)
【復習】4分でわかるハッシュテーブル（動画）
動画:
オンラインコース:
リニアプロービングを使用した配列による実装
⬆トップに戻る
二分探索 (整数のソートされた配列に対する)
再帰を使用した二分探索
二分探索 (ビデオ)
二分探索 (ビデオ)
詳細
青写真
【復習】4分でわかる二分探索（動画）
埋め込む：
絶対整数
スワップ
バイト内のビットを数える 4 つの方法 (ビデオ)
ビットをカウントする
32 ビット整数のセットビット数を数える方法
バイナリ: プラスとマイナス (2 の補数を使用する理由) (ビデオ)
1 の補数
2の補数
言葉
優れたイントロ: ビット操作 (ビデオ)
C プログラミング チュートリアル 2-10: ビット演算子 (ビデオ)
ビット操作
ビット単位の演算
ビサックス
ビットトゥイドラー
ビット・トゥイドラー・インタラクティブ
ビットハック (ビデオ)
練習操作
(2^1 から 2^16 および 2^32) までの 2 の累乗の多くを知っている必要があります。
ビットのチートシート
&、|、^、~、>>、<< を使用したビット操作についてよく理解します。
2 と 1 の補数
カウントセットビット
値を交換します:
絶対値:
⬆トップに戻る
BFS のメモ:
DFS のメモ:
レベル順序 (BFS、キューを使用)
時間計算量: O(n)
空間の複雑さ: 最良: O(1)、最悪: O(n/2)=O(n)
時間計算量: O(n)
空間複雑さ: 最良: O(log n) - 平均。最悪の木の高さ: O(n)
順序 (DFS: 左、自分、右)
事後順序 (DFS: 左、右、自己)
予約注文 (DFS: 自分、左、右)
木の紹介 (ビデオ)
ツリートラバーサル (ビデオ)
BFS (幅優先検索) および DFS (深さ優先検索) (ビデオ)
【レビュー】4分でわかる幅優先検索（動画）
【レビュー】4分で深さ優先検索（動画）
[レビュー] 11 分でわかるツリー トラバーサル (プレイリスト) (ビデオ)
insert // ツリーに値を挿入します
get_node_count // 保存されている値の数を取得します
print_values // ツリー内の値を最小値から最大値まで出力します。
ツリーの削除
is_in_tree // 指定された値がツリーに存在する場合は true を返します
get_height // ノード単位の高さを返します (単一ノードの高さは 1)
get_min // ツリーに格納されている最小値を返します
get_max // ツリーに格納されている最大値を返します
is_binary_search_tree
削除値
get_successor // ツリー内で指定された値の次に高い値を返します。値がない場合は -1 を返します。
二分探索木 - C/C++ での実装 (ビデオ)
BST 実装 - スタックとヒープでのメモリ割り当て (ビデオ)
二分探索ツリーで最小要素と最大要素を見つける (ビデオ)
二分木の高さを求める (ビデオ)
バイナリ ツリー トラバーサル - 幅優先戦略と深さ優先戦略 (ビデオ)
バイナリ ツリー: レベル順序トラバーサル (ビデオ)
バイナリ ツリー トラバーサル: Preorder、Inorder、Postorder (ビデオ)
二分木が二分探索木かどうかを確認する (ビデオ)
二分探索ツリーからノードを削除する (ビデオ)
二分探索木の Inorder Successor (ビデオ)
二分探索ツリーのレビュー (ビデオ)
紹介（ビデオ）
MIT (ビデオ)
C/C++:
埋め込む：
入れる
sift_up - 挿入に必要
get_max - 最大項目を削除せずに返します。
get_size() - 格納されている要素の数を返す
is_empty() - ヒープに要素が含まれていない場合は true を返します
extract_max - 最大項目を返し、それを削除します
sift_down - extract_max に必要
Remove(x) - インデックス x の項目を削除します
heapify - heap_sort に必要な要素の配列からヒープを作成します
heap_sort() - ソートされていない配列を取得し、最大ヒープまたは最小ヒープを使用してその場でソートされた配列に変換します。
ツリーとして視覚化されますが、通常はストレージ内では線形です (配列、リンク リスト)
ヒープ
紹介（ビデオ）
二分木 (ビデオ)
樹高備考（動画）
基本操作（動画）
完全な二分木 (ビデオ)
疑似コード (ビデオ)
ヒープ ソート - 開始へのジャンプ (ビデオ)
ヒープソート (ビデオ)
ヒープの構築 (ビデオ)
MIT 6.006 アルゴリズムの概要: バイナリ ヒープ
CS 61B レクチャー 24: 優先キュー (ビデオ)
線形時間ビルドヒープ (最大ヒープ)
【レビュー】13分でヒープ（プレイリスト）（動画）
最大ヒープを実装します。
⬆トップに戻る
注:
リンクされたリストをソートすることはお勧めしませんが、マージソートは可能です。
リンクされたリストの並べ替えを結合
ソートアルゴリズムの安定性
ソートアルゴリズムの安定性
ソートアルゴリズムの安定性
ソートアルゴリズム - 安定性
バブルソートはありません - ひどいです - O(n^2) (n <= 16 の場合を除く)
ソートを実装し、最良のケース/最悪のケース、それぞれの平均複雑さを把握します。
ソートアルゴリズムの安定性 (「クイックソートは安定していますか?」)
リンクされたリストではどのアルゴリズムを使用できますか?配列ではどれですか?両方のうちどちらですか?
ヒープソートについては、上記のヒープ データ構造を参照してください。ヒープソートは優れていますが、安定していません
セジウィック - マージソート (5 ビデオ)
1. マージソート
2. ボトムアップのマージソート
3. 並べ替えの複雑さ
4. コンパレータ
5. 安定性
Sedgewick - クイックソート (4 ビデオ)
1. クイックソート
2. 選択
3. 重複キー
4. システムソート
カリフォルニア大学バークレー校:
CS 61B 講義 29: 並べ替え I (ビデオ)
CS 61B 講義 30: 仕分け II (ビデオ)
CS 61B 講義 32: 仕分け III (ビデオ)
CS 61B レクチャー 33: 並べ替え V (ビデオ)
CS 61B 2014-04-21: 基数ソート(ビデオ)
バブルソート (ビデオ)
バブルソートの分析 (ビデオ)
挿入ソート、マージソート (ビデオ)
挿入ソート (ビデオ)
マージソート (ビデオ)
クイックソート (ビデオ)
選択範囲の並べ替え (ビデオ)
ソートコードをマージ:
出力配列の使用 (C)
出力配列の使用 (Python)
インプレース (C++)
クイックソートコード:
実装(C)
実装(C)
実装（Python）
【レビュー】18分で並び替え（プレイリスト）
4 分で簡単仕分け (ビデオ)
4 分でヒープソート (ビデオ)
3 分でソートをマージする (ビデオ)
2 分でできるバブルソート (ビデオ)
3 分で選択項目を並べ替える (ビデオ)
2 分で挿入ソート (ビデオ)
埋め込む：
マージソート: O(n log n) 平均および最悪
