คำถามสัมภาษณ์ Binary Search ที่ผิดพลาดของ Steve Ballmer

คำถามสัมภาษณ์ Binary Search ที่ผิดพลาดของ Steve Ballmer

• Steve Ballmer เคยโยนคำถามแนวปริศนาให้ผู้สมัครในการสัมภาษณ์ที่ Microsoft โดยคำถามนี้อิงกับการค้นหาแบบทวิภาคและค่าคาดหมาย
• Ballmer เสนอเกมว่า "ผมกำลังนึกถึงตัวเลขระหว่าง 1 ถึง 100 ถ้าคุณทายถูก ผมจะจ่ายเงินให้ และถ้าทายผิด คุณต้องจ่ายเงินให้ผม"
• Ballmer แย้งว่าไม่ควรรับเกมนี้ ด้วยเหตุผลสองข้อ: ข้อแรกคือเขาสามารถเลือกตัวเลขที่ยากที่สุดได้ และข้อที่สองคือถ้าเลือกแบบสุ่ม ค่าคาดหมายจะติดลบ

กลยุทธ์ Binary Search

• หากทำตามกลยุทธ์ Binary Search จะทำให้ Ballmer ต้องจ่าย $1 เมื่อเขาเลือกตัวเลขบางค่า
• ตัวอย่างเช่น ถ้า Ballmer เลือก 59 ก็สามารถหาเจอได้ภายใน 5 ขั้นตอนด้วยกลยุทธ์ Binary Search และ Emily Chang ก็เกือบตอบถูกจริง ๆ

การคำนวณค่าคาดหมาย

• ถ้า Ballmer เลือกตัวเลขแบบสุ่ม ค่าคาดหมายคือ $0.20
• สามารถใช้ตัวอย่างโค้ดเพื่อคำนวณจำนวนครั้งที่เดาในแต่ละค่าและค่าคาดหมายรวมได้
• ค่าคาดหมายคำนวณได้เป็น 5 * 1/100 + 4 * 2/100 + 3 * 4/100 + 2 * 8/100 + 1 * 16/100 + 0 * 32/100 + -1 * 37/100

ข้อผิดพลาดของ Ballmer

• เป็นไปได้ว่า Ballmer ไม่ได้นับกรณีที่เดาได้ $0 อยู่ 6 ครั้ง
• ถ้า Ballmer พูดว่า "ผมกำลังนึกถึงตัวเลขระหว่าง 1 ถึง 100 ถ้าคุณทายถูก ผมจะจ่ายเงินให้ และถ้าทายผิด คุณจะได้รับเงิน" ค่าคาดหมายจะกลายเป็น -$0.49

ความคิดเห็น

• Damian Cugley: สงสัยว่าอัลกอริทึมการเดาแบบอื่นจะทำได้ดีกว่าหรือไม่
• royalroad: สิ่งที่ Ballmer อธิบายเป็นเกมข้อมูลไม่สมบูรณ์ และถ้าจะคำนวณค่าคาดหมายที่เหมาะสมที่สุด ต้องหาสมดุลแนช
• espadrine: เป็นไปได้ว่า Ballmer สื่อเป็นนัยว่าเขาสามารถเปลี่ยนเลขลับได้

สรุปของ GN⁺

• บทความนี้เป็นกรณีศึกษาที่น่าสนใจเกี่ยวกับอัลกอริทึม Binary Search และการคำนวณค่าคาดหมาย
• ข้อเสนอเกมของ Ballmer แสดงให้เห็นวิธีคำนวณค่าคาดหมายผ่านการวิเคราะห์ทางคณิตศาสตร์
• เนื้อหานี้อาจช่วยให้เข้าใจและประยุกต์ใช้อัลกอริทึม Binary Search ได้ดีขึ้น
• โปรเจ็กต์อื่นที่มีลักษณะคล้ายกัน ได้แก่ "HackerRank" และ "LeetCode"

[GN⁺]

ความคิดเห็นจาก Hacker News

• ประสบการณ์การสัมภาษณ์สำหรับบทบาทระดับอาวุโสในโดเมนที่ซับซ้อน (การชำระเงิน)

  • ผ่านการสัมภาษณ์ได้สำเร็จโดยอาศัยประสบการณ์มากกว่า 10 ปีในสายงานการชำระเงิน
  • สำหรับบทบาทระดับอาวุโส ทักษะการสื่อสารเชิงนุ่มนวลและการจัดการความขัดแย้งสำคัญกว่าความรู้เชิงผู้เชี่ยวชาญเฉพาะด้าน
  • ในรอบสุดท้ายได้รับคำแนะนำเชิงลบด้วยเหตุผลว่ามีประสบการณ์ด้านการชำระเงินแบบเรียลไทม์ไม่มากพอ
  • ทำให้ตระหนักว่าไม่อยากทำงานที่ธนาคารอเมริกันขนาดใหญ่

• การถกเถียงเรื่องการเลือกตัวเลขของ Ballmer

  • ผู้เข้าสัมภาษณ์ตั้งสมมติฐานว่า Ballmer เลือกตัวเลขแบบสุ่ม
  • หากสมมติว่า Ballmer เลือกตัวเลขแบบเป็นปฏิปักษ์ ก็อาจเลือกค่าคาดเดาเริ่มต้นต่างออกไปได้
  • สนใจการวิเคราะห์อัลกอริทึมที่ใช้ random offset เพื่อหลีกเลี่ยงการโจมตีแบบเป็นปฏิปักษ์ ขณะยังคงข้อดีของ binary search ไว้

• ความมีประโยชน์ของ binary search ในฐานะเครื่องมือแก้ปัญหา

  • ตระหนักว่า binary search มีประโยชน์ในการแก้ปัญหาในระบบที่ซับซ้อน
  • แชร์กรณีที่แก้ปัญหาเครื่องมือเรนเดอร์ของ Figma ได้ด้วย binary search
  • แก้ปัญหาโดยค่อย ๆ ตัดองค์ประกอบของปัญหาออกและตรวจสอบผลกระทบ

• การแชร์สคริปต์ Python

  • มีการให้สคริปต์ Python สำหรับจำลองเกมทายตัวเลข
  • ใช้ binary search เพื่อทายเลขเป้าหมายและคำนวณจำนวนเงินที่จ่ายเฉลี่ย

• ความผิดพลาดในการอธิบายความสำเร็จว่าเกิดจากสติปัญญาของตนเอง

  • ตั้งคำถามถึงความผิดพลาดที่อธิบายความสำเร็จของตนว่าเกิดจากสติปัญญา และสมมติว่าตนเองถูกเสมอ
  • ถูกนำไปเปรียบเทียบกับ imposter syndrome ในด้านตรงข้าม

• คำถามว่าเป็นเกมที่ยุติธรรมหรือไม่

  • มีคำถามว่าในการสัมภาษณ์จะเล่นเกมอย่างยุติธรรมหรือไม่ และจะตรวจสอบได้อย่างไร

• ความสนใจต่อคำตอบแบบดุลยภาพ Nash

  • สนใจแนวคิดที่ให้ผู้ทายคืนค่าเป็นตัวเลขสุ่มที่อยู่ใกล้กับ binary search
  • สงสัยว่าผู้เลือกใช้การกระจายเริ่มต้นแบบสม่ำเสมอหรือไม่สม่ำเสมอ

• Ballmer หลบเลี่ยงคำถาม

  • เมื่อเห็นว่า Chang ไม่ได้คิดเรื่อง binary search และค่าคาดหวังอย่างชัดเจน Ballmer จึงพยายามหลบเลี่ยงคำถาม
  • มีการพูดคุยว่าทำไมผู้สัมภาษณ์สายเทคนิคถึงชอบคำถามนี้

• จุดประสงค์ของคำถามสัมภาษณ์

  • คาดหวังว่าคำถามสัมภาษณ์จะแสดงให้เห็นกระบวนการแก้ปัญหา
  • หากมองเห็นข้อผิดพลาดในคำถาม กลับอาจได้รับการประเมินเชิงบวกมากขึ้น

• กำลังหานักเขียนโปรแกรม แต่กลับได้จ้างนักคณิตศาสตร์

  • กล่าวถึงสถานการณ์ที่ระหว่างการมองหานักเขียนโปรแกรม สุดท้ายกลับได้จ้างนักคณิตศาสตร์