En sevdiğim yazılım mühendisliği mülakat sorusu: medyan hesaplama

• Teknik mülakatlardaki küçük uygulama problemleri bulmacalardan daha etkili olabilir; medyan hesaplama, temel kodlama becerilerini ve tasarım sezgisini birlikte ortaya koyar
• Bu, sıralama gerektiren bir problem olduğu için fonksiyonun sıralamayı kendisinin mi yapacağı, çağıranın mı yapacağı ve orijinal dizinin değiştirilip değiştirilemeyeceği gibi API tartışmalarına doğal biçimde uzanır
• Tek ve çift uzunlukları ayıran dallanma, indeks hesaplama ve off-by-one hataları, adayın hata ayıklama sürecini gözlemlemek için uygundur
• Medyan ile ortalama arasındaki fark, test yazma kolaylığı ve Python’un standart statistics kütüphanesi bilgisi gibi konular da bu kısa problem içinde görülebilir
• Örnek uygulama, boş listede ValueError fırlatır, sorted() ile kopyalayıp sıralar; çift uzunlukta ortadaki iki değerin ortalamasını, tek uzunlukta ise ortadaki değeri döndürür

---

Medyan sorusu neden mülakat için uygundur

• İyi bir teknik mülakat sorusu, bulmaca gibi kıvraklaştırılmış bir problem değil; sezgisel bir uygulama içinde daha derin konuları açığa çıkarabilmelidir
• “Bir sayı dizisini alıp medyanını döndüren bir fonksiyon yazın” sorusu, adayın gerçekten program yazıp yazamadığını görmek için bir Fizz Buzz türü sinyal olarak kullanışlıdır
• Dizi değerlerini tek bir sonuca indirgeme işi temel bir yetkinliktir ve problemin kendisi de konuşma ve hata ayıklamayı birlikte görmek için yeterince küçüktür

Uygulama sürecinde ortaya çıkan karar noktaları

• Medyan hesaplamak için önce sıralama gerekir
  • Sıralamayı fonksiyonun kendisinin mi yapacağına, yoksa çağıranın sıralanmış diziyi mi geçmesi gerektiğine karar verilmelidir
  • Dizi referansla geçirildiğinde orijinali değiştirmenin kabul edilip edilmediği de API sözleşmesinin parçasıdır
  • Bu tür seçimler performans tartışmalarına da bağlanır
• İndeks hesaplamasında off-by-one tuzakları vardır
  • Burada önemli olan hatanın kendisinden çok, küçük bir problemi nasıl hata ayıkladığını gözlemleyebilmektir
• Dizi uzunluğuna göre dönüş biçimi değişir
  • Çift uzunlukta ortadaki iki değerin ortalaması döndürülür
  • Tek uzunlukta ortadaki değer döndürülür

Kısa bir problemden genişleyen konuşma

• Medyan, çoğu durumda neden ortalamadan daha iyi bir seçim olabileceği gibi istatistik tartışmalarına açılabilir
• Girdi ve beklenen değerler basit olduğu için test etmesi kolaydır; adayın test sezgisini göstermesi için de uygundur
• Python’da statistics standart kütüphanesi bilgisini ortaya koymak için de bir fırsattır

Örnek Python uygulamasındaki tercihler

• Boş listede ValueError("median called with empty list") oluşur
• sorted(numbers) kullanılarak, numbers.sort()tan farklı olarak girdi listesi doğrudan sıralanmaz
• Uzunluk len(numbers) ile alınır, orta indeks mid = length // 2 olarak hesaplanır
• Çift uzunlukta (numbers[mid - 1] + numbers[mid]) / 2.0 döndürülür, tek uzunlukta ise numbers[mid] döndürülür

[GN⁺]

Lobste.rs yorumları

