Zwar schreibt heutzutage kaum mehr jemand komplizierte Algorithmen, doch Einstellungstests prüfen dennoch oft, ob der Kandidat die Theorie abrufbar parat hat.

© themaster444, Pixelio.de

Hurra, das Ende der Krise ist nah! Und damit bricht die Bewerbungszeit an. Ist der Aufschwung erst einmal da, sitzt das Geld der Unternehmen wieder locker. Um Profit daraus zu ziehen, muss der Kandidat aber seinen Lebenslauf entstaubt haben und auf Interviewfragen blitzschnelle und gescheite Antworten wissen.

Fallende Bowlingkugeln

Eine neuerdings beliebte Einstellungsfrage bei den Softwareschmieden im Silicon Valley ist, wie man mit zwei Bowlingkugeln feststellen kann, aus welchem Stockwerk eines 100-stöckigen Hauses diese den freien Fall ins Erdgeschoss gerade noch überstehen. Die Anzahl der notwendigen Fallversuche ist für den ungünstigsten Fall zu minimieren.

Eine simple Methode wäre, im ersten Stockwerk anzufangen, die erste Bowlingkugel runterzuwerfen und zu sehen, ob sie heil bleibt. Kommt sie unbeschadet an, setzt der Proband die Versuchsreihe im zweiten Stock fort und arbeitet sich langsam bis ganz nach oben vor.Im ungünstigsten Fall, wenn nämlich die Bowlingkugeln so stabil sind, dass sie auch einen Sturz aus dem 100. Stockwerk überstehen, verbrät man so 100 Versuche, bis das Ergebnis feststeht.

Nun stehen aber nicht nur eine, sondern zwei Bowlingkugeln zur Verfügung und im Rahmen des Versuchs dürfen gerne beide kaputtgehen, allerdings muss dann das kritische Stockwerk feststehen. Ein kleiner Tipp: 15 Versuche müssen reichen, sonst gilt der Test als nicht bestanden und der Kandidat muss sich anderswo eine Stelle suchen (Abbildung 1).

Wer glaubt, das Zeug für die Software-Entwicklung im Silicon Valley zu haben, hört jetzt auf zu lesen, versetzt sich in das nicht ganz stressfreien Szenario eines Einstellungsgesprächs und rechnet kühlen Kopfes erfolgsversprechende Ansätze durch. Die Zeit läuft ...

Abbildung 1: Aus welchem Stockwerk kommt die Bowlingkugel gerade noch unbeschadet an? Bei 100 Stockwerken müssen maximal 15 Versuche mit zwei Kugeln reichen.

Der entscheidende Trick

Wie bereits erwähnt führt der lineare Ansatz zwar zum Ziel, verbrät aber zu viele Versuche. Mit einer binären Suche verhält es sich ähnlich, denn teilt man 100 Stockwerke durch 2 und lässt die erste Kugel aus dem 50. Stockwerk fallen, bräuchte man, falls sie zerbricht, im ungünstigsten Fall 49 weitere Versuche, um das richtige Stockwerk zu ermitteln, denn die zweite Kugel darf nicht zu Bruch gehen, ehe das Ergebnis vorliegt.

Der Trick, auf den der Kandidat kommen muss, besteht darin, die 100 Stockwerke in Abschnitte mit schrittweise abnehmender Breite zu unterteilen (Abbildung 2). Der erste Abschnitt ist »n« Stockwerke lang, der zweite »n-1«, der dritte »n-2« und so weiter, bis ein Abschnitt das 100. Stockwerk streift.

Mit dieser Aufteilung schreitet der Proband von links nach rechts durch die Abschnitte und lässt die erste Bowlingkugel jeweils aus dem ersten Stockwerk des gerade bearbeiteten Abschnitts fallen. Geht sie zu Bruch, fährt er mit der zweiten Bowlingkugel im zweiten Stockwerk des vorherigen Abschnitts fort (falls dieser existiert), bis auch sie zerschmettert am Boden liegt oder das Ende des Abschnitts erreicht ist. Damit steht das kritische Stockwerk fest.

