Jadual Kandungan[Sembunyi][Tunjukkan]
- 1. Bagaimanakah anda mentakrifkan Array?
- 2. Tatasusunan Dinamik: Apakah Itu? Apakah yang membezakannya daripada Tatasusunan Asas?
- 3. Bagaimanakah tatasusunan dan kamus berbeza antara satu sama lain?
- 4. Senaraikan beberapa kebaikan dan kelemahan tatasusunan.
- 5. Apakah yang dimaksudkan dengan “Sparse Array”?
- 6. Bilakah anda akan memilih senarai terpaut berbanding tatasusunan?
- 7. Apakah yang membezakan tatasusunan diindeks daripada tatasusunan bersekutu?
- 8. Apakah kelebihan Heap berbanding tatasusunan yang disusun?
- 9. Bolehkah kita menentukan saiz tatasusunan menjadi negatif?
- 10. Bagaimanakah anda mencari integer yang hilang dalam tatasusunan 1 hingga 100 elemen?
- 11. Bagaimanakah anda mencari indeks unsur dalam tatasusunan?
- 12. Bagaimanakah anda boleh menyingkirkan elemen tertentu daripada tatasusunan?
- 13. Bagaimanakah kesamaan dua tatasusunan boleh disahkan?
- 14. Apabila kita membincangkan tatasusunan, apakah yang anda maksudkan dengan frasa "Dimensi" dan "Subskrip"?
- Soalan Temuduga Pengekodan
- 15. Cari pasangan dalam tatasusunan yang mempunyai jumlah yang ditentukan
- 16. Isih tatasusunan binari dengan masa linear
- 17. Cari produk dua int terbesar dalam tatasusunan.
- 18. Bagaimana untuk mengalihkan semua sifar tatasusunan ke penghujung
- 19. Bagaimana untuk mengisih tatasusunan dengan dua entri yang ditukar dalam satu operasi.
- 20. Bagaimana untuk menggabungkan dua tatasusunan yang disusun pada tempatnya.
- 21. Bagaimana untuk menyusun semula susunan item dalam kedudukan tinggi dan rendah berselang-seli?
- 22. Bagaimana untuk menggantikan setiap elemen tatasusunan tanpa menggunakan operator pembahagian dengan hasil darab setiap elemen dalam tatasusunan?
- 23. Cari unsur paling ganjil dalam tatasusunan dalam masa logaritma
- 24. Bagaimana untuk mendapatkan elemen yang lebih besar berikutnya untuk setiap elemen dalam tatasusunan bulat?
- 25. Cari kiraan penyongsangan tatasusunan?
- 26. Apakah Masalah Memerangkap Air Hujan?
- Kesimpulan
Temu bual pengekodan mengandungi satu siri soalan DSA. Anda harus mahir dengan tatasusunan jika anda sedang bersiap sedia untuk temu duga teknologi anda yang akan datang dengan FAANG atau perniagaan teknologi Tahap-1 yang lain.
Dalam kebanyakan wawancara pengekodan, ia berada di tempat kedua untuk Strings. Tatasusunan ialah himpunan elemen data berkaitan yang disimpan berdekatan antara satu sama lain dalam ingatan.
Memandangkan ia disambungkan kepada semua bahasa pengaturcaraan, seperti C, C++, Java, Python, Perl, dan Ruby, ia berada di mana-mana. Teruskan membaca untuk beberapa cabaran pengekodan latihan dan soalan serta jawapan temu bual berdasarkan tatasusunan.
Python akan digunakan dalam siaran ini untuk menangani isu pengekodan kerana ia mudah digunakan, difahami dan mesti biasa kepada kebanyakan kita.
Mari kita mulakan.
1. Bagaimanakah anda mentakrifkan Array?
- Sekumpulan jenis data yang berkaitan ialah tatasusunan.
- Tatasusunan sentiasa tetap.
- Jenis pembolehubah yang sama disimpan di beberapa tempat oleh objek tatasusunan.
- Jenis primitif dan rujukan objek kedua-duanya serasi dengannya.
2. Tatasusunan Dinamik: Apakah Itu? Apakah yang membezakannya daripada Tatasusunan Asas?
Penskalaan automatik yang disediakan oleh tatasusunan dinamik (juga dirujuk sebagai tatasusunan boleh tumbuh, tatasusunan boleh diubah saiz, tatasusunan boleh ubah atau Senarai Senarai dalam Java) merupakan kelebihan yang ketara.
Anda mesti sentiasa mengetahui berapa banyak elemen tatasusunan anda akan disimpan terlebih dahulu kerana tatasusunan mempunyai saiz tetap. Tatasusunan dinamik, sebaliknya, berkembang apabila anda menambah ahli tambahan padanya, jadi anda tidak perlu mengetahui saiz tepatnya terlebih dahulu.
3. Bagaimanakah tatasusunan dan kamus berbeza antara satu sama lain?
Ini adalah susunan soalan temuduga berasaskan asas yang kerap ditanya. Berikut ialah perbezaan utama antara tatasusunan dan kamus:
- Tatasusunan ialah senarai tertib item yang serupa. Kamus pula mempunyai pasangan nilai kunci.
- Saiz tatasusunan boleh berubah secara dinamik. Idea dinamik seperti itu tidak wujud dalam kamus.
- Sebelum menggunakan tatasusunan, saiznya mesti ditentukan. Saiz kamus tidak perlu disesuaikan.
- Gunakan pernyataan Redim jika anda ingin mengembangkan saiz tatasusunan. Dalam kamus, elemen boleh ditambah tanpa pengisytiharan.
4. Senaraikan beberapa kebaikan dan kelemahan tatasusunan.
Kelebihan:
- Tatasusunan boleh mengisih beberapa elemen secara serentak.
- lain-lain struktur data, seperti tindanan, baris gilir, senarai terpaut, pokok, graf, dll., boleh dilaksanakan dalam tatasusunan.
- Indeks boleh digunakan untuk mencapai elemen tatasusunan.
Kelemahan:
- Saiz tatasusunan mesti diisytiharkan terlebih dahulu. Pada saat pengisytiharan tatasusunan, kami mungkin tidak, walau bagaimanapun, menyedari saiz yang kami perlukan.
- Struktur tatasusunan adalah statik. Ia membayangkan bahawa saiz tatasusunan sentiasa tetap dan peruntukan memori tidak boleh ditambah atau dikurangkan.
5. Apakah yang dimaksudkan dengan “Sparse Array”?
Tatasusunan jarang ialah tatasusunan data yang mempunyai banyak entri dengan nilai sifar. Sebaliknya, tatasusunan padat mengandungi sebahagian besar itemnya dengan nilai bukan sifar. Indeks tatasusunan jarang, yang menukar nombor kepada objek, mungkin termasuk jurang. Berbanding dengan HashMap, ia lebih cekap ingatan.
6. Bilakah anda akan memilih senarai terpaut berbanding tatasusunan?
Apabila menggunakan senarai terpaut dan bukannya tatasusunan, pertimbangkan:
- Anda tidak memerlukan sebarang elemen untuk mempunyai akses rawak.
- Di mana kebolehramalan temporal adalah penting, anda memerlukan sisipan dan pengalihan masa tetap daripada senarai.
- Untuk membuat baris gilir keutamaan, anda mungkin perlu meletakkan item di tengah senarai.
- Anda tidak tahu berapa lama senarai itu. Jika saiz tatasusunan meningkat, anda mesti mengisytiharkan semula dan menduplikasi memori, sama seperti tatasusunan mudah.
7. Apakah yang membezakan tatasusunan diindeks daripada tatasusunan bersekutu?
Perbezaan utama antara tatasusunan bersekutu dan diindeks disenaraikan dalam jadual berikut.
- Pasangan nilai kunci dalam format teks atau angka digunakan untuk mengisih tatasusunan bersekutu. Kekunci tatasusunan yang diindeks semuanya berangka, dan setiap kunci disambungkan kepada nilai yang berbeza.
- Dalam tatasusunan bersekutu, kuncinya mungkin rentetan. Tatasusunan diindeks dengan kekunci integer bermula pada 0.
- Jadual dua lajur meniru gelagat tatasusunan bersekutu. Serupa dengan jadual satu lajur ialah tatasusunan diindeks.
- Peta ialah jenis tatasusunan bersekutu. Tatasusunan indeks bukan peta.
8. Apakah kelebihan Heap berbanding tatasusunan yang disusun?
Kecekapan masa menggunakan Timbunan atas Tatasusunan Terisih adalah faedah utama. Walaupun operasi timbunan lebih cepat, menyusun tatasusunan memerlukan banyak masa. Timbunan boleh menemui elemen terkecil dengan jauh lebih cepat daripada tatasusunan boleh diisih.
Koleksi nombor yang diberikan boleh disusun dalam salah satu daripada dua cara menggunakan Tatasusunan Diisih. Sebaliknya, untuk koleksi nombor tertentu, mungkin terdapat lebih daripada satu timbunan berpotensi.
9. Bolehkah kita menentukan saiz tatasusunan menjadi negatif?
Tidak, kita tidak boleh menentukan integer negatif sebagai saiz tatasusunan. Tidak akan ada ralat masa kompilasi jika kami mengisytiharkan. Pada masa jalanan, kami akan, bagaimanapun, menghadapi NegativeArraySizeException.
10. Bagaimanakah anda mencari integer yang hilang dalam tatasusunan 1 hingga 100 elemen?
Jumlah siri boleh dikira dengan menggunakan fungsi berikut: n (n + 1) / 2
Hanya jika tatasusunan tidak mempunyai sebarang pendua atau mempunyai lebih daripada satu integer yang hilang, fungsi ini akan beroperasi. Sama ada tatasusunan mempunyai elemen pendua, anda boleh mengisih tatasusunan untuk melihat sama ada terdapat sebarang elemen yang setara.
11. Bagaimanakah anda mencari indeks unsur dalam tatasusunan?
Indeks elemen boleh ditemui melalui carian linear atau binari. Sehingga ia mengesan padanan elemen yang diperlukan, fungsi carian linear akan digelung pada setiap elemen dalam tatasusunan. Ia mengembalikan indeks sebaik sahaja ia mencari elemen padanan. Akibatnya, kerumitan temporal carian linear ialah O. (n). Kedua-dua tatasusunan yang diisih dan tidak diisih boleh menggunakan carian linear.
Menggunakan carian binari, yang membahagikan tatasusunan secara berterusan kepada separuh sehingga median selang sepadan dengan elemen yang diperlukan dan menyediakan indeks, anda boleh mendapatkan indeks elemen jika tatasusunan diisih. Akibatnya, kerumitan temporal carian binari ialah O. (log n).
12. Bagaimanakah anda boleh menyingkirkan elemen tertentu daripada tatasusunan?
Memandangkan anda tidak boleh memadamkan elemen daripada tatasusunan asal kerana ia adalah set tetap dengan saiz yang ditentukan, penemuduga meminta anda mencadangkan pendekatan yang berbeza dan menangani masalah yang ditimbulkan oleh soalan itu. Tindakan terbaik ialah membuat tatasusunan baharu untuk memadamkan elemen. Anda boleh menduplikasi elemen daripada tatasusunan pertama dalam tatasusunan ini dan hanya memasukkan elemen yang ingin anda padamkan.
Strategi lain melibatkan mencari elemen sasaran dalam tatasusunan dan kemudian membalikkan susunan semua item yang berada di sebelah kanan elemen sasaran.
13. Bagaimanakah kesamaan dua tatasusunan boleh disahkan?
Anda mesti terlebih dahulu mengesahkan panjang dua tatasusunan yang disediakan. Item padanan kedua-dua tatasusunan dibandingkan apabila panjangnya sama. Kedua-dua tatasusunan akan dianggap sama. jika setiap pasangan komponen dalam setiap surat-menyurat adalah sama. Pendekatan ini tidak dinasihatkan untuk menyemak kesamaan dua tatasusunan jika tatasusunan bersaiz besar kerana ia akan mengambil banyak masa. Anda juga boleh menggunakan kaedah equals() yang disertakan dalam kelas Arrays, namun, jika penemuduga meminta anda membandingkan dua tatasusunan tanpa menggunakan kaedah terbina dalam, cara ini akan berguna.
14. Apabila kita membincangkan tatasusunan, apakah yang anda maksudkan dengan frasa "Dimensi" dan "Subskrip"?
"Dimensi" tatasusunan ialah bilangan indeks, atau subskrip, yang diperlukan untuk mengenal pasti setiap ahli individu. Subskrip dan dimensi mungkin tidak jelas. Dimensi ialah perihalan julat kunci yang dibenarkan, manakala subskrip ialah nombor. Terdapat hanya satu subskrip yang diperlukan untuk setiap dimensi tatasusunan.
Sebagai contoh, tatasusunan arr[10][5] mempunyai dua dimensi. Saiz 10 pada satu dan 5 pada satu lagi. Untuk menangani komponennya, anda memerlukan dua subskrip. Kedua-duanya adalah antara 0 dan 4; satu antara 0 dan 9, termasuk.
Soalan Temuduga Pengekodan
15. Cari pasangan dalam tatasusunan yang mempunyai jumlah yang ditentukan
Sebagai contoh,
Input:
- nombor = [8, 7, 2, 5, 3, 1]
- sasaran = 10
Output:
- Pasangan ditemui (8, 2)
- Or
- Pasangan ditemui (7, 3)
Input:
- nombor = [5, 2, 6, 8, 1, 9]
- sasaran = 12
Output:
- Pasangan tidak ditemui
16. Isih tatasusunan binari dengan masa linear
Isih tatasusunan binari dalam masa linear dan dalam kawasan tetap. Output sepatutnya memaparkan semua sifar dahulu, kemudian semua.
Sebagai contoh,
- Input: { 1, 0, 1, 0, 1, 0, 0, 1 }
- Output: { 0, 0, 0, 0, 1, 1, 1, 1 }
Pendekatan yang mudah adalah untuk mengira jumlah bilangan tatasusunan 0s, katakan k, dan kemudian mengisi indeks k pertama dalam tatasusunan dengan 0s dan indeks selebihnya dengan 1. Sebagai alternatif, kita mungkin mengira berapa banyak 1 adalah jumlah dalam tatasusunan k, isikan indeks k terakhir dalam tatasusunan dengan 1, dan biarkan indeks yang lain diisi dengan 0.
Pendekatan yang diberikan mempunyai kerumitan masa O(n) dan tidak menggunakan storan tambahan, dengan n ialah saiz input.
17. Cari produk dua int terbesar dalam tatasusunan.
Cari hasil darab terbesar bagi dua nombor dalam tatasusunan integer.
Fikirkan tatasusunan 10 3 5 6 2 sebagai contoh. Pasangan (-10, -3) atau (5, 6) ialah produk tertinggi.
Untuk memikirkan setiap gabungan elemen dan memikirkan produk mereka adalah pendekatan yang bodoh. Jika produk pasangan semasa lebih besar daripada produk maksimum yang diperoleh setakat ini, kemas kini produk maksimum. Cetak komponen produk akhir yang terakhir.
Penyelesaian di atas, di mana n ialah jumlah input, mempunyai kerumitan masa O(n2) dan tidak mengambil ruang lagi.
18. Bagaimana untuk mengalihkan semua sifar tatasusunan ke penghujung
Gerakkan semua sifar dalam tatasusunan integer ke penghujung. Jawapannya hendaklah mengelak daripada menggunakan ruang malar dan mengekalkan susunan relatif komponen tatasusunan.
Input: {1,2,3,0,8,0,4,7}
Output ialah {1,2,3,8,4,7,0,0}
Letakkan elemen pada kedudukan tersedia berikut dalam tatasusunan jika elemen semasa bukan sifar. Isikan semua indeks yang tinggal dengan 0 setelah item tatasusunan semuanya telah diproses.
Penyelesaian sebelumnya mempunyai kerumitan masa O(n), dengan n ialah saiz input.
19. Bagaimana untuk mengisih tatasusunan dengan dua entri yang ditukar dalam satu operasi.
Isih tatasusunan dalam masa linear diberi dua item bertukar dan tatasusunan dengan semua elemennya disusun dalam tertib menaik. Berpura-pura bahawa tatasusunan tidak mengandungi pendua.
Input:= [1,9,3,4,7,2] atau [9,3,7,2,1,4] atau [2,4,1,7,3,9]
Output: = [1,2,3,4,7,9]
Bermula dengan elemen kedua dalam tatasusunan, objektifnya adalah untuk membandingkan setiap elemen dengan pendahulunya. Kedudukan pertikaian disimpan dengan mengambil dua penunjuk, x, dan y.
Kemas kini x kepada indeks elemen sebelumnya dan y kepada indeks elemen semasa jika yang pertama lebih besar daripada yang terakhir. Kemas kini y kepada indeks elemen semasa jika ternyata elemen sebelumnya lebih besar daripada elemen semasa.
Akhir sekali, tukar elemen pada indeks x dan y setelah kami selesai memproses setiap pasangan elemen bersebelahan.
Disebabkan oleh fakta bahawa kaedah yang disebutkan di atas hanya melakukan satu imbasan tatasusunan input saiz n, kerumitan masanya ialah O(n). Tiada ruang tambahan diperlukan untuk penyelesaiannya.
20. Bagaimana untuk menggabungkan dua tatasusunan yang disusun pada tempatnya.
Gabungkan item tatasusunan X[] dan Y[]—dua tatasusunan yang diisih bersaiz m dan n setiap satu—dengan mengekalkan susunan yang diisih, iaitu dengan mengisi X[] dengan elemen terkecil m pertama dan mengisi Y[] dengan elemen yang tinggal.
Jika elemen dalam tatasusunan X[] sudah berada di kedudukan yang betul (iaitu, elemen yang paling kecil di antara elemen yang tinggal), abaikan; jika tidak, gantikannya dengan elemen terkecil, yang juga merupakan ahli pertama Y[]. Untuk mengekalkan susunan yang diisih selepas bertukar, pindahkan elemen (sekarang di Y[0]) ke lokasi yang sepatutnya dalam Y[].
Saiz tatasusunan pertama ialah m dan saiz tatasusunan kedua ialah n, dan kerumitan masa ialah O(mn).
21. Bagaimana untuk menyusun semula susunan item dalam kedudukan tinggi dan rendah berselang-seli?
Susun semula tatasusunan integer supaya setiap ahli berikutnya lebih besar daripada elemen sebelumnya dan seterusnya. Andaikan tatasusunan tidak termasuk unsur pendua.
Menyusun tatasusunan atau menggunakan ruang tambahan tidak diperlukan untuk pendekatan yang berkesan. Pelannya adalah, sebagai permulaan, ahli kedua tatasusunan dan naik dua untuk setiap lelaran gelung.
Tukar komponen jika elemen terakhir melebihi yang pertama. Dalam nada yang sama, tukar kedua-dua item jika elemen berikut lebih besar daripada elemen semasa. Kami akan memperoleh tatasusunan yang dikehendaki yang mematuhi sekatan yang ditentukan pada akhir gelung.
22. Bagaimana untuk menggantikan setiap elemen tatasusunan tanpa menggunakan operator pembahagian dengan hasil darab setiap elemen dalam tatasusunan?
Tanpa menggunakan operator bahagian, gantikan setiap elemen dalam tatasusunan integer dengan hasil darab semua elemen lain.
Dalam masa linear dan ruang malar, kita boleh menggunakan rekursi untuk menangani isu ini. Mengira secara rekursif produk setiap elemen dalam subarray kanan dan menghantar produk subarray kiri sebagai parameter fungsi ialah tanggapan.
Kerumitan masa ialah O(n).
23. Cari unsur paling ganjil dalam tatasusunan dalam masa logaritma
Memandangkan tatasusunan integer di mana semua kecuali satu ahli mempunyai bilangan kejadian genap, masalahnya ialah untuk menentukan berapa kali satu elemen ini muncul. Cari unsur yang berlaku ganjil dalam masa logaritma dan ruang malar jika unsur yang sama berlaku secara berpasangan dalam tatasusunan dan tidak boleh ada lebih daripada dua kejadian unsur tertentu dalam satu baris.
Operasi XOR membolehkan kami menyelesaikan isu ini dalam masa linear. Matlamatnya adalah untuk XOR setiap elemen dalam tatasusunan. Hanya unsur yang berlaku ganjil kekal selepas unsur yang berlaku genap membatalkan satu sama lain.
Masalah ini juga boleh diselesaikan dalam masa O(log(n)).
24. Bagaimana untuk mendapatkan elemen yang lebih besar berikutnya untuk setiap elemen dalam tatasusunan bulat?
Elemen yang lebih besar seterusnya untuk setiap elemen dalam tatasusunan integer bulat harus ditempatkan. Integer pertama yang lebih besar selepas unsur x dalam tatasusunan ialah elemen seterusnya yang lebih besar bagi elemen tersebut.
Dari kanan ke kiri, kami mungkin mengendalikan item tatasusunan. Matlamatnya adalah untuk menggelungkan setiap elemen x sehingga sama ada timbunan kosong atau kita mempunyai elemen yang lebih tinggi di atasnya. Tetapkan elemen x yang lebih besar seterusnya untuk muncul di atas tindanan apabila ia muncul.
25. Cari kiraan penyongsangan tatasusunan?
Cari jumlah bilangan penyongsangan tatasusunan. Pasangan I j) dirujuk sebagai penyongsangan bagi tatasusunan A jika I j) dan (A[i] > A[j]). Kita mesti mengira setiap pasangan ini dalam tatasusunan.
Mengira semua ahli tatasusunan yang kurang daripadanya di sebelah kanannya dan menambah hasil pada output ialah pendekatan yang mudah.
Penyelesaian ini mempunyai kerumitan O(n2), di mana n ialah saiz input.
26. Apakah Masalah Memerangkap Air Hujan?
Mencari air paling banyak yang boleh terperangkap dalam set bar tertentu dengan lebar satu unit setiap satu dikenali sebagai isu "hujan memerangkap".
Matlamatnya adalah untuk menentukan bar tertinggi yang boleh diletakkan di kiri dan kanan setiap bar. Minimum bar terkemuka ke kiri dan kanan, kurang ketinggian bar semasa, ialah kuantiti air yang disimpan di atas setiap bar.
Kesimpulan
Berbanding dengan topik struktur data lain, tatasusunan adalah lebih mudah. Untuk menjawab soalan temuduga tatasusunan, anda perlu mempunyai pemahaman asas tatasusunan.
Anda harus menyemak secara meluas asas tatasusunan, termasuk operasi tatasusunan (daripada mengisytiharkan/membuat tatasusunan kepada mengakses/mengubah suai item tatasusunan), serta konsep pengaturcaraan seperti gelung, rekursi dan pengendali asas untuk berjaya menjawab soalan temu bual tatasusunan. Kenali isu tersebut sepenuhnya.
Anda harus mendapatkan penjelasan jika anda mempunyai sebarang pertanyaan. Fikirkan tentang membahagikan isu kepada bahagian yang lebih mudah diurus. Pastikan anda mempunyai algoritma dalam fikiran sebelum anda memulakan pengaturcaraan; tuliskannya atau gambarkannya dalam carta alir. kemudian mula menulis kod.
Sila tinggalkan balasan anda