Kerangka penyelesaian masalah

Soal wawancara coding jarang selesai hanya dengan menulis kode begitu pernyataannya selesai dibaca. Topik ini memperkenalkan kerangka penyelesaian masalah bergaya UMPIRE, yakni enam tahap tetap yang mengubah soal mentah menjadi jawaban teruji, mulai dari pertanyaan klarifikasi sampai taksiran kompleksitas. Satu contoh soal array klasik dikerjakan utuh dengan kerangka itu dalam Python dan Java. Setelah membacanya, proses berpikir di depan pewawancara dapat disuarakan tahap demi tahap, alih-alih dikerjakan dalam diam.

Proses berpikir yang disuarakan#

Pewawancara tidak hanya menilai kode akhir, melainkan juga cara kandidat berpikir sampai ke kode itu. Kandidat yang bekerja dalam diam meninggalkan pewawancara tanpa bahan penilaian dan tanpa kesempatan mengoreksi arah bila pendekatannya meleset. Sebaliknya, proses yang disuarakan membuat kesalahan arah terdeteksi pada menit pertama, ketika memperbaikinya masih murah. Kerangka memberi tempat tetap bagi setiap kalimat yang diucapkan selama pengerjaan soal.

UMPIRE adalah kerangka enam tahap untuk soal pemrograman yang dikerjakan secara langsung. Setiap tahap menghasilkan satu keluaran nyata yang dapat ditunjukkan kepada pewawancara, yaitu rumusan soal versi sendiri, daftar pendekatan kandidat, rencana tertulis, kode yang berjalan, hasil pengujian, dan taksiran biayanya. Karena keluarannya nyata, kemajuan pekerjaan mudah diamati dan tidak ada tahap yang bisa dilewati diam-diam. Keluaran per tahap juga menjadi pola bicara siap pakai, misalnya kalimat pembuka berupa nama tahap dan kalimat penutup berupa keluarannya.

Enam tahap UMPIRE#

Enam tahap UMPIRE berjalan berurutan, tetapi tidak kaku. Understand memastikan soal dipahami dalam versi sendiri, mencakup masukan, keluaran, dan batasannya. Match mencocokkan soal dengan pola yang sudah dikenal, misalnya array, hash map, two pointer, atau rekursi. Plan mengubah pendekatan terpilih menjadi langkah tertulis yang bisa dipahami orang lain tanpa membaca kode. Kode baru ditulis pada tahap Implement, mengikuti rencana yang sudah disepakati. Review menguji kode pada beberapa kasus termasuk kasus tepi, sedangkan Evaluate menaksir waktu dan memori yang dipakainya.

Diagram berikut merangkum urutan keenam tahap beserta tugasnya, dari kiri ke kanan.

Urutan tahap ini juga menyelamatkan saat mentok. Bila kode pada tahap Implement terus menemui jalan buntu, UMPIRE menyuruh mundur satu tahap ke Plan, bahkan ke Match bila polanya ternyata keliru. Mundur seperti ini terlihat seperti kemunduran, padahal biayanya jauh lebih murah daripada menulis ulang kode yang salah arah. Langkah mundur semacam itu hanya mungkin bila setiap tahap meninggalkan keluarannya sendiri.

Pertanyaan klarifikasi yang layak diajukan#

Tahap Understand menghasilkan pertanyaan klarifikasi, dan kualitas pertanyaannya ikut dinilai oleh pewawancara. Pertanyaan yang baik menyempitkan ruang masalah, bukan meminta petunjuk jawaban. Lima pertanyaan berikut layak dibawa ke setiap sesi soal karena muncul di hampir semua soal array dan string.

• Berapa ukuran masukan maksimal, karena ukuran itu menentukan kompleksitas mana yang masih diterima.
• Apakah masukan bisa kosong atau hanya berisi satu elemen, karena kedua kasus itu paling sering merusak kode.
• Apakah boleh ada duplikat atau nilai negatif, karena keduanya mengubah syarat perulangan.
• Bila jawaban tidak tunggal, apakah satu jawaban sudah cukup atau semua jawaban harus dilaporkan.
• Apakah data sudah terurut, karena urutan membuka jalan bagi two pointer dan pencarian biner.

Pertanyaan semacam ini cepat diajukan, lima buah biasanya tidak lebih dari satu menit, tetapi pengaruhnya besar pada sisa sesi. Bila jawaban pewawancara melarang satu pendekatan, misalnya meminta solusi tanpa memori tambahan, larangan itu langsung memangkas daftar kandidat pada tahap Match. Setelah jawaban terkumpul, bacakan sekali lagi rumusan soal versi sendiri, sehingga kesepahaman teruji sebelum tahap Plan dimulai.

