Struktur Data Yang Paling Penting Yang Harus Anda Ketahui Tentang Wawancara Pemrograman Anda

Nicklaus Wirth, seorang ilmuwan komputer Swiss, menulis sebuah buku pada tahun 1976 berjudul Algorithms + Data Structures = Programs .

Setelah lebih dari 40 tahun, identitas ini tetap valid. Inilah sebabnya mengapa pencari kerja yang ingin menjadi programmer harus menunjukkan bahwa mereka mengetahui struktur data dan dapat menerapkannya.

Dalam hampir semua tugas, seorang kandidat membutuhkan pemahaman yang mendalam tentang struktur data. Pada saat yang sama, tidak terlalu penting apakah Anda seorang lulusan (lulus dari universitas atau kursus pemrograman), atau Anda memiliki pengalaman puluhan tahun di belakang Anda.

Kadang-kadang dalam pertanyaan wawancara satu atau lain struktur data disebutkan secara langsung, misalnya, "diberikan pohon biner". Dalam kasus lain, tugas dirumuskan dengan cara yang lebih terselubung, misalnya, "Anda perlu melacak berapa banyak buku yang kami miliki dari masing-masing penulis."

Mempelajari struktur data adalah bisnis yang sangat diperlukan, bahkan jika Anda hanya ingin meningkatkan profesional di pekerjaan Anda saat ini. Mari kita mulai dengan dasar-dasarnya.

Diterjemahkan ke Alconost

Apa itu struktur data?

Singkatnya, struktur data adalah wadah di mana informasi disusun dengan cara yang khas. Berkat "tata letak" ini, struktur data akan efektif dalam beberapa operasi dan tidak efisien pada yang lain. Tujuan kami adalah untuk memahami struktur data sedemikian rupa sehingga Anda dapat memilih dari mereka yang paling cocok untuk memecahkan masalah spesifik yang Anda hadapi.

Mengapa kita membutuhkan struktur data?

Karena struktur data digunakan untuk menyimpan informasi secara tertib, dan data adalah fenomena paling penting dalam ilmu komputer, nilai sebenarnya dari struktur data jelas.

Tidak masalah apa pun tugas yang Anda selesaikan, dengan satu atau lain cara Anda harus berurusan dengan data, apakah itu gaji karyawan, harga saham, daftar produk untuk pergi ke toko atau direktori telepon biasa.

Bergantung pada skenario tertentu, data harus disimpan dalam format yang sesuai. Kami memiliki sejumlah struktur data yang menyediakan beragam format kepada kami.

Struktur Data Umum

Pertama, mari daftar struktur data yang paling umum, dan kemudian parsing masing-masing pada gilirannya:

1. Array
2. Tumpukan
3. Antrian
4. Daftar Tertaut
5. Pohon
6. Hitungan
7. Burs (pada dasarnya, ini juga pohon, tetapi mereka harus dipertimbangkan secara terpisah).
8. Tabel hash

Array

Array adalah struktur data paling sederhana dan paling umum. Struktur data lainnya, seperti tumpukan dan antrian, berasal dari array.

Yang diperlihatkan di sini adalah susunan sederhana dari elemen-elemen yang mengandung ukuran 4 (1, 2, 3, dan 4).

Setiap item data diberi nilai numerik positif yang disebut indeks dan sesuai dengan posisi item ini dalam array. Di sebagian besar bahasa pemrograman, elemen dalam array diberi nomor dari 0.

Ada dua jenis array:

• Satu dimensi (seperti yang ditunjukkan di atas)
• Multidimensional (array di mana array lain tertanam)

Operasi array yang paling sederhana

• Sisipkan - masukkan elemen pada posisi dengan indeks yang diberikan
• Dapatkan - kembalikan elemen yang menempati posisi dengan indeks yang diberikan
• Hapus - hapus item dengan indeks yang ditentukan
• Ukuran - Dapatkan jumlah total elemen dalam array

Wawancara Pertanyaan yang Sering Diajukan

• Temukan elemen array minimum kedua
• Temukan bilangan bulat yang tidak berulang dalam array
• Gabungkan dua array yang diurutkan
• Susun ulang nilai positif dan negatif dalam array

Tumpukan

Semua orang tahu opsi "Batalkan" yang terkenal, yang disediakan di hampir semua aplikasi. Pernah bertanya-tanya bagaimana cara kerjanya? Artinya adalah ini: keadaan sebelumnya dari pekerjaan Anda disimpan dalam program (jumlah negara yang disimpan terbatas), dan mereka berada dalam memori dalam urutan ini: elemen yang disimpan terakhir lebih dulu. Array saja tidak bisa menyelesaikan masalah ini. Di sinilah tumpukan berguna.

