Analisis tanya jawab dari wawancara untuk pengembang Java. Bagian 9

Kembang api! Menjadi seorang programmer tidaklah mudah. Anda perlu terus belajar, selalu mempelajari sesuatu yang baru. Namun, seperti dalam bisnis lainnya, hal tersulit adalah memulai, mengambil langkah pertama menuju tujuan Anda. Dan sejak Anda duduk di situs ini dan membaca artikel ini, Anda telah menyelesaikan langkah pertama. Ini berarti bahwa sekarang Anda perlu bergerak dengan sengaja menuju tujuan Anda, tanpa memperlambat atau mematikannya. Jika saya memahaminya dengan benar, tujuan Anda adalah menjadi pengembang Java atau menambah pengetahuan Anda jika Anda salah satunya. Jika ya, maka Anda berada di tempat yang tepat, karena kami akan terus menganalisis daftar lengkap 250+ pertanyaan wawancara pengembang Java. Ayo lanjutkan!

Koleksi

84. Beritahu kami tentang iterator dan kegunaannya

Koleksi adalah salah satu topik favorit dalam setiap wawancara pengembang Java, dan ketika berbicara tentang hierarki koleksi, kandidat sering kali mengatakan bahwa itu dimulai dengan antarmuka Koleksi . Tapi ini tidak benar, karena di atas antarmuka ini ada satu lagi - Iterable . Antarmuka ini mewakili metode iterator() , yang memungkinkan Anda memanggil objek Iterator untuk koleksi saat ini. Dan apa sebenarnya objek Iterator ini ? Iterator adalah objek yang menyediakan kemampuan untuk menelusuri koleksi dan mengulangi elemen tanpa pengguna perlu mengetahui implementasi koleksi tertentu. Artinya, ini adalah semacam penunjuk ke elemen-elemen koleksi, yang seolah-olah terlihat pada suatu tempat tertentu di dalamnya. Iterator memiliki metode berikut:

• hasNext() - mengembalikan nilai true jika ada elemen yang terletak setelah pointer (metode ini memungkinkan Anda mengetahui apakah akhir koleksi telah tercapai);
• next() - mengembalikan elemen berikutnya setelah pointer. Jika tidak ada, NoSuchElementException akan dilempar . Artinya, sebelum menggunakan metode ini, lebih baik memastikan bahwa elemen tersebut ada - menggunakan hasNext() ;
• hapus() - menghapus elemen terakhir yang diterima dari koleksi menggunakan metode next() . Jika next() belum pernah dipanggil sebelum delete() dipanggil, pengecualian akan diberikan - IllegalStateException ;
• forEachRemaining(<Consumer>) - melakukan tindakan yang diteruskan dengan setiap elemen koleksi (metode ini muncul di Java 8).

Berikut adalah contoh kecil dari iterasi melalui daftar dan menghapus semua elemennya menggunakan metode iterator yang dibahas:

List<String> list = new ArrayList<>();
list.add("Hello ");
list.add("World, ");
list.add("It's ");
list.add("Amigo!");
Iterator iterator = list.iterator();

while(iterator.hasNext()) {
   iterator.next();
   iterator.remove();
}
System.out.println(list.size());

Konsol akan menampilkan: Artinya penghapusan elemen berhasil. Setelah kita memiliki iterator, kita bisa menggunakan metode untuk mencetak semua elemen ke layar:

iterator.forEachRemaining(x -> System.out.print(x));

Namun setelah ini, iterator akan menjadi tidak cocok untuk digunakan lebih lanjut, karena iterator akan melintasi seluruh daftar, dan iterator biasa tidak memiliki metode untuk menelusuri kembali. Di sini kita secara bertahap mendekati LinkedList , yaitu metode listIterator() , yang mengembalikan tipe iterator yang dimodernisasi - ListIterator . Selain metode iterator biasa (standar), metode ini juga memiliki metode tambahan:

• add(<Element>) - memasukkan elemen baru ke dalam daftar;
• hasPrevious() - mengembalikan nilai true jika ada elemen yang terletak sebelum pointer (apakah ada elemen sebelumnya);
• nextIndex() - mengembalikan indeks dalam daftar elemen berikutnya setelah penunjuk;
• sebelumnya() - mengembalikan elemen sebelumnya (hingga penunjuk);
• previousIndex() - mengembalikan indeks elemen sebelumnya;
• set(<Element>) - Menggantikan elemen terakhir yang dikembalikan oleh metode next() atau previous() .

