このチートシートは、技術面接の準備に役立ちます。これにより、重要なことをブラッシュアップできます。 実際、これはコンピューターサイエンスコースの内容であり、詳細はありません。
データ構造の基礎
配列
定義：
- ほとんどの場合、ゼロベースのシーケンシャルインデックスに基づいてデータ項目を格納します。
- それは集合論のタプルに基づいています。
- 配列は、最も古く、最も使用されているデータ構造の1つです。
知っておくべきこと：
- 配列はインデックス作成に最適です。 検索、挿入、削除には不向きです（配列の最後でこれを行わない場合）。
- 主な種類は線形配列 、または一次元です。
- サイズは静的です。つまり、線形配列を宣言するとき、固定サイズが指定されます。
- 動的配列は線形配列と似ていますが、追加の要素用にスペースを確保します。
- 動的配列に入力するとき、その内容はより大きな配列にコピーされます。
- 2次元配列には、グリッドまたはネストされた配列のように、2つのインデックスxとyがあります。
効率（「O」は素晴らしい） ：
- インデックス：線形配列-O（1）、動的配列-O（1）。
- 検索：線形配列-O（n）、動的配列-O（n）。
- 最適化された検索：線形配列-O（log n）、動的配列-O（log n）。
- 挿入：線形配列は無効で、動的配列はO（n）です。
リンクリスト
定義：
- データは、他のノードを指すノードに保存されます。
- ノードには、1つのデータ要素と1つのリンク（別のノードへ）が含まれます。
- リンクリストは、あるノードから別のノードへのリンクを使用して、ノードを相互に接続します。
知っておくべきこと：
- リンクリストは、挿入と削除を最適化するように設計されています。 インデックス作成および検索時にゆっくり動作します。
- 二重リンクリストには、以前のノードを参照するノードが含まれます。
- 循環リンクリストは、 テール （最後のノード）がヘッド （最初のノード）を参照する単純なリンクリストです。
- スタックは通常、リンクリストを使用して実装されますが、配列から作成することもできます。
- スタックはLIFOデータ構造です（ 後入れ先出し ）。
- スタックの基礎となるリンクリストの先頭は、アイテムを挿入および削除する唯一の場所です。
- キューは、リンクされたリストまたは配列を使用して実装することもできます。
- キューはFIFOデータ構造（ 先入れ先出し ）です。
- キューは、アイテムが先頭から削除され、末尾に追加される二重リンクリストです。
効率（「O」は素晴らしい）：
- インデックス：リンクリスト-O（n）。
- 検索：リンクリスト-O（n）。
- 最適化された検索：リンクリスト-O（n）。
- 挿入：リンクリスト-O（1）。
ハッシュテーブル
定義：
- データはキーと値のペアとして保存されます。
- ハッシュ関数はキーを受け入れ、そのキーのみに一致する出力を返します。
- このプロセスはハッシュと呼ばれます。入力データと出力データを互いに明確に照合します。
- ハッシュ関数は、データのメモリ内の一意のアドレスを返します。
知っておくべきこと：
- ハッシュ関数は、検索、挿入、削除を最適化するように設計されています。
- ハッシュ衝突は、関数が2つの異なる入力データに対して同じ出力を返す状況です。
- この問題は、すべてのハッシュ関数に共通です。
- 多くの場合、ハッシュテーブルを巨大なサイズに増やすことで解決します。
- ハッシュは、連想配列とデータベースのインデックス作成に重要です。
効率（「O」は素晴らしい）：
- インデックス作成：ハッシュテーブル-O（1）。
- 検索：ハッシュテーブル-O（1）。
- 挿入：ハッシュテーブル-O（1）。
二分木
定義：
- 二分木は、各ノードが最大2つの子を持つデータ構造です。
- 子要素は左と右です。
知っておくべきこと：
- ツリーは、リストとソートを最適化するように設計されています。
- 縮退したツリーは不均衡なツリーです。 それが完全に一方的なものである場合、それは実際にはリンクリストです。
- ツリーは、他のデータ構造と比較して実装が比較的簡単です。
- 二分探索木を作成するために使用されます。
- キー比較を使用して、バイナリツリーは子ノードに向かう方向を決定します。
- 左の子ノードのキーは、親のキーよりも小さいです。
- 右の子ノードのキーは、親のキーよりも大きくなっています。
- 重複するノードは存在できません。
- 上記に関連して、このようなツリーは、バイナリツリーよりもデータ構造として使用されることが多くなります。
効率（「O」は素晴らしい）：
- インデックス：バイナリ検索ツリーはO（log n）です。
- 検索：バイナリ検索ツリーはO（log n）です。
- 挿入：バイナリ検索ツリーはO（log n）です。
検索する
広い検索
定義：
- 幅優先検索は、ツリー（またはグラフ）を検索し、ルートから始まるレベルで参照するアルゴリズムです。
- アルゴリズムは、現在のレベルのすべてのノードを検出します。通常、左から右に移動します。
- このプロセス中に、現在のレベルのノードに関連付けられているすべての子ノードが登録されます。
- 現在のレベルでの検索が完了すると、アルゴリズムは次のレベルの左端のノードに移動します。
- 最下位レベルの最後の右ノードが最後に分析されます。
知っておくべきこと：
- 幅優先検索は、幅が深さを超えるツリーを検索するのに最適です。
- ツリーを歩いている間、アルゴリズムはその情報をキューに保存します。
- キューを使用するため、このような検索方法は、深層検索よりも多くのメモリを消費します。
- キューはメモリを使用してポインタを保持します。
効率（「O」は素晴らしい）：
- 検索：ワイド検索-O（| E | + | V |）。
- Eはエッジ（面？）の数です。
- Vは頂点の数です。
深さ検索
定義：
- 深さ検索は、ルートから開始して深さで最初にツリー（またはグラフ）を検索するアルゴリズムです。
- アルゴリズムはツリーを通過し、左の子ノードに沿ってレベル間を通過して、一番下に到達します。
- ブランチに沿ったパッセージが完了すると、アルゴリズムは戻り、このブランチの適切な子ノードを調べます。 さらに、可能であれば、前のルートの右側にあるノードの左端を選択します。
- ブランチ全体の表示が終了すると、アルゴリズムはルートの右側にあるノードに移動し、再び左の子ノードに沿って最下部に移動します。
- 分析される最後のノードは、右端のノードです（すべての先行ノードの右側にあります）。
知っておくべきこと：
- このアルゴリズムは、深さが幅を超えるツリーの検索に最適です。
- アルゴリズムはスタックを使用します。
- スタックはLIFO構造であるため、ノードポインターを追跡する必要がないため、幅優先検索の場合よりもメモリの消費が少なくなります。
- アルゴリズムが左側に進むことができない場合、スタックの分析を開始します。
効率（「O」は素晴らしい）：
- 検索：深い検索-O（| E | + | V |）。
- Eはエッジ（面？）の数です。
- Vは頂点の数です。
検索の幅と深さの比較
- ツリーのサイズと形状に応じて、検索のタイプを選択します。
- 幅の広い小さな木の場合、幅優先探索を使用します。
- 深くて狭い木には、深さ検索を使用します。
ニュアンス：
- 幅優先検索ではノードとその子に関する情報を格納するためにキューを使用するため、コンピューターで利用できるよりも多くのメモリを使用する可能性があります。 （しかし、ほとんど心配する必要はありません。）
- 非常に深いツリーで深さ検索を適用すると、アルゴリズムが極端に下がってしまう可能性があります。 詳細についてはこちらをご覧ください 。
- 幅検索は循環アルゴリズムです。
- ディープサーチは再帰的なアルゴリズムです。
効率的なソート
ソートのマージ
定義：
- ソートアルゴリズムを使用したデータの比較：
- データセット全体が少なくとも2つのグループに分割されます。
- 値のペアが相互に比較され、最小値が左に移動します。
- すべてのペア内でソートした後、左の2つのペアの左の値が比較されます。 したがって、4つの値のグループが作成されます。左側の2つの最小値、右側の最大値です。
- このプロセスは、1つのセットのみが残るまで繰り返されます。
知っておくべきこと：
- これは、基本的なソートアルゴリズムの1つです。
- データは可能な限り小さなセットに分割され、比較されます。
効率（「O」は素晴らしい）：
- 最適なソートオプション：マージソート-O（n）。
- 中間ソートオプション：マージソート-O（n log n）。
- 最悪のソートオプション：マージソート-O（n log n）。
クイックソート
定義：
- 比較ベースのソートアルゴリズム。
- データセット全体は、中央の要素を選択し、それよりも小さい人をすべて左に移動することにより、半分に分割されます。
- 次に、左側で2つの要素のみが残るまで同じ手順を繰り返し実行します。 その結果、左側がソートされます。
- その後、右側でも同じことが行われます。
- このアルゴリズムは、コンピュータアーキテクチャアーキテクチャでの使用に適しています。
知っておくべきこと：
- ここの「O」の大きさは他の多くのソートアルゴリズムと同じ意味（場合によってはさらに悪い）ですが、実際にはこのアルゴリズムは、たとえばマージによる同じソートの場合、より高速に動作することがよくあります。
- データは、完全にソートされるまで順次半分に分割されます。
効率（「O」は素晴らしい）：
- ベストソートオプション：クイックソート-O（n）。
- 中間ソートオプション：クイックソート-O（n log n）。
- 最悪のソートオプション：クイックソートはO（n ^ 2）です。
バブルソート
定義：
- 比較ベースのソートアルゴリズム。
- 左から右に反復し、各ペア内の値を比較し、最小のものを左に移動します。
- 値が既に移動できなくなるまで、このプロセスが繰り返されます。
知っておくべきこと：
- アルゴリズムの実装は非常に簡単ですが、ここで説明する3つすべての中で最も効率が悪いものです。
- 2つの値を比較し、最小の値を左に移動することにより、アルゴリズムは1つの位置を右に移動します。
効率（「O」は素晴らしい）：
- ベストソート：バブルソート-O（n）。
- 中間ソートオプション：バブルソート-O（n ^ 2）。
- 最悪のソートオプション：バブルソートはO（n ^ 2）です。
マージソートとクイックソートアルゴリズムの比較
- 多くの場合、クイックソートは実際にはより効果的です。
- マージソートは、データセットを可能な限り最小のグループにすぐに分割し、セットを復元して、グループを増分的にソートおよび拡大します。
- クイックソートは、再帰的にソートされるまで、セットを平均値で順番に分割します。
主要なアルゴリズムの種類
再帰的アルゴリズム
定義：
- 定義からわかるように、このアルゴリズムは自分自身を呼び出します。
- 再帰シナリオ -条件ステートメントを使用して再帰をトリガーする場合。
- 基本的なシナリオは、条件ステートメントを使用して再帰を中断する場合です。
知っておくべきこと：
- スタックレベルが深すぎるため、スタックがオーバーフローします。
- 再帰アルゴリズムの実行中に上記のいずれかに直面した場合、すべてが台無しになります。
- これは、エラーのためにベーススクリプトが実行されなかったこと、または問題が深刻なために再帰が中断される前にメモリが不足したことを意味します。
- ベースラインシナリオを達成できるかどうかを知ることは、再帰の適切な使用に不可欠な部分です。
- このようなアルゴリズムは、詳細な検索時によく使用されます。
反復アルゴリズム
定義：
- 反復とは、限られた回数だけ繰り返し呼び出されるアルゴリズムです。 各呼び出しは個別の反復です。
- データセットをインクリメンタルにトラバースするためによく使用されます。
知っておくべきこと：
- 反復は通常、ループ、
for
、while
until
式として表されます。 - 反復とは、データセットを1回だけ通過することです。
- このようなアルゴリズムは、配列の処理によく使用されます。
再帰と反復の比較
- 再帰性と反復性を区別することは困難な場合があります。両方を使用して相互に実装するためです。 ただし：
- 通常、再帰性はより表現力があり、実装が簡単です。
- 反復により消費されるメモリは少なくなります。
- 関数型言語は再帰を使用する傾向があります（Haskellなど）。
- 命令型言語は反復を使用する傾向があります（例：Ruby）。
- Stack Overflowの投稿から詳細情報を入手できます。
配列をトラバースするための擬似コード（これが反復がこのために使用される理由です）
| ----------------------------------|---------------------------------- recursive method (array, n) | iterative method (array) if array[n] is not nil | for n from 0 to size of array print array[n] | print(array[n]) recursive method(array, n+1) | else | exit loop |
貪欲
定義：
- 貪欲は、特定の条件を満たす情報のみを選択するアルゴリズムです。
- 欲張りアルゴリズムには、5つの主要なコンポーネントが含まれます。
- ソリューションの作成に基づいた候補のセット（候補セット）。
- ソリューションに追加する最適な候補を決定する選択機能。
- 候補者が決定に貢献できるかどうかを決定する実行可能性関数。
- 解または部分的な値に値を割り当てる目的関数。
- 完全なソリューションが見つかったことを示すソリューション関数。
知っておくべきこと：
- この問題の最適な解決策を見つけるために、貪欲なアルゴリズムが使用されます。
- それらは通常、処理された情報のごく一部だけが望ましい結果をもたらすデータセットに適用されます。
- 多くの場合、貪欲なアルゴリズムは、他の大規模なアルゴリズムの「O」を減らすのに役立ちます。
配列内の2つの数値の最大の差を見つけるための貪欲なアルゴリズムの擬似コード
greedy algorithm (array) var largest difference = 0 var new difference = find next difference (array[n], array[n+1]) largest difference = new difference if new difference is > largest difference repeat above two steps until all differences have been found return largest difference
このアルゴリズムは、すべての違いを互いに比較する必要がないため、全体の反復を節約できます。