Steve Ballmers fehlerhafte Binary-Search-Interviewfrage

Steve Ballmers fehlerhafte Binary-Search-Interviewfrage

• Steve Ballmer stellte Bewerber:innen in Microsoft-Interviews Rätselfragen. Diese Frage basiert auf Binary Search und dem Erwartungswert.
• Ballmer schlug folgendes Spiel vor: „Ich denke mir eine Zahl zwischen 1 und 100 aus. Wenn du sie errätst, gebe ich dir Geld, und wenn du falsch liegst, bekommst du Geld.“
• Ballmer behauptete, man solle dieses Spiel nicht annehmen. Dafür nannte er zwei Gründe: Erstens könne er die schwierigste Zahl auswählen, und zweitens sei der Erwartungswert bei zufälliger Auswahl negativ.

Binary-Search-Strategie

• Folgt man der Binary-Search-Strategie, muss Ballmer $1 zahlen, wenn er eine bestimmte Zahl auswählt.
• Wenn Ballmer zum Beispiel 59 wählt, kann man sie mit der Binary-Search-Strategie in 5 Schritten finden. Emily Chang lag in der Praxis tatsächlich fast richtig.

Berechnung des Erwartungswerts

• Wenn Ballmer die Zahl zufällig auswählt, beträgt der Erwartungswert $0.20.
• Anhand eines Codebeispiels lässt sich berechnen, wie viele Versuche für jeden Wert nötig sind und wie hoch der gesamte Erwartungswert ist.
• Der Erwartungswert wird als 5 * 1/100 + 4 * 2/100 + 3 * 4/100 + 2 * 8/100 + 1 * 16/100 + 0 * 32/100 + -1 * 37/100 berechnet.

Ballmers Fehler

• Möglicherweise hat Ballmer die 6 Fälle nicht mitgezählt, in denen $0 geraten wurde.
• Wenn Ballmer gesagt hätte: „Ich denke mir eine Zahl zwischen 1 und 100 aus. Wenn du sie errätst, gebe ich dir Geld, und wenn du falsch liegst, bekommst du Geld“, dann läge der Erwartungswert bei -$0.49.

Kommentare

• Damian Cugley: Er fragt sich, ob ein anderer Ratealgorithmus besser sein könnte.
• royalroad: Was Ballmer beschrieben hat, ist ein Spiel mit unvollständiger Information, und um den optimalen Erwartungswert zu berechnen, müsse man ein Nash-Gleichgewicht finden.
• espadrine: Möglicherweise deutete Ballmer an, dass er die geheime Zahl ändern könnte.

Zusammenfassung von GN⁺

• Dieser Beitrag liefert ein interessantes Beispiel für den Binary-Search-Algorithmus und die Berechnung von Erwartungswerten.
• Ballmers Spielvorschlag zeigt, wie man den Erwartungswert durch mathematische Analyse berechnen kann.
• Das kann helfen, den Binary-Search-Algorithmus zu verstehen und anzuwenden.
• Andere Projekte mit ähnlicher Funktionalität sind „HackerRank“ und „LeetCode“.

[GN⁺]

Hacker-News-Kommentare

• Interview-Erfahrung für eine Senior-Rolle in einem komplexen Fachgebiet (Zahlungsverkehr)

  • Das Interview wurde auf Grundlage von mehr als 10 Jahren Erfahrung im Zahlungsverkehr erfolgreich abgeschlossen
  • Für eine Senior-Rolle sind Soft-Skills in der Kommunikation und im Konfliktmanagement wichtiger als reine Fachexpertise
  • In der letzten Runde gab es eine negative Empfehlung mit der Begründung, dass Erfahrung mit Echtzeitzahlungen fehle
  • Es wurde klar, dass man nicht bei einer großen US-Bank arbeiten möchte

• Diskussion über Ballmers Zahlenwahl

  • Es wird angenommen, dass Ballmer die Zahl zufällig auswählt
  • Wenn man annimmt, dass Ballmer die Zahl feindselig auswählt, könnte man den anfänglichen Schätzwert anders wählen
  • Interesse an der Analyse eines Algorithmus, der einen zufälligen Offset verwendet, um feindselige Angriffe zu vermeiden und gleichzeitig die Vorteile der binären Suche zu erhalten

• Nützlichkeit der binären Suche als Werkzeug zur Problemlösung

  • Erkenntnis, dass binäre Suche nützlich ist, um Probleme in komplexen Systemen zu lösen
  • Geteiltes Beispiel, wie ein Problem mit Figma-Rendering-Tools mithilfe der binären Suche gelöst wurde
  • Probleme werden gelöst, indem man Elemente entfernt und prüft, welche Auswirkungen das hat

• Freigabe eines Python-Skripts

  • Bereitstellung eines Python-Skripts zur Simulation eines Zahlenschätzspiels
  • Verwendet binäre Suche, um die Zielzahl zu erraten und den durchschnittlichen Auszahlungsbetrag zu berechnen

• Der Fehler, Erfolg der eigenen Intelligenz zuzuschreiben

  • Frage nach dem Irrtum, den eigenen Erfolg der Intelligenz zuzuschreiben und anzunehmen, dass man immer recht hat
  • Wird mit dem gegenteiligen Impostor-Syndrom verglichen

• Frage, ob es ein faires Spiel ist

  • Frage, ob im Interview fair gespielt wird und wie sich das überprüfen lässt

• Neugier auf die Nash-Gleichgewichtslösung

  • Neugier darauf, dass der Ratende eine Zufallszahl in der Nähe der binären Suche zurückgibt
  • Frage, ob der Wählende eine uniforme oder nicht uniforme Anfangsverteilung verwendet

• Ballmers Ausweichen der Frage

  • Ballmers Bemühung, der Frage auszuweichen, nachdem er sah, dass Chang nicht ausdrücklich über binäre Suche und Erwartungswert nachdachte
  • Diskussion darüber, warum technische Interviewer diese Frage mögen

• Zweck von Interviewfragen

  • Erwartung, dass Interviewfragen den Problemlösungsprozess sichtbar machen
  • Wenn man einen Fehler in der Frage entdeckt, kann das im Gegenteil sogar positiv bewertet werden

• Auf der Suche nach einem Programmierer wird ein Mathematiker eingestellt

  • Erwähnung der Situation, in der man bei der Suche nach einem Programmierer am Ende einen Mathematiker einstellt