• Bu yazıyı pek anlayamadım. Yazarın medyanın O(n) zamanda hesaplanabildiğini bilmediği anlaşılıyor. Kaynak: https://rcoh.me/posts/linear-time-median-finding/
  Dolayısıyla “sayılar en baştan sıralı olmalı” ifadesi yanlış. Bu yüzden bunun iyi bir mülakat sorusu olduğunu da düşünmüyorum. En iyi çözüm karmaşık bir algoritma; ezbere bilinmiyorsa o anda beklemek zor, ezbere bilinip bilinmediği de adayı değerlendirmeye pek yardımcı olmaz.
  Bunun yerine adaydan diziyi bir kütüphane fonksiyonuyla sıralayıp ortadaki değeri döndüren saf çözümü sunması istenebilir

  • Bu probleme n*log(n) çözümü verdiğim için telefon mülakatında elendiğimi hatırladım, neredeyse sinirlenecektim
    Daha sonra algoritma dersinde quickselect öğrendim ve “herhalde bunu o anda aklıma getirmemi beklemiyorlardı” diye düşündüm. Neyse, belki de o pozisyona uygun değildim
  • Yazının yazarıyım. Aday quickselect’ten bahsederse epey etkileyici olur bence. Yine de bunun kötü bir soru olduğunu düşünmüyorum. Sezgisel algoritmalarla bile konuşulacak çok şey var
    “Diziyi bir kütüphane fonksiyonuyla sıralayıp ortadaki değeri döndüren saf çözüm” beklenebileceği sözüne gelince, adaydan python standard library’den daha iyi kod beklemem

• Bonus olarak, birinin algoritma çalışıp çalışmadığını, en azından mülakata hazırlanıp hazırlanmadığını hemen anlayabilirsiniz. Çünkü quickselect kullanmayı önerecektir: https://en.wikipedia.org/wiki/Quickselect

  • Bundan bahsedilmemiş olmasına şaşırdım. Bu soru bana sorulsa ve C++ kullansam muhtemelen nth_element kullanırdım
    Quickselect’i sıfırdan elle yazmam gerekseydi onu da yapabilirdim. Temelde bölme + ikili aramaya yakın
  • Gerçekte öyle olmadığını düşünüyorum. Bu soru temel düzeyde “gerçekten programlama yapabiliyor mu?”, yani “ön eleme yapan kişi işini düzgün yapmış mı?” sorusuna bakıyor gibi görünüyor. Quickselect’i kafadan anlatabilecek olsam bile muhtemelen kusursuz yapamazdım ve mülakatçının zamanını boşa harcamamak için saf çözümü seçerdim
  • Dizi uzunluğunun çift olduğu durum ilginç. Ortadaki iki indeks için genel quickselect’i iki kez çalıştırmak ya da quickselect’i işe göre uyarlamak gibi yollar seçilebilir. İkisi pratikte aynı şeye de dönüşebilir
  • Listenin mutlaka sıralı olması gerektiği şartı kafamı karıştırdı. Sezgisel olarak da bunun şart olması gerekmiyor
  • LLM’den aldığım yanıt buydu; gerekirse seçilebilecek değişmez bir varyant da yanında vardı

• Python’ın int tipinde overflow yok ama C, C++ veya Go kullanılıyorsa çift uzunluklu dizi dalında toplama overflow’unu da dert etmek gerekmez mi?

  • O toplama int üzerinde değil, float üzerinde gerçekleşiyor. Yine de overflow ile inf olma ihtimali var. Dizinin iki elemanı da sys.float_info.max ise cevap da sys.float_info.max olmalı, ama toplamanın sonucu inf oluyor ve onu 2’ye bölseniz de hâlâ inf kalıyor
    Toplama için 2’ye bölmeyi dağıtarak düzeltmeye çalışabilirsiniz, ama bu kez denormal sayılarda yanlış cevap çıkar. Çoğu kişi, programda bu soruna yol açacak kadar büyük sayıların bulunmadığını varsayıyor gibi. numpy de burada bir uyarıyla birlikte inf döndürüyor:

    >>> 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)  
    

• Medyanın kendisini seçmenin de aslında birkaç farklı yolu var. Doğrusal interpolasyon mu yapılacak, üst sınır mı kullanılacak, alt sınır mı kullanılacak gibi seçimler var
  Bir de kuantillere geçince saatlerce konuşulabilir. Tek bir tane seçmekle birden fazlasını tek seferde seçmek için yaklaşım farklı olmalı

• Orijinal yazıdaki gibi mülakat soruları kullanmıyorum. Ben yumuşaklık arıyorum; yani soruyu çözmenin zorluğu adayın becerisi ve deneyimine göre akıcı biçimde değişmeli. Özellikle kütüphane fonksiyonlarının, quickselect’in, radix sort gibi algoritmaların varlığını bilip bilmemek sonucu keskin biçimde değiştiriyorsa, ölçüm için iyi bir soru değildir
  Adayın deneyimini ve becerisini ölçmek yerine belirli bir sihirli nesneyi bilip bilmediğini test etmiş olursunuz. Takip sorularıyla telafi edilebilir ama en baştan daha yumuşak bir soru sormak daha iyidir

  • Paylaşabilirseniz, böyle yumuşak sorulara somut örnekleri çok merak ediyorum