Contoh soal: jumlah subarray maksimum#

Kerangka ini sekarang diterapkan pada satu soal klasik. Diberikan array bilangan bulat, misalnya [-2, 1, -3, 4, -1, 2, 1, -5, 4], cari jumlah terbesar yang dapat diperoleh dari sebuah subarray, yaitu potongan elemen berdampingan tanpa melompati satu pun elemen. Pada contoh itu jawabannya 6, diperoleh dari potongan [4, -1, 2, 1].

Tahap Understand memperjelas dua hal. Masukannya satu array yang boleh memuat angka negatif dan panjangnya minimal satu elemen, karena array kosong tidak memiliki subarray apa pun. Keluarannya satu bilangan, yaitu jumlah subarray terbesar, bukan potongannya, meskipun pewawancara bisa meminta potongan itu sebagai pertanyaan lanjutan.

Tahap Match menyusun kandidat pendekatan. Cara paling lugas adalah mencoba semua pasangan batas kiri dan kanan lalu menghitung jumlah setiap potongannya, tetapi cara itu memakan $O(n^2)$ waktu untuk $n$ elemen. Pola yang lebih cocok adalah satu lintasan dengan dua variabel, yakni jumlah berjalan untuk potongan yang sedang diperpanjang dan jumlah terbaik yang pernah tercatat. Pendekatan ini dikenal sebagai algoritma Kadane dan memakan $O(n)$ waktu.

Tahap Plan menuliskan langkahnya dalam tiga baris. Inisialisasi kedua variabel dengan elemen pertama, karena potongan kosong tidak diperbolehkan. Pada setiap elemen berikutnya, jumlah berjalan diperbarui dengan memilih yang lebih besar antara memulai potongan baru dari elemen itu atau meneruskan potongan lama. Jumlah terbaik diperbarui setiap kali jumlah berjalan melampauinya.

Implement, Review, dan Evaluate#

Implementasi mengikuti rencana tanpa keputusan baru. Berikut versi Python-nya, lengkap dengan baris pelacakan di dalam perulangan supaya dua variabel utamanya terlihat bergerak. Pelacakan semacam ini alat belajar, dan boleh dihapus dari kode jawaban.

"""Jumlah subarray maksimum dengan satu lintasan (algoritma Kadane)."""


def jumlah_subarray_maksimum(angka):
    """Kembalikan jumlah terbesar dari subarray berurutan dalam angka."""
    terbaik = angka[0]
    berjalan = angka[0]
    for i in range(1, len(angka)):
        berjalan = max(angka[i], berjalan + angka[i])
        terbaik = max(terbaik, berjalan)
        print(f"i={i}  nilai={angka[i]:3d}  berjalan={berjalan:3d}  terbaik={terbaik:3d}")
    return terbaik


data = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print("array :", data)
hasil = jumlah_subarray_maksimum(data)
print("jumlah subarray maksimum :", hasil)

array : [-2, 1, -3, 4, -1, 2, 1, -5, 4]
i=1  nilai=  1  berjalan=  1  terbaik=  1
i=2  nilai= -3  berjalan= -2  terbaik=  1
i=3  nilai=  4  berjalan=  4  terbaik=  4
i=4  nilai= -1  berjalan=  3  terbaik=  4
i=5  nilai=  2  berjalan=  5  terbaik=  5
i=6  nilai=  1  berjalan=  6  terbaik=  6
i=7  nilai= -5  berjalan=  1  terbaik=  6
i=8  nilai=  4  berjalan=  5  terbaik=  6
jumlah subarray maksimum : 6

Keluarannya memperlihatkan pola inti Kadane. Pada i=3, jumlah berjalan melompat dari -2 menjadi 4 karena memulai potongan baru lebih menguntungkan daripada meneruskan potongan yang selama ini merugi. Nilai 6 tercapai pada i=6 dan tidak ada yang melampauinya sampai akhir, sehingga jawaban akhirnya 6, persis potongan [4, -1, 2, 1] yang diperkirakan di awal.

Algoritma yang sama dalam Java ditulis dengan Math.max, yang berperilaku sama dengan max bawaan Python. Keluarannya identik baris demi baris dengan versi Python, sehingga cukup satu dari keduanya yang diketik ulang saat berlatih.

public class SubarrayMaksimum {

