Menjelajahi pertanyaan dan jawaban dari wawancara kerja untuk posisi pengembang Java. Bagian 9

Menjadi seorang programmer tidaklah mudah. Selalu ada sesuatu yang baru untuk dipelajari. Dan, seperti dalam upaya lainnya, hal tersulit adalah memulai, mengambil langkah pertama menuju tujuan Anda. Namun karena Anda sudah berada di sini dan membaca artikel ini, Anda telah menyelesaikan langkah pertama. Artinya, sekarang Anda harus dengan sengaja bergerak menuju tujuan Anda, tanpa memperlambat dan tidak membelok ke samping. Saya berasumsi tujuan Anda adalah menjadi pengembang Java atau menambah pengetahuan Anda jika Anda sudah menjadi pengembang. Jika iya, mari kita terus membahas daftar lengkap pertanyaan wawancara pengembang Java. Ayo lanjutkan!

Koleksi

84. Ceritakan kepada kami tentang iterator dan cara penggunaannya

Koleksi adalah topik favorit dalam setiap wawancara pengembang Java. Saat menjawab pertanyaan tentang hierarki koleksi, kandidat sering kali mengatakan bahwa hierarki dimulai dengan antarmuka Koleksi . Tapi ini tidak benar. Ada antarmuka lain satu tingkat di atas: Iterable . Antarmuka ini terdiri dari metode iterator() , yang memungkinkan Anda mengakses objek Iterator untuk koleksi saat ini. Dan apa sebenarnya objek Iterator ini ? Objek Iterator menyediakan kemampuan untuk menelusuri koleksi dan mengulangi elemen-elemennya, dan pengguna tidak perlu mengetahui detail implementasi spesifik dari koleksi tersebut. Dengan kata lain, ini adalah semacam penunjuk ke elemen koleksi, seolah-olah ia mengintip ke dalam salah satu elemen tersebut. Iterator memiliki metode seperti:

• hasNext() — mengembalikan nilai true jika iterasi memiliki elemen lain (metode ini memberi tahu Anda ketika Anda telah mencapai akhir koleksi);

• next() — mengembalikan item berikutnya dalam iterasi. Jika tidak ada, maka NoSuchElementException akan dilempar. Artinya sebelum Anda menggunakan metode ini, yang terbaik adalah menggunakan metode hasNext() untuk memastikan elemen berikutnya ada;

• hapus() — menghapus dari koleksi elemen terakhir yang diterima menggunakan metode next() . Jika next() belum pernah dipanggil, maka pemanggilan delete() akan menyebabkan IllegalStateException dilempar;

• forEachRemaining(<Consumer>) — mengeksekusi tindakan yang diteruskan pada setiap elemen koleksi (metode ini muncul di Java 8).

Berikut adalah contoh kecil melakukan iterasi melalui daftar dan menghapus semua elemennya menggunakan berbagai metode iterator yang telah kita lihat:

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 yang berikut: Ini berarti elemen tersebut berhasil dihapus. Setelah Anda mendapatkan iterator, Anda dapat menggunakan metode untuk menampilkan semua elemen di layar:

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

Namun begitu kita melakukan ini, iterator menjadi tidak cocok untuk digunakan lebih lanjut: iterator telah melintasi seluruh daftar, dan iterator biasa tidak memiliki metode untuk melakukan iterasi mundur. Dan itu menjadi awal yang bagus untuk berdiskusi tentang LinkedList , khususnya, metode listIterator()- nya , yang mengembalikan tipe iterator yang disempurnakan: ListIterator . Selain metode iterator biasa (standar), jenis ini memiliki yang berikut:

• add(<Element>) — menambahkan elemen baru ke daftar;

• hasPrevious() — mengembalikan nilai true jika ada elemen yang terletak sebelum elemen berikutnya (jika ada elemen sebelumnya);

• nextIndex() — mengembalikan indeks elemen berikutnya;

• previous() — mengembalikan elemen sebelumnya (yang sebelum elemen berikutnya);

• previousIndex mengembalikan indeks elemen sebelumnya.

• set(<Element>) — menggantikan elemen terakhir yang dikembalikan oleh next() atau previous() .

