面接で尋ねられる可能性のあること: Java のデータ構造。パート1

こんにちは！どう考えても、技術入社面接に合格しなければ開発者になることはできません。 Java に関連する技術は数多くあり、すべてを学ぶのは不可能です。原則として、プロジェクトにとって重要なフレームワークで優れた経験を持つ開発者を探している場合にのみ、面接中に具体的なことを尋ねられます。そうであれば、あなたはこのフレームワークを全速力で通過することになることは間違いありません。しかし、私たちは今、すべての Java 開発者が知っておくべき基礎について話しています。すべてが始まる古典的な知識について。今日は、 Java のインタビュー データ構造の基本的なトピックの 1 つについて触れたいと思います。ですから、無駄なことをするのではなく、始めてみましょう。面接中にこのトピックに関して尋ねられる可能性のある質問のリストを見つけてください。

1. データ構造について少し教えてください

データ構造は、特定の方法で構造化された情報を含むデータ ストアです。これらの構造は、特定の操作を効率的に実行できるように設計されています。データ構造の典型的な例は次のとおりです。

• 配列、
• スタック、
• 行列、
• 関連リスト、
• グラフ、
• 木、
• プレフィックスツリー、
• ハッシュ表。

詳細については、こちらとこちらをご覧ください。データはプログラムの重要なコンポーネントであり、構造により、このデータを特定の明確に構造化された形式で保存できます。アプリケーションが何をするとしても、この側面は常にアプリケーションに存在します。Web ストアの場合は製品に関する情報が保存され、ソーシャル ネットワークの場合はユーザーとファイルに関するデータなどが保存されます。

2. 配列について何を知っていますか?

配列とは、同じ型の値をあらかじめ指定された数だけ格納するための入れ物です。文字列値を含む配列を作成する例:

String[] strArray = {"Java","is","the","best","language"};

配列を作成するとき、そのすべての要素にメモリが割り当てられます。最初に指定した要素のセルが多いほど、より多くのメモリが割り当てられます。特定の数のセルを含む空の配列が作成されると、配列のすべての要素にデフォルト値が割り当てられます。例えば：

int[] arr = new int[10];

したがって、ブール型 の要素を持つ配列の場合、初期 (デフォルト) 値はfalseになり、数値 - 0、char型の要素を持つ配列の場合- \u0000になります。クラス型 (オブジェクト) の配列の場合 - null (空の文字列 - ""ではなく 、具体的にはnull )。つまり、上記の例では、arr配列の値は直接指定されるまですべて 0 になります。コレクションとは異なり、配列は動的ではありません。特定のサイズの配列が宣言されると、サイズ自体を変更することはできません。新しい要素を配列に追加するには、新しい大きな配列を作成し、古い配列からすべての要素をその配列にコピーする必要があります (これが ArrayList の仕組みです)。誰もが知っているわけではないが、非常にうまく捕まえることができるポイントが 1 つあります。Java には、単純な型と本格的なオブジェクトへの参照という2 つのタイプの変数があります。配列は次のうちどれですか? たとえば、次のようになります。

int[] arr = new int[10];

すべてが単純であるように見えます。これらは 10 個のint要素です。つまり、これは単純なタイプと言えるでしょうか？たとえそれがどのようなものであっても。 Java では、配列は動的に作成されるオブジェクトであり、オブジェクト型の変数に割り当てることができます。 Object クラスのすべてのメソッドは配列に対して呼び出すことができます。したがって、次のように書くこともできます。

Object arr = new int[]{7,5,4,3};
System.out.println(arr.toString());

コンソールに出力すると、次のような結果が得られる場合があります。 Java の配列の機能の詳細については、Java 配列に関するこの記事を参照してください。知識を強化するために、このコレクションからいくつかの問題を解くことができます。

3. コレクションの階層を説明する

コレクションは、データを操作するときに柔軟性が必要な状況で使用されます。コレクションでは、要素の追加、要素の削除、その他多くの操作を実行できます。Java にはさまざまな実装があり、現在の状況に適したコレクションを選択するだけで済みます。通常、Collectionインターフェースについて言及するときは、その実装のいくつかとMapとの関係を列挙するよう求められます。さて、調べてみましょう。したがって、コレクションとマップはデータ構造の 2 つの異なる階層です。Collection階層の様子: Collectionインターフェイスは、基本メソッドのリストを備えたキートップ リンクであり、そこから 3 つの基本タイプのデータ構造 ( Set、List、Queue )が生成されます。 Set<T> は、各オブジェクトが一意であるオブジェクトのコレクションを表すインターフェイスです。 List<T>は、リストと呼ばれるオブジェクトの順序付けされたシーケンスを表すインターフェイスです。 Queue<T> は、キュー (要素の順次ストレージ) として編成される構造を担当するインターフェイスです。前述したように、Mapは別の階層です。Map <K, V> は、要素がキーと値のペアとして含まれる辞書を表すインターフェイスです。さらに、すべてのキー (K) はMapオブジェクト内で一意です。このタイプのコレクションでは、キー (オブジェクトの一意の識別子) がわかっていれば、要素を見つけやすくなります。

