Apa yang mungkin mereka tanyakan saat wawancara: Struktur data di Java. Bagian 1

Halo! Tidak peduli bagaimana Anda melihatnya, Anda tidak bisa menjadi seorang pengembang tanpa berhasil melewati wawancara masuk teknis. Ada banyak teknologi yang berhubungan dengan Java, dan tidak mungkin mempelajari semuanya. Biasanya, sesuatu yang spesifik ditanyakan selama wawancara hanya jika mereka mencari pengembang dengan pengalaman baik dalam beberapa kerangka kerja yang penting untuk proyek tersebut. Jika demikian, Anda akan didorong melalui kerangka ini dengan kecepatan penuh, Anda tidak ragu. Namun sekarang kita berbicara tentang dasar yang harus diketahui oleh setiap pengembang Java. Tentang pengetahuan klasik dari mana semuanya dimulai. Hari ini saya ingin menyentuh salah satu topik mendasar dari setiap wawancara - struktur data di Java . Jadi, daripada bertele-tele, mari kita mulai. Temukan daftar pertanyaan yang mungkin ditanyakan kepada Anda tentang topik ini selama wawancara.

1. Ceritakan sedikit tentang struktur data

Struktur data adalah penyimpanan data yang berisi informasi yang terstruktur dengan cara tertentu. Struktur ini dirancang untuk kinerja operasi tertentu yang efisien. Contoh umum struktur data adalah:

• array,
• tumpukan,
• antrian,
• daftar terkait,
• grafik,
• pohon,
• pohon awalan,
• tabel hash.

Anda dapat mengetahui lebih banyak tentang mereka di sini dan di sini . Data adalah komponen kunci dalam sebuah program, dan struktur memungkinkan data ini disimpan dalam bentuk yang spesifik dan terstruktur dengan jelas. Apapun yang dilakukan aplikasi Anda, aspek ini akan selalu ada di dalamnya: jika itu adalah toko web, maka informasi tentang produk akan disimpan, jika itu adalah jejaring sosial, data tentang pengguna dan file, dan seterusnya.

2. Apa yang anda ketahui tentang Array?

Array adalah wadah untuk menyimpan nilai-nilai yang bertipe sama, yang jumlahnya telah ditentukan sebelumnya. Contoh pembuatan array dengan nilai string:

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

Saat membuat array, memori dialokasikan untuk semua elemennya: semakin banyak sel untuk elemen yang ditentukan pada awalnya, semakin banyak memori yang akan dialokasikan. Jika array kosong dengan jumlah sel tertentu dibuat, maka semua elemen array akan diberi nilai default. Misalnya:

int[] arr = new int[10];

Jadi, untuk array dengan elemen bertipe boolean , nilai awal ( default ) akan menjadi false , untuk array dengan nilai numerik - 0, dengan elemen bertipe char - \u0000 . Untuk array tipe kelas (objek) - null (bukan string kosong - “” tetapi secara khusus null ). Artinya, pada contoh di atas, semua nilai array arr akan menjadi 0 hingga ditentukan secara langsung. Berbeda dengan koleksi, array tidak dinamis. Setelah array dengan ukuran tertentu dideklarasikan, ukurannya tidak dapat diubah. Untuk menambahkan elemen baru ke array, Anda perlu membuat array baru yang lebih besar dan menyalin semua elemen dari array lama ke dalamnya (begitulah cara kerja ArrayList). Ada satu hal yang tidak diketahui semua orang dan Anda bisa memahaminya dengan baik. Ada dua tipe variabel di Java - tipe sederhana dan referensi ke objek lengkap. Manakah dari berikut ini yang merupakan array? Misalnya, di sini:

int[] arr = new int[10];

Tampaknya semuanya sederhana - ini adalah 10 elemen int . Jadi, dapatkah kita mengatakan bahwa ini adalah tipe yang sederhana? Tidak peduli bagaimana keadaannya. Di Java, array adalah objek, dibuat secara dinamis dan dapat ditugaskan ke variabel bertipe Object. Semua metode kelas Object dapat dipanggil pada array. Jadi kita bahkan bisa menulis:

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

Saat mengeluarkan ke konsol Anda mungkin mendapatkan sesuatu seperti: Baca selengkapnya tentang fitur-fitur array di Java di artikel tentang Java Array ini . Untuk mengkonsolidasikan pengetahuan Anda, Anda dapat memecahkan beberapa masalah dari koleksi ini .

3. Menjelaskan hierarki koleksi

Koleksi digunakan dalam situasi di mana Anda memerlukan fleksibilitas saat bekerja dengan data. Koleksi dapat menambahkan elemen, menghapus elemen, dan melakukan banyak operasi lainnya. Ada banyak implementasi berbeda di Java, dan kita hanya perlu memilih koleksi yang tepat untuk situasi saat ini. Biasanya, ketika Anda menyebutkan antarmuka Collection , Anda diminta untuk membuat daftar beberapa implementasinya dan hubungannya dengan Map . Baiklah, mari kita cari tahu. Jadi, Koleksi dan Peta adalah dua hierarki berbeda untuk struktur data. Seperti apa hierarki Koleksi : Antarmuka Koleksi adalah tautan teratas utama dengan daftar metode dasar, yang menjadi sumber tiga tipe dasar struktur data - Set , Daftar , Antrean . Set<T> adalah antarmuka yang mewakili kumpulan objek yang setiap objeknya unik. List<T> adalah antarmuka yang mewakili urutan objek yang disebut daftar. Queue<T> adalah antarmuka yang bertanggung jawab atas struktur yang diatur sebagai antrian (penyimpanan elemen secara berurutan). Seperti disebutkan sebelumnya, Map adalah hierarki terpisah: Map<K, V> adalah antarmuka yang mewakili kamus yang elemennya terkandung sebagai pasangan nilai kunci. Selain itu, semua kunci (K) bersifat unik di dalam objek Map . Koleksi jenis ini memudahkan untuk menemukan suatu elemen jika kita mengetahui kunci – pengenal unik objek tersebut.

