Wawancara Teknis Gagal (2022)

 (xeiaso.net)
1 poin oleh GN⁺ 2023-07-09 | 1 komentar | Bagikan ke WhatsApp
  • Palima Aethera tampak seperti kandidat yang bisa menyelamatkan infrastruktur Techaro yang kacau, tetapi membalikkan suasana wawancara dengan sengaja memberikan solusi pengurutan yang ganjil saat live coding
  • Pewawancara Jeff, setelah memastikan pelafalan nama dan apakah wajah itu asli, menunjukkan ketertarikan besar pada pengalaman Palima dengan infrastruktur MovieFlix dan alasan memilih FreeBSD
  • Dalam tugas mengurutkan array angka, Palima mengimplementasikan sleepsort di Haskell dengan membuat thread untuk setiap nilai, lalu tidur sebanding dengan nilainya sebelum mencetaknya
  • Palima bersikeras bahwa solusi ini adalah “pengurutan waktu konstan”, dan menjelaskan bahwa ia mengurangi waktu tunda dari kelipatan 100000 menjadi 10000 mikrodetik untuk optimalisasi 10x, yang membuat Jeff tertawa
  • Setelah wawancara, Palima memperkirakan akan ditolak, tetapi Techaro malah mengirim niat perekrutan dengan nominal yang cukup besar, dan Palima memutuskan untuk tidur karena pekerjaan itu akan mengurutkan dirinya sendiri

Hari wawancara yang dimulai dari mimpi

  • Dalam mimpi, Palima melihat jimat kewaspadaan di pergelangan tangannya hilang dan menyadari bahwa dirinya sedang bermimpi
  • Setelah terbangun di pagi hari karena getaran jam tangan, ia teringat ada jadwal penting hari itu
  • Perjalanan ke tempat kerja selesai hanya dalam 30 detik, dan Palima duduk di kursi yang dimodifikasi agar bisa menampung ekor dan sirip punggungnya
  • Workstation memberi tahu bahwa Firefox sudah usang, lalu skrip membangun dan menjalankan versi baru

Awal wawancara Techaro

  • Rapat video dilakukan melalui layanan seri E100, dan Palima menyalakan lampu kamera
  • Pewawancara pertama, Jeff, salah mengucapkan nama Palima lalu langsung membetulkannya
    • Palima menjelaskan bahwa pelafalannya adalah Pa-lee-mah, dan Aethera dibaca Ay-theer-ah
    • Jeff berkata ia akan mencatatnya agar orang lain juga bisa menyebutnya dengan benar
  • Ketika Jeff bertanya apakah ia memakai avatar virtual, Palima menjawab, “Ini wajah asliku”
  • Hanya dari deskripsi lowongan, Palima sudah menangkap bahwa infrastruktur Techaro sedang kacau dan membutuhkan seorang pahlawan

Perkenalan karier dan pengalaman infrastruktur

  • Palima memperkenalkan dirinya sebagai seseorang yang sering membuat perangkat otomatis digital lalu melepasnya ke dunia untuk menjalankan tujuannya
  • Di MovieFlix, ia berkontribusi membangun infrastruktur streaming serentak untuk film dan acara TV populer
  • Ia menambahkan bahwa ada banyak proyek yang tidak bisa diungkapkan, dan Jeff saat ini menerima manfaat dari setidaknya tiga di antaranya
  • Alasannya ingin bergabung dengan perusahaan kecil adalah karena ia ingin mengenal orang-orang secara lebih personal, dan daya tarik bekerja seperti komponen anonim di dalam mesin tidak bertahan lama
  • Sebagai proyek infrastruktur favorit, ia menyebut benchmark kernel OS untuk backend MovieFlix
    • Palima berharap Linux menang, tetapi setelah epoll(7), FreeBSD berjalan lebih cepat sehingga ia memilih FreeBSD
    • Ia menambahkan bahwa kemungkinan ia masih punya hak commit FreeBSD