Abbildung 2: Die 100 Stockwerke werden in Abschnitte mit stetig abnehmender Breite aufgeteilt.

Das Interessante an der in Abbildung 2 gezeigten Aufteilung ist, dass die Anzahl der notwendigen Versuche zur Ermittlung des kritischen Stockwerks immer auf maximal »n+1« begrenzt ist, egal in welcher Höhe es kracht. Ist der kritische Punkt zum Beispiel das letzte Stockwerk im ersten Abschnitt, bricht die erste Kugel im ersten Stockwerk des zweiten Abschnitts beim zweiten Wurf. Dann wirft der Proband die zweite Kugel aus dem zweiten, dritten, bis zum n-ten Stockwerk des ersten Abschnitts.

Sie bleibt bis zum Ende heil, also ist n das höchstmögliche Stockwerk. Anzahl der Versuche: zwei mit der ersten Kugel und »n-1« mit der zweiten, macht insgesamt »n+1« Versuche.

Ist das kritische Stockwerk hingegen das letzte Stockwerk im fünften Abschnitt, der die Länge »n-4« hat, bricht die erste Kugel beim sechsten Versuch, also im ersten Stockwerk des sechsten Abschnitts. Um nun mit der zweiten Kugel alle verbleibenden Stockwerke des fünften Abschnitts durchzuprobieren, sind nur »n-4-1« Versuche notwendig, denn der Abschnitt hat die Länge »n-4« und das erste Stockwerk dort wurde vorher bereits beackert und für gut befunden. Anzahl der maximal notwendigen Versuche, falls auch das letzte Feld des fünften Abschnitts die Kugel sicher fallen lässt: »6+n-4-1«, also ebenfalls »n+1«.

Zwar schreibt heutzutage kaum mehr jemand komplizierte Algorithmen, doch Einstellungstests prüfen dennoch oft, ob der Kandidat die Theorie abrufbar parat hat.

Kommentare (3)
von squirrel, 10.02.2010 10:53	Komme auch auf max. 14 Versuche In Lisp: ;; bowl (defun floorlist (&key (mxfloor 100)) "build 1st list for iteration" (let ((steps (ceiling (- (sqrt (+ 1 (* 8 mxfloor))) 1) 2))) (loop for x from steps downto 1 for y = steps then (+ x y) while (< y mxfloor) collect y))) (defun thrower (flist smash &key (ball 2) (ok 0)) "start throwing balls and watch what happens" (let ((tfl (first flist)) (ret 'bang!)) (unless (or (null flist) (zerop ball)) (when (< tfl smash) (pop flist) (setf ok tfl ret 'ok)) (when (>= tfl smash) (decf ball) (setf flist (loop for i from (1+ ok) to (1- tfl) collect i))) (cons (list ret tfl) (thrower flist smash :ball ball k ok))))) (loop for i from 1 to 101 do (print i) (princ (thrower (floorlist :mxfloor 100) i))) Die erste Kugel wird gleich aus dem 14. Stock abgeworfen.
von Toralf Förster, 16.11.2009 11:21	eine Addition zuviel Zumindest eine Addition läßt sich einsparen durch diese Umsortierung $sum += $n; push @stops, $sum; die kostbare eingesparte CPU Zeit kann man ja dann an den eigenen BOINC Client verfüttern
von R. Schmidt, 07.11.2009 16:57	13 Nach meinem Dafürhalten geht es auch mit n=13, also maximal 14 Versuchen. Der zweite Abschnitt ist nicht n-1 lang, sondern ebenfalls n. Alle weiteren Abschnitte sind ebenfalls um 1 länger, denn ein Stock ist immer schon durch den vorherigen Versuch erledigt. Hier ein kurzes Skript, das mir meinen Wurfplan erstellt: #! /usr/bin/perl -w # s. Linux Magazin Nr. 12 2009 S. 116 $n = 13; for($i = $n + 1, $inc = $n, $k = 1; $i <= 100 && $inc > 0; $i += $inc, $inc -= 1, $k++) { print "Kugel: $k: Stock: $i\n"; } print "\n"; Man möge mich bitte korrigiern, wenns falsch ist.