Tumpukan dapat dibandingkan dengan tumpukan buku yang tinggi. Jika Anda membutuhkan buku yang terletak di dekat bagian tengah tumpukan, Anda harus terlebih dahulu menghapus semua buku di atas. Beginilah prinsip LIFO bekerja (Last come, first go).

Itu terlihat seperti tumpukan yang mengandung tiga elemen data (1, 2 dan 3), di mana 3 berada di atas - oleh karena itu akan dihapus terlebih dahulu:

Operasi tumpukan paling sederhana:

• Push - Mendorong item ke tumpukan di atas
• Pop - Mengembalikan item teratas setelah menghapusnya dari tumpukan
• isEmpty - Mengembalikan nilai true jika tumpukan kosong
• Top - Mengembalikan item teratas tanpa mengeluarkannya dari tumpukan

Wawancara Pertanyaan yang Sering Diajukan tentang Stack

• Hitung ekspresi postfix menggunakan stack
• Sortir Nilai pada Stack
• Periksa tanda kurung yang seimbang dalam ekspresi

Antrian

Antrian, seperti tumpukan, adalah struktur data linier di mana elemen disimpan secara berurutan. Satu-satunya perbedaan yang signifikan antara tumpukan dan antrian adalah bahwa dalam antrian, bukannya LIFO, prinsip FIFO berlaku (First come, first go).

Contoh realistis ideal antrian - ini adalah antrian pelanggan di kantor tiket. Pembeli baru berada di ujung garis, bukan di awal. Orang yang berada dalam antrian terlebih dahulu akan menjadi yang pertama untuk membeli tiket dan meninggalkannya terlebih dahulu.

Berikut adalah gambar antrian dengan empat elemen data (1, 2, 3, dan 4), di mana 1 masuk terlebih dahulu dan meninggalkan antrian terlebih dahulu:

Operasi antrian sederhana

• Enqueue () - Menambahkan item ke akhir antrian
• Dequeue () - Menghapus item dari depan antrian
• isEmpty () - Mengembalikan nilai true jika antrian kosong
• Top () - Mengembalikan item pertama dalam antrian

Wawancara Pertanyaan yang Sering Diajukan

• Menerapkan tumpukan menggunakan antrian
• Bayar item k pertama dalam antrian
• Hasilkan angka biner dari 1 hingga n menggunakan antrian

Daftar tertaut

Daftar tertaut adalah struktur data linear penting lainnya yang sekilas menyerupai sebuah array. Namun, daftar tertaut berbeda dari array dalam alokasi memori, struktur internal, dan bagaimana operasi dasar menyisipkan dan menghapus dilakukan di dalamnya.

Daftar tertaut menyerupai rantai simpul, yang masing-masing berisi informasi: misalnya, data dan penunjuk ke simpul berikutnya dalam rantai. Ada pointer kepala yang sesuai dengan elemen pertama dalam daftar yang ditautkan, dan jika daftar itu kosong, maka itu hanya diarahkan ke nol (tidak ada).

Menggunakan daftar tertaut, sistem file, tabel hash, dan daftar adjacency diimplementasikan.

Ini adalah bagaimana Anda dapat memvisualisasikan struktur internal daftar tertaut:


Ada beberapa jenis daftar tertaut:

• Daftar Tautan Tunggal (Searah)
• Daftar tertaut ganda (dua arah)

Operasi paling sederhana dengan daftar tertaut adalah:

• InsertAtEnd - Menyisipkan item yang ditentukan di akhir daftar yang ditautkan.
• InsertAtHead - Menyisipkan elemen yang ditentukan di awal (dari kepala) dari daftar tertaut
• Hapus - Menghapus item yang ditentukan dari daftar yang ditautkan.
• DeleteAtHead - Menghapus item pertama dalam daftar yang ditautkan.
• Cari - Mengembalikan item yang ditentukan dari daftar yang ditautkan.
• isEmpty - Mengembalikan nilai true jika daftar tertaut kosong

Wawancara Pertanyaan yang Sering Diajukan:

• Bayar daftar tertaut
• Temukan lingkaran dalam daftar tertaut
• Kembalikan simpul ke-N dari atas daftar tertaut
• Hapus nilai duplikat dari daftar tertaut

Hitungan

Grafik adalah sekumpulan node yang terhubung satu sama lain dalam bentuk jaringan. Node juga disebut simpul. Pasangan (x, y) disebut tepi, yang berarti bahwa titik x terhubung ke titik y . Suatu edge dapat memiliki bobot / biaya - indikator yang mengkarakterisasi seberapa mahal transisi dari vertex x ke vertex y.


