algo calisthenics

アルゴリズムとデータ構造

このリポジトリを練習の遊び場（kata）として、また一般的でシンプルでありながら強力なアルゴリズムを思い出させるつもりです。エレガントなところ、私はClojureトランスデューサーを使用します。これは、シーケンスを処理するための優れた電動ツールです。このドキュメントは徹底的に思えるかもしれませんが、私はそれを勉強する必要があるときにいつでも戻ってくることができるリストとしてそれを使用するつもりです。ここにリストされているすべてを実装していません。

ライティングスタイル

ここでのコードは、プロのコーディングに使用するスタイルでは形作られていません。すべてのチームには、コードスタイルに関する文化と意見があり、これらの一般的なガイドラインに固執することをお勧めします。さらに、コードは主に他の人が読み取るために記述されています。または、マシンの読者のみをターゲットにする場合、私たち全員がアセンブリで最大のパフォーマンスを求めてコーディングします。私が書いているコードは、チームの一部がこのチームの他の人によって書かれている可能性があることを意図しています。

ここのコードは、EMACSとORG-MODEのおかげで、Litterateプログラミングで書かれています。 Clojureで記述されたコードは、その背後にある理由を説明するテキストファイルから派生していることを意味します。読みやすくなることを願っています。

Python

新しい問題の準備をします

./dev-resources/new-problem.sh 
  --problem-path neetcode_practice_2024/arrays_and_hashing/problem_4_anagram_groups

--helpを参照してください。

初期化スクリプトが完了すると、テストの提案されたコマンドが最後に表示されます。

poetry run ptw -- -- 
  src/neetcode_practice_2024/arrays_and_hashing/problem_4_anagram_groups.py 
  tests/neetcode_practice_2024/arrays_and_hashing/problem_4_anagram_groups_test.py

詩やpytestとの対話

たとえば、開発中にテストを視聴するには：

poetry run ptw
poetry run ptw -- -- --memray
poetry run ptw -- -- --benchmark-only
poetry run ptw -- -- --benchmark-skip

周りの小さなダンス-- --おそらく避けることができますが、私は何が実行されるかについて非常に明示的になることを好むので、私はpoetry左端の前の議論として守ります。

メモリフレームグラフを取得するには：

poetry run memray run -m neetcode_practice_2024.arrays_and_hashing.problem_1_contains_duplicate --integer_array " 1, 2, 3, 4 "
poetry run python -m memray flamegraph memray-neetcode_practice_2024.arrays_and_hashing.problem_1_contains_duplicate.554244.bin

CPUフレームグラフ（または他のグラフ）を取得するには：

poetry run python -m cProfile -o program.prof -m neetcode_practice_2024.arrays_and_hashing.problem_1_contains_duplicate --integer_array " 1, 2, 3, 4, 4 "
poetry run snakeviz program.prof

ベンチマークを実行してグラフィカルな要約を取得するには：

poetry run pytest --benchmark-only --benchmark-histogram

学習リスト

ソートアルゴリズム

• ゼロから実装：バブルソート、マージソート、クイックソート、ヒープソート。
• 整数の配列が与えられた場合、Quick選択アルゴリズムを使用してKTH最小要素を見つけます。
• カウントソートアルゴリズムを実装して、既知の範囲の値を持つ整数の配列をソートします。
• Quick Sortを使用して「3方向パーティション」の問題を解き、アレイを複製値で効率的にソートします。

検索アルゴリズム

• ゼロからの実装：バイナリ検索（ソートされた配列の場合）、線形検索。
• 回転したソートアレイが与えられた場合、変更されたバイナリ検索を使用してターゲット要素を見つけます。

トラバーサルのグラフ、ツリー、およびアルゴリズム

• ゼロからの実装：幅広い最初の検索（BFS）、深さfirst検索（DFS）、Dijkstraのアルゴリズム、Bellman-Fordアルゴリズム。
• さまざまな表現を実装：隣接するマトリックス、隣接リスト。
• Dijkstraのアルゴリズムを使用して、加重グラフで2つのノード間の最短パスを見つけます。
• バイナリ検索ツリーを実装し、挿入、削除、検索などの基本操作を実行します。
• 指示されたグラフが与えられた場合、2つのノード間にルートがあるかどうかを確認します。
• 無向グラフで接続されたコンポーネントの数を見つけます。
• 指向性環状グラフ（DAG）のトポロジーソートを実装します。
• バイナリツリー内の2つのノードの最も低い共通祖先（LCA）を見つけます。
• バイナリツリーが与えられた場合、有効なバイナリ検索ツリー（BST）であるかどうかを確認してください。
• グラフが与えられた場合、KosarajuのアルゴリズムまたはTarjanのアルゴリズムを使用して、強く接続されたすべてのコンポーネント（SCC）を見つけます。
• Floyd-Warshallアルゴリズムを実装して、加重グラフで最短パスをすべて見つけます。
• N-aryツリーが与えられた場合、レベルオーバートラバーサルまたは深さfirstのトラバーサルを実行します（たとえば、予約注文、ポストオーダー）。

動的プログラミング