Live coding: sleepsort

  • Jeff menjelaskan bahwa latar belakang Palima terlihat cocok dengan tipe yang dicari Techaro, tetapi untuk menilai semua orang dengan standar yang sama, mereka tetap harus menjalankan tantangan coding
  • Tugasnya adalah mengurutkan array angka di situs web, lalu menjelaskan cara pengurutannya
  • Bahasanya bebas, dan Palima menulis kode Haskell
  • Implementasinya membuat green thread terpisah untuk setiap angka, lalu menulis nilai ke channel untuk dicetak setelah threadDelay (100000 * time)
  • Palima mengatakan bahwa pengurutan ini tidak memakai perbandingan, dan bahwa “kadang yang dibutuhkan hanyalah sedikit istirahat”
  • Saat Jeff bertanya apakah waktu eksekusinya tidak berubah sesuai nilai masukan, Palima menjawab bahwa kompleksitas waktu tidak memedulikan efek samping seperti waktu

Optimisasi dan hasil yang tak terduga

  • Ketika Jeff bertanya soal cara optimisasi, Palima hanya mengubah kelipatan waktu tunda
    • 100000 * time dikurangi menjadi 10000 * time
    • Palima menjelaskan bahwa sekarang itu 10 kali lebih cepat
  • Jeff akhirnya tertawa lepas, dan ketika Palima ditanya mengapa ia memakai algoritme pengurutan yang aneh seperti itu, ia balik bertanya, “Kenapa Anda memberi pertanyaan aneh seperti itu?”
  • Palima menilai Techaro tidak cukup kompleks untuk menampung dirinya, dan bahwa alih-alih Kubernetes, satu server khusus dari Typhoon Digital saja sudah cukup
  • Setelah wawancara selesai, ia memperkirakan email penolakan akan segera datang
  • Namun, Techaro malah mengirim email yang menyatakan ingin merekrutnya dengan nominal yang cukup besar, dan Palima bertanya-tanya apakah mereka benar-benar tahu apa yang siap mereka tanggung
  • Palima memutuskan untuk tidur lagi, karena pada malam hari pekerjaan itu akan mengurutkan dirinya sendiri

Bacaan terkait

