Teknik mülakatın boşa çıkması (2022)

 (xeiaso.net)
1 puan yazan GN⁺ 2023-07-09 | 1 yorum | WhatsApp'ta paylaş
  • Palima Aethera, Techaro’nun karmaşık altyapısını kurtaracak aday gibi görünür; ancak canlı kodlama sırasında bilerek tuhaf bir sıralama çözümü sunarak mülakatın havasını değiştirir
  • Mülakatçı Jeff, adının telaffuzunu ve yüzünün gerçek olup olmadığını doğruladıktan sonra Palima’nın MovieFlix altyapı deneyimine ve FreeBSD seçimi örneğine büyük ilgi gösterir
  • Sayı dizisi sıralama görevinde Palima, Haskell ile her değer için bir thread oluşturup değere orantılı süre uyuduktan sonra çıktı veren sleepsort uygular
  • Palima bu çözümün “sabit zamanlı sıralama” olduğunu iddia eder; gecikme süresini 100000 mikro saniye katından 10000 mikro saniye katına indirerek 10 kat optimizasyon yaptığını anlatıp Jeff’i güldürür
  • Mülakattan sonra Palima eleneceğini bekler; ancak Techaro kayda değer bir tutarla işe alma niyetini iletir ve Palima işlerin kendiliğinden sıralanacağını söyleyerek uyumaya karar verir

Rüyada başlayan mülakat günü

  • Palima, rüyasında bileğindeki uyanış tılsımının kaybolduğunu görüp rüya gördüğünü fark eder
  • Sabah kol saatinin titreşimiyle uyandıktan sonra, o gün önemli bir programı olduğunu hatırlar
  • İşe gitmesi 30 saniyede biter ve Palima, kuyruğu ile sırt yüzgecini alacak şekilde değiştirilmiş sandalyesine oturur
  • İş istasyonu Firefox’un eski olduğunu bildirir; bir script yeni sürümü derleyip çalıştırır

Techaro mülakatının başlangıcı

  • Görüntülü toplantı E100 serisi bir servis üzerinden yapılır ve Palima kamera ışığını açar
  • İlk mülakatçı Jeff, Palima’nın adını yanlış telaffuz eder ve hemen düzeltir
    • Palima, Pa-lee-mah ve Aethera için Ay-theer-ah diye telaffuz edildiğini söyler
    • Jeff, başkalarının da doğru söyleyebilmesi için not alacağını belirtir
  • Jeff sanal avatar kullanıp kullanmadığını sorunca Palima, “Bu benim gerçek yüzüm” diye yanıtlar
  • Palima, yalnızca işe alım açıklamasına bakarak Techaro’nun altyapısının kaotik olduğunu ve bir kahramana ihtiyaç duyduğunu anlar

Kariyer tanıtımı ve altyapı deneyimi

  • Palima, dijital otomatik düzenekler yapıp hedeflerini gerçekleştirmeleri için dünyaya saldığı çok iş yaptığını anlatır
  • MovieFlix’te popüler film ve TV programları için eşzamanlı streaming altyapısı kurulmasına katkıda bulunur
  • Açıklayamayacağı çok sayıda proje de olduğunu, Jeff’in şu anda bunların en az üçünden faydalandığını ekler
  • Küçük bir şirkete katılmak istemesinin nedeni insanları daha kişisel düzeyde tanımak istemesidir; makinenin içindeki anonim bir parça gibi çalışmanın cazibesinin uzun sürmediğini düşünür
  • Sevdiği altyapı projesi olarak MovieFlix backend’i için OS kernel benchmark’larını gösterir
    • Palima Linux’un kazanmasını umduğunu, ancak epoll(7) sonrasında FreeBSD daha hızlı çalıştığı için FreeBSD seçtiklerini söyler
    • Hâlâ FreeBSD commit yetkisi olabileceğini de ekler