    static int jumlahSubarrayMaksimum(int[] angka) {
        int terbaik = angka[0];
        int berjalan = angka[0];
        for (int i = 1; i < angka.length; i++) {
            berjalan = Math.max(angka[i], berjalan + angka[i]);
            terbaik = Math.max(terbaik, berjalan);
            System.out.printf("i=%d  nilai=%3d  berjalan=%3d  terbaik=%3d%n",
                    i, angka[i], berjalan, terbaik);
        }
        return terbaik;
    }

    public static void main(String[] args) {
        int[] data = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println("array : " + java.util.Arrays.toString(data));
        int hasil = jumlahSubarrayMaksimum(data);
        System.out.println("jumlah subarray maksimum : " + hasil);
    }
}

array : [-2, 1, -3, 4, -1, 2, 1, -5, 4]
i=1  nilai=  1  berjalan=  1  terbaik=  1
i=2  nilai= -3  berjalan= -2  terbaik=  1
i=3  nilai=  4  berjalan=  4  terbaik=  4
i=4  nilai= -1  berjalan=  3  terbaik=  4
i=5  nilai=  2  berjalan=  5  terbaik=  5
i=6  nilai=  1  berjalan=  6  terbaik=  6
i=7  nilai= -5  berjalan=  1  terbaik=  6
i=8  nilai=  4  berjalan=  5  terbaik=  6
jumlah subarray maksimum : 6

Tahap Review menguji kasus tepi sebelum kode dinyatakan selesai. Tiga kasus paling bernilai untuk soal ini adalah array satu elemen, array yang seluruhnya negatif, dan array yang seluruhnya positif. Karena kedua variabel diinisialisasi dengan elemen pertama dan bukan nol, array [-3, -1, -4] menghasilkan -1, yakni potongan satu elemen yang paling sedikit merugi. Kesalahan klasiknya adalah menginisialisasi jumlah terbaik dengan 0, sehingga array yang seluruhnya negatif dilaporkan bernilai 0 padahal jawaban yang benar harus negatif.

Tahap Evaluate menutup siklusnya. Satu lintasan tunggal memakan $O(n)$ waktu dan $O(1)$ memori tambahan, hanya dua variabel bilangan, dibandingkan $O(n^2)$ pada kandidat yang ditolak. Perbandingan dengan kandidat yang sudah disebut pada tahap Match adalah bagian dari jawaban, bukan catatan kaki, karena perbandingan itulah bukti bahwa pola yang dipilih memang tepat.

Kesalahan umum#

1. Menulis kode sebelum klarifikasi. Kebiasaan ini terlihat cepat, tetapi satu asumsi keliru, misalnya mengira array selalu terurut, membuat seluruh kode perlu dibongkar. Perbaikannya adalah mengajukan pertanyaan klarifikasi dan membacakan rumusan soal versi sendiri sebelum menyentuh editor.
2. Diam terlalu lama. Keheningan biasanya lahir dari keinginan menemukan solusi sempurna dalam hati, padahal pewawancara kehilangan bahan penilaian selama keheningan itu. Ucapkan tahap yang sedang dikerjakan beserta kandidat yang sedang dipertimbangkan, meskipun belum pasti, karena arah yang salah justru bisa dikoreksi lebih awal.
3. Berhenti begitu contoh soal lolos. Contoh pada pernyataan soal hanyalah satu kasus, sedangkan kasus tepi seperti array satu elemen dan array seluruhnya negatif justru yang paling sering merusak kode. Susun daftar kasus uji sendiri dan jalankan semuanya sebelum kode dinyatakan selesai.

Ringkasan#

• UMPIRE membagi pengerjaan soal menjadi enam tahap, yaitu Understand, Match, Plan, Implement, Review, dan Evaluate, dengan satu keluaran nyata per tahap.
• Pertanyaan klarifikasi tentang ukuran masukan, kasus kosong, duplikat, dan keunikan jawaban menyempitkan soal sebelum kode ditulis.
• Algoritma Kadane menyelesaikan jumlah subarray maksimum dalam satu lintasan dengan dua variabel, jumlah berjalan dan jumlah terbaik, sehingga memakan $O(n)$ waktu dan $O(1)$ memori tambahan.
• Proses berpikir disuarakan sejak tahap pertama karena pewawancara menilai jalan pemecahan masalahnya, bukan hanya kode akhirnya.

Referensi#

• Coding interview techniques — Tech Interview Handbook — Memperkenalkan metode UMPIRE untuk menyusun pengerjaan soal wawancara coding secara terstruktur.
• Maximum subarray problem — Wikipedia — Deskripsi soal jumlah subarray maksimum beserta algoritma Kadane dan analisis kompleksitasnya.
• Class Math — Java 21 API documentation — Dokumentasi Math.max yang dipakai pada versi Java dalam topik ini.