La question d’entretien erronée de Steve Ballmer sur la recherche binaire

La question d’entretien erronée de Steve Ballmer sur la recherche binaire

• Steve Ballmer posait des questions-pièges aux candidats lors des entretiens chez Microsoft. Cette question reposait sur la recherche binaire et la valeur espérée.
• Ballmer proposait le jeu suivant : « Je pense à un nombre entre 1 et 100. Si vous le trouvez, je vous donne de l’argent ; si vous vous trompez, c’est vous qui recevez de l’argent. »
• Ballmer affirmait qu’il ne fallait pas accepter ce jeu. Selon lui, pour deux raisons : d’abord parce qu’il pouvait choisir le nombre le plus difficile, ensuite parce que si le nombre était choisi au hasard, la valeur espérée était négative.

Stratégie de recherche binaire

• En suivant une stratégie de recherche binaire, Ballmer finit par payer 1 $ lorsqu’il choisit un nombre précis.
• Par exemple, si Ballmer choisit 59, on peut le trouver en 5 étapes avec une stratégie de recherche binaire. Emily Chang était d’ailleurs presque tombée juste.

Calcul de la valeur espérée

• Si Ballmer choisit un nombre au hasard, la valeur espérée est de 0,20 $.
• Un exemple de code permet de calculer le nombre de tentatives pour chaque valeur ainsi que la valeur espérée totale.
• La valeur espérée se calcule ainsi : 5 * 1/100 + 4 * 2/100 + 3 * 4/100 + 2 * 8/100 + 1 * 16/100 + 0 * 32/100 + -1 * 37/100.

L’erreur de Ballmer

• Il est possible que Ballmer n’ait pas pris en compte les 6 cas où l’on devine 0 $.
• Si Ballmer avait dit : « Je pense à un nombre entre 1 et 100. Si vous le trouvez, je vous donne de l’argent ; si vous vous trompez, c’est vous qui recevez de l’argent », alors la valeur espérée aurait été de -0,49 $.

Commentaires

• Damian Cugley : il se demande si un autre algorithme de devinette pourrait faire mieux.
• royalroad : ce que décrit Ballmer est un jeu à information incomplète, et pour calculer la valeur espérée optimale, il faut trouver un équilibre de Nash.
• espadrine : Ballmer a peut-être laissé entendre qu’il pouvait changer le nombre secret.

Résumé de GN⁺

• Cet article offre un cas intéressant autour de l’algorithme de recherche binaire et du calcul de la valeur espérée.
• La proposition de jeu de Ballmer montre comment calculer une valeur espérée à l’aide d’une analyse mathématique.
• Cela peut aider à comprendre et à appliquer l’algorithme de recherche binaire.
• Parmi d’autres projets aux fonctionnalités similaires, on peut citer "HackerRank" et "LeetCode".

[GN⁺]

Avis Hacker News

• Expérience d’entretien pour un poste senior dans un domaine complexe (paiements)

  • Entretien mené avec succès en s’appuyant sur plus de 10 ans d’expérience dans le secteur des paiements
  • Pour un poste senior, les compétences de communication et la gestion des conflits sont plus importantes que l’expertise purement thématique
  • Lors du dernier tour, recommandation négative au motif d’un manque d’expérience en paiements en temps réel
  • Prise de conscience de ne pas vouloir travailler dans une grande banque américaine

• Discussion sur le choix des nombres par Ballmer

  • Le candidat suppose que Ballmer choisit les nombres de façon aléatoire
  • Si l’on suppose que Ballmer choisit les nombres de manière hostile, on peut choisir une valeur initiale différente
  • Intérêt pour l’analyse d’un algorithme utilisant un décalage aléatoire afin d’éviter une attaque adverse tout en conservant les avantages de la recherche binaire

• Utilité de la recherche binaire comme outil de résolution de problèmes

  • Réalisation que la recherche binaire est utile pour résoudre des problèmes dans des systèmes complexes
  • Partage d’un cas où un problème avec les outils de rendu de Figma a été résolu grâce à une recherche binaire
  • Résolution du problème en supprimant des éléments et en vérifiant leur impact

• Partage d’un script Python

  • Fourniture d’un script Python qui simule un jeu de devinette de nombres
  • Utilisation de la recherche binaire pour deviner le nombre cible et calculer le paiement moyen

• Erreur consistant à attribuer son succès à sa propre intelligence

  • Question sur l’erreur qui consiste à attribuer son succès à son intelligence et à supposer qu’on a toujours raison
  • Comparaison avec la version inverse du syndrome de l’imposteur

• Question sur le caractère équitable du jeu

  • Question de savoir si l’entretien se joue de manière équitable et comment on peut le vérifier

• Curiosité à propos d’une solution d’équilibre de Nash

  • Curiosité sur le fait que le devineur renvoie des nombres aléatoires proches de la recherche binaire
  • Interrogation sur le fait que le sélectionneur utilise une distribution initiale uniforme ou non uniforme

• Ballmer évite la question

  • Effort de Ballmer pour esquiver la question en voyant que Chang ne réfléchit pas explicitement à la recherche binaire et à la valeur espérée
  • Discussion sur les raisons pour lesquelles les intervieweurs techniques aiment cette question

• Objectif de la question d’entretien

  • Attente qu’une question d’entretien serve à montrer le processus de résolution de problème
  • Repérer une erreur dans la question peut au contraire conduire à une évaluation positive

• En cherchant un programmeur, on embauche parfois un mathématicien

  • Mention de situations où, en cherchant un programmeur, on finit par embaucher un mathématicien