Seperti yang Anda lihat, fungsi iterator ini jauh lebih menarik: memungkinkan Anda bergerak ke dua arah dan membebaskan tangan Anda saat bekerja dengan elemen. Selain itu, ketika orang berbicara tentang iterator, terkadang yang mereka maksud adalah polanya sendiri. Untuk menghindari masalah dan membicarakannya dengan meyakinkan, baca artikel tentang pola Iterator ini .

85. Apa hierarki koleksi di Java Collection Framework?

Ada dua hierarki koleksi di Java. Hirarki pertama adalah hierarki Koleksi itu sendiri dengan struktur sebagai berikut: Hirarki tersebut, pada gilirannya, dibagi menjadi beberapa subkoleksi berikut:

• Himpunan adalah antarmuka yang mendeskripsikan struktur data sebagai himpunan yang berisi elemen unik yang tidak berurutan (tidak berulang). Antarmuka memiliki implementasi standar - TreeSet , HashSet dan LinkedHashSet .
• Daftar adalah antarmuka yang menggambarkan struktur data yang menyimpan urutan objek yang diurutkan. Instance yang terdapat dalam Daftar dapat disisipkan dan dihapus berdasarkan indeksnya dalam koleksi ini (analog dengan array, tetapi dengan pengubahan ukuran dinamis). Antarmuka memiliki implementasi standar - ArrayList , Vector ( dianggap usang dan tidak benar-benar digunakan ) dan LinkedList .
• Queue merupakan antarmuka yang menggambarkan struktur data yang menyimpan elemen dalam bentuk antrian yang mengikuti aturan FIFO - First In First Out . Antarmukanya memiliki implementasi standar berikut: LinkedList (ya, ini juga mengimplementasikan Queue ) dan PriotityQueue .

Hirarki koleksi yang kedua adalah Map , yang memiliki struktur sebagai berikut: Dalam koleksi ini tidak ada pembagian menjadi subkoleksi (karena hierarki Map itu sendiri adalah sesuatu seperti subkoleksi, tetapi terletak terpisah). Implementasi Peta Standar adalah Hashtable (dianggap tidak digunakan lagi), LinkedHashMap , dan TreeMap . Sebenarnya, ketika ditanya tentang Collection , biasanya yang dimaksud adalah kedua hierarki tersebut.

86. Apa struktur internal dari ArrayList?

ArrayList mirip dengan array, tetapi dengan kemampuan untuk berkembang secara dinamis. Apa artinya? Faktanya adalah ArrayList bekerja berdasarkan array biasa, yaitu menyimpan elemen dalam array internal (ukuran defaultnya adalah 10 sel). Ketika array internal penuh, array baru dibuat, yang ukurannya ditentukan oleh rumus:

<размерТекущегоМассива> * 3 / 2  + 1

Artinya, jika ukuran array kita adalah 10, maka ukuran array baru adalah: 10 * 3 / 2 + 1 = 16. Selanjutnya, semua nilai dari array pertama (lama) disalin ke dalamnya menggunakan metode System.arraycopy () asli , dan array pertama dihapus. Sebenarnya, ini adalah bagaimana ekstensibilitas dinamis dari ArrayList diimplementasikan . Mari kita lihat metode ArrayList yang paling sering digunakan : 1. add(<Element>) - menambahkan elemen ke akhir array (ke sel kosong terakhir), dan pertama-tama periksa apakah ada ruang dalam array ini. Jika tidak ada, array baru dibuat di mana elemen-elemen tersebut disalin. Kompleksitas logaritmik dari operasi ini adalah O(1). Ada metode serupa - add(<Index>,<Element>) . Itu menambahkan elemen bukan ke akhir daftar (array), tetapi ke sel tertentu dengan indeks yang muncul sebagai argumen. Dalam hal ini, kompleksitas logaritmik akan berbeda tergantung di mana ia ditambahkan:

• jika ini kira-kira di awal daftar, kompleksitas logaritmiknya akan mendekati O(N), karena semua elemen yang terletak di sebelah kanan elemen baru harus dipindahkan satu sel ke kanan;
• jika elemen disisipkan di tengah - O(N/2) karena kita hanya perlu memindahkan separuh elemen daftar satu sel ke kanan.