Jenis grafik:

• Grafik tidak terarah
• Grafik Berorientasi

Dalam bahasa pemrograman, grafik dapat terdiri dari dua jenis:

• Matriks adjacency
• Daftar Adjacency

Algoritma traversal grafik umum:

• Pencarian luas
• Pencarian Kedalaman

Wawancara Pertanyaan yang Sering Diajukan:

• Terapkan pencarian luas dan mendalam
• Periksa apakah grafik itu pohon atau tidak
• Hitung jumlah tepi dalam grafik
• Temukan jalur terpendek antara dua puncak

Pohon

Pohon adalah struktur data hierarkis yang terdiri dari simpul (node) dan tepi yang menghubungkannya. Pohon mirip dengan grafik, namun, perbedaan utama antara pohon dan grafik adalah ini: tidak ada siklus dalam pohon.

Pohon banyak digunakan di bidang kecerdasan buatan dan dalam algoritma yang kompleks, bertindak sebagai gudang informasi yang efektif dalam menyelesaikan masalah.

Berikut adalah diagram pohon sederhana dan terminologi dasar yang terkait dengan struktur data ini:


Jenis pohon berikut ada:

• N-tree
• Pohon seimbang
• Pohon biner
• Pohon pencarian biner
• Pohon AVL
• Ebony merah
• 2-3 pohon

Dari pohon-pohon di atas, pohon biner dan pohon pencarian biner paling sering digunakan.

Pertanyaan wawancara yang sering diajukan tentang pohon:

Temukan ketinggian pohon biner
Temukan nilai maksimum kth di pohon pencarian biner
Temukan node yang terletak "k" dari root
Temukan nenek moyang dari simpul yang diberikan di pohon biner

Boron

Boron, juga disebut sebagai "pohon awalan", adalah struktur data seperti pohon yang sangat efektif dalam memecahkan masalah string. Ini menyediakan pengambilan data cepat dan paling sering digunakan untuk mencari kata-kata dalam kamus, autocomplete di mesin pencari, dan bahkan untuk IP routing.

Inilah bagaimana tiga kata "atas" (atas), "demikian" (karenanya), dan "mereka" (mereka) disimpan di hutan:


Kata-kata disusun dari atas ke bawah, dan simpul hijau "p", "s" dan "r" masing-masing lengkap, kata "atas", "demikian" dan "mereka".

Pertanyaan wawancara yang sering diajukan tentang bur:

• Hitung jumlah total kata yang disimpan di hutan pinus
  
• Tampilkan semua kata yang disimpan di hutan.
  
• Urutkan elemen array menggunakan boron
  
• Membangun kata-kata kosakata menggunakan boron
  
• Buat Kamus T9
  

Meja hash

Hashing adalah proses yang digunakan untuk secara unik mengidentifikasi objek dan menyimpan setiap objek dengan indeks pra-komputasi yang disebut "kuncinya". Dengan demikian, objek disimpan sebagai nilai kunci, dan koleksi objek tersebut disebut kamus. Setiap objek dapat dicari dengan kuncinya. Ada beberapa struktur data yang dibangun berdasarkan prinsip hashing, tetapi paling sering tabel hash digunakan dari struktur tersebut.

Sebagai aturan, tabel hash diimplementasikan menggunakan array.

Kinerja struktur data hash tergantung pada tiga faktor berikut:

• Fungsi hash
• Ukuran Meja Hash
• Metode Pengolahan Tabrakan

Berikut ini menunjukkan bagaimana hash memetakan ke array. Indeks array ini dihitung menggunakan fungsi hash.

Wawancara Pertanyaan Hash Yang Sering Diajukan:

• Temukan pasangan simetris dalam array
• Lacak jalur lengkap
• Cari apakah array adalah himpunan bagian dari array lain
• Periksa apakah array terpisah

Di atas menggambarkan delapan struktur data paling penting yang pasti perlu Anda ketahui sebelum Anda pergi ke wawancara pemrograman.

Semoga berhasil dan pembelajaran yang menarik! :)

Tentang penerjemah

Artikel ini diterjemahkan oleh Alconost.

Alconost melokalkan game , aplikasi , dan situs dalam 68 bahasa. Penerjemah asli bahasa, pengujian linguistik, platform cloud dengan API, pelokalan berkelanjutan, manajer proyek 24/7, segala format sumber daya string.

Kami juga membuat video iklan dan pelatihan - untuk situs yang menjual, gambar, iklan, pelatihan, permainan asah, penjelajah, trailer untuk Google Play dan App Store.

Lebih detail