4. セットについて何を知っていますか?

前述したように、このコレクションには多くのユニークな要素が含まれています。つまり、同じオブジェクトをJava Set内に複数回出現させることはできません。また、番号 (インデックス) によってSetから要素を抽出することはできず、総当たりでしか抽出できないことも指摘しておきます。重要なことは、Set の実装が異なれば、データの構造化方法も異なるということです。具体的な実装については今後検討していきます。したがって、 Set : HashSetの主な実装は、ハッシュ テーブルに基づくセットであり、検索に役立ちます。ハッシュ関数を使用すると、検索および挿入時のパフォーマンスが向上します。要素の数に関係なく、一般に挿入と検索 (場合によっては削除) は一定時間 - O(1) に近い時間で実行されます。ハッシュ関数については後ほど詳しく見ていきます。HashSet にはHashMap が含まれており、ここですべての魔法が行われることにも注意してください。Java の HashSet に関する詳細な記事は次のとおりです。 LinkedHashSet - このクラスは、新しいメソッドを追加せずにHashSetを拡張します。LinkedListと同様に、このクラスは、セットの要素のリンクされたリストを、挿入された順序で維持します。これにより、特定のSet実装内で必要な順序を整理できます。TreeSetクラスは、要素を格納する構造を編成するために、赤黒ツリーに基づくセットを作成します。言い換えれば、特定のセット内で要素を昇順に並べ替えることができます。Integerなど、「ボックス」の標準オブジェクトを使用する場合は、整数のセットを昇順に並べるために何もする必要はありません。

TreeSet set = new TreeSet<>();
set.add(4);
set.add(2);
set.add(3);
set.add(1);

System.out.println(set);

コンソールでは次の出力が得られます。 つまり、このセットでは、数値がソートされた形式で格納されます。TreeSetでString要素を使用すると、それらはアルファベット順にソートされます。では、標準 (カスタム) クラスがある場合はどうなるでしょうか? このクラスのオブジェクトはどのようにTreeSetを構成するのでしょうか? このSetに任意のオブジェクトを割り当てようとすると、次のようになります。

TreeSet set = new TreeSet<>();
set.add(new Cat(4, "Murzik"));
set.add(new Cat(2, "Barsik"));
set.add(new Cat(3, "Гарфилд"));

System.out.println(set);

TreeSet はこのタイプのオブジェクトを並べ替える方法を知らないため、 ClassCastException を 受け取ります。この場合、カスタム オブジェクトでComparableインターフェイスとそのCompareToメソッドを実装する必要があります。

public class Cat implements Comparable {
    int age;
    String name;

   public Cat(int age, String name) {
       this.age = age;
       this.name = name;
   }

   @Override
   public int compareTo(Cat cat) {
       return age > cat.age ? 1 : -1;
   }

   @Override
   public String toString() {
       return "Cat{" +
               "age=" + age +
               ", name='" + name + '\'' +
               '}';
   }
}

お気づきのとおり、compareToメソッドはintを返します。

• 現在の (この) オブジェクトが大きいとみなされる場合は 1。
• 現在のオブジェクトが引数として渡されたオブジェクトよりも小さいとみなされる場合は -1。
• オブジェクトが等しい場合は 0 (この場合は使用しません)。

この場合、TreeSetは正しく動作し、結果が表示されます。 もう 1 つの方法は、コンパレータインターフェイスとその比較メソッド を実装する別の並べ替えクラスを作成することです。

public class CatComparator implements Comparator {

   @Override
   public int compare(Cat o1, Cat o2) {
       return o1.age > o2.age ? 1 : -1;
   }
}

この場合、これを使用するには、このクラスのオブジェクトをTreeSetコンストラクターに設定する必要があります。

TreeSet set = new TreeSet<>(new CatComparator());

この後、TreeSetに含まれるCatクラスのすべてのオブジェクトが、 Cat Comparatorクラスを使用して並べ替えられます。Java のComparatorとComparableについて詳しくは、この記事を参照してください。

5. キューについて教えてください

キューは、要素を順番に格納するデータ構造であるキューとして編成された構造を担当するインターフェイスです。たとえば、人の列から最初に入る人は他の人より早く到着した人になり、最後に入る人は他の人より遅く到着した人になります。この方法はFIFO、つまり先入れ先出しと呼ばれます。独自のキューメソッドは、最初または最後の要素の操作に重点を置いています。次に例を示します。

• add and offer - キューの最後に要素を挿入します。
• 削除- このキューのヘッダーを取得して削除します。
• Peak - キューヘッダーを取得しますが、削除しません。

パート2