Zwar schreibt heutzutage kaum mehr jemand komplizierte Algorithmen, doch Einstellungstests prüfen oft ab, ob der Kandidat die Theorie abrufbar im Hirnkasten parat hat. Zeit, die grauen Zellen aufzufrischen!
Hurra, das Ende der Krise ist nah, bald ist wieder Bewerbungszeit! Richtig, denn ist der Aufschwung einmal da, sitzt das Geld in den Unternehmen wieder locker. Um Profit daraus zu ziehen, muss der Kandidat aber seinen Lebenslauf entstaubt haben und auf Interviewfragen blitzschnelle und gescheite Antworten wissen.
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 Erdgeschoß gerade noch überstehen. Die Anzahl der dazu notwendigen Fallversuche ist dabei für den ungünstigsten Fall zu minimieren.
| |
| Abbildung 1: Aus welchem Stockwerk kommt die Bowlingkugel gerade noch unbeschadet an? |
Eine simple Methode wäre freilich, im ersten Stockwerk anzufangen, die erste Bowlingkugel runterzuwerfen, und zu sehen, ob sie heil bleibt oder nicht. Kommt sie unbeschadet unten an, setzt der Proband die Versuchsreihe im zweiten Stockwerk fort und arbeitet sich langsam bis ganz nach oben ins 100. Stockwerk 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 zerdeppert werden, allerdings muss dann das kritische Stockwerk exakt feststehen. Noch ein kleiner Tipp: 15 Versuche müssen reichen, sonst gilt der Einstellungstest leider als nicht bestanden und der Kandidat muss sich andernorts um eine Stelle, eventuell sogar in der Amateurliga, bemühen. Wer glaubt, das Zeug für die Softwareentwicklung 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, tick-tack!
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 zwei und lässt die erste Kugel aus dem 50. Stockwerk fallen, bräuchte man, falls sie zerbricht, im ungünstigsten Fall weitere 49 Versuche, um das kritische Stockwerk zu ermitteln, denn die zweite Kugel darf nun nicht zu Bruch gehen, bevor das Ergebnis eindeutig feststeht.
Der Trick, auf den der Kandidat kommen muss, ist, die 100 Stockwerke in Abschnitte mit schrittweise abnehmender Breite zu unterteilen (Abbildung 1). Der erste Abschnitt ist n Stockwerke lang, der zweite n-1, der dritte n-2, und so weiter, bis ein Abschnitt das 100ste Stockwerk streift. Mit dieser Aufteilung schreitet man 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 man mit der zweiten Bowlingkugel im zweiten Stockwerk des vorhergehenden 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 1 gezeigten Aufteilung ist, dass die Anzahl der zur Ermittlung des kritischen Stockwerks notwendigen Versuche immer auf maximal n+1 begrenzt ist, egal in welcher Höhe es letztendlich kracht. Ist der kritische Punkt zum Beispiel das letzte Stockwerk im ersten Abschnitt, bricht die erste Kugel im ersten Stockwerk des zweiten Abschnitts beim insgesamt zweiten Wurf. Danach 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: 2 mit der ersten Kugel und n-1 mit der zweiten, macht insgesamt n+1.
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, 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.
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 eins ab, und sobald ein Abschnitt die Länge eins 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 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 Gauss gilt also n(n+1)/2 >= 100, was aufgelöst eine
quadratische Gleichung ergibt, deren einzige positive Lösung nach der
im Gymnasium gelehrten binomischen Formel etwa 13,65 ist (Abbildung 3).
Der kleinste akzeptable Wert für N ist demnach 14, die numerische
Aufteilung der Abschnitte zeigt Abbildung 4.
 |
| Abbildung 3: Die Bedingung mit der Gaußschen Formel lässt sich in eine quadratische Gleichung umformen, die der Kandidat mit der binomischen Formel löst. |
 |
| Abbildung 4: Mit N=14 ergibt sich diese Verteilung der Stockwerke in Abschnitte. |
Das Listing bball-drop 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 Nummer des jeweils ersten Stockwerks eines Abschnitts enthält,
also (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
(es wird also z.B. mit ``bball-drop 99'' aufgerufen) oder es legt den
in Zeile 23 voreingestellten Wert 42 fest. Per Log4perl gibt es dann
geheimnistuerisch mit ``pst, pst'' den vom Algorithmus zu ermittelnden
Wert in Zeile 25 aus und fängt danach an, die einzelnen Abschnitte
abzufahren. 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 eins verminderter Wert ergibt das gesuchte
höchste Stockwerk, das die Kugeln noch überleben würden.
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 }
 |
| Abbildung 5: Im schlechtesten Fall benötigt der Algorithmus 15 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 6: Die Testsuite bestätigt, dass das Skript für alle möglichen Stockwerkkombinationen das richtige Ergebnis liefert und nie mehr als 15 Versuche benötigt. |
Bei derart filigranen Gartenzaunproblemen schleichen sich natürlich
unweigerlich Bugs ein, deshalb ist eine Regressionstestsuite unabdingbar.
Listing suite nutzt das Modul Sysadm::Install, um das Skript
bball-drop wieder und wieder mit unterschiedlichen maximal aushaltbaren
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 5 und 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 zur
Ermittlung des Ergebnisses notwendigen Schritte.
Die zwei Test::More-Prüfkommandos
in den Zeilen
15 und 17 verifizieren, ob das vom Skript ermittelte Resultat dem vorgegebenen
Parameter entspricht und ob die maximal zulässige Anzahl von Versuchen (15)
nicht überschritten wurde. Das Modul Test::More vom CPAN liefert hierzu
die bewährte Ausgabe im TAP-Format (``1 ok'') und 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 6).
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!
Listings zu diesem Artikel: ftp://www.linux-magazin.de/pub/listings/magazin/2009/12/Perl
 |
Michael Schilliarbeitet als Software-Engineer bei Yahoo! in Sunnyvale, Kalifornien. Er hat "Goto Perl 5" (deutsch) und "Perl Power" (englisch) für Addison-Wesley geschrieben und ist unter mschilli@perlmeister.com zu erreichen. Seine Homepage: http://perlmeister.com. |