4. Apa yang kamu ketahui tentang Set?

Seperti disebutkan sebelumnya, koleksi ini menampilkan banyak elemen unik. Dengan kata lain, objek yang sama tidak boleh muncul lebih dari satu kali dalam satu Java Set . Saya juga ingin menunjukkan bahwa kita tidak dapat mengekstraksi elemen dari Kumpulan berdasarkan angka (indeks) - hanya dengan kekerasan. Yang penting adalah implementasi Set yang berbeda memiliki cara berbeda dalam menyusun data. Kami akan mempertimbangkan implementasi spesifik lebih lanjut. Jadi, implementasi utama dari Set : HashSet adalah himpunan yang didasarkan pada tabel hash, yang pada gilirannya membantu pencarian. Menggunakan fungsi hash yang meningkatkan kinerja selama pencarian dan penyisipan. Berapapun jumlah elemennya, secara umum, penyisipan dan pencarian (terkadang penghapusan) dilakukan dalam waktu yang mendekati konstan - O(1). Kita akan melihat fungsi hash lebih detail nanti. Saya juga ingin mencatat bahwa HashSet berisi HashMap , di situlah semua keajaiban terjadi. Berikut ini artikel detail tentang HashSet di Java . LinkedHashSet - kelas ini memperluas HashSet tanpa menambahkan metode baru. Seperti LinkedList , kelas ini memelihara daftar tertaut dari elemen-elemen suatu himpunan sesuai urutan penyisipannya. Hal ini memungkinkan Anda untuk mengatur urutan yang diperlukan dalam implementasi Set tertentu . Kelas TreeSet membuat kumpulan yang didasarkan pada pohon merah-hitam untuk mengatur struktur penyimpanan elemen. Dengan kata lain, dalam himpunan tertentu kita dapat mengurutkan elemen-elemen dalam urutan menaik. Jika kita menggunakan beberapa objek standar dari “kotak”, misalnya Integer , maka kita tidak perlu melakukan apa pun untuk menyusun himpunan Integer dalam urutan menaik:

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

System.out.println(set);

Dan di konsol kita akan mendapatkan output: Artinya, pada himpunan ini angka-angkanya disimpan dalam bentuk yang diurutkan. Jika kita menggunakan elemen String dalam TreeSet , elemen tersebut akan diurutkan, tetapi berdasarkan abjad. Nah, bagaimana jika kita memiliki kelas standar (custom)? Bagaimana objek kelas ini menyusun TreeSet ? Jika kita mencoba menetapkan objek sembarang ke Set ini :

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);

Kami akan menerima ClassCastException karena TreeSet tidak mengetahui cara mengurutkan objek jenis ini. Dalam hal ini, kita memerlukan objek khusus untuk mengimplementasikan antarmuka Comparable dan metode CompareTo -nya :

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 + '\'' +
               '}';
   }
}

Seperti yang Anda perhatikan, metode CompareTo mengembalikan int :

• 1 jika benda (ini) saat ini dianggap besar;
• -1 jika objek saat ini dianggap lebih kecil dari objek yang dijadikan argumen;
• 0 jika objeknya sama (kami tidak menggunakan ini dalam kasus ini).

Dalam hal ini, TreeSet kami akan berfungsi dengan benar dan menampilkan hasilnya: Cara lain adalah dengan membuat kelas pengurutan terpisah yang mengimplementasikan antarmuka pembanding dan metode perbandingannya :

public class CatComparator implements Comparator {

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

Dalam hal ini, untuk menggunakannya, kita harus menyetel objek kelas ini ke konstruktor TreeSet :

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

Setelah ini, semua objek kelas Cat yang termasuk dalam TreeSet akan diurutkan menggunakan kelas Cat Comparator . Anda dapat mempelajari lebih lanjut tentang Comparator dan Comparable di Java dari artikel ini .

5. Beritahu kami tentang Antrian

Antrian adalah antarmuka yang bertanggung jawab atas struktur yang disusun sebagai antrian - struktur data yang menyimpan elemen secara berurutan. Misalnya, dari antrian orang, orang yang masuk pertama adalah orang yang datang lebih awal dari yang lain, dan orang terakhir adalah orang yang datang lebih lambat dari orang lain. Cara ini disebut FIFO , yaitu First in First Out . Metode Antrian Unik fokus bekerja dengan elemen pertama atau terakhir, misalnya:

• tambahkan dan tawarkan - menyisipkan elemen di akhir antrian,
• hapus - mengambil dan menghapus header antrian ini,
• mengintip - Mengambil tetapi tidak menghapus header antrian.

BAGIAN 2