面接でよく聞かれるアルゴリズムに関する18の質問

アルゴリズムは比較的複雑かつ基本的な科目です。プログラミングを学ぶ人は誰でも、多数のアルゴリズムを学びます。統計によると、面接で最もよく聞かれる質問は次の 18 個です。この記事では、これに関心のあるアルゴリズム エンジニアやプログラマーが参考にできるように、基本的な回答をいくつか紹介します。

1) アルゴリズムについて簡単に説明してください。

アルゴリズムとは、いくつかの値を入力として受け取り、対応する出力値を生成する、明確に定義された計算手順です。簡単に言えば、入力を出力に変換する一連の計算ステップです。

2) クイックソートアルゴリズムとは何か説明してください。

クイック ソート アルゴリズムを使用すると、リストまたはクエリをすばやくソートできます。これは、分割交換ソートの原理に基づいています。このタイプのアルゴリズムは、占有するスペースが少なく、ソートするリストを 3 つの主要な部分に分割します。

ピボットより小さい要素

ピボット要素 ピボット（選択された比較値）

ピボットより大きい要素

3) アルゴリズムの時間計算量を説明してください。

アルゴリズムの時間複雑度は、プログラムが完了するまでに必要な合計時間を表し、通常は Big O 表記法を使用して表現されます。

4) 時間計算量に使用される表記法の種類は何ですか?

時間計算量に使用されるシンボルの種類は次のとおりです。

ビッグオー：目標多項式以下を意味します

ビッグオメガ：ターゲット多項式より大きいか等しいことを意味します

ビッグシータ：ターゲット多項式との等式を示す

リトルオー：それは目標多項式より小さいことを意味します

リトルオメガ：目標多項式より大きいことを意味します

5) バイナリ検索の仕組みを説明してください。

バイナリ検索では、まず配列の中央の位置を決定し、次に検索する値と配列の中央の位置の値を比較します。配列の中央の値より小さい場合は、検索する値は中央の値より前にある必要があります。このようにして、最終結果が得られるまで検索範囲を継続的に絞り込んでいきます。

6) バイナリ検索を使用してリンクリストを検索できるかどうかを説明してください。

リンクリストではランダムアクセスが許容されないため、O(1) 時間で中間の要素に到達することはできません。したがって、バイナリ検索はリンクリストでは不可能です (順次リンクリストまたはソートされたリンクリストでは使用できます)。

7) ヒープソートとは何か説明してください。

ヒープソートは選択ソートの改良版と見ることができ、比較ベースのソートアルゴリズムとして定義できます。入力を未ソート領域とソート領域に分割し、最小の要素を継続的に削除してソート領域に移動することで、未ソート領域を縮小します。

8) スキップリストとは何ですか?

スキップ リストは、アルゴリズムがシンボル テーブルまたは辞書内の要素を検索、削除、挿入できるようにするデータ構造化方法です。スキップ リストでは、各要素はノードによって表されます。検索関数は、キーに関連付けられた値の内容を返します。挿入操作は指定されたキーを新しい値に関連付け、削除操作は指定されたキーを削除します。

9) 挿入ソートアルゴリズムの空間計算量とは何か説明してください。

挿入ソートはインプレースソートアルゴリズムであり、追加のストレージスペースを必要としないか、または少量のストレージスペースしか必要としません。挿入ソートの場合、初期データの外側にリスト要素を 1 つだけ保存すればよく、空間計算量は O(1) になります。

10) 「ハッシュ アルゴリズム」とは何か、また何に使用されるのかを説明してください。

「ハッシュ アルゴリズム」は、任意の長さの文字列を受け取り、それを一意の固定長文字列に縮小するハッシュ関数です。パスワードの有効性、メッセージとデータの整合性、その他多くの暗号化システムに使用されます。

11) リンクリストに循環があるかどうかを確認する方法を説明してください。

リンク リストにループがあるかどうかを確認するには、2 つのポインターを使用する方法を採用します。 2 つのポインタを保持し、2 つのノードを処理した後で 1 つずつ増分し、各ノードを処理した後でポインタが同じノードを指す状況が発生する場合、これはリンク リストにサイクルがある場合にのみ発生します。

12) 暗号化アルゴリズムの仕組みを説明してください。

暗号化とは、プレーンテキストを暗号文と呼ばれる暗号文形式に変換するプロセスです。テキストを変換するために、アルゴリズムは「キー」と呼ばれる一連のビットを使用して計算を実行します。キーが大きくなるほど、暗号文を作成するための潜在的なパターンの数が増えます。ほとんどの暗号化アルゴリズムでは、長さが約 64 ～ 128 ビットの固定入力ブロックが使用されますが、ストリーミング アプローチを使用するアルゴリズムもあります。

13) 一般的に使用されている暗号化アルゴリズムをいくつか挙げてください。

一般的に使用される暗号化アルゴリズムは次のとおりです。

• 3ウェイ
• フグ
• キャスト
• CMEA
• ゴスト
• DES とトリプル DES
• アイデア
• LOKI 他

14) アルゴリズムの最良のケースと最悪のケースの違いは何ですか?

最良のケース: アルゴリズムの最良のケースは、アルゴリズムが最良のパフォーマンスを発揮するデータ配置として説明されます。たとえば、バイナリ検索を実行する場合、ターゲット値が検索対象のデータ センター内にある場合、これが最良のケースであり、最良のケースの時間計算量は 0 です。

最悪のシナリオ: 特定のアルゴリズムで起こり得る最悪の入力シナリオ。たとえば、クイックソートでは、キー値のサブリストの最小または最小の要素を選択すると、最悪のシナリオが発生し、時間の計算量がすぐに O(n2) に低下します。

15) 基数ソートアルゴリズムとは何か説明してください。

「バケット方式」とも呼ばれる基数ソートでは、数値を比較し、異なる「バケット」に割り当てることで要素をソートします。これは線形ソートアルゴリズムの 1 つです。

16) 再帰アルゴリズムとは何か説明してください。

再帰アルゴリズムは、複雑な問題を小さなサブ問題に分割し、サブ問題が簡単に解決できるほど小さくなるまで、そのサブ問題を解く方法です。通常、自分自身を呼び出す関数が含まれます。

17) 再帰アルゴリズムの 3 つの法則は何ですか?

すべての再帰アルゴリズムは3つのルールに従う必要がある

再帰アルゴリズムには基点が必要です

再帰アルゴリズムは、基点に向かう状態変化プロセスを持つ必要がある。

再帰アルゴリズムは自分自身を呼び出す必要がある

18) バブルソートアルゴリズムとは何か説明してください。

バブルソートアルゴリズムは、シンキングソートとも呼ばれます。このタイプのソートでは、ソート対象のリストの隣接する要素が互いに比較されます。順序が間違っている場合は、値が入れ替えられ、最終結果が「表面化」するまで正しい順序に配置されます。