▲

GN⁺: 스티브 발머의 잘못된 Binary Search 인터뷰 질문

 (blog.jgc.org)
1P by neo 3달전 | favorite | 댓글 1개

Steve Ballmer의 잘못된 이진 검색 인터뷰 질문

  • Steve Ballmer는 Microsoft 인터뷰에서 후보자들에게 퍼즐 질문을 던졌음. 이 질문은 이진 검색과 기대값에 기반을 둠.
  • Ballmer는 "1부터 100 사이의 숫자를 생각하고 있다. 맞추면 돈을 주고, 틀리면 돈을 받는다"라는 게임을 제안했음.
  • Ballmer는 이 게임을 수락해서는 안 된다고 주장했음. 이유는 두 가지로, 첫째는 자신이 가장 어려운 숫자를 선택할 수 있기 때문이고, 둘째는 무작위로 선택할 경우 기대값이 음수이기 때문임.

이진 검색 전략

  • 이진 검색 전략을 따르면 Ballmer가 특정 숫자를 선택할 때 $1을 지불하게 됨.
  • 예를 들어, Ballmer가 59를 선택하면 이진 검색 전략으로 5단계 만에 찾을 수 있음. 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⁺의 정리

  • 이 글은 이진 검색 알고리듬과 기대값 계산에 대한 흥미로운 사례를 제공함.
  • Ballmer의 게임 제안은 수학적 분석을 통해 기대값을 계산하는 방법을 보여줌.
  • 이진 검색 알고리듬을 이해하고 적용하는 데 도움이 될 수 있음.
  • 유사한 기능을 가진 다른 프로젝트로는 "HackerRank"와 "LeetCode"가 있음.
▲
neo 3달전  [-]
Hacker News 의견

  • 복잡한 도메인(결제)에서의 시니어 역할 인터뷰 경험

    • 결제 분야에서 10년 이상의 경험을 바탕으로 인터뷰를 성공적으로 마침
    • 시니어 역할에서는 주제 전문 지식보다 소프트 커뮤니케이션 기술과 갈등 관리가 더 중요함
    • 마지막 라운드에서 실시간 결제 경험이 부족하다는 이유로 부정적인 추천을 받음
    • 큰 미국 은행에서 일하고 싶지 않음을 깨달음

  • Ballmer의 숫자 선택에 대한 논의

    • 인터뷰 대상자가 Ballmer가 무작위로 숫자를 선택한다고 가정함
    • Ballmer가 적대적으로 숫자를 선택한다고 가정하면 초기 추측 값을 다르게 선택할 수 있음
    • 이진 탐색의 이점을 유지하면서 적대적 공격을 피하기 위해 무작위 오프셋을 사용하는 알고리즘 분석에 관심이 있음

  • 이진 탐색의 문제 해결 도구로서의 유용성

    • 이진 탐색이 복잡한 시스템에서 문제를 해결하는 데 유용함을 깨달음
    • Figma의 렌더링 도구 문제를 이진 탐색을 통해 해결한 사례 공유
    • 문제 요소를 제거하고 영향을 확인하는 방식으로 문제를 해결함

  • Python 스크립트 공유

    • 숫자 추측 게임을 시뮬레이션하는 Python 스크립트 제공
    • 이진 탐색을 사용하여 목표 숫자를 추측하고 평균 지불액을 계산함

  • 성공을 자신의 지능에 귀속하는 오류

    • 자신의 성공을 지능에 귀속하고 자신이 항상 옳다고 가정하는 오류에 대한 질문
    • 반대의 임포스터 증후군과 비교됨

  • 공정한 게임 여부에 대한 질문

    • 인터뷰에서 공정한 게임을 할 것인지, 이를 어떻게 확인할 수 있는지에 대한 질문

  • Nash 균형 해에 대한 호기심

    • 추측자가 이진 탐색 근처의 무작위 숫자를 반환하는 것에 대한 호기심
    • 선택자가 균일 또는 비균일 초기 분포를 사용하는지에 대한 궁금증

  • Ballmer의 질문 회피

    • Chang이 이진 탐색과 기대값에 대해 명시적으로 생각하지 않는 것을 보고 Ballmer가 질문을 회피하려는 노력
    • 기술 인터뷰어들이 이 질문을 좋아하는 이유에 대한 논의

  • 인터뷰 질문의 목적

    • 인터뷰 질문이 문제 해결 과정을 보여주는 것에 대한 기대
    • 질문에서 실수를 발견하면 오히려 긍정적인 평가를 받을 수 있음

  • 프로그래머를 찾다가 수학자를 고용하는 경우

    • 프로그래머를 찾는 과정에서 수학자를 고용하게 되는 상황에 대한 언급
답변달기