Seperti yang Anda lihat, iterator ini memiliki fungsi yang jauh lebih menarik: memungkinkan Anda berjalan di kedua arah dan memberikan banyak kebebasan saat bekerja dengan elemen. Anda juga harus tahu bahwa ketika orang berbicara tentang iterator, terkadang yang mereka maksud adalah pola desain itu sendiri.

85. Hierarki koleksi apa yang ada di Java Collection Framework?

Ada dua hierarki koleksi di Java. Hierarki pertama adalah hierarki Koleksi, yang memiliki struktur sebagai berikut: Ini dibagi menjadi beberapa subkoleksi berikut:

• Himpunan adalah antarmuka yang mendeskripsikan himpunan, struktur data yang berisi elemen unik yang tidak berurutan (tidak berulang). Antarmuka ini memiliki beberapa implementasi standar: TreeSet , HashSet , dan LinkedHashSet .

• Daftar adalah antarmuka yang menggambarkan struktur data yang menyimpan urutan objek yang diurutkan. Objek dalam Daftar dapat disisipkan dan dihapus berdasarkan indeksnya dalam daftar (seperti array, tetapi dengan pengubahan ukuran dinamis). Antarmuka ini juga memiliki beberapa implementasi standar: ArrayList , Vector ( tidak digunakan lagi dan sebenarnya tidak digunakan ), dan LinkedList .

• Antrian adalah antarmuka yang menggambarkan struktur data yang menyimpan item dalam antrian First In First Out (FIFO) . Antarmuka ini memiliki implementasi standar berikut: LinkedList (benar, ini juga mengimplementasikan Queue ) dan PriotityQueue .

Hirarki koleksi kedua adalah hierarki Peta , yang memiliki struktur sebagai berikut: Hirarki koleksi ini tidak memiliki pembagian ke dalam subkoleksi (karena hierarki Peta itu sendiri merupakan subkoleksi yang berdiri sendiri). Implementasi Map standar adalah Hashtable (tidak digunakan lagi), LinkedHashMap , dan TreeMap . Dalam praktiknya, ketika orang bertanya tentang Koleksi , yang mereka maksud biasanya adalah kedua hierarki.

86. Apa struktur internal dari ArrayList?

ArrayList seperti array, tetapi dapat diperluas secara dinamis . Maksudnya itu apa? Di bawah tenda, ArrayList menggunakan array biasa, yaitu menyimpan elemen-elemennya dalam array internal yang ukuran defaultnya adalah 10 sel. Setelah array internal penuh, array baru dibuat. Ukuran array baru ditentukan dengan rumus ini:

<size of the current array> * 3 / 2 + 1

Jadi, jika ukuran array kita adalah 10, maka ukuran array barunya adalah: 10 * 3 / 2 + 1 = 16. Kemudian semua nilai dari array asli (lama) disalin ke dalamnya menggunakan built-in Metode System.arraycopy() , dan array asli dihapus. Singkatnya, itulah cara ArrayList mengimplementasikan pengubahan ukuran dinamis. Mari pertimbangkan metode ArrayList yang paling populer : 1. add(<Element>) — menambahkan elemen ke akhir array (di sel kosong terakhir), setelah terlebih dahulu memeriksa apakah ada sel yang tersedia di array. Jika tidak, array baru akan dibuat, dan elemen-elemennya disalin ke dalamnya. Kompleksitas waktu operasi ini adalah O(1). Ada metode add(<Index>, <Element>) yang serupa . Itu menambahkan elemen bukan ke akhir daftar (array), tetapi ke sel tertentu yang ditunjukkan oleh indeks yang masuk sebagai argumen. Dalam hal ini, kompleksitas waktu akan bervariasi tergantung di mana Anda menambahkan:

• jika penambahannya dekat dengan awal daftar, maka kompleksitas waktunya akan mendekati O(N), karena semua elemen yang terletak di sebelah kanan yang baru harus dipindahkan satu sel ke kanan;
• jika elemen disisipkan di tengah, maka akan menjadi O(N/2), karena kita hanya perlu menggeser setengah item daftar satu sel ke kanan.

