Pertanyaan wawancara software engineering favorit saya: menghitung median

• Soal implementasi kecil dalam wawancara teknis bisa lebih efektif daripada teka-teki, dan menghitung median memperlihatkan sekaligus kemampuan coding dasar dan kepekaan desain
• Karena ini adalah soal yang membutuhkan pengurutan, pembahasan secara alami berlanjut ke API: apakah fungsi harus mengurutkan sendiri, apakah pemanggil harus mengurutkan, dan apakah boleh mengubah array asli
• Percabangan untuk panjang ganjil dan genap, perhitungan indeks, serta kesalahan off-by-one cocok untuk mengamati proses debugging kandidat
• Dalam soal singkat ini, kita bisa memeriksa perbedaan median dan rata-rata, kemudahan menulis tes, hingga pengetahuan tentang pustaka standar statistics di Python
• Contoh implementasinya melempar ValueError untuk daftar kosong, menyalin lalu mengurutkan dengan sorted(), kemudian mengembalikan rata-rata dua nilai tengah untuk panjang genap dan nilai tengah untuk panjang ganjil

---

Mengapa soal median cocok untuk wawancara

• Pertanyaan wawancara teknis yang baik bukanlah soal yang dibuat rumit seperti teka-teki, melainkan harus bisa memunculkan topik yang lebih dalam dari implementasi yang intuitif
• Pertanyaan “tulis fungsi yang menerima array angka dan mengembalikan mediannya” cocok dipakai sebagai sinyal ala Fizz Buzz untuk memastikan apakah kandidat benar-benar bisa memprogram
• Pekerjaan mereduksi nilai array menjadi satu hasil termasuk kemampuan dasar, dan soalnya sendiri cukup kecil sehingga mudah melihat percakapan dan debugging secara bersamaan

Titik-titik penilaian yang tampak dalam proses implementasi

• Menghitung median terlebih dahulu membutuhkan pengurutan
  • Perlu diputuskan apakah fungsi akan mengurutkan sendiri atau pemanggil harus memberikan array yang sudah terurut
  • Saat array dikirim sebagai referensi, apakah boleh mengubah data asli juga menjadi bagian dari kontrak API
  • Pilihan seperti ini juga terkait dengan pembahasan performa
• Perhitungan indeks memiliki jebakan off-by-one
  • Yang bisa diamati bukan sekadar ada tidaknya kesalahan, tetapi bagaimana kandidat men-debug soal kecil
• Cara mengembalikan nilai berbeda sesuai panjang array
  • Untuk panjang genap, kembalikan rata-rata dua nilai tengah
  • Untuk panjang ganjil, kembalikan nilai tengah

Percakapan yang berkembang dari soal singkat

• Median dapat berlanjut ke diskusi statistik, misalnya mengapa dalam banyak kasus median bisa menjadi pilihan yang lebih baik dibanding rata-rata
• Input dan nilai yang diharapkan sederhana sehingga mudah diuji, dan kandidat dapat menunjukkan kepekaan mereka terhadap testing
• Di Python, ini juga menjadi kesempatan untuk memperlihatkan pengetahuan tentang pustaka standar statistics

Pilihan dalam contoh implementasi Python

• Daftar kosong memunculkan ValueError("median called with empty list")
• Menggunakan sorted(numbers) sehingga, berbeda dari numbers.sort(), daftar input tidak diurutkan secara langsung
• Panjang dihitung dengan len(numbers), dan indeks tengah dihitung dengan mid = length // 2
• Untuk panjang genap, kembalikan (numbers[mid - 1] + numbers[mid]) / 2.0, sedangkan untuk panjang ganjil kembalikan numbers[mid]

[GN⁺]

Komentar di Lobste.rs

• Saya kurang memahami tulisan ini. Sepertinya penulis tidak tahu bahwa median bisa dihitung dalam O(n). Referensi: https://rcoh.me/posts/linear-time-median-finding/
  Jadi pernyataan bahwa “angka harus sudah terurut sejak awal” itu salah. Karena itu, saya juga tidak menganggap ini sebagai soal wawancara yang bagus. Solusi optimalnya adalah algoritme yang rumit, sehingga sulit diharapkan muncul spontan kecuali kandidat memang menghafalnya, dan apakah ia menghafalnya pun tidak banyak membantu dalam menilai kandidat.
  Lebih baik meminta kandidat memberikan solusi naif: mengurutkan array dengan fungsi library lalu mengembalikan nilai tengah

  • Saya hampir kesal karena pernah tersaring di wawancara telepon setelah memberi solusi n*log(n) untuk soal ini
    Belakangan di kelas algoritme saya belajar quickselect, dan berpikir, “masa mereka berharap saya terpikir ini spontan?” Yah, mungkin memang posisinya tidak cocok untuk saya
  • Saya penulisnya. Kalau kandidat menyebut quickselect, saya rasa itu cukup mengesankan. Meski begitu, saya tidak menganggap ini pertanyaan yang buruk. Dengan algoritme yang intuitif saja sudah ada banyak hal untuk dibahas
    Mengenai pernyataan bahwa kita bisa mengharapkan “solusi naif yang mengurutkan array dengan fungsi library lalu mengembalikan nilai tengah”, saya tidak mengharapkan kandidat menulis kode yang lebih baik daripada python standard library

