© themaster444, Pixelio.de

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

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«.

Gesucht: n

Soweit ist der Algorithmus also klar und im ungünstigsten Fall auf »n+1« Versuche beschränkt. Aber welcher Wert ist für n zu wählen, falls das Haus 100 Stockwerke hat? Die Aufgabe verlangt, die maximal notwendige Anzahl der Versuche zu minimieren, also sind klarerweise kleine Werte für »n« von Vorteil. Allerdings nimmt die Breite der Abschnitte ausgehend von »n« schrittweise um 1 ab und sobald ein Abschnitt die Länge 1 aufweist, ist der Ofen aus, falls dann alle aneinandergelegten Abschnitte noch nicht 100 Stockwerke abdecken.

Folglich muss die Summe aus »n + (n-1) + (n-2) + … + 1« möglichst genau 100 ergeben. Sie darf leicht darüber liegen, aber nicht darunter. Der deutsche Mathematiker Carl Friedrich Gauß hat für die Summe dieser Zahlenreihe bekanntlich schon im Kindesalter eine Formel gefunden, als der Lehrer die Volksschulklasse dazu aufforderte, die Zahlen von 1 bis 100 von Hand zu addieren, und der geniale Gauß sofort, ohne auch nur eine einzige Addition auszuführen, das Ergebnis ablieferte [2].

Nach Gauß gilt also »n(n+1)/2 >= 100«, was aufgelöst eine quadratische Gleichung ergibt, deren einzige positive Lösung nach der im Gymnasium gelernten binomischen Formel etwa 13,65 ist. Der kleinste akzeptable Wert für n ist demnach 14, die numerische Aufteilung der Abschnitte zeigt Abbildung 3.

Abbildung 3: Mit n=14 ergibt sich diese Verteilung der Stockwerke in Abschnitte.

In Perl gegossen

Das Listing 1 zeigt eine Implementierung des Algorithmus in Perl. Zeile 9 setzt die Anzahl der Stockwerke (100) in die binomische Formel ein, rundet den ermittelten Fließkommawert mit der Funktion »ceil()« aus dem Posix-Modul auf die nächste ganze Zahl auf und erhält so den Wert 14 in der Variablen »$n«.

Die »while«-Schleife ab Zeile 16 legt einen Array »@stops« an, der als Elemente die Nummern der ersten Stockwerke jedes Abschnitts enthält, also etwa 1, 15, 28, … 91, 96, 100. Das Stockwerk, aus dem die Bowlingkugeln den Sturz gerade noch überleben, nennt das Skript »Highest OK floor« und nimmt dessen Nummer zu Testzwecken entweder auf der Kommandozeile entgegen (dazu ruft man es also zum Beispiel mit »bball-drop 99« auf) oder es legt den in Zeile 23 voreingestellten Wert 42 fest.

01 #!/usr/local/bin/perl -w
02 use strict;
03 use POSIX qw(ceil);
04 use Log::Log4perl qw(:easy);
05 Log::Log4perl->easy_init($INFO);
06
07 my $total = 100;
08
09 my $n = ceil( (-1 + sqrt(1+4*2*$total))
10               / 2 );
11
12 my $sum   = 1;
13 my @stops = ();
14 push @stops, $sum;
15
16 while($sum + $n <= $total) {
17     push @stops, $sum + $n;
18     $sum += $n;
19     $n--;
20 }
21
22 my $last_ok_floor =
23   (defined $ARGV[0] ? $ARGV[0] : 42);
24
25 INFO "Pst, pst: Highest OK floor is ",
26      $last_ok_floor;
27
28 my $tries       = 0;
29 my $ok_floor    = 1;
30 my $smash_floor = $total + 1;
31
32 for my $stop (@stops) {
33     $tries++;
34     if(!try_floor($stop, $last_ok_floor)) {
35         $smash_floor = $stop;
36         last;
37     }
38     $ok_floor = $stop;
39 }
40
41 for my $try_floor ( $ok_floor+1 ..
42                     $smash_floor-1) {
43     $tries++;
44     if(!try_floor($try_floor,
45                  $last_ok_floor) ) {
46         $smash_floor = $try_floor;
47         last;
48     }
49     $smash_floor = $try_floor + 1;
50 }
51
52 INFO "Highest OK floor: ", $smash_floor-1,
53      " ($tries tries)";
54
55 ###########################################
56 sub try_floor {
57 ###########################################
58     my($floor, $last_ok_floor) = @_;
59
60     if($floor > $last_ok_floor) {
61         INFO "Floor $floor: Wham, busted!";
62         return 0;
63     }
64
65     INFO "Floor $floor: Okay.";
66     return 1;
67 }