Artinya, kompleksitas waktu metode ini berkisar dari O(1) hingga O(N), tergantung di mana elemen dimasukkan. 2. set(<Index>, <Element>) — menulis elemen ke posisi yang ditentukan dalam daftar. Jika suatu elemen sudah ada pada posisi itu, metode akan menimpanya. Kompleksitas waktu dari operasi ini adalah O(1), karena tidak melibatkan operasi shift apa pun: kita hanya menggunakan indeks untuk menghitung alamat sel dalam array, yang memiliki kompleksitas O(1), dan kemudian menulis elemen baru . 3. hapus(<index>) — menghapus elemen berdasarkan indeksnya di array internal. Saat menghapus item yang tidak ada di akhir daftar, semua item di sebelah kanan item yang dihapus harus digeser satu sel ke kiri untuk menutup celah akibat penghapusan. Oleh karena itu, kompleksitas waktu akan sama dengan add(<Index>, <Element>) ketika sebuah elemen ditambahkan di tengah: O(N/2). Lagi pula, Anda perlu menggeser setengah elemen satu sel ke kiri. Dan jika kita berbicara tentang permulaan, maka O(N). Atau jika di akhir, maka O(1), karena Anda tidak perlu memindahkan apa pun.

87. Apa struktur internal LinkedList?

ArrayList berisi elemen dalam array internal, tetapi LinkedList menyimpannya dalam daftar tertaut ganda . Artinya setiap elemen mengandung link ke elemen sebelumnya dan ke elemen berikutnya . Elemen pertama tidak tertaut ke elemen sebelumnya (bagaimanapun juga, ini adalah elemen pertama). Itu juga dianggap sebagai kepala daftar, dan objek LinkedList memiliki referensi langsung ke sana. Demikian pula, elemen terakhir tidak memiliki elemen berikutnya, karena merupakan bagian akhir dari daftar. Objek LinkedList juga mereferensikannya secara langsung. Artinya kompleksitas waktu untuk mengakses bagian awal atau akhir suatu daftar adalah O(1). Di ArrayList , jika daftar bertambah, maka array internal bertambah. Di sini semuanya lebih mudah: menambahkan referensi semudah mengubah beberapa tautan. Mari kita lihat beberapa metode LinkedList yang paling sering digunakan: 1. add(<Element>) — menambahkan elemen ke akhir daftar, yaitu setelah elemen terakhir (5), link ke elemen baru akan ditambahkan sebagai berikutnya . Referensi sebelumnya dalam elemen baru akan menunjuk ke elemen (5) yang sekarang mendahuluinya dalam daftar. Kompleksitas waktu dari operasi ini adalah O(1), karena kita hanya memerlukan tautan ke elemen terakhir, dan seperti yang Anda ingat, objek LinkedList memiliki referensi langsung ke ekor, dan mengaksesnya memiliki kompleksitas waktu konstan yang minimal. 2. add(<Index>, <Element>) — menambahkan elemen berdasarkan indeks. Saat menambahkan elemen, katakanlah, di tengah daftar, metode ini pertama-tama melakukan iterasi pada elemen dari kepala dan ekor (di kedua arah) hingga tempat yang diinginkan ditemukan. Jika kita menambahkan elemen di antara elemen ketiga dan keempat (pada gambar di atas), maka link selanjutnya dari elemen ketiga akan mengarah ke elemen baru. Dan elemen yang baru ditambahkan sebelumnya akan mengarah ke elemen ketiga. Pada gilirannya, tautan sebelumnya dari elemen keempat yang lama kini akan mengarah ke elemen baru, dan tautan berikutnya dari elemen baru akan mengarah ke elemen keempat yang baru: Kompleksitas waktu metode ini bergantung pada indeks elemen baru:

• jika dekat dengan kepala atau ekor, operasi akan mendekati O(1), karena sebenarnya tidak perlu melakukan iterasi pada elemen;
• jika mendekati tengah, maka kita akan mendapatkan O(N/2), karena metode ini akan mencari dari kepala dan ekor secara bersamaan hingga elemen yang diinginkan ditemukan.

3. set(<Index>, <Element>) — menulis elemen ke posisi yang ditentukan dalam daftar. Kompleksitas waktu operasi ini akan berkisar dari O(1) hingga O(N/2), sekali lagi bergantung pada seberapa dekat elemen baru dengan kepala, ekor, atau tengah. 4. hapus(<index>) — menghapus elemen dari daftar dengan membuat elemen sebelum yang dihapus ( sebelumnya ) sekarang merujuk ke elemen setelah yang dihapus ( berikutnya ). Begitu pula sebaliknya, yaitu elemen setelah yang dihapus sekarang merujuk ke elemen sebelum yang dihapus: Proses ini kebalikan dari penjumlahan berdasarkan indeks ( add(<Index>, <Element>) ).