• Sebagai bonus, kita bisa langsung tahu apakah seseorang pernah belajar algoritme, atau setidaknya menyiapkan diri untuk wawancara. Mereka akan mengusulkan memakai quickselect: https://en.wikipedia.org/wiki/Quickselect

  • Saya terkejut itu tidak disebutkan. Kalau mendapat pertanyaan ini dan memakai C++, saya mungkin akan menggunakan nth_element
    Dan kalau harus menulis quickselect sendiri dari nol, itu juga bisa. Pada dasarnya mirip dengan partitioning + binary search
  • Menurut saya kenyataannya tidak begitu. Pertanyaan ini terlihat seperti soal dasar untuk mengecek “apakah benar-benar bisa memprogram?”, alias “apakah screener sudah melakukan tugasnya dengan benar?”. Sekalipun saya bisa menjelaskan quickselect lancar dari kepala, rasanya saya tetap tidak akan bisa melakukannya dengan sempurna dan akan memilih solusi naif agar tidak membuang waktu pewawancara
  • Kasus panjang array genap itu menarik. Bisa menjalankan quickselect umum dua kali untuk dua indeks tengah, atau menyesuaikan quickselect dengan kebutuhan. Keduanya bisa saja pada dasarnya menjadi hal yang sama
  • Saya bingung karena ada persyaratan bahwa list harus terurut. Secara intuitif pun sebenarnya tidak harus begitu
  • Jawaban yang saya dapat dari LLM adalah ini, plus ada varian immutable yang bisa dipilih kalau perlu

• Tipe int di Python tidak mengalami overflow, tetapi kalau memakai C, C++, atau Go, bukankah pada cabang array dengan panjang genap kita juga perlu khawatir soal addition overflow?

  • Penjumlahan itu terjadi pada float, bukan int. Meski begitu, tetap ada kemungkinan menjadi inf karena overflow. Jika dua elemen array sama-sama sys.float_info.max, jawabannya seharusnya juga sys.float_info.max, tetapi hasil penjumlahannya menjadi inf, dan setelah dibagi 2 pun tetap inf
    Kita mungkin mencoba memperbaikinya dengan mendistribusikan pembagian 2 terhadap penjumlahan, tetapi itu akan menghasilkan jawaban yang salah untuk bilangan subnormal. Kebanyakan orang tampaknya berasumsi angka sebesar yang memicu masalah ini tidak akan muncul dalam program. numpy juga menghasilkan inf di sini disertai peringatan:

    >>> import sys  
    >>> import numpy  
    >>> numpy.median([sys.float_info.max, sys.float_info.max])  
    .../venv/lib64/python3.11/site-packages/numpy/_core/_methods.py:132: RuntimeWarning: overflow encountered in reduce  
      ret = umr_sum(arr, axis, dtype, out, keepdims, where=where)  
    np.float64(inf)  
    

• Sebenarnya ada beberapa cara untuk memilih median itu sendiri. Ada pilihan seperti apakah akan memakai interpolasi linear, mengambil batas atas, atau mengambil batas bawah
  Dan kalau masuk ke kuantil, kita bisa membicarakannya berjam-jam. Pendekatannya harus berbeda antara memilih satu nilai saja dan memilih beberapa nilai sekaligus

• Saya tidak memakai soal wawancara seperti di tulisan asli. Saya menuntut kehalusan, maksudnya tingkat kesulitan penyelesaian soal harus berubah mulus sesuai kemampuan dan pengalaman kandidat. Khususnya, jika hasilnya berubah drastis hanya karena mengetahui keberadaan fungsi library, quickselect, atau algoritme seperti radix sort, maka itu bukan soal yang bagus untuk pengukuran
  Itu jadinya bukan mengukur pengalaman dan kemampuan kandidat, melainkan menguji apakah mereka mengetahui artefak sihir tertentu. Memang bisa dilengkapi dengan pertanyaan lanjutan, tetapi lebih baik sejak awal memberi soal yang lebih halus

  • Kalau bisa dibagikan, saya sangat penasaran dengan contoh konkret soal yang halus seperti itu