Daftar Isi[Bersembunyi][Menunjukkan]
- 1. Bagaimana Anda mendefinisikan Array?
- 2. Array Dinamis: Apa Itu? Apa yang membedakan mereka dari Array Dasar?
- 3. Bagaimana array dan kamus berbeda satu sama lain?
- 4. Sebutkan beberapa keuntungan dan kerugian dari array.
- 5. Apa yang dimaksud dengan "Array Jarang"?
- 6. Kapan Anda akan memilih daftar tertaut daripada array?
- 7. Apa yang membedakan array terindeks dari array asosiatif?
- 8. Apa kelebihan yang dimiliki Heap dibandingkan array yang diurutkan?
- 9. Bisakah kita mendefinisikan ukuran array menjadi negatif?
- 10. Bagaimana Anda menemukan bilangan bulat yang hilang dalam larik 1 hingga 100 elemen?
- 11. Bagaimana Anda menemukan indeks elemen dalam array?
- 12. Bagaimana cara menghilangkan elemen tertentu dari array?
- 13. Bagaimana persamaan dua array dapat diverifikasi?
- 14. Ketika kita membahas array, apa yang Anda maksud dengan frasa “Dimensi” dan “Subskrip”?
- Pertanyaan Wawancara Pengkodean
- 15. Carilah pasangan dalam array yang memiliki jumlah yang ditentukan
- 16. Penyortiran array biner dengan waktu linier
- 17. Temukan produk dua-int terbesar dalam sebuah array.
- 18. Cara menggeser semua nol array ke akhir
- 19. Bagaimana mengurutkan array dengan dua entri yang diaktifkan dalam satu operasi.
- 20. Bagaimana menggabungkan dua array yang diurutkan pada tempatnya.
- 21. Bagaimana cara menyusun ulang array item dalam posisi tinggi dan rendah bergantian?
- 22. Bagaimana cara mensubstitusi setiap elemen array tanpa menggunakan operator pembagian dengan perkalian setiap elemen array?
- 23. Temukan elemen paling aneh dalam array dalam waktu logaritmik
- 24. Bagaimana cara mendapatkan elemen berikutnya yang lebih besar untuk setiap elemen dalam array melingkar?
- 25. Temukan jumlah inversi array?
- 26. Apa Masalah Perangkap Air Hujan?
- Kesimpulan
Wawancara pengkodean berisi serangkaian pertanyaan DSA. Anda harus terampil dengan susunan jika Anda bersiap untuk wawancara teknologi yang akan datang dengan FAANG atau bisnis teknologi Tier-1 lainnya.
Dalam sebagian besar wawancara pengkodean, ia berada di tempat kedua setelah Strings. Array adalah pengelompokan elemen data terkait yang disimpan dalam jarak dekat satu sama lain dalam memori.
Karena mereka terhubung ke semua bahasa pemrograman, seperti C, C++, Java, Python, Perl, dan Ruby, mereka ada di mana-mana. Lanjutkan membaca untuk beberapa latihan tantangan pengkodean dan wawancara pertanyaan dan jawaban berdasarkan array.
Python akan digunakan dalam posting ini untuk mengatasi masalah pengkodean karena mudah digunakan, dipahami, dan harus akrab bagi kebanyakan dari kita.
Mari kita mulai.
1. Bagaimana Anda mendefinisikan Array?
- Sekelompok tipe data terkait adalah array.
- Array selalu tetap.
- Jenis variabel yang sama disimpan di beberapa tempat oleh objek array.
- Tipe primitif dan referensi objek keduanya kompatibel dengannya.
2. Array Dinamis: Apa Itu? Apa yang membedakan mereka dari Array Dasar?
Penskalaan otomatis yang disediakan oleh array dinamis (juga disebut sebagai array yang dapat ditumbuhkan, array yang dapat diubah ukurannya, array yang dapat diubah, atau ArrayLists di Java) merupakan keuntungan yang signifikan.
Anda harus selalu tahu berapa banyak elemen yang akan disimpan array Anda sebelumnya karena array memiliki ukuran tetap. Array dinamis, di sisi lain, tumbuh saat Anda menambahkan anggota tambahan ke dalamnya, jadi Anda tidak perlu mengetahui ukuran pastinya sebelumnya.
3. Bagaimana array dan kamus berbeda satu sama lain?
Ini adalah serangkaian pertanyaan wawancara berbasis fundamental yang sering ditanyakan. Berikut ini adalah perbedaan utama antara array dan kamus:
- Array adalah daftar terurut dari item serupa. Kamus, di sisi lain, memiliki pasangan nilai kunci.
- Ukuran array dapat berubah secara dinamis. Ide dinamis seperti itu tidak ada dalam kamus.
- Sebelum menggunakan array, ukurannya harus ditentukan. Ukuran kamus tidak perlu disesuaikan.
- Gunakan pernyataan Redim jika Anda ingin memperluas ukuran array. Dalam kamus, sebuah elemen dapat ditambahkan tanpa deklarasi.
4. Sebutkan beberapa keuntungan dan kerugian dari array.
Keuntungan:
- Array dapat mengurutkan sejumlah elemen secara bersamaan.
- Lainnya struktur data, seperti tumpukan, antrian, daftar tertaut, pohon, grafik, dll., dapat diimplementasikan dalam array.
- Indeks dapat digunakan untuk mencapai elemen array.
kekurangan:
- Ukuran array harus dideklarasikan terlebih dahulu. Pada saat deklarasi array, kita mungkin tidak menyadari ukuran yang kita butuhkan.
- Struktur array adalah statis. Ini menyiratkan bahwa ukuran array selalu tetap dan alokasi memori tidak dapat ditambah atau dikurangi.
5. Apa yang dimaksud dengan "Array Jarang"?
Array jarang adalah array data yang memiliki banyak entri dengan nilai nol. Sebaliknya, array padat berisi sebagian besar itemnya dengan nilai bukan nol. Indeks array jarang, yang mengubah angka menjadi objek, mungkin termasuk celah. Dibandingkan dengan HashMap, mereka lebih hemat memori.
6. Kapan Anda akan memilih daftar tertaut daripada array?
Saat menggunakan daftar tertaut alih-alih array, pertimbangkan:
- Anda tidak memerlukan elemen apa pun untuk memiliki akses acak.
- Di mana prediktabilitas temporal sangat penting, Anda memerlukan penyisipan dan penghapusan waktu konstan dari daftar.
- Untuk membuat antrian prioritas, Anda mungkin perlu menempatkan item di tengah daftar.
- Anda tidak tahu berapa lama daftarnya. Jika ukuran array meningkat, Anda harus mendeklarasikan ulang dan menduplikasi memori, seperti halnya array sederhana.
7. Apa yang membedakan array terindeks dari array asosiatif?
Perbedaan utama antara array asosiatif dan diindeks tercantum dalam tabel berikut.
- Pasangan nilai kunci dalam format teks atau numerik digunakan untuk mengurutkan array asosiatif. Kunci array yang diindeks semuanya numerik, dan setiap kunci terhubung ke nilai yang berbeda.
- Dalam array asosiatif, kuncinya mungkin berupa string. Array terindeks dengan kunci integer mulai dari 0.
- Tabel dua kolom meniru perilaku array asosiatif. Mirip dengan tabel satu kolom adalah array yang diindeks.
- Peta adalah tipe array asosiatif. Array indeks bukan peta.
8. Apa kelebihan yang dimiliki Heap dibandingkan array yang diurutkan?
Efisiensi waktu menggunakan Heap over Sorted Arrays adalah keuntungan utama. Sementara operasi heap lebih cepat, pengurutan array membutuhkan banyak waktu. Heap dapat menemukan elemen terkecil jauh lebih cepat daripada array yang dapat diurutkan.
Kumpulan angka yang diberikan dapat diatur dalam salah satu dari dua cara menggunakan Array Terurut. Di sisi lain, untuk kumpulan angka tertentu, mungkin ada lebih dari satu tumpukan potensial.
9. Bisakah kita mendefinisikan ukuran array menjadi negatif?
Tidak, kita tidak dapat mendefinisikan bilangan bulat negatif sebagai ukuran array. Tidak akan ada kesalahan waktu kompilasi jika kami mendeklarasikan. Namun, saat runtime, kita akan menemukan NegativeArraySizeException.
10. Bagaimana Anda menemukan bilangan bulat yang hilang dalam larik 1 hingga 100 elemen?
Jumlah deret dapat dihitung dengan menerapkan fungsi berikut: n (n + 1) / 2
Hanya jika array tidak memiliki duplikat atau memiliki lebih dari satu bilangan bulat yang hilang, fungsi ini akan beroperasi. Apakah array memiliki elemen duplikat, Anda dapat mengurutkan array untuk melihat apakah ada elemen yang setara.
11. Bagaimana Anda menemukan indeks elemen dalam array?
Indeks elemen dapat ditemukan melalui pencarian linier atau biner. Sampai menemukan kecocokan elemen yang diperlukan, fungsi pencarian linier mengulang setiap elemen dalam array. Ini mengembalikan indeks setelah menemukan elemen yang cocok. Akibatnya, kompleksitas temporal pencarian linier adalah O. (n). Array yang diurutkan dan tidak disortir dapat menggunakan pencarian linier.
Menggunakan pencarian biner, yang terus-menerus membagi array menjadi dua hingga median interval cocok dengan elemen yang diperlukan dan menyediakan indeks, Anda bisa mendapatkan indeks elemen jika array diurutkan. Akibatnya, kompleksitas temporal pencarian biner adalah O. (log n).
12. Bagaimana cara menghilangkan elemen tertentu dari array?
Karena Anda tidak bisa begitu saja menghapus elemen dari larik asli karena mereka adalah kumpulan tetap dengan ukuran yang ditentukan, pewawancara mencari Anda untuk menyarankan pendekatan yang berbeda dan menangani masalah yang timbul dari pertanyaan tersebut. Tindakan terbaik adalah membuat array baru untuk menghapus elemen. Anda dapat menduplikasi elemen dari larik pertama dalam larik ini dan hanya menyertakan elemen yang ingin Anda hapus.
Strategi lain melibatkan menemukan elemen target dalam array dan kemudian membalikkan urutan semua item yang berada di sebelah kanan elemen target.
13. Bagaimana persamaan dua array dapat diverifikasi?
Anda harus terlebih dahulu memverifikasi panjang dari dua array yang disediakan. Item yang cocok dari kedua array dibandingkan ketika panjangnya sama. Kedua array akan dianggap sama. jika setiap pasangan komponen dalam setiap korespondensi adalah sama. Pendekatan ini tidak disarankan untuk memeriksa kesetaraan dua array jika array berukuran besar karena akan memakan banyak waktu. Anda juga dapat menggunakan metode equals() yang disertakan dalam kelas Arrays, namun, jika pewawancara meminta Anda untuk membandingkan dua array tanpa menggunakan metode bawaan, cara ini akan berguna.
14. Ketika kita membahas array, apa yang Anda maksud dengan frasa “Dimensi” dan “Subskrip”?
"Dimensi" array adalah jumlah indeks, atau subskrip, yang diperlukan untuk mengidentifikasi setiap anggota individu. Subskrip dan dimensi mungkin tidak jelas. Dimensi adalah deskripsi rentang kunci yang diizinkan, sedangkan subskrip adalah angka. Hanya ada satu subskrip yang diperlukan untuk setiap dimensi array.
Misalnya, array arr[10][5] memiliki dua dimensi. Ukuran 10 di satu dan 5 di sisi lain. Untuk mengatasi komponennya, Anda memerlukan dua subskrip. Keduanya antara 0 dan 4; satu antara 0 dan 9, inklusif.
Pertanyaan Wawancara Pengkodean
15. Carilah pasangan dalam array yang memiliki jumlah yang ditentukan
Sebagai contoh,
Memasukkan:
- bilangan = [8, 7, 2, 5, 3, 1]
- sasaran = 10
Keluaran:
- Pasangan ditemukan (8, 2)
- Or
- Pasangan ditemukan (7, 3)
Memasukkan:
- bilangan = [5, 2, 6, 8, 1, 9]
- sasaran = 12
Keluaran:
- Pasangan tidak ditemukan
16. Penyortiran array biner dengan waktu linier
Urutkan array biner dalam waktu linier dan di area tetap. Outputnya harus menampilkan semua nol terlebih dahulu, lalu semuanya.
Sebagai contoh,
- Masukan: { 1, 0, 1, 0, 1, 0, 0, 1 }
- Keluaran: { 0, 0, 0, 0, 1, 1, 1, 1 }
Pendekatan langsung adalah menghitung jumlah total array dari 0s, katakanlah k, dan kemudian mengisi indeks k pertama dalam array dengan 0s dan indeks sisanya dengan 1. Sebagai alternatif, kita mungkin menghitung berapa banyak 1s total dalam array k, isi indeks k terakhir dalam array dengan 1, dan biarkan sisa indeks diisi dengan 0.
Pendekatan yang diberikan memiliki kompleksitas waktu O(n) dan tidak menggunakan penyimpanan tambahan, di mana n adalah ukuran input.
17. Temukan produk dua-int terbesar dalam sebuah array.
Temukan produk terbesar dari dua angka dalam array bilangan bulat.
Pikirkan tentang array 10 3 5 6 2 sebagai contoh. Pasangan (-10, -3) atau (5, 6) adalah produk tertinggi.
Memikirkan setiap kombinasi elemen dan mencari tahu produk mereka adalah pendekatan yang bodoh. Jika produk dari pasangan saat ini lebih besar dari produk maksimum yang diperoleh sejauh ini, perbarui produk maksimum. Cetak komponen produk akhir terakhir.
Solusi di atas, di mana n adalah jumlah input, memiliki kompleksitas waktu O(n2) dan tidak memakan tempat lagi.
18. Cara menggeser semua nol array ke akhir
Pindahkan semua nol dalam array integer ke akhir. Jawabannya harus menghindari penggunaan ruang konstan dan mempertahankan urutan relatif dari komponen array.
Masukan: {1,2,3,0,8,0,4,7}
Outputnya adalah {1,2,3,8,4,7,0,0}
Letakkan elemen pada posisi yang tersedia berikut dalam array jika elemen saat ini bukan nol. Isi semua indeks yang tersisa dengan 0 setelah item array semuanya diproses.
Solusi sebelumnya memiliki kompleksitas waktu O(n), di mana n adalah ukuran input.
19. Bagaimana mengurutkan array dengan dua entri yang diaktifkan dalam satu operasi.
Urutkan array dalam waktu linier yang diberikan dua item yang ditukar dan array dengan semua elemennya diatur dalam urutan menaik. Berpura-pura bahwa array tidak berisi duplikat.
Masukan:= [1,9,3,4,7,2] atau [9,3,7,2,1,4] atau [2,4,1,7,3,9]
Keluaran: = [1,2,3,4,7,9]
Dimulai dengan elemen kedua dalam larik, tujuannya adalah untuk membandingkan setiap elemen dengan pendahulunya. Posisi sengketa disimpan dengan mengambil dua pointer, x, dan y.
Perbarui x ke indeks elemen sebelumnya dan y ke indeks elemen saat ini jika yang pertama lebih besar dari yang terakhir. Perbarui y ke indeks elemen saat ini jika ternyata elemen sebelumnya lebih besar dari elemen saat ini.
Terakhir, alihkan elemen pada indeks x dan y setelah kita selesai memproses setiap pasangan elemen yang berdekatan.
Karena fakta bahwa metode yang disebutkan di atas hanya melakukan pemindaian tunggal dari array input berukuran n, kompleksitas waktunya adalah O(n). Tidak ada ruang tambahan yang diperlukan untuk solusi.
20. Bagaimana menggabungkan dua array yang diurutkan pada tempatnya.
Gabungkan item dari array X[] dan Y[]—dua array terurut dengan ukuran m dan n masing-masing—dengan mempertahankan urutan terurut, yaitu dengan mengisi X[] dengan elemen terkecil m pertama dan mengisi Y[] dengan elemen elemen yang tersisa.
Jika sebuah elemen dalam larik X[] sudah berada pada posisi yang tepat (yaitu yang terkecil di antara elemen yang tersisa), abaikan saja; jika tidak, ganti dengan elemen terkecil, yang juga merupakan anggota pertama dari Y[]. Untuk mempertahankan urutan terurut setelah bertukar, transfer elemen (sekarang di Y[0]) ke lokasi yang tepat di Y[].
Ukuran array pertama adalah m dan ukuran array kedua adalah n, dan kompleksitas waktu adalah O(mn).
21. Bagaimana cara menyusun ulang array item dalam posisi tinggi dan rendah bergantian?
Susun ulang array bilangan bulat sehingga setiap anggota berikutnya lebih besar dari elemen sebelumnya dan berikutnya. Asumsikan array tidak menyertakan elemen duplikat.
Menyortir larik atau memanfaatkan ruang tambahan tidak diperlukan untuk pendekatan yang efektif. Rencananya adalah, untuk memulai, anggota kedua dari array dan naik dua untuk setiap iterasi loop.
Tukar komponen jika elemen terakhir melebihi yang pertama. Dalam nada yang sama, ganti kedua item jika elemen berikut lebih besar dari elemen saat ini. Kami akan mendapatkan array yang diinginkan yang sesuai dengan batasan yang ditentukan pada akhir loop.
22. Bagaimana cara mensubstitusi setiap elemen array tanpa menggunakan operator pembagian dengan perkalian setiap elemen array?
Tanpa menggunakan operator pembagian, ganti setiap elemen dalam array integer dengan produk dari semua elemen lainnya.
Dalam waktu linier dan ruang konstan, kita dapat memanfaatkan rekursi untuk mengatasi masalah ini. Secara rekursif menghitung produk dari setiap elemen di subarray kanan dan melewatkan produk subarray kiri sebagai parameter fungsi adalah gagasan.
Kompleksitas waktu adalah O(n).
23. Temukan elemen paling aneh dalam array dalam waktu logaritmik
Mengingat array integer di mana semua kecuali satu anggota memiliki jumlah kemunculan genap, masalahnya adalah menentukan berapa kali elemen ini muncul. Temukan elemen ganjil yang muncul dalam waktu logaritmik dan ruang konstan jika elemen yang sama muncul berpasangan dalam larik dan tidak akan pernah ada lebih dari dua contoh elemen tertentu dalam satu baris.
Operasi XOR memungkinkan kami untuk menyelesaikan masalah ini dalam waktu linier. Tujuannya adalah untuk XOR setiap elemen dalam array. Hanya unsur-unsur yang muncul ganjil yang tersisa setelah unsur-unsur yang muncul genap saling meniadakan.
Masalah ini bahkan dapat diselesaikan dalam waktu O(log(n)).
24. Bagaimana cara mendapatkan elemen berikutnya yang lebih besar untuk setiap elemen dalam array melingkar?
Elemen yang lebih besar berikutnya untuk setiap elemen dalam array integer melingkar harus ditempatkan. Bilangan bulat pertama yang lebih besar setelah elemen x dalam larik adalah elemen berikutnya yang lebih besar dari elemen tersebut.
Dari kanan ke kiri, kami dapat beroperasi pada item array. Tujuannya adalah untuk mengulang setiap elemen x sampai tumpukan kosong atau kita memiliki elemen yang lebih tinggi di atasnya. Atur elemen x yang lebih besar berikutnya untuk muncul di atas tumpukan ketika itu muncul.
25. Temukan jumlah inversi array?
Temukan jumlah total inversi array. Pasangan I j) disebut sebagai inversi array A jika I j) dan (A[i] > A[j]). Kita harus menghitung setiap pasangan ini dalam array.
Menghitung semua anggota array yang lebih sedikit di sebelah kanannya dan menambahkan hasilnya ke output adalah pendekatan yang mudah.
Solusi ini memiliki kompleksitas O(n2), di mana n adalah ukuran input.
26. Apa Masalah Perangkap Air Hujan?
Menemukan air paling banyak yang dapat terperangkap dalam satu set palang dengan lebar masing-masing satu unit dikenal sebagai masalah “menjebak curah hujan”.
Tujuannya adalah untuk menentukan bar tertinggi yang boleh ditempatkan di kiri dan kanan setiap bar. Minimum dari batang-batang terkemuka di kiri dan kanan, dikurangi tinggi dari batang-batang saat ini, adalah jumlah air yang ditampung di atas setiap batang-batang.
Kesimpulan
Dibandingkan dengan topik struktur data lainnya, array lebih sederhana. Untuk menjawab pertanyaan wawancara array, Anda harus memiliki pemahaman mendasar tentang array.
Anda harus meninjau secara ekstensif dasar-dasar array, termasuk operasi array (dari mendeklarasikan/membuat array hingga mengakses/memodifikasi item array), serta konsep pemrograman seperti loop, rekursi, dan operator dasar agar berhasil menjawab pertanyaan wawancara array. Kenali masalahnya sepenuhnya.
Anda harus mencari klarifikasi jika Anda memiliki pertanyaan. Pikirkan tentang membagi masalah menjadi bagian-bagian yang lebih mudah dikelola. Pastikan Anda memiliki algoritme dalam pikiran sebelum memulai pemrograman; menuliskannya atau memvisualisasikannya dalam diagram alur. kemudian mulai menulis kode.
Tinggalkan Balasan