Per Log4perl gibt es dann geheimnistuerisch mit “Pst, pst” den vom Algorithmus zu ermittelnden Wert in Zeile 25 aus und fängt dann an, die einzelnen Abschnitte abzuarbeiten. Die For-Schleife ab Zeile 32 fährt jeweils an den Anfang eines Abschnitts im Array »@stop« und ruft die Routine »try_floor()« mit dem aktuell zu testenden und dem geheimen maximal machbaren Stockwerk auf.

Übersteigt die getestete Höhe diese kritische Höhe, gibt »try_floor()« einen falschen Wert zurück, um anzudeuten, dass die gerade geworfene Bowlingkugel nun zerschmettert am Boden liegt.

Findet die »for«-Schleife ab Zeile 32 ein Stockwerk, das die erste Kugel nicht überlebt, bricht sie mit »last« ab und setzt die Variable »$smash_floor« auf das Stockwerk, das den Bruch ausgelöst hat.Anschließend fährt die Schleife ab Zeile 41 zurück zum nächsten Stockwerk des letzten erfolgreichen Wurfs und steigt Stufe um Stufe höher, bis auch die zweite Kugel den Geist aufgibt oder das Ende des Abschnitts erreicht ist. Im ersten Fall bricht auch diese Schleife mit »last« ab und das Ergebnis liegt in »$smash_floor«. Ein um 1 verminderter Wert ergibt das gesuchte höchste Stockwerk, das die Kugeln noch überleben würden.

Auf dem Prüfstand

Bei derart filigranen Problemen schleichen sich fast unweigerlich Bugs ein, deshalb ist eine Regressions-Testsuite unabdingbar. Listing 2 nutzt das Modul Sysadm::Install, um das Skript »bball-drop« wieder und wieder mit unterschiedlichen maximal erreichbaren Stockwerken von 0 bis 100 aufzurufen. Die Funktion »tap()« ruft das Skript auf und fängt praktischerweise Stdout und Stderr in verschiedenen Variablen ab. Die Ausgabe des Skripts sieht in etwa aus wie in Abbildung 4. Der reguläre Ausdruck in Zeile 12 von »suite« schnappt sich das ausgegebene Resultat mit dem höchsten erfolgreich absolvierten Stockwerk und der Gesamtzahl der notwendigen Schritte.

01 #!/usr/local/bin/perl -w
02 use strict;
03 use Sysadm::Install qw(:all);
04 use Test::More;
05
06 plan tests => 202;
07
08 for my $floor (0..100) {
09   my($stdout, $stderr, $rc) =
10               tap "bball-drop", $floor;
11
12   if($stderr =~ /floor: (d+) ((d+)/) {
13      my($result, $tries) = ($1, $2);
14
15      is($floor, $result,
16         "result: $result $tries");
17      ok($tries <= 15,
18         "result: $result $tries");
19   } else {
20       die "Unmatched: $stderr";
21   }
22 }

Abbildung 4: Im schlechtesten Fall benötigt der Algorithmus 15 Schritte.

Die zwei Test::More-Prüfkommandos in den Zeilen 15 und 17 verifizieren, ob das vom Skript ermittelte Resultat dem vorgegebenen Parameter entspricht. Das Modul Test::More vom CPAN liefert hierzu die bewährte Ausgabe im TAP-Format (»1 ok«). Das dem Modul beiliegende und generell mit neuen Perl-Distributionen verfügbare Skript »prove« wickelt eine Test-Harness darum, die bestätigt, dass alle 202 Tests erfolgreich abliefen (Abbildung 5). Das ist einfacher als die vom Testskript »suite« ausgegebenen 202 Zeilen manuell nach Fehlern zu durchsuchen. Alle Tests bestanden, der Kandidat hat 100 Punkte, einer erfolgreichen Karriere im IT-Sektor steht nun nichts mehr im Wege! (jcb)

Abbildung 5: Die Testsuite bestätigt, dass das Skript für alle möglichen Stockwerk-Kombinationen das richtige Ergebnis liefert und nie mehr als 15 Versuche benötigt.