88. Apa struktur internal HashMap?

Ini mungkin salah satu pertanyaan wawancara paling populer untuk ditanyakan kepada kandidat pengembang Java. HashMap berfungsi dengan pasangan nilai kunci . Bagaimana cara menyimpannya di dalam HashMap itu sendiri? HashMap memiliki array node internal:

Node<K,V>[] table

Secara default, ukuran array adalah 16, dan ukurannya menjadi dua kali lipat setiap kali diisi dengan elemen (yaitu, ketika LOAD_FACTOR tercapai ; ini menentukan ambang batas seberapa penuh array dapat diperoleh — secara default, ukurannya adalah 0,75 ) . Masing-masing node menyimpan hash dari kunci, kunci, nilai, dan referensi ke elemen berikutnya: Dalam hal ini, "referensi ke elemen berikutnya" berarti kita berurusan dengan daftar tertaut tunggal, di mana setiap elemen berisi tautan ke elemen berikutnya. Dengan kata lain, HashMap menyimpan datanya dalam serangkaian daftar tertaut tunggal. Tapi izinkan saya segera mengatakan bahwa ketika sel array tabel memiliki daftar tertaut tunggal yang terdiri dari lebih dari satu elemen, itu tidak baik. Fenomena ini disebut tumbukan . Tapi hal pertama yang pertama. Mari kita lihat bagaimana pasangan baru disimpan menggunakan metode put . Pertama, metode ini mendapatkan hashCode() kuncinya . Ini menyiratkan bahwa agar HashMap berfungsi dengan benar, kunci yang Anda gunakan harus berupa kelas yang menggantikan metode ini. Kode hash ini kemudian digunakan dalam metode hash() internal untuk menentukan indeks beberapa sel dalam array tabel. Indeks yang dihasilkan memungkinkan kita mengakses sel tertentu dari array tabel. Kami memiliki dua kasus di sini:

1. Selnya kosong — dalam hal ini, nilai Node baru disimpan di dalamnya.
2. Sel tidak kosong — dalam hal ini, nilai kunci dibandingkan. Jika keduanya sama, maka nilai Node yang baru akan menimpa nilai Node yang lama; jika tidak sama, maka nilai berikutnya diakses, dan kuncinya dibandingkan... Dan seterusnya, hingga nilai baru menimpa nilai lama atau kita mencapai akhir dari daftar tertaut tunggal dan kemudian menyimpan nilai baru di sana sebagai elemen terakhir.

Saat mencari elemen berdasarkan kunci (menggunakan metode get(<key>) ), hashCode() kunci dihitung, dan kemudian indeksnya dalam array dihitung menggunakan hash() . Angka yang dihasilkan adalah indeks sel dalam larik tabel , yang kemudian kita cari dengan melakukan iterasi pada node dan membandingkan kunci dari node yang diinginkan dengan kunci dari node saat ini. Idealnya, operasi Map memiliki kompleksitas algoritmik O(1), karena kita mengakses sebuah array, dan, seperti yang Anda ingat, adalah O(1), berapa pun jumlah elemen yang dikandungnya. Namun kita tidak sedang menangani kasus yang ideal. Ketika sel tidak kosong (2) dan sudah menyimpan beberapa node, maka kompleksitas algoritmik menjadi O(N) (linier), karena sekarang elemen perlu diulang sebelum kita menemukan tempat yang tepat. Saya tidak bisa tidak menyebutkan bahwa mulai di Java 8, jika sebuah node dalam bentuk daftar tertaut tunggal memiliki lebih dari 8 elemen (tabrakan), maka node tersebut akan diubah menjadi pohon biner. Dalam hal ini, kompleksitas algoritmiknya bukan lagi O(N), namun O(log(N)) — dan itu masalah lain, bukan? HashMap adalah topik besar, dan orang-orang suka bertanya tentang hal itu dalam wawancara kerja. Jadi, saya sarankan Anda mengetahuinya seperti punggung tangan Anda. Secara pribadi, saya belum pernah melakukan wawancara yang tidak menyertakan pertanyaan tentang HashMap . Itu saja untuk hari ini. Bersambung...