Masalah dan Skenario Penerapan
Menggunakan fixed array, implementasikan dynamic array dengan get(index), set(index, value), dan append(value). Lakukan resize saat penuh, jelaskan kebijakan pertumbuhan, perilaku batas, waktu append kasus terburuk dan teramortisasi, serta bandingkan pertumbuhan linear dengan geometris.
Asumsikan referensi atau nilai berukuran tetap, indeks berbasis nol, exception untuk akses di luar batas, dan append pada array kosong. Bank soal wawancara publik menghubungkan implementasi dynamic array/vector dengan Microsoft, manajemen memori, dan analisis amortisasi; MIT 6.006 mencatat append dynamic array sebagai teramortisasi Θ(1).
Apa yang Dinilai oleh Pewawancara
- Apakah Anda memisahkan
sizedaricapacitydan mempertahankan invarian bahwa elemen valid menempati slotsizepertama. - Apakah Anda memilih pertumbuhan geometris alih-alih menambah satu slot setiap kali.
- Apakah Anda dapat membuktikan batas teramortisasi dengan analisis agregat, akuntansi, atau potensial daripada sekadar menyatakan O(1).
- Apakah Anda mencakup kapasitas nol, integer overflow, kegagalan alokasi, penyusutan (shrinking), dan penyisipan di tengah.
Pertanyaan Klarifikasi Sebelum Menjawab
- Apakah hanya append di akhir yang diperlukan, atau juga insert di tengah, delete, dan pop? Hal tersebut mengubah kompleksitas.
- Apakah nilai berukuran tetap? Apakah semantik referensi, pembatalan iterator (iterator invalidation), atau keamanan thread (thread safety) diperlukan?
- Apakah tujuannya adalah meminimalkan penyalinan, overhead memori yang lebih rendah, atau batas latensi yang ketat?
- Apakah penyusutan (shrinking) diperlukan? Jika ya, apakah ambang batasnya harus dipisahkan dari ambang pertumbuhan untuk menghindari thrashing?
Kerangka Jawaban 30 Detik
Saya akan menyimpan backing array, size, dan capacity. Append menulis langsung saat slot masih tersedia. Ketika penuh, array yang lebih besar dialokasikan, menyalin size elemen pertama, dan menulis nilai baru. Pertumbuhan geometris seperti penggandaan adalah kuncinya: jumlah total elemen yang disalin selama n append adalah deret geometri di bawah 2n, sehingga total operasi adalah O(n) dan append adalah teramortisasi O(1). Pemanggilan resize itu sendiri masih O(n), sehingga ini bukan jaminan O(1) kasus terburuk per pemanggilan.
Pembahasan Mendalam Langkah Demi Langkah
Status dan Invarian
Pertahankan tiga field: backing array data, jumlah elemen valid size, dan slot yang dialokasikan capacity. Selalu pertahankan size minimal nol dan tidak lebih besar dari capacity; elemen valid menempati [0, size). Append menulis ke data[size] dan menambah size. get dan set hanya menerima [0, size), tidak pernah slot kapasitas yang belum diinisialisasi.
Kebijakan Pertumbuhan Geometris
Ketika size == capacity, alokasikan setidaknya max(1, capacity * 2), salin elemen lama, dan ganti referensi backing. Kapasitas nol memerlukan penanganan khusus, jika tidak, perkalian akan tetap menghasilkan nol. Penggandaan menciptakan rangkaian append murah yang sebanding dengan ukuran saat ini; faktor yang lebih besar menyalin lebih jarang tetapi menyisakan lebih banyak ruang yang tidak terpakai.
~~~java final class DynamicArray { private Object[] data = new Object[0]; private int size = 0;
public void append(Object value) { if (size == data.length) { int next = Math.max(1, data.length * 2); Object[] grown = new Object[next]; System.arraycopy(data, 0, grown, 0, size); data = grown; } data[size++] = value; }
public int size() { return size; }
public Object get(int index) { check(index); return data[index]; }
public void set(int index, Object value) { check(index); data[index] = value; }
private void check(int index) { if (index < 0 || index >= size) throw new IndexOutOfBoundsException(); } } ~~~
Object[] adalah cara umum untuk mengilustrasikan implementasi di bawah generic type erasure; kode produksi tetap memerlukan kebijakan eksplisit untuk null, kegagalan alokasi, dan konkurensi. Invarian dan kompleksitas tidak bergantung pada Java.
Pembuktian Teramortisasi
Asumsikan kapasitas dimulai dari 1 dan berlipat ganda. Pada n append, penulisan biasa membutuhkan konstanta n; penyalinan resize terjadi pada kapasitas 1, 2, 4, 8, dan seterusnya, dengan total di bawah 2n. Oleh karena itu, total operasi berada di bawah 3n ditambah inisialisasi, menghasilkan biaya teramortisasi O(1) per operasi.
Ini adalah jaminan atas urutan kasus terburuk, bukan rata-rata atas input acak. Append yang memicu resize tetap menyalin Θ(n) elemen, sehingga satu pemanggilan memiliki waktu kasus terburuk O(n). get dan set adalah O(1) kasus terburuk, dan penyimpanan backing adalah O(n).
Pertumbuhan Linear dan Penyusutan
Menambahkan hanya c slot setiap kali membuat biaya penyalinan menjadi sekitar c + 2c + ...; menyisipkan n elemen membutuhkan biaya Θ(n²), sehingga append terdegradasi menjadi teramortisasi Θ(n). Pertumbuhan geometris biasanya merupakan trade-off yang lebih baik, meskipun faktor yang lebih besar meningkatkan puncak ruang yang tidak terpakai.
Jika pop didukung, susutkan di bawah batas rendah (low-water mark). Pisahkan ambang batas pertumbuhan dan penyusutan—misalnya, gandakan saat penuh dan bagi dua saat di bawah seperempat—untuk menghindari pemindahan berulang saat append dan pop bergantian. Penyusutan mempertahankan operasi akhir teramortisasi O(1) tetapi menambahkan jeda pelepasan memori dan penyalinan.
Batasan yang Dapat Diuji
Uji append pertama ke array kosong, append pada kapasitas tepat, pertumbuhan berulang, referensi duplikat, indeks negatif, index == size, kapasitas sangat besar, overflow, dan kegagalan alokasi. Penghitung salinan terkontrol dapat memverifikasi bahwa n append melakukan total Θ(n) salinan; hanya memeriksa konten akhir akan meloloskan implementasi pertumbuhan linear berbiaya kuadratik.
Contoh Jawaban Berkualitas Tinggi
Saya akan memisahkan backing array, size, dan capacity, dengan elemen valid selalu berada di size posisi pertama. Append menulis ke dalam kapasitas bebas; saat penuh, array dialokasikan dua kali lipat dari kapasitas, menyalin elemen lama, dan kemudian menulis nilainya. Kapasitas awal nol mendapatkan kasus khusus satu slot.
Pembuktian penggandaan adalah bagian yang penting: selama n append, penyalinan resize tetap di bawah 2n; menambahkan n penulisan konstan menghasilkan total kerja O(n) dan append teramortisasi O(1). Pemanggilan resize itu sendiri tetap O(n), sehingga biaya teramortisasi bukan batas latensi per pemanggilan. Pertumbuhan linear berbiaya Θ(n²) dalam total penyalinan. Jika penyusutan diperlukan, saya akan menggunakan histeresis dan menguji input kosong, batas indeks, overflow, dan kegagalan alokasi.
Kesalahan Umum
- Menambah satu slot setiap kali penuh → total penyalinan menjadi kuadratik → gunakan pertumbuhan geometris dan tunjukkan deretnya.
- Menyebut append sebagai kasus terburuk O(1) → mengabaikan penyalinan saat resize → bedakan O(n) satu pemanggilan dari O(1) teramortisasi dalam urutan.
- Memvalidasi
getterhadap capacity → mengembalikan slot yang belum diinisialisasi → wajibkan indeks minimal nol dan di bawah size. - Menggandakan kapasitas nol → array tidak pernah tumbuh → gunakan kapasitas minimum satu.
- Menyusutkan segera pada penggunaan rendah → append/pop yang bergantian menyebabkan pemindahan berulang → pisahkan ambang batas pertumbuhan dan penyusutan.
Pertanyaan Lanjutan dan Tanggapan
Bagaimana jika setiap append harus memiliki waktu kasus terburuk O(1)?
Resize array yang berurutan (contiguous) melakukan migrasi O(n), sehingga tidak dapat menjanjikan batas ketat tersebut seperti yang tertulis. Segmented array, migrasi bertahap (incremental), atau pra-alokasi batas atas yang diketahui dapat mengubah trade-off, dengan mengorbankan lokalitas, konstanta pengindeksan, atau ruang. Konfirmasikan terlebih dahulu apakah persyaratannya benar-benar kasus terburuk.
Apa yang berubah jika faktor pertumbuhannya 1.25 alih-alih 2?
Setiap faktor yang lebih besar dari 1 tetap menghasilkan append akhir teramortisasi O(1), tetapi penyalinan terjadi lebih sering dan ruang cadangan lebih sedikit. Saat faktor mendekati 1, konstanta meningkat; pilih berdasarkan anggaran memori, perilaku alokator, dan target latensi alih-alih Big-O saja.
Bagaimana cara membuktikan bahwa pertumbuhan linear adalah O(n²)?
Jika setiap resize menambah c slot, resize ke-j menyalin sekitar jc elemen. n elemen pertama memicu sekitar n/c kali resize, sehingga totalnya adalah c + 2c + ... + (n/c)c = Θ(n²). Oleh karena itu, append teramortisasi adalah Θ(n).
Bagaimana penyisipan di tengah mengubah kompleksitas?
Bahkan dengan kapasitas cadangan, penyisipan di tengah menggeser sufiks dan merupakan kasus terburuk O(n). Penyalinan saat resize adalah pekerjaan tambahan; dynamic array dioptimalkan untuk akses acak dan operasi akhir, bukan untuk setiap jenis penyisipan.
Bagaimana cara kerja concurrent append?
Gunakan lock, kepemilikan single-thread, atau protokol indeks atomik dengan koordinasi resize. Hanya menjadikan size atomik tidak melindungi seluruh urutan pemeriksaan kapasitas, alokasi, penyalinan, dan publikasi. Jika konkurensi tidak diperlukan, nyatakan batas single-thread secara eksplisit.