Wawancara coding untuk posisi pengembang perangkat lunak sering menguji pemahaman algoritma pencarian. Pencarian termasuk kategori soal yang paling sering muncul karena dipakai terus dalam pekerjaan sehari-hari. Berikut tujuh algoritma pencarian untuk coding interview yang perlu kamu kuasai.
1. Linear Search
Linear search memeriksa setiap elemen satu per satu sampai target ditemukan atau data habis. Kompleksitas waktunya O(n), jadi efisien hanya untuk data kecil atau tidak terurut. Di interview, linear search sering muncul sebagai baseline sebelum kamu menawarkan solusi yang lebih baik. Jika pewawancara memberimu array kecil yang tidak terurut, sebutkan bahwa linear search cukup, lalu tunjukkan bahwa kamu tahu keterbatasannya.
2. Binary Search
Binary search bekerja pada data terurut dengan membagi ruang pencarian menjadi dua setiap iterasi. Kompleksitasnya O(log n), jauh lebih cepat daripada linear search untuk data besar. Soal binary search klasik meliputi mencari elemen tertentu, menemukan titik rotasi pada array yang dirotasi, atau mencari batas bawah dan atas. Pastikan kamu bisa menulis versi iteratif dan rekursif tanpa bug, terutama penanganan kondisi batas seperti low <= high dan pembaruan mid.
Untuk memperdalam pemahaman tentang efisiensi, baca Big O Notation: Cara Mengukur Efisiensi Algoritma.
3. Depth-First Search (DFS)
DFS menjelajahi graf atau pohon dengan menelusuri satu cabang sedalam mungkin sebelum mundur. Algoritma ini biasanya diimplementasikan dengan rekursi atau stack. Dalam interview, DFS sering dipakai untuk soal seperti mendeteksi siklus, mencari jalur, atau menghasilkan permutasi. DFS tidak menjamin jalur terpendek pada graf tak berbobot; untuk itu kamu perlu BFS. DFS lebih hemat memori pada graf lebar karena tidak menyimpan seluruh level.
4. Breadth-First Search (BFS)
BFS menelusuri graf level demi level menggunakan queue. Algoritma ini menemukan jalur terpendek pada graf tak berbobot, sehingga sering menjadi pilihan untuk soal mencari jarak minimum atau langkah minimum dalam grid. Kompleksitas waktunya O(V + E) untuk graf dengan V simpul dan E sisi. Saat menulis BFS, tandai simpul sebagai dikunjungi ketika dimasukkan ke queue, bukan saat dikeluarkan, untuk menghindari duplikasi.
Jika kamu perlu menerapkan BFS pada graf berbobot, pertimbangkan Dijkstra. Panduan lengkapnya ada di Panduan Langkah demi Langkah Menerapkan Algoritma Dijkstra.
5. Pencarian dalam Graf Terarah dengan Topological Sort
Topological sort bukan algoritma pencarian dalam arti sempit, tetapi sering muncul dalam soal yang meminta urutan pengerjaan atau deteksi dependensi siklik. Implementasinya menggunakan DFS atau Kahn’s algorithm. Contoh soalnya menentukan urutan mata kuliah berdasarkan prasyarat, atau mendeteksi deadlock pada sistem. Kuasai kedua pendekatan karena pewawancara kadang meminta variasi.
6. A* (A-Star)
A* adalah algoritma pencarian jalur yang menggabungkan biaya aktual (g) dan estimasi heuristik (h). Algoritma ini optimal jika heuristiknya admissible. Dalam coding interview, A* jarang diminta untuk diimplementasikan penuh, tetapi konsepnya sering muncul dalam soal desain sistem atau pengantar kecerdasan buatan. Pahami cara kerja priority queue dan cara memilih heuristik yang tepat, misalnya jarak Manhattan pada grid.
7. Pencarian String (KMP dan Rabin-Karp)
Soal pencarian pola dalam string sering muncul untuk posisi yang berhubungan dengan pengolahan teks. Algoritma Knuth-Morris-Pratt (KMP) menggunakan prefix function untuk mencapai O(n + m), sedangkan Rabin-Karp memakai rolling hash. Keduanya layak diketahui, setidaknya konsep dasarnya, karena pewawancara kadang meminta alternatif dari brute force O(n*m).
Pemahaman struktur data yang tepat juga memengaruhi pilihan algoritma pencarian. Lihat perbandingannya di Membandingkan Struktur Data untuk Belajar Algoritma.
Tips Menghadapi Soal Pencarian di Interview
- Selalu tanyakan apakah data terurut. Jika ya, binary search hampir selalu jadi kandidat pertama.
- Sebutkan kompleksitas waktu dan ruang sebelum menulis kode.
- Untuk graf, tanyakan apakah berbobot dan apakah perlu jalur terpendek.
- Uji dengan kasus tepi: array kosong, satu elemen, target tidak ada.
- Latih menulis kode di atas kertas atau whiteboard tanpa bantuan IDE.
Jika kamu ingin berlatih menulis pesan error yang baik saat menguji kode, ada panduan di Cara Menulis Pesan Error yang Membantu Pengguna, Bukan Menghakimi. Untuk pengembangan web, kamu mungkin perlu memuat data tanpa refresh; simak Perbandingan 3 Plugin jQuery untuk Load Data Tanpa Refresh.
Ringkasan
Tujuh algoritma di atas mencakup soal dari yang sederhana hingga yang kompleks. Fokus pada binary search, DFS, dan BFS karena ketiganya paling sering muncul. Untuk persiapan yang lebih sistematis, lihat Membandingkan Metode Latihan Algoritma: Mana yang Paling Efektif?.
Pertanyaan yang Sering Diajukan
Apakah saya perlu menghafal implementasi setiap algoritma?
Tidak perlu menghafal baris per baris. Yang penting adalah memahami logika dan kompleksitasnya, serta mampu menulis versi yang benar dengan sedikit bantuan.
Algoritma mana yang paling sering keluar di interview?
Binary search, BFS, dan DFS adalah tiga yang paling sering muncul. Kuasai ketiganya terlebih dahulu sebelum mempelajari yang lain.
Bagaimana cara berlatih algoritma pencarian secara efektif?
Kerjakan soal-soal dari platform latihan dengan fokus pada pola, bukan sekadar jawaban. Setelah menyelesaikan satu soal, coba variasikan input atau ubah batasannya untuk memperdalam pemahaman.