Pertanyaan wawancara Binary Search Steve Ballmer yang keliru

Pertanyaan wawancara binary search Steve Ballmer yang keliru

• Steve Ballmer pernah melemparkan pertanyaan teka-teki kepada kandidat dalam wawancara Microsoft. Pertanyaan ini didasarkan pada binary search dan nilai harapan.
• Ballmer mengusulkan permainan: "Saya sedang memikirkan sebuah angka antara 1 sampai 100. Jika Anda menebaknya dengan benar, saya memberi Anda uang; jika salah, Anda menerima uang."
• Ballmer berpendapat bahwa permainan ini tidak boleh diterima. Alasannya ada dua: pertama, karena ia bisa memilih angka yang paling sulit; kedua, jika angka dipilih secara acak maka nilai harapannya negatif.

Strategi binary search

• Jika mengikuti strategi binary search, saat Ballmer memilih angka tertentu kita akan membayar $1.
• Sebagai contoh, jika Ballmer memilih 59, angka itu bisa ditemukan dalam 5 langkah dengan strategi binary search. Emily Chang benar-benar hampir menebaknya.

Perhitungan nilai harapan

• Jika Ballmer memilih angka secara acak, nilai harapannya adalah $0.20.
• Melalui contoh kode, kita bisa menghitung jumlah tebakan untuk setiap nilai dan nilai harapan keseluruhannya.
• Nilai harapan dihitung sebagai 5 * 1/100 + 4 * 2/100 + 3 * 4/100 + 2 * 8/100 + 1 * 16/100 + 0 * 32/100 + -1 * 37/100.

Kesalahan Ballmer

• Ada kemungkinan Ballmer tidak memasukkan kasus menebak $0 sebanyak 6 kali.
• Jika Ballmer berkata, "Saya sedang memikirkan sebuah angka antara 1 sampai 100. Jika Anda menebaknya dengan benar, saya memberi Anda uang; jika salah, Anda menerima uang," maka nilai harapannya menjadi -$0.49.

Komentar

• Damian Cugley: Penasaran apakah algoritme tebakan lain bisa lebih baik.
• royalroad: Yang dijelaskan Ballmer adalah permainan dengan informasi tidak lengkap, dan untuk menghitung nilai harapan optimal kita perlu mencari keseimbangan Nash.
• espadrine: Ada kemungkinan Ballmer mengisyaratkan bahwa ia bisa mengubah angka rahasianya.

Ringkasan GN⁺

• Artikel ini memberikan contoh menarik tentang algoritme binary search dan perhitungan nilai harapan.
• Usulan permainan dari Ballmer menunjukkan cara menghitung nilai harapan melalui analisis matematis.
• Ini dapat membantu dalam memahami dan menerapkan algoritme binary search.
• Proyek lain dengan fungsi serupa antara lain "HackerRank" dan "LeetCode".

[GN⁺]

Komentar Hacker News

• Pengalaman wawancara untuk peran senior di domain yang kompleks (pembayaran)

  • Berhasil menyelesaikan wawancara berdasarkan pengalaman lebih dari 10 tahun di bidang pembayaran
  • Untuk peran senior, keterampilan komunikasi interpersonal dan manajemen konflik lebih penting daripada keahlian topik semata
  • Menerima rekomendasi negatif di putaran terakhir karena dianggap kurang memiliki pengalaman pembayaran real-time
  • Menyadari bahwa dirinya tidak ingin bekerja di bank besar AS

• Diskusi tentang pemilihan angka oleh Ballmer

  • Kandidat wawancara mengasumsikan Ballmer memilih angka secara acak
  • Jika diasumsikan Ballmer memilih angka secara adversarial, nilai tebakan awal bisa dipilih secara berbeda
  • Tertarik pada analisis algoritma yang menggunakan offset acak untuk menghindari serangan adversarial sambil mempertahankan keunggulan binary search

• Kegunaan binary search sebagai alat pemecahan masalah

  • Menyadari bahwa binary search berguna untuk menyelesaikan masalah dalam sistem yang kompleks
  • Membagikan kasus penyelesaian masalah pada alat rendering Figma melalui binary search
  • Menyelesaikan masalah dengan menghapus elemen penyebab dan memeriksa dampaknya

• Berbagi skrip Python

  • Menyediakan skrip Python yang mensimulasikan permainan tebak angka
  • Menggunakan binary search untuk menebak angka target dan menghitung rata-rata pembayaran

• Kesalahan mengatribusikan kesuksesan pada kecerdasan diri

  • Pertanyaan tentang kekeliruan mengatribusikan kesuksesan diri pada kecerdasan dan menganggap diri selalu benar
  • Dibandingkan dengan imposter syndrome yang bersifat kebalikan

• Pertanyaan tentang apakah ini permainan yang adil

  • Pertanyaan tentang apakah wawancara akan dimainkan secara adil, dan bagaimana hal itu bisa dipastikan

• Rasa ingin tahu tentang solusi ekuilibrium Nash

  • Rasa ingin tahu tentang penebak yang mengembalikan angka acak di sekitar binary search
  • Ingin tahu apakah pihak pemilih menggunakan distribusi awal yang uniform atau non-uniform

• Ballmer menghindari pertanyaan

  • Upaya Ballmer untuk menghindari pertanyaan setelah melihat Chang tidak secara eksplisit memikirkan binary search dan nilai harapan
  • Diskusi tentang alasan pewawancara teknis menyukai pertanyaan ini

• Tujuan pertanyaan wawancara

  • Harapan bahwa pertanyaan wawancara menunjukkan proses pemecahan masalah
  • Jika menemukan kesalahan dalam pertanyaan, hal itu justru bisa dinilai positif

• Saat mencari programmer tetapi malah mempekerjakan matematikawan

  • Penyebutan situasi ketika dalam proses mencari programmer justru akhirnya mempekerjakan matematikawan