1 komentar

 
GN⁺ 2023-07-09
Komentar Hacker News

  • Itu bukan waktu konstan, dan juga bukan waktu polinomial, melainkan pseudo-polynomial time. Sepertinya akan gagal untuk bilangan negatif, dan agar menjadi linear terhadap jumlah bit yang merepresentasikan input, dibutuhkan bentuk seperti 10000 * log(time + min(time) + 1)
    Dalam teori kompleksitas komputasi, ketika algoritme numerik berjalan dalam pseudo-polynomial time, itu berarti waktu jalannya merupakan polinomial terhadap nilai numerik input, yaitu bilangan bulat terbesar yang muncul di input, bukan polinomial terhadap panjang input (jumlah bit yang diperlukan untuk merepresentasikan angka tersebut)
    https://en.m.wikipedia.org/wiki/Pseudo-polynomial_time

    • Kamu paham kan kalau itu bagian dari leluconnya? Kalau mau membunuh lelucon dengan terlalu masuk detail, sebenarnya juga tidak perlu menunggu dalam waktu nyata
      Kompleksitas komputasi membahas jumlah langkah dalam model komputasi, bukan berapa banyak waktu jam dinding yang berlalu. sleep sort memanfaatkan sifat scheduler sistem operasi, dan dalam lingkungan waktu virtual, waktu langsung melompat ke kejadian terjadwal berikutnya. Jika itu diasumsikan sebagai model komputasinya, secara praktis ini berjalan dengan kompleksitas polinomial
      Dan kalau mau mengajari orang lain, setidaknya ejaan pseudo-polynomial sebaiknya benar
    • Bukankah setiap masalah pseudo-polynomial bisa dibuat menjadi waktu polinomial hanya dengan mengubah encoding? Jika ada kotak hitam yang menghitung suatu nilai dalam pseudo-polynomial time, kita bisa membuat kotak yang menerima satu input tunggal berisi 1 sebanyak panjang masing-masing nilai, dipisahkan dengan 0
      Mengubahnya kembali menjadi bilangan bulat itu linear, lalu kita panggil kotak hitam lama dan kembalikan hasilnya, sehingga sekarang itu menjadi waktu polinomial terhadap panjang input saya. Saya menyebut bilangan bulat, tetapi intinya adalah cara encoding, jadi untuk titik desimal bisa memakai satu 0, dan untuk pemisah input 00, misalnya
      Bagaimanapun juga, inti leluconnya bukankah bahwa waktu tidur tidak dihitung? Komputer bisa melakukan hal lain selama itu. Rasanya cukup meyakinkan dalam gaya “bodoh tapi saya suka”

  • sleep sort berasal dari /prog/ [0]. Mungkin cukup banyak lurker HN yang ikut dalam thread sleep sort saat itu, dan xena mungkin salah satunya :)
    [0] https://www.cs.princeton.edu/courses/archive/fall13/cos226/l...

    • Kalau saya memasukkan bubuk mesiu ke meriam sesuai angka saat ini, lalu menaruh lebih banyak bubuk untuk angka yang lebih besar agar terbang lebih jauh, kemudian saya berjalan sambil memungut angka-angka di sepanjang lintasannya, apakah ini physical sort?
    • Sudah lama sekali saya tidak memikirkan /prog/. Postingan favorit saya adalah tentang seorang programmer magang yang menemukan operator <=> untuk dipakai saat ingin memeriksa “lebih kecil, sama dengan, atau lebih besar dari”. Jenius

  • Seperti yang dikatakan penulis asli, tulisan ini sangat mirip dengan gaya cerita seri Interview milik aphyr, misalnya “Rewriting the Technical Interview”. Semuanya enak dibaca
    [0] - https://aphyr.com/posts/353-rewriting-the-technical-intervie...

    • Gayanya sangat berbeda, tetapi dalam hal mengejek wawancara teknis, ada juga “Fizzbuzz in Tensorflow” (2016)
      https://joelgrus.com/2016/05/23/fizz-buzz-in-tensorflow/
      Cuplikan:

      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

  • Komputer harus membaca input untuk mengurutkan, jadi setidaknya membutuhkan waktu linear. Terlebih lagi jika kita tidak mengetahui informasi lain seperti distribusi seragam pada input
    Ada berbagai algoritme pengurutan waktu linear seperti sleep sort, postman sort, counting sort, dan lain-lain. Namun itu berlaku untuk himpunan angka atau key yang dapat diurutkan secara terbatas
    Tetapi jika memakai sempoa alih-alih komputer, ada constant-time sort yang nyaris sungguhan: https://en.wikipedia.org/wiki/Bead_sort

    • Ada juga yang disebut sorting network. Tentu saja ini tidak banyak mengubah poin utamanya :D

  • Cerita yang lucu, tapi dalam makna apa pun ini bukan waktu konstan
    Membuat N thread dan menambahkan semuanya ke daftar bangun yang terurut memerlukan waktu antara O(N log N) hingga O(N^2), tergantung pada sistem operasi atau runtime bahasa
    Di suatu tempat di baliknya ada daftar terurut, heap, atau algoritme N^2. Demikian pula, sleep sort sendiri setidaknya memerlukan waktu linear karena untuk mengeluarkan N item yang terurut, ia harus membangunkan N thread
    Lebih buruk lagi, waktu dinding nyata juga bertambah sesuai besar nilainya. Anda memang bisa lebih dulu mencari nilai minimum dan maksimum lalu memampatkan rentangnya, tetapi itu juga waktu linear

    • Dengan risiko merusak leluconnya, saat saya mengatakan “waktu konstan”, saya memang mengisyaratkan kata dan bentuk dari analisis kompleksitas waktu, tetapi sebenarnya saya tidak bermaksud begitu secara harfiah
      Yang dipakai di sini adalah lelucon ambiguitas dari dua sudut pandang yang saling berbenturan terhadap kata “waktu”. Memang benar bahwa dari sudut pandang analisis kompleksitas, mustahil membuat algoritme pengurutan menjadi waktu konstan
      Maksud sebenarnya dari lelucon itu adalah waktu dinding. Dalam wawancara, waktu itu lebih relevan, dan secara realistis ketika seseorang melempar hal seperti “coba tulis fungsi pengurutan bilangan bulat”, jarang sekali mereka hanya memakai angka di bawah 100, jadi program ini secara rasa hampir berjalan seketika
      Ini adalah lelucon metalinguistik yang halus, yang mengolok-olok dengan membalik pemahaman tentang cara kerja ilmu komputer. Sayang leluconnya tidak berhasil
    • Dalam alam semesta dengan umur terbatas, semuanya adalah waktu konstan
      https://en.wikipedia.org/wiki/Ultimate_fate_of_the_universe#...
    • Secara teoretis, argumen yang masuk ke sleep pada akhirnya harus bermuara pada bilangan bulat, jadi bisa juga diproses dalam waktu linear dengan sesuatu seperti radix sort
      Ada ruang masalah tempat itu tetap menguntungkan meskipun muncul ketergantungan pada besar nilai terbesar
      Tentu saja, dalam praktiknya tidak ada sistem seperti itu. Timeout system call biasanya bukan area di mana cara itu menguntungkan. Dan tentu saja, daripada cara yang berbanding linear dengan nilai maksimum, lebih baik langsung menerapkan radix sort yang hanya berbanding dengan log(max_value)
    • Biaya membuat N thread dan menambahkannya ke daftar bangun terurut sebesar O(N log N) hingga O(N^2) bukanlah batasan fundamental dari sistem penjadwalan
      Terlebih lagi jika mempertimbangkan perangkat keras khusus yang memungkinkan penjadwalan waktu konstan terhadap jumlah thread. Misalnya, meskipun sama sekali tidak ekonomis di dunia nyata, kita bisa membuat scheduler yang memantulkan paket informasi dengan laser ke himpunan cermin besar pada berbagai jarak lalu mengembalikannya ke detektor yang terhubung ke komputer
      Caranya adalah memanfaatkan kecepatan cahaya untuk menunda selama waktu yang ditentukan. Jadi sleep sort tidak secara hakiki bergantung pada kompleksitas algoritmik tersembunyi dari cara penjadwalan thread tertentu, dan meskipun tidak praktis, secara teoretis bisa dioptimalkan menjadi O(1)
    • Ini mirip gaya membangun cluster Kubernetes untuk mengembalikan “Hello World”

  • Jika Anda menyukai ini, ada juga semacam karya lanjutan bernama Protos: https://xeiaso.net/blog/protos
    Saya masih menulis lebih banyak cerita dalam “semesta” ini, tetapi perlu waktu agar energi satirnya terkumpul. Episode berikutnya mungkin tentang komputasi spasial

    • Bagian “tepat saat notifikasi kalender bahwa standup meeting akan segera dimulai berbunyi” terasa seperti alam semesta kita
      Meski begitu, tampaknya alam semesta itu lebih pandai memberi nama

  • Bagian yang mengubah threadDelay (100000 * time) menjadi threadDelay (10000 * time) lalu berkata “sekarang sepuluh kali lebih cepat” berkaitan dengan tulisan ini: https://thedailywtf.com/articles/The-Speedup-Loop

  • Saya belum membaca artikelnya, tapi saya benci hal-hal seperti ini. Dulu saya pernah wawancara jarak jauh dengan Meta, dan lawan bicara saya terus makan sambil menghadap mikrofon sepanjang waktu
    Sangat mengganggu sampai saya bahkan lupa cara menulis for loop

    • Rekrutmen jarak jauh jauh lebih baik. Dulu, setelah bicara singkat dengan perekrut atau HR, kita harus memakai setelan dan menyetir jauh atau naik pesawat, dan biasanya satu hari penuh habis begitu saja
      Kalau sedang bekerja, kita harus mengambil cuti, dan ada stres seperti “apakah saya membuang jatah cuti saya untuk ini?”, “parkirnya bagaimana?”, “apakah saya akan tiba tepat waktu?” Lalu setelah itu menjalani “wawancara awal” 30 menit, menunggu berminggu-minggu, lalu entah mendapat undangan wawancara yang sebenarnya atau justru di-ghosting
      Seluruh prosesnya bisa memakan waktu sebulan, dan mungkin butuh setidaknya dua hari cuti serta perjalanan yang cukup jauh
      Sekarang, perekrut atau HR menelepon dan menanyakan apakah Anda bisa panggilan video, lalu di hari yang sama melakukan panggilan 15–20 menit, setelah itu CV diteruskan ke pengambil keputusan, dan satu atau lebih wawancara video atau sesi teknis dijadwalkan. Beberapa perusahaan meminta Anda mengerjakan tes kepribadian/teknis dari rumah dengan nyaman
      Jika Anda pekerja jarak jauh, semua itu bahkan bisa dibereskan saat jam makan siang. Memang bandwidth komunikasi tatap muka jauh lebih besar, tetapi hanya dengan remote Anda bisa wawancara dengan perusahaan di Tel Aviv pagi hari, perusahaan di Warsaw saat makan siang, dan perusahaan di California pada malam hari di hari yang sama

  • Bukankah membuat 1000 thread setidaknya waktu linear? Mungkin bisa ditekan sampai logaritmik, tetapi sepertinya kode itu tidak otomatis melakukannya

    • Tergantung “waktu” dilihat sebagai apa. Jika yang dimaksud adalah waktu dalam kompleksitas algoritmik, maka memang setidaknya linear. Jika yang dimaksud adalah waktu dinding, yaitu waktu yang lebih penting dalam kode wawancara, maka itu waktu konstan
    • Sulit mengatakan bahwa sleep sort lebih waktu konstan daripada algoritme pengurutan lainnya
      Agar sleep sort menjadi waktu konstan, input harus punya batas atas, yaitu ada batas pada angka terbesar, dan kita juga harus tidak menghitung pekerjaan sewenang-wenang seperti membaca dan memproses input serta membuat thread
      Tetapi jika hal-hal seperti itu diizinkan, maka semua pengurutan lain juga menjadi waktu konstan. Sepertinya salah satu saja sudah cukup
    • Dalam praktiknya bahkan bukan linear. Tidur adalah penyisipan heap, dan itu memerlukan O(log n)
    • Saat wawancara dia memang benar-benar sedang tidur. Kalau tidak, tidak mungkin dia mengklaim kompleksitas asimtotik itu “waktu konstan” padahal kalimat pertama programnya sudah berisi loop berurutan atas semua nilai input

  • Jika runtime thread mempertahankan konsep waktunya sendiri, algoritmenya bahkan tidak perlu tidur berdasarkan waktu nyata
    Setelah semua thread dibuat, runtime bisa menyadari bahwa semua thread sedang idle dan thread berikutnya yang akan dijadwalkan adalah thread pada waktu N, jadi cukup perbarui waktu saat ini ke N lalu jalankan thread tersebut. Ulangi ini, maka Anda akan mendapatkan array yang terurut tanpa sleep sama sekali
    Pada akhirnya, pekerjaan pengurutan sebenarnya sudah selesai ketika thread mulai tidur, dan sesudah itu mereka hanya mendaftarkan diri ke pengatur yang akan membangunkannya nanti, misalnya timer wheel. Tidak perlu benar-benar melakukan sleep
    Saya tidak tahu soal Haskell, tetapi runtime tokio di Rust memungkinkan ini dengan start_paused: https://docs.rs/tokio/latest/tokio/runtime/struct.Builder.ht...

    • Pada dasarnya saya memahami ini sebagai cara kerja simulasi kejadian diskret di balik layar. Dengan struktur data yang sesuai, misalnya heap, Anda menyimpan batas kejadian masa depan di sana, lalu bergantian menambahkan kejadian masa depan ke heap dan mengambil kejadian berikutnya dari heap
      Jika mengabaikan berbagai lapisan abstraksi dan detail implementasi yang disederhanakan, mengurutkan nilai dengan scheduler seperti ini pada dasarnya hanyalah heap sort :)
    • Jika Anda benar-benar mulai menghitung apa yang harus dijalankan berikutnya, Anda sedang menciptakan ulang selection sort, dan itu tidak lagi berjalan dalam waktu linear. Jadi secara praktis ini bukan algoritma pengurutan yang masuk akal :)