Artinya, kompleksitas logaritmik metode ini berkisar dari O(N) hingga O(1) tergantung di mana elemen dimasukkan. 2. set(<Index>,<Element>) - menulis elemen ke posisi yang ditentukan dalam daftar. Jika sudah ada elemen pada posisi itu, timpa elemen tersebut. Kompleksitas logaritmik dari operasi ini adalah O(1), karena tidak ada pergeseran: hanya mencari berdasarkan indeks dalam array, yang seperti kita ingat, memiliki kompleksitas O(1), dan menulis elemennya. 3. hapus(<index>) - menghapus elemen berdasarkan indeksnya di array internal. Saat menghapus item yang tidak ada di akhir daftar, Anda harus memindahkan semua item di sebelah kanannya satu sel ke kiri untuk menutup celah yang tersisa setelah menghapus item tersebut. Oleh karena itu, kompleksitas logaritmik akan sama dengan add(<Index>,<Element>) jika elemen berada di tengah - O(N/2) - karena Anda perlu menggeser separuh elemen satu ke kiri. Oleh karena itu, jika itu di awal - O(N). Nah, kalau di akhir O(1), tidak perlu dipindahkan apa pun. Bagi mereka yang ingin mempelajari topik ini lebih dalam, saya akan meninggalkan tautan ini ke artikel dengan analisis kelas ArrayList .

87. Apa struktur internal LinkedList?

Jika ArrayList berisi elemen dalam array internal, maka LinkedList berbentuk daftar tertaut ganda. Artinya setiap elemen berisi link ke elemen sebelumnya ( previous ) dan elemen berikutnya ( next ). Elemen pertama tidak memiliki link ke elemen sebelumnya (ini adalah elemen pertama), namun dianggap sebagai bagian atas daftar, dan LinkedList memiliki link langsung ke elemen tersebut. Elemen terakhir, pada kenyataannya, tidak memiliki elemen berikutnya, ini adalah bagian akhir dari daftar, dan oleh karena itu terdapat tautan langsung ke elemen tersebut di LinkedList itu sendiri . Oleh karena itu, kompleksitas logaritmik dalam mengakses bagian awal atau akhir suatu daftar adalah O(1). Di ArrayList, ketika daftar bertambah, array internal bertambah, tetapi di sini semuanya terjadi lebih sederhana - ketika elemen ditambahkan, beberapa tautan berubah begitu saja. Mari kita lihat beberapa metode LinkedlList yang paling sering digunakan : 1. add(<Element>) - menambahkan di akhir daftar, mis. setelah elemen terakhir (5) tautan ke elemen baru akan ditambahkan sebagai next . Elemen baru akan memiliki link ke elemen terakhir (5) seperti elemen sebelumnya . Kompleksitas logaritmik dari operasi semacam itu adalah O(1), karena hanya tautan ke elemen terakhir yang diperlukan, dan seperti yang Anda ingat, ekornya memiliki tautan langsung dari LinkedList dan kompleksitas logaritmik untuk mengaksesnya minimal. 2. add(<Index>,<Element>) - menambahkan elemen berdasarkan indeks. Saat menambahkan elemen, misalnya, ke tengah daftar, elemen dari kepala dan ekor (di kedua sisi) diiterasi terlebih dahulu hingga tempat yang diinginkan ditemukan. Jika kita ingin menyisipkan elemen di antara elemen ketiga dan keempat (pada gambar di atas), maka saat mencari tempat yang tepat, link berikutnya dari elemen ketiga sudah mengarah ke elemen baru. Untuk yang baru, link sebelumnya akan mengarah ke yang ketiga. Oleh karena itu, tautan elemen keempat - sebelumnya - sudah akan mengarah ke elemen baru, dan tautan berikutnya dari elemen baru akan mengarah ke elemen keempat: Kompleksitas logaritmik metode ini akan bergantung pada indeks yang diberikan ke elemen baru:

• jika dekat dengan kepala atau ekor, ia akan mendekati O(1), karena sebenarnya tidak perlu melakukan iterasi pada elemen;
• jika mendekati tengah, maka O(N/2) - elemen dari kepala dan ekor akan diurutkan secara bersamaan hingga elemen yang diperlukan ditemukan.

