Steve Ballmers fehlerhafte Interviewfrage zur binären Suche
(blog.jgc.org)- Das als Microsoft-Interviewrätsel bekannte Zahlenspiel fragt nach binärer Suche und dem Erwartungswert, doch unter der Bedingung, dass die Zahl zufällig gewählt wird, ist die Schlussfolgerung „für den Teilnehmer nachteilig“ falsch
- Die Regeln bestehen darin, eine Zahl zwischen 1 und 100 mithilfe von Hinweisen einzugrenzen und zu erraten; mit zunehmender Anzahl der Versuche sinkt die Belohnung, die bei $5 beginnt, und später zahlt der Teilnehmer Geld
- Der Hinweis, dass Ballmer absichtlich eine schwer zu erratende Zahl wählen kann, ist richtig; selbst mit der Strategie der binären Suche werden bestimmte 37 Zahlen erst beim 7. Versuch gefunden, sodass der Teilnehmer $1 zahlen muss
- Wenn die Zahl zufällig ist, ergeben sowohl der Perl-Code als auch die Wahrscheinlichkeitsrechnung einen Erwartungswert von $0.20, also einen positiven Erwartungswert für den Teilnehmer
- Hätte es keinen Bereich mit $0 Belohnung gegeben und müsste der Teilnehmer ab dem 6. Versuch sofort zahlen, läge der Erwartungswert bei -$0.49 und würde damit zu Ballmers Schlussfolgerung passen
Regeln des Zahlenratespiels
- Steve Ballmer stellt in einem kurzen Video ein Rätsel vor, das er Bewerbern in Microsoft-Vorstellungsgesprächen gestellt haben soll
- Eine Person denkt sich eine Zahl zwischen 1 und 100 aus, und der Bewerber erhält bei jedem Tipp den Hinweis „höher“ oder „niedriger“, um den Bereich einzugrenzen
- Die Belohnung hängt von der Anzahl der Versuche bis zum Treffer ab
-
- Versuch: $5
- 2.: $4
- 3.: $3
- 4.: $2
- 5.: $1
- 6.: $0
- 7.: Teilnehmer zahlt $1
- 8.: Teilnehmer zahlt $2
- 9.: Teilnehmer zahlt $3
-
- Die Kernfrage lautet: „Soll man dieses Spiel annehmen?“
- Ballmers Schlussfolgerung war „No“, und zwar aus zwei Gründen
- Er könne selbst die am schwersten zu erratende Zahl wählen
- Selbst wenn er die Zahl zufällig wähle, sei der Erwartungswert negativ, sodass der Teilnehmer am Ende Ballmer Geld zahle
Womit Ballmer recht hatte: Er kann die Zahl adversarial wählen
- Ballmers erster Grund, dass er eine schwierige Zahl wählen könne, stimmt
- Unter der Bedingung, dass die Zahl zufällig gewählt wird, ist die Strategie der binären Suche optimal
- Selbst bei binärer Suche muss der Teilnehmer $1 zahlen, wenn Ballmer bestimmte Zahlen auswählt
- Diese Zahlen sind 2, 5, 8, 11, 14, 17, 20, 22, 24, 27, 30, 33, 36, 39, 42, 45, 47, 49, 52, 55, 58, 61, 64, 67, 70, 72, 74, 77, 80, 83, 85, 87, 90, 93, 96, 98, 100
- Bei den übrigen Zahlen erhält der Teilnehmer $0 oder eine positive Belohnung
- Zahlen mit $0 sind 1, 4, 7, 10, 13, 16, 19, 23, 26, 29, 32, 35, 38, 41, 44, 48, 51, 54, 57, 60, 63, 66, 69, 73, 76, 79, 82, 86, 89, 92, 95, 99
- Bei allen anderen Zahlen erhält der Teilnehmer einen Teil von Ballmers Geld
Beispiel mit der Zahl 59
- Ballmer wählte im Video 59
- Mit der Strategie der binären Suche lässt sich die Zahl in 5 Schritten als 50, 75, 62, 56, 59 finden
- In diesem Fall erhält die Interviewerin Emily Chang $1
- Emily Changs tatsächliche Tipps waren 50, 75, 60, 55, 57, 58, 59 und lagen damit ziemlich nahe an der 5-Schritte-Lösung der binären Suche
Bei zufälliger Auswahl ist der Erwartungswert positiv
- Nimmt man an, dass Ballmer die Zahl zufällig auswählt, ist die Schlussfolgerung eines negativen Erwartungswerts falsch
- Der Perl-Code berechnet für jede Zahl von 1 bis 100, nach wie vielen Schritten sie per binärer Suche gefunden wird, summiert die Auszahlungen und bildet den Durchschnitt
- Das Ergebnis ist ein Erwartungswert des Spiels von $0.20
- Dasselbe Ergebnis lässt sich auch probabilistisch bestätigen
- Beim 1. Tipp wird 50 gewählt, die Erfolgswahrscheinlichkeit beträgt 1/100 und die Belohnung $5
- Beim 2. Tipp wird 25 oder 75 gewählt, die Erfolgswahrscheinlichkeit beträgt 2/100 und die Belohnung $4
- Beim 3. Tipp wird 12, 37, 62 oder 88 gewählt, die Erfolgswahrscheinlichkeit beträgt 4/100 und die Belohnung $3
- Beim 4. Tipp wird 6, 18, 31, 43, 56, 68, 81 oder 94 gewählt, die Erfolgswahrscheinlichkeit beträgt 8/100 und die Belohnung $2
- Danach geht es nach demselben Muster weiter
- Die Gleichung für den Erwartungswert lautet
5 * 1/100 + 4 * 2/100 + 3 * 4/100 + 2 * 8/100 + 1 * 16/100 + 0 * 32/100 + -1 * 37/100, das Ergebnis ist 0.2 - Der letzte Term
-1 * 37/100steht für die verbleibenden möglichen Zahlen, nachdem der binäre Suchbaum bis zum Ende durchlaufen wurde
Wo der Fehler entstanden sein könnte
- Eine Möglichkeit ist, dass Ballmer den Bereich mit $0 Belohnung nicht beabsichtigt hatte
- Wären die Regeln „$5, $4, $3, $2, $1, danach zahlt der Teilnehmer $1, $2, $3“, dann läge der Erwartungswert bei -$0.49
- In dieser Variante stimmt Ballmers Schlussfolgerung eines „negativen Erwartungswerts“
1 Kommentare
Hacker-News-Kommentare
Der Beitrag legt nahe, dass der Bewerber annimmt, die Zahl werde zufällig gewählt, tatsächlich könnte Ballmer sie aber auch adversarial auswählen
Wenn der Bewerber jedoch Ballmers adversariale Wahl annimmt, kann er den ersten Schätzwert anders setzen und so die Wahrscheinlichkeiten verändern. Auch der Autor des Originaltexts geht offenbar von einem Start bei 50 aus, aber aufgrund der Eigenschaften der Binärsuche könnte man einen Anfangswert wählen, der von 50 abweicht, und jedes Mal einen zufälligen Offset verwenden. So ließen sich einfache adversariale Angriffe, die auf die Heuristik zielen, abwehren, während man den Großteil der Vorteile der Binärsuche behält
Ich würde gern eine Analyse des optimalen Algorithmus zur Wahl eines zufälligen Offsets sehen, der auf solche einfachen adversarialen Entscheidungen reagiert
Ich kann mir Ballmer richtig vorstellen, wie er sagt: „Nein, der erste Tipp muss 50 sein. Das weiß doch jeder.“
Das heißt, auf jeder Seite des ersten Tipps dürfen höchstens 64 Zahlen liegen. Wenn man diesen Offset wie gesagt zufällig wählt, würden die meisten adversarialen Beispiele, die auf Schwächen der Binärsuche abzielen, neutralisiert, und möglicherweise ließe sich sogar der Vorteil adversarialer Wahl selbst beseitigen. Dann bräuchte man allerdings vielleicht eine auf den Offset abgestimmte Verteilung
Ich würde so eine Analyse ebenfalls gern sehen
Der Kernpunkt ist, dass der Erwartungswert des Spiels selbst dann noch negativ ist, wenn Ballmer zufällig wählt und der Bewerber darauf optimal reagiert; allein das reicht aus, um sicher zu sagen, dass das Spiel für den Bewerber nachteilig ist
Der Beitrag beantwortet die schwierigere Frage „Wie hoch ist also der tatsächliche Erwartungswert?“ nicht. Aber wenn der Bewerber den ersten Tipp zufällig zwischen 40 und 60 wählt und von dort aus Binärsuche macht, scheint es schwer vorstellbar, dass Ballmer deutlich besser abschneiden könnte als bei einer zufälligen Anfangszahl
In einem von der Simulation gefundenen Nash-Gleichgewicht wählt Ballmer gemischt Zahlen nahe den beiden Enden des Bereichs. Nicht immer genau 1 oder 100, aber in deren Nähe. Dabei gewann der Ballmer-Spieler mit einem Erwartungswert von etwa 0,85 bis 1,00 Dollar pro Runde
Entsprechend beginnt auch die Strategie des Ratenden mit einer Binärsuche an den Extremen des Bereichs, in der Hoffnung, die richtige Seite zu treffen. Das ist ähnlich wie beim Elfmeterschießen im Fußball, wenn Schütze und Torwart beide eine Richtung wählen. Der Torwart will dieselbe Seite wählen, der Schütze die entgegengesetzte. Nur gibt es hier 100 Optionen, sodass sich das Tor viel zu breit anfühlt
Inzwischen denke ich, dass sich das Gleichgewicht komplett verändern und die Ergebnisse der Spieler verbessern würden, wenn man die verbleibenden Entscheidungen nicht mehr an ein Binärsuchmuster bindet. Allerdings entstünde dann für jeden Bereich eine eigene Strategiewahl, was die Berechnung deutlich aufwendiger macht. Und ich habe dafür gerade 2 Stunden lang Arbeit vermieden, also war es nicht gerade sinnvoll. Trotzdem interessiert mich, was passiert, wenn man die Binärsuch-Beschränkung aufhebt
Ich hatte kürzlich ein Vorstellungsgespräch für eine Senior-Rolle im komplexen Bereich Payments und arbeite seit über zehn Jahren in diesem Feld.
Ich kenne Payments nicht nur in den USA, sondern auch im Vereinigten Königreich und in den meisten EU-Rechtsräumen in- und auswendig, daher lief das Gespräch makellos. Da es sich um eine Senior-Rolle handelte, waren Einfluss, geschmeidige Kommunikation und Konfliktmanagement wichtiger als reine Fachexpertise, und auch das habe ich gut gemacht. Sie hatten absichtlich einen unangenehmen Senior Manager dabeigesetzt, der mich ständig unterbrach, und im anschließenden Feedback hieß es, es sei eine Meisterklasse im Umgang mit Konflikten gewesen.
Die letzte Runde fand mit einem Business-Verantwortlichen statt, der sich offenbar selbst als faktischen Domain-Experten sah, und er stellte fortlaufend Trivia-Fragen zu Payments. Es wirkte wie ein Plan, möglichst viel belangloses Wissen abzuklappern, bis er einen Grund für eine Absage finden konnte.
Die letzte Frage war, ob ich tatsächlich schon einmal mit Echtzeitzahlungen gearbeitet habe, und ich hatte in mehreren Ländern damit Erfahrung. FedNow in den USA ist jedoch erst sehr kürzlich eingeführt worden, daher hatte ich bisher nur die Spezifikation gelesen und einige Anbieter evaluiert, um zu entscheiden, ob man es selbst bauen oder einkaufen sollte. Daraufhin sprach er eine negative Empfehlung aus, weil ich angeblich keine Erfahrung mit Echtzeitzahlungen hätte.
Ehrlich gesagt möchte ich in so einem Umfeld nicht arbeiten. Es war eine große US-Bank, und das größte Problem dort waren nicht Produktinnovation oder Kundenfokus, sondern Betriebsstörungen. Unabhängig von meiner Payment-Expertise ist das ein Bereich, den ich schon in mehreren Großunternehmen gerettet habe, und das habe ich auch klar vermittelt. Mit etwas Glück muss man aber nicht erst durch Leid herausfinden, dass so ein Ort unerquicklich ist.
Das deutet nicht nur auf eine toxische Unternehmenskultur hin, sondern auch darauf, dass diese Kultur akzeptiert wird. Solche Orte ziehen Menschen an, die Konflikte geradezu mögen, und sobald es genug davon gibt, prägen sie die Kultur.
Es wird nicht oft so gesagt, aber Konflikte sind ein Führungsversagen. Häufig ließe sich ein Konflikt schon dadurch lösen, dass eine sehr hochrangige Führungskraft mit den Fingern schnippt und sagt: „Sie beide sorgen bitte dafür, dass das funktioniert.“ Stattdessen ist die Führung entweder zu weit vom Geschehen entfernt, um Teams auszurichten, oder sie verteidigt interne Konflikte grundsätzlich im Namen des Wettbewerbs. So oder so kann es die Hölle sein, an so einem Ort zu arbeiten.
Am Ende ging es darum, an einen Punkt zu kommen, an dem der Kandidat die Antwort spontan wahrscheinlich nicht mehr weiß. Das sollte weder feindselig noch unhöflich sein; ich wollte sehen, ob jemand sagen kann: „Das weiß ich nicht.“ Nichtwissen gehört zum technischen Alltag ganz normal dazu, aber wenn man das nicht entspannt sagen kann, kann das ein großes Problem sein.
Insgesamt waren die fähigsten Kandidaten fast immer diejenigen, die mit „Das weiß ich nicht“ am gelassensten umgehen konnten. Wenn jemand defensiv wurde, war das für mich immer ein Warnsignal.
Toxische Führungskräfte mögen überteuerte externe Consultants und Berater oft lieber als interne Mitarbeitende, die deutlich weniger verdienen.
Wenn man vollständig vorbereitet und mehr als qualifiziert ist, der Prozess sich aber nicht wie eine echte Bewertung von Technik und Erfahrung anfühlt, sondern wie ein Trivia-Quiz, ist das unglaublich frustrierend. Wie andere schon gesagt haben, ist dieses Verhalten ein klares Signal für eine toxische Kultur.
Noch absurder ist, dass es eigentlich genau umgekehrt sein sollte. Wenn man ein Team aufbauen oder jemanden ersetzen will, sollte man versuchen, eine Person zu finden, die besser ist als alle, die man derzeit hat.
Wenn nach einem Ablehnungsgrund gesucht wird, indem man sich an Nebensächlichkeiten festbeißt oder irrelevante Details ausgräbt, ist das ein riesiges Warnsignal. Es bedeutet, dass man an Innovation oder echter Problemlösung nicht interessiert ist. Dasselbe gilt für endlose Betriebsstörungen, die wir anderswo längst gelöst haben.
In so einer Situation ist es oft das Beste, zu sagen, dass es einem leidtut, Zeit verschwendet zu haben, und zu gehen. Aber ich verstehe auch, dass man bereit ist, Unsinn zu ertragen, wenn es in der Region genau diesen Job gibt. Trotzdem kann es sich manchmal als verkappter Segen erweisen, einer solchen Kugel ausgewichen zu sein. Das kann sogar dann gelten, wenn man wie ich damals arbeitslos ist und einem das Geld ausgeht.
Es ist diese Art von Ausfragen der Vorfahren, bis die Antwort schließlich „Bauer“ lautet.
„Soll man dieses Spiel mitspielen?“
Natürlich. Spiele mag man, und der Zweck eines Spiels ist Spaß. Wenn es nur um die ersten 20 Dollar geht, kann man sich das als Preis für zehn Minuten unterhaltsames Spiel leisten.
Danach kann man sagen: „Ich habe einmal 20 Dollar verloren, als ich mit Steve Ballmer binär gesucht habe“, und das ist ein Satz, der sich gut bei einem Abendessen erzählen lässt und mir daher mehr als 20 Dollar wert ist.
Wahrscheinlich lag auch darin ein Grund, warum Microsoft in der Ballmer-Ära an Einfluss verlor. Es wurde zu sehr auf technische Dinge geschaut und viel zu wenig auf die menschliche Seite.
Hätte jemand im Interview so geantwortet, hätte ich ihn niemals eingestellt. Tatsächlich hatte ich einmal einen Kandidaten dieser Art. Wenn man fragte: „Wie würden Sie das angehen?“, antwortete er: „Das sollte man nicht tun, man sollte etwas anderes machen.“ Er wurde nicht eingestellt.
Über die Jahre habe ich allmählich erkannt, dass binäre Suche ein erstaunliches Werkzeug zur Problemlösung ist, besonders in Systemen, die so groß und komplex sind, dass sie schwer zu debuggen sind
Kürzlich hatte ein Kollege ein Problem mit einem Figma-Rendering-Tool, zu dem kein Source Code vorlag. Beim Export bestimmter Designs dauerte alles viel zu lange, und der Kollege hatte tagelang wahllos dies und das verändert, aber nichts half. Ein einzelner Versuch dauerte mehrere Stunden, und manchmal stürzte sogar der Browser ab
Meine vorgeschlagene Lösung war, die Hälfte der Elemente zu entfernen und zu prüfen, welchen Einfluss das auf die Exportzeit hat. Dann haben wir das bei der Gruppe wiederholt, bei der der Fehler weiterhin auftrat. Innerhalb weniger Stunden fanden wir das Element, das praktisch eine Endlosschleife verursachte
Jedes Mal, wenn wir uns vom Endgerät, etwa einer Workstation, einen Schritt entfernten, gingen wir im Netzwerk zwei Schritte nach oben. So konnte man den Bereich leicht erweitern und zugleich sehr schnell eingrenzen: „Bis hierhin funktioniert es, ab hier ist es kaputt“
Der Administrator nutzte binäre Suche, um den verantwortlichen Abonnenten schnell zu finden, und veränderte den Inhalt selektiv, indem er irgendwo in der Nachricht zusätzliche Leerzeichen einfügte
Ich entfernte Teile des Codes, prüfte, ob es immer noch kaputt war, und entfernte dann noch mehr
Gibt es einen Namen für den Fehlschluss, den eigenen Lebenserfolg der eigenen Intelligenz zuzuschreiben und deshalb anzunehmen, man sei klüger als alle anderen und habe bei allem recht?
So etwas wie das Gegenteil des Impostor-Syndroms
Der zweite Teil, also „Ich bin überlegen und weiß alles“, ist wohl einfach nur eine altmodische schlechte Persönlichkeitseigenschaft
https://en.wikipedia.org/w/index.php?title=Luciferianism&old...
Es ist die Versuchung, als intelligenter Mensch zum Hüter der Welt werden zu wollen. Die Versuchung, eine Welt zu erschaffen, die auf dem eigenen Wissen und der eigenen ultimativen Wahrheit basiert, und zu glauben, man finde solche Wahrheiten leichter und schneller als gewöhnliche Menschen. Das erteilt einem moralisch eine Art Lizenz, und der Zweck rechtfertigt die Mittel. Man glaubt dann, dass das Böse, das man jetzt tut, später mit doppelt so viel Gutem aufgewogen wird
Dazu kommen fundamentaler Attributionsfehler und der Dunning-Kruger-Effekt. Auf der Verhaltensebene verbindet sich illusorische Überlegenheit mit moralischer Lizenzierung, und bei Menschen mit großem Erfolg verstrickt sich das zusätzlich mit einem Enthemmungseffekt, bei dem sie größere Risiken eingehen. Zu diesen Risiken gehört auch, andere negativ zu beeinflussen
Es wirkt, als kämen all diese Effekte in gewissem Maß zusammen. Es geht nicht zwingend um Intelligenz, sondern eher um Macht, zumindest so, wie die Person sie wahrnimmt. Wer zum Beispiel glaubt, in X von Natur aus besser zu sein, empfindet mehr Macht und ist weniger gehemmt, Überlegenheit zu zeigen oder andere dominieren zu wollen
Jeder hat schon Menschen erlebt, die an früherem Ruhm festhalten, nicht verstehen, dass ihre beste Zeit vorbei ist, und Macht ausüben wollen, die sie längst nicht mehr haben. Für mich ist das das eigentliche Gegenteil des Impostor-Syndroms: ein Zustand, in dem das Bewusstsein für sich selbst und für soziale Dynamiken nicht mit dem Wandel der Zeiten Schritt hält
narzisstische Persönlichkeitsstörung
antisozial
Ich hatte einmal einen Kollegen, der eine Lieblingsfrage für Bewerbungsgespräche hatte. Sie betraf Graph-Datenstrukturen, und sobald Kandidaten antworteten, fielen sie immer wieder durch
Merkwürdigerweise sind im Laufe der Zeit alle Kandidaten durchgefallen, die auf diese Frage geantwortet hatten. Also setzten wir uns alle zusammen und schauten uns an, welche Frage er da eigentlich stellte, und als wir sie gemeinsam lösten, stellten wir fest, dass seine eigene Lösung falsch war
Wie sich herausstellte, hatte er während seiner ganzen Karriere mit dieser einen Frage Leute durchfallen lassen
Das war für uns alle eine demütigende Erfahrung und eine Lektion darin, alles noch einmal zu überprüfen, bevor man Fragen stellt. Die meisten Bewerber in einem Interview sind absolut einstellbar. Manchmal kann auch einfach man selbst falschliegen
Macht man einen Fehler und ist sofort raus? Gab es wirklich so viele perfekte Bewerber, dass man fast alle aussortieren konnte?
Als Bewerber wäre die erste Frage: „Spielen Sie fair, und wie kann ich das überprüfen?“
„Zweitens validiere ich Eingabewerte, wenn es um nennenswertes Geld geht. Das heißt nicht, dass ich Ihnen persönlich misstraue, sondern dass ich der Situation selbst nicht traue. Wie könnte ich das verifizieren, oder möchten Sie, dass ich einfach davon ausgehe, dass es verifiziert ist, und weitermache?“
Das sind gute Fragen, aber wie man sie stellt, ist ebenfalls wichtig. Software Engineering ist nicht nur reine Ingenieursarbeit, Kommunikation ist enorm wichtig
Wie bei den meisten Interviewfragen würde ich erwarten, dass es hier darum geht, wie jemand sein Denken entwickelt und den Lösungsweg zeigt
Wenn der Interviewer diese Frage gestellt hat und du den Fehler entdeckt hast, hilft dir das bei der Einstellung möglicherweise sogar
Hier gibt es noch einen anderen interessanten Punkt. Als Ballmer klar wurde, dass Chang diese Frage nicht explizit über binäre Suche und Erwartungswert angeht, bemühte er sich in dieser Diskussion über genau diese Frage ziemlich stark und diplomatisch darum, von ihr wegzulenken
Das ist nicht überraschend. Sie ist Profi-Journalistin. Überraschend ist eher, dass Ballmer diese Frage offenbar so sehr mochte wie viele technische Interviewer, dass er sie unbedingt einbringen musste, obwohl sie mit Changs Frage nur wenig zu tun hatte
Die Nash-Gleichgewichts-Lösung würde mich wirklich interessieren.
Wie in einem Kommentar gesagt wurde, scheint die ratende Seite wohl zufällige Zahlen in der Nähe der Binärsuche zurückzugeben. Aber ich frage mich, ob die wählende Seite eine gleichmäßige Anfangsverteilung verwendet oder eine ungleichmäßige Verteilung. Irgendjemand auf HN weiß das sicher oder kann es erklären.
Zwischen dem Spiel mit 5 Zahlen und dem mit 100 Zahlen liegt natürlich eine große Lücke. Mit wachsender Zahl an Optionen könnte sich die optimale gemischte Strategie stabilisieren, oder sie könnte sich, soweit ich weiß, immer seltsamer verhalten. Falls jemand das Spiel mit 6, 7 usw. Zahlen gründlich untersucht, würde ich das gern erfahren.
Bei anderen Strategien hat der Bewerber die Strategie, eine „Trickzahl“ zu raten, und Ballmer die Strategie, keine „Trickzahl“ zu wählen.
Der Bewerber kann Ballmer nicht dazu zwingen, einen Trick anzuwenden.