• 問題をより小さな重複するサブ問題に分割するという概念を理解し、メモまたは集計を使用します。
• 再帰的なプログラミングアプローチと動的プログラミングアプローチの両方を使用して、古典的な「フィボナッチ」問題を解決します。
• ウェイトと値のあるアイテムのセットを考えると、0-1ナップサックの問題を使用して、特定の最大重量で取得できる最大値を見つけます。

貪欲なアルゴリズム

• 局所的に最適な選択を行うことが、グローバルに最適なソリューションにつながる問題を理解すること。
• 重複しないアクティビティの最大数を選択する必要がある「アクティビティ選択問題」のソリューションを実装します。
• 異なる宗派と量のコインのセットを考えると、貪欲なアプローチを使用してその量を作るために必要なコインの最小数を見つけます。

バックトラッキングアルゴリズム

• 「n-queens」の問題を解決して、互いに攻撃することなくn×nチェスボードにn女王を配置します。
• Sudokuソルバーを実装して、部分的に満たされた数独パズルを解決します。

文字列操作アルゴリズム

• 文字列マッチング
• 文字列反転
• パリンドロームチェック
• 2つの文字列が与えられた場合、1つが他の文字列の順列であるかどうかを確認します。
• 「Rabin-Karp」アルゴリズムを実装して、特定のテキストにパターンを見つけます。

ビット操作アルゴリズム

• ビットワイズ操作、配列内の単一の一意の要素を見つけます。
• 1つの数値を除いてすべての数値が2回発生する配列がある場合、単一の一意の数字を見つけます。
• 関数を実装して、整数で1に設定されているビット数をカウントします。

アルゴリズムを分割して征服します

• バイナリ検索、最大サブアレイ合計を見つけます。
• 大型整数の高速乗算のためにKaratsubaアルゴリズムを実装します。
• Divide and Conquerアプローチを使用して、2Dスペースの一連のポイントの中で最も近いポイントを見つけます。

ランダム化されたアルゴリズム

• アレイをランダムに内側にシャッフルします。
• 「ランダム化された選択」アルゴリズムを実装して、配列内のkth最小要素を見つけます。

スライドウィンドウテクニック

• 整数の配列が与えられた場合、サイズkの連続したサブアレイの最大合計を見つけます。
• 指定された文字列にせいぜいk異なる文字を持つ最長のサブストリングを見つけます。

間隔の問題

• 間隔のリストが与えられた場合、重複する間隔をマージします。
• 間隔のリストをスケジュールするために必要な会議室の最小数を見つけます。

試みます

• 効率的な文字列検索と検索のためにTRIEデータ構造を実装します。
• 単語のリストを指定して、Trieを使用して最も長い一般的なプレフィックスを見つけます。
• 特定の単語セットのトライを使用してオートコンプリート機能を実装します。
• 単語のリストを考えると、連結がパリンドロームを形成するようにすべての単語ペアを見つけます。

ハッシュ

• ハッシュ関数、衝突解像度技術、およびユースケースの実装。
• 衝突解像度でハッシュテーブルを実装します（例、チェーンまたはオープンアドレス指定）。
• ハッシュマップを使用して、文字列に最初の非繰り返し文字を見つけます。
• 複数のパターンと一致する文字列にrabin-karpアルゴリズムを実装します。
• 文字周波数のハッシュマップを使用して文字を繰り返すことなく、最長のサブストリングを見つけます。

ヒープ

• Min-HeapsとMax Heapsとそのアプリケーションの実装（例：優先キュー）。
• MinheapまたはMax-Heapをゼロから実装します。
• 一連の要素を考えると、ヒープベースのアプローチを使用してKth最大の要素を見つけます。

マトリックス操作

• m×nマトリックスを与えられた場合、その場所に90度回転させます。
• 0Sおよび1Sのマトリックスが与えられた場合、1の最大平方（最大サイズの正方形サブマトリックス）を見つけ、その面積を返します。

赤黒樹またはAVLの木

• 赤黒またはAVLツリーの挿入および削除操作を実装します。
• 回転を実行して、不均衡なバイナリ検索ツリーのバランスを取ります。

データ構造の実装

• 配列とリスト：配列、リンクリスト、およびその操作の実装。
• スタックとキュー：スタックとキューのデータ構造とそのアプリケーションの実装。
• ハッシュマップ：ハッシュマップを実装し、時間の複雑さを理解します。

ツール

アルゴリズムとデータ構造は、より現実的な設定とより堅牢なテストのために、単純なRESTFUL APIによって公開されます。

• パフォーマンス

  • APIロード：ガトリング、jmeter、ローカスト。

  • マイクロベンチマーク：JMH、Criterium;

  • リソース： htop 、 top 、 vmstat ;

  • 記憶：objgraph、ジャム。

• 行動

  • テスト：不適格、模擬、生成またはプロパティベースのテスト、標準テストライブラリおよびプラクティス。

  • 静的分析：Sonarqube;

  • プロファイリング：フレームグラフ、cprofile、VisualVM、Spring Boot Actuator、JStack;

• コードスタイル

  • 突然変異試験：レイン・ミュータント、ピット、宇宙線。

  • コードカバレッジ：Cloverage、Coverage.py、Jacoco;

  • コードメトリック：Radon、CheckStyle、JQAssistant;

• 観察可能性：プロメテウス、グラファナ。

（ここにリストされているツールは、いくつかの言語に固有の場合があります）