3. set(<Index>,<Element>) - menulis elemen ke posisi yang ditentukan dalam daftar. Kompleksitas logaritmik operasi ini akan berkisar dari O(1) hingga O(N/2), sekali lagi bergantung pada seberapa dekat elemen tersebut dengan kepala, ekor, atau tengah. 4. hapus(<index>) - menghapus elemen dari daftar, pada dasarnya membuat elemen yang ada sebelum elemen yang dihapus ( sebelumnya ) merujuk pada elemen yang muncul setelah elemen yang dihapus ( berikutnya ). Begitu pula sebaliknya: sehingga elemen yang muncul setelah yang dihapus mengacu pada elemen yang muncul sebelum yang dihapus: Hasilnya adalah proses kebalikan dari penjumlahan berdasarkan indeks ( add(<Index>,<Element>) ). Bagi mereka yang ingin mempelajari lebih lanjut tentang struktur internal LinkedList , saya sarankan membaca artikel ini .

88. Apa struktur internal HashMap?

Mungkin salah satu pertanyaan paling populer saat mewawancarai pengembang Java. HashMap v berfungsi dengan pasangan nilai kunci . Bagaimana cara menyimpannya di dalam HashMapv itu sendiri ? Di dalam HashMap ada array node:

Node<K,V>[] table

Secara default, ukuran array adalah 16, dan ukurannya berlipat ganda setiap kali diisi dengan elemen (ketika LOAD_FACTOR tercapai - persentase kepenuhan tertentu, secara default adalah 0.75 ). Setiap node menyimpan hash dari kunci, kunci, nilai, dan tautan ke elemen berikutnya: Sebenarnya, “tautan ke elemen berikutnya” berarti bahwa kita berurusan dengan daftar tertaut tunggal, di mana setiap elemen berisi tautan ke yang selanjutnya. Artinya, HashMap menyimpan data dalam array daftar tertaut tunggal. Tapi saya akan segera mencatatnya: ketika satu sel dari array tabel memiliki tautan ke daftar tertaut tunggal serupa yang terdiri dari lebih dari satu elemen, ini tidak baik. Fenomena ini disebut tumbukan . Tapi hal pertama yang pertama. Mari kita lihat bagaimana pasangan baru disimpan menggunakan metode put . Pertama, hachCode() kunci diambil. Oleh karena itu, agar peta hash berfungsi dengan benar , Anda perlu mengambil kelas yang metode ini diganti sebagai kuncinya. Kode hash ini kemudian digunakan dalam metode internal - hash() - untuk menentukan nomor dalam ukuran array tabel . Selanjutnya, dengan menggunakan nomor yang diterima, sel tertentu dari array tabel diakses . Di sini kita memiliki dua kasus:

1. Selnya kosong - nilai Node baru disimpan di dalamnya .
2. Sel tidak kosong - nilai kuncinya dibandingkan. Jika sama, nilai Node baru akan menimpa nilai lama, jika tidak sama, elemen berikutnya diakses dan dibandingkan dengan kuncinya... Begitu seterusnya hingga nilai baru menimpa nilai lama atau mencapai akhir daftar tertaut tunggal dan akan disimpan di sana sebagai elemen terakhir.

Saat mencari elemen dengan kunci ( metode get(<key>) ), kode hash kunci dihitung, kemudian nilainya dalam array menggunakan hash() , dan menggunakan nomor yang dihasilkan, sel array tabel ditemukan , dimana pencarian sudah dilakukan dengan menghitung node dan membandingkan kunci dari node yang diinginkan dengan kunci dari node saat ini. Operasi di Map, dalam situasi ideal, memiliki kompleksitas algoritmik O(1), karena operasi tersebut mengakses array, dan seperti yang Anda ingat, berapa pun jumlah elemennya, operasi pada array memiliki kompleksitas O(1) . Tapi ini idealnya. Ketika sel array yang digunakan tidak kosong (2) dan sudah ada beberapa node di sana, kompleksitas algoritmik berubah menjadi linier O(N), karena sekarang elemen perlu diulangi sebelum menemukan tempat yang tepat. Saya tidak bisa tidak menyebutkan ini: dimulai dengan Java 8, jika satu node daftar tertaut memiliki lebih dari 8 elemen (tabrakan), itu berubah menjadi pohon biner. Dalam hal ini, kompleksitas algoritmiknya tidak lagi menjadi O(N), tetapi O(log(N)) - itu soal lain, bukan? HashMap adalah topik besar, dan orang-orang suka bertanya tentang hal itu dalam wawancara. Oleh karena itu, saya menyarankan Anda untuk memahaminya secara detail (agar memantul dari gigi Anda). Secara pribadi, saya belum pernah melakukan wawancara tanpa pertanyaan HashMap . Anda dapat mempelajari lebih dalam tentang HashMap di artikel ini . Itu saja untuk hari ini, untuk dilanjutkan...