Canlı kodlama: sleepsort

  • Jeff, Palima’nın geçmişinin Techaro’nun aradığı profile uygun göründüğünü, ancak herkesi aynı ölçütle değerlendirmek için bir kodlama challenge’ı yapmaları gerektiğini açıklar
  • Görev, web sitesindeki bir sayı dizisini sıralamak ve sıralama yöntemini de açıklamaktır
  • Dil serbesttir ve Palima Haskell kodu yazar
  • Uygulama, her sayı için ayrı bir green thread oluşturup threadDelay (100000 * time) sonrasında bir kanala değeri yazarak çıktı verme biçimindedir
  • Palima bu sıralamanın karşılaştırma kullanmadığını ve “bazen tek gerekenin biraz dinlenmek olduğunu” söyler
  • Jeff, sürenin girdiye göre değişip değişmediğini sorunca Palima, zaman karmaşıklığının zaman gibi yan etkilerle ilgilenmediğini yanıtlar

Optimizasyon ve beklenmeyen sonuç

  • Jeff optimizasyon yolunu sorunca Palima yalnızca gecikme çarpanını değiştirir
    • 100000 * time değerini 10000 * time değerine düşürür
    • Palima bunun artık 10 kat daha hızlı olduğunu açıklar
  • Jeff sonunda kahkaha atar; Palima, neden böyle garip bir sıralama algoritması kullandığı sorusuna “neden böyle garip bir soru sordun?” diye karşılık verir
  • Palima, Techaro’nun kendisini barındıracak kadar karmaşık olmadığını; Kubernetes yerine Typhoon Digital’ın tek bir özel sunucusunun bile yeterli olacağını düşünür
  • Mülakatı bitirdikten sonra yakında ret e-postası geleceğini tahmin eder
  • Ancak Techaro, onu kayda değer bir tutarla işe almak istediklerini belirten bir e-posta gönderir; Palima da onların neyin altına girmeye çalıştıklarını bilip bilmediğini merak eder
  • Palima, akşama doğru işlerin kendiliğinden sıralanacağını söyleyerek tekrar uyumaya karar verir

İlgili okumalar

1 yorum

 
GN⁺ 2023-07-09
Hacker News yorumları

  • Bu ne sabit zaman ne de polinomsal zaman; sözde polinomsal zaman. Negatif sayılarda başarısız olur gibi duruyor ve girdiyi ifade eden bit sayısına göre doğrusal olması için 10000 * log(time + min(time) + 1) gibi bir şeye ihtiyaç var
    Hesaplama karmaşıklığı teorisinde, sayısal bir algoritmanın sözde polinomsal zamanda çalışması, çalışma süresinin girdi uzunluğunun (yani sayıyı ifade etmek için gereken bit sayısının) bir polinomu olduğu anlamına gelmez; girdinin sayısal değeri, yani girdide geçen en büyük tamsayı cinsinden bir polinom olduğu anlamına gelir
    https://en.m.wikipedia.org/wiki/Pseudo-polynomial_time

    • Bunun şakanın bir parçası olduğunu biliyorsun, değil mi? Detaya girip şakayı öldürelim dersek, aslında gerçek zamanda beklemek de gerekmiyor
      Hesaplama karmaşıklığı, saatte geçen süreyi değil, hesaplama modelindeki adım sayısını ele alır. sleep sort, işletim sistemi zamanlayıcısının özelliklerinden yararlanır ve sanal zaman ortamında zaman bir sonraki planlanmış olaya doğrudan ilerler. Bunu hesaplama modeli olarak varsayarsan, pratikte polinomsal karmaşıklıkta çalışır
      Bir de başkalarına bir şey öğreteceksen, en azından pseudo-polynomial yazımını doğru yazmak iyi olur
    • Her sözde polinomsal problem, sadece kodlamayı değiştirerek polinomsal zamana çevrilemez mi? Bir değeri sözde polinomsal zamanda hesaplayan bir kutun varsa, her değerin uzunluğu kadar 1 koyup 0 ile ayıran tek bir girdi alan bir kutu yapabilirsin
      Bunu tekrar tamsayıya çevirmek doğrusaldır; sonra mevcut kutuyu çağırıp sonucu döndürürsen, artık benim girdi uzunluğuma göre polinomsal zamanlı olur. Tamsayı dedim ama asıl mesele kodlama biçimi; örneğin ondalık ayırıcı için bir 0, girdiler arası ayraç için 00 kullanmak da mümkün
      Her hâlükârda şakanın özü, uyuyarak geçen sürenin sayılmaması değil mi? Bilgisayar o sırada başka işler yapabilir. “Saçma ama hoşuma gidiyor” hissiyle gayet ikna edici

  • sleep sort /prog/'da [0] ortaya çıktı. O zamanlar sleep sort başlığında yer alan HN takipçileri de epey vardır; xena da onlardan biri olabilir :)
    [0] https://www.cs.princeton.edu/courses/archive/fall13/cos226/l...

    • Eğer mevcut sayıya göre topa barut doldurup, sayı büyüdükçe daha fazla barut koyarak onu daha uzağa fırlatırsam ve sonra yürüyüp yol üzerindeki sayıları toplarsam, buna fiziksel sıralama mı denir?
    • /prog/'u düşünmeyeli gerçekten çok olmuş. En sevdiğim gönderi, bir çırak programcının “küçük, eşit ya da büyük” kontrolü yapmak istediğinde kullanılan <=> operatörünü icat ettiğini anlatıyordu. Dâhiyane

  • Asıl yazarın da dediği gibi, bu yazı aphyr'ın Interview serisine, örneğin “Rewriting the Technical Interview” gibi metinlerin anlatım tarzına çok benziyor. Hepsi keyifle okunur
    [0] - https://aphyr.com/posts/353-rewriting-the-technical-intervie...

    • Üslup oldukça farklı ama teknik mülakatlarla dalga geçmesi açısından “Fizzbuzz in Tensorflow” (2016) da var
      https://joelgrus.com/2016/05/23/fizz-buzz-in-tensorflow/
      Kısa bir tat bırakması için:

      interviewer: Um, you understand the problem is fizzbuzz, right?
      me: Do I ever. So, now let's talk models. I'm thinking a simple multi-layer-perceptron with one hidden layer

  • Bilgisayarda sıralama, girdinin okunmasını gerektirdiği için en azından doğrusal zaman ister. Girdi hakkında eşit dağılım gibi ek bilgiler bilinmiyorsa bu daha da geçerlidir
    Doğrusal zamanlı sıralamalar arasında sleep sort, postman sort, counting sort gibi şeyler vardır. Tabii bunlar sınırlı sayı kümeleri ya da sıralanabilir anahtarlar içindir
    Ama bilgisayar yerine abaküs kullanırsan, neredeyse gerçekten sabit zamanlı sıralama sayılabilecek bir şey var: https://en.wikipedia.org/wiki/Bead_sort

    • Bir de sorting network diye bir şey var. Gerçi bu, asıl noktayı pek değiştirmiyor :D

  • Sevimli bir hikâye ama hiçbir anlamda sabit zaman değil
    N adet thread oluşturup hepsini sıralı bir uyandırma listesine eklemek, işletim sistemine ya da dil çalışma zamanına bağlı olarak O(N log N) ile O(N^2) arasında sürer
    Bir yerlerde sıralı liste, heap veya N^2 algoritması vardır. Aynı şekilde sleep sort'un kendisi de N adet sıralı öğeyi yazdırmak için N thread'i uyandırmak zorunda olduğundan en az doğrusal zamandır
    Daha da kötüsü, gerçek duvar saati süresi de değerlerin büyüklüğüne göre artar. Önce en küçük ve en büyük değeri bulup aralığı sıkıştırabilirsiniz ama bu da doğrusal zamandır

    • Espriyi öldürme riskini göze alırsam, “sabit zaman” dediğimde zaman karmaşıklığı analizinin söylemini ve biçimini ima ediyordum ama gerçekten o anlamda söylemiyordum
      Burada “zaman” kelimesine dair birbiriyle çakışan iki bakışı kullanan çift anlamlı bir şaka var. Karmaşıklık analizi açısından bir sıralama algoritmasını sabit zamanlı yapmak imkânsız, bu doğru
      Şakanın asıl kastı duvar saati zamanı. Mülakatta daha ilgili olan süre de bu ve pratikte biri size “bir tamsayı sıralama fonksiyonu yazın” gibi bir şey attığında 100'den küçük sayılar kullanması pek yaygın olmadığından bu program hissedilir biçimde neredeyse anında çalışır
      Bilgisayar biliminin nasıl çalıştığına dair anlayışı tersyüz ederek dalga geçen ince, üstdilsel bir şaka. Şakanın tutmamasına üzüldüm
    • Sonlu ömürlü bir evrende her şey sabit zamandır
      https://en.wikipedia.org/wiki/Ultimate_fate_of_the_universe#...
    • Teoride sleep'e giren argümanın eninde sonunda bir tamsayıya indirgenmesi gerektiğinden, radix sort gibi bir şey kullanarak bunu doğrusal zamanda da halledebilirsiniz
      En büyük değerin büyüklüğüne bağımlılık doğsa bile bunun avantaj sağladığı problem alanları vardır
      Elbette pratikte böyle bir sistem yok. Sistem çağrısı timeout'ları genelde bu yaklaşımın avantajlı olduğu yerler değil. Ve tabii ki maksimum değere doğrusal orantılı bir yöntem yerine yalnızca log(max_value) ile orantılı olan radix sort'u doğrudan uygulamak daha iyidir
    • N adet thread oluşturup bunları sıralı bir uyandırma listesine eklemenin maliyetinin O(N log N) ile O(N^2) arasında olması, scheduling sistemlerinin temel bir sınırı değildir
      Özellikle de thread sayısına göre sabit zamanlı scheduling mümkün kılan özel donanımları hesaba katarsanız. Örneğin pratikte ekonomikliği hiç olmayan ama teorik olarak, bilgi paketlerini devasa bir mesafeye göre dizilmiş ayna kümesine lazerle sektirip bilgisayara bağlı bir algılayıcıya geri döndüren bir scheduler yapabilirsiniz
      Bu, ışık hızını kullanarak belirlenmiş süre kadar gecikme yaratma yöntemidir. Dolayısıyla sleep sort herhangi bir thread scheduling yönteminin gizli algoritmik karmaşıklığına özsel olarak bağımlı değildir; pratik olmasa da teoride O(1)'e optimize edilebilir
    • Bu, Kubernetes kümesi kurup “Hello World” döndürme tarzına benziyor

  • Bunu beğendiyseniz Protos adında bir nevi devam eseri de var: https://xeiaso.net/blog/protos
    Bu “evrenin” hikâyelerini daha fazla yazıyorum ama hiciv enerjisinin dolması biraz zaman alıyor. Sonraki bölüm uzamsal hesaplama olabilir

    • “Stand-up toplantısının başlamak üzere olduğunu haber veren takvim bildirimi tam çalacakken” kısmı bizim evren gibi
      Yine de o evren isim koyma konusunda daha iyi gibi görünüyor

  • threadDelay (100000 * time) ifadesini threadDelay (10000 * time) olarak değiştirip “artık on kat daha hızlı” demesi şu yazıyla ilgili: https://thedailywtf.com/articles/The-Speedup-Loop

  • Yazıyı okumadım ama böyle şeylerden nefret ediyorum. Bir keresinde Meta ile uzaktan mülakat yaptım ve karşımdaki kişi bütün süre boyunca mikrofona doğru bir şeyler yiyordu
    O kadar dikkat dağıtıcıydı ki for döngüsü yazmayı bile unuttum

    • Uzaktan işe alım çok daha iyi. Eskiden işe alım sorumlusu ya da İK ile kısa bir görüşmeden sonra takım elbise giyip uzaklara araba sürmek ya da uçmak gerekiyordu ve genelde bütün gün gidiyordu
      Çalışıyorsanız izin almanız gerekiyordu ve “Sınırlı iznimi buna mı harcıyorum?”, “Park yeri bulabilecek miyim?”, “Zamanında varabilecek miyim?” gibi stresler vardı. Sonra 30 dakikalık bir “ilk görüşme” yapıp haftalarca bekliyor, ardından ya gerçek mülakata çağrılıyor ya da tamamen görmezden geliniyordunuz
      Tüm süreç bir ay sürebiliyor, en az iki gün izin ve ciddi yolculuk gerektirebiliyordu
      Şimdi ise işe alım sorumlusu ya da İK arayıp görüntülü görüşme yapıp yapamayacağınızı soruyor, aynı gün 15-20 dakikalık bir görüşme oluyor, ardından özgeçmişi karar vericiye iletiyorlar ve bir veya daha fazla görüntülü mülakat ya da teknik oturum planlıyorlar. Bazı şirketler rahatça evden kişilik/teknik test yapmanızı istiyor
      Uzaktan çalışan biriyseniz hepsini öğle arasında bile halledebilirsiniz. Yüz yüze iletişimin bant genişliği çok daha yüksek ama aynı gün sabah Tel Aviv'deki bir şirketle, öğlen Warsaw'daki bir şirketle, akşam da California'daki bir şirketle mülakat yapabilmek ancak uzaktan mümkün

  • 1000 thread oluşturmak en azından doğrusal zaman değil mi? Logaritmiğe kadar düşürülebilir belki ama o kod bunu kendiliğinden yapıyor gibi görünmüyor

    • “Zaman”ı ne olarak aldığınıza bağlı. Algoritmik karmaşıklıktaki zaman ise en az doğrusal, evet. Duvar saati zamanıysa, yani mülakat kodunda daha önemli olan zaman, sabit zamandır
    • sleep sort'un diğer sıralama algoritmalarından daha sabit zamanlı olduğu pek söylenemez
      sleep sort'un sabit zamanlı olması için girdiye bir üst sınır, yani en büyük sayıya bir limit olması ve girdi okuma, işleme, thread oluşturma gibi keyfi işleri saymamanız gerekir
      Ama bunlara izin verirseniz diğer bütün sıralamalar da sabit zamanlı olur. Sanırım ikisinden yalnızca birine izin vermek bile yeterli
    • Aslında doğrusal bile değil. Uyutma işlemi bir heap ekleme ve O(log n) sürüyor
    • Mülakat sırasında gerçekten uyuyordu galiba. Yoksa girdideki tüm değerler üzerinde sıralı döngü yapan bir programın daha ilk satırı ortadayken asimptotik karmaşıklığın “sabit zaman” olduğunu iddia edemezsiniz

  • Eğer thread runtime'ı kendi zaman kavramını koruyorsa, algoritmanın gerçek zamanda uyumasına bile gerek yoktur
    Tüm thread'ler oluşturulduktan sonra runtime, tüm thread'lerin boşta olduğunu ve sıradaki planlanacak thread'in zaman N'deki thread olduğunu fark edebilir; bu durumda mevcut zamanı N olarak güncelleyip o thread'i çalıştırması yeterlidir. Bunu tekrarlarsanız hiç sleep olmadan sıralanmış bir dizi elde edersiniz
    Sonuçta sıralama işi, thread'ler uyumaya başladığı anda zaten bitmiştir; daha sonra onları uyandıracak bir düzenleyiciye, örneğin bir timer wheel'e, kendilerini kaydettirmiş durumdadırlar. Gerçekte uyuma işlemini gerçekleştirmeye gerek yoktur
    Haskell'i bilmiyorum ama Rust'ın tokio runtime'ı bunu start_paused ile mümkün kılıyor: https://docs.rs/tokio/latest/tokio/runtime/struct.Builder.ht...

    • Bunu temelde ayrık olay simülasyonunun içeride çalışma biçimi olarak anlıyorum. Uygun bir veri yapısında, örneğin bir heap'te, gelecekteki olay sınırlarını tutup; gelecekteki olayları heap'e eklemekle bir sonraki olayı heap'ten çıkarmayı sırayla yaparsınız
      Çeşitli soyutlama katmanlarını ve atlanan uygulama ayrıntılarını bir kenara bırakırsak, böyle bir scheduler ile değerleri sıralamak düpedüz heap sort'tur :)
    • Gerçekte sırada neyin çalıştırılacağını hesaplamaya başlarsanız, selection sort'u yeniden icat etmiş olursunuz ve artık doğrusal zamanlı değildir. Bu yüzden pratikte anlamlı bir sıralama algoritması değildir :)