Câu hỏi phỏng vấn Binary Search sai lầm của Steve Ballmer

Câu hỏi phỏng vấn về tìm kiếm nhị phân sai lầm của Steve Ballmer

• Steve Ballmer đã đưa ra các câu hỏi dạng đố vui cho ứng viên trong các buổi phỏng vấn tại Microsoft. Câu hỏi này dựa trên tìm kiếm nhị phân và kỳ vọng toán học.
• Ballmer đề xuất một trò chơi: “Tôi đang nghĩ đến một số từ 1 đến 100. Nếu đoán đúng, bạn nhận tiền; nếu đoán sai, bạn phải trả tiền.”
• Ballmer cho rằng không nên chấp nhận trò chơi này. Có hai lý do: thứ nhất là ông ấy có thể chọn con số khó nhất, và thứ hai là nếu chọn ngẫu nhiên thì kỳ vọng toán học là âm.

Chiến lược tìm kiếm nhị phân

• Nếu làm theo chiến lược tìm kiếm nhị phân, Ballmer sẽ phải trả $1 khi chọn một số cụ thể.
• Ví dụ, nếu Ballmer chọn 59 thì có thể tìm ra trong 5 bước bằng chiến lược tìm kiếm nhị phân. Emily Chang trên thực tế đã đoán gần đúng.

Tính kỳ vọng toán học

• Nếu Ballmer chọn số ngẫu nhiên, kỳ vọng toán học là $0.20.
• Có thể dùng ví dụ mã để tính số lần đoán cho từng giá trị và kỳ vọng tổng thể.
• Kỳ vọng được tính là 5 * 1/100 + 4 * 2/100 + 3 * 4/100 + 2 * 8/100 + 1 * 16/100 + 0 * 32/100 + -1 * 37/100.

Sai lầm của Ballmer

• Có thể Ballmer đã không tính đến trường hợp đoán $0 trong 6 lần.
• Nếu Ballmer nói “Tôi đang nghĩ đến một số từ 1 đến 100. Nếu đoán đúng, bạn nhận tiền; nếu đoán sai, bạn phải trả tiền.” thì kỳ vọng sẽ là -$0.49.

Bình luận

• Damian Cugley: Tò mò liệu có thuật toán đoán nào khác tốt hơn không.
• royalroad: Điều Ballmer mô tả là một trò chơi thông tin không hoàn hảo, và để tính kỳ vọng tối ưu thì cần tìm cân bằng Nash.
• espadrine: Có thể Ballmer đã ngụ ý rằng ông ấy có thể thay đổi số bí mật.

Tóm tắt của GN⁺

• Bài viết này đưa ra một ví dụ thú vị về thuật toán tìm kiếm nhị phân và cách tính kỳ vọng toán học.
• Đề xuất trò chơi của Ballmer cho thấy cách tính kỳ vọng thông qua phân tích toán học.
• Nội dung này có thể giúp hiểu và áp dụng thuật toán tìm kiếm nhị phân.
• Các dự án khác có chức năng tương tự gồm có "HackerRank" và "LeetCode".

[GN⁺]

Ý kiến Hacker News

• Kinh nghiệm phỏng vấn cho vai trò senior trong một lĩnh vực phức tạp (thanh toán)

  • Đã hoàn thành tốt buổi phỏng vấn dựa trên hơn 10 năm kinh nghiệm trong lĩnh vực thanh toán
  • Với vai trò senior, kỹ năng giao tiếp mềm và quản lý xung đột quan trọng hơn chuyên môn sâu về chủ đề
  • Ở vòng cuối, đã nhận được đánh giá không tích cực vì thiếu kinh nghiệm về thanh toán thời gian thực
  • Nhận ra rằng mình không muốn làm việc tại một ngân hàng lớn của Mỹ

• Thảo luận về cách Ballmer chọn con số

  • Ứng viên phỏng vấn giả định rằng Ballmer chọn số một cách ngẫu nhiên
  • Nếu giả định Ballmer chọn số theo hướng đối kháng, có thể chọn giá trị đoán ban đầu khác đi
  • Quan tâm đến việc phân tích thuật toán dùng độ lệch ngẫu nhiên để tránh tấn công đối kháng trong khi vẫn giữ được lợi thế của tìm kiếm nhị phân

• Tính hữu ích của tìm kiếm nhị phân như một công cụ giải quyết vấn đề

  • Nhận ra rằng tìm kiếm nhị phân hữu ích trong việc giải quyết vấn đề trong các hệ thống phức tạp
  • Chia sẻ trường hợp đã dùng tìm kiếm nhị phân để giải quyết một vấn đề với công cụ rendering của Figma
  • Giải quyết vấn đề bằng cách loại bỏ các yếu tố gây lỗi và kiểm tra tác động

• Chia sẻ script Python

  • Cung cấp script Python mô phỏng trò chơi đoán số
  • Sử dụng tìm kiếm nhị phân để đoán số mục tiêu và tính khoản chi trả trung bình

• Sai lầm khi quy thành công cho trí thông minh của bản thân

  • Đặt câu hỏi về sai lầm khi quy thành công của mình cho trí thông minh và cho rằng bản thân luôn đúng
  • Được so sánh với hội chứng kẻ mạo danh theo chiều ngược lại

• Câu hỏi về việc đây có phải là một trò chơi công bằng hay không

  • Đặt câu hỏi liệu trong phỏng vấn có chơi công bằng hay không, và làm sao có thể xác nhận điều đó

• Sự tò mò về nghiệm cân bằng Nash

  • Tò mò về việc người đoán trả về một số ngẫu nhiên gần với tìm kiếm nhị phân
  • Thắc mắc liệu người chọn có dùng phân phối ban đầu đồng đều hay không đồng đều

• Ballmer né tránh câu hỏi

  • Khi thấy Chang không suy nghĩ rõ ràng về tìm kiếm nhị phân và kỳ vọng, Ballmer đã cố né tránh câu hỏi
  • Thảo luận về lý do các interviewer kỹ thuật thích câu hỏi này

• Mục đích của câu hỏi phỏng vấn

  • Kỳ vọng rằng câu hỏi phỏng vấn sẽ cho thấy quá trình giải quyết vấn đề
  • Nếu phát hiện ra sai sót trong câu hỏi thì ngược lại còn có thể được đánh giá tích cực

• Tìm lập trình viên nhưng lại tuyển một nhà toán học

  • Đề cập đến tình huống trong quá trình tìm lập trình viên lại tuyển phải một nhà toán học