Open Source im professionellen Einsatz
Linux-Magazin 12/2009
© themaster444, Pixelio.de

© themaster444, Pixelio.de

Perl-Skript knackt Karriere-Knobelei

Herausgekegelt

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

693

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

Linux-Magazin kaufen

Einzelne Ausgabe
 
Abonnements
 
TABLET & SMARTPHONE APPS
Bald erhältlich
Get it on Google Play

Deutschland

Ähnliche Artikel

  • Perl-Snapshot: Der Fall der Bowlingkugeln

    Wie viele Versuche braucht man mindestens, um herauszufinden, bis zu welchem Stockwerk eines Wolkenkratzers eine Bowlingkugel unbeschadet aus dem Fenster fällt? Knobeln Sie mit Mike Schilli im monatlichen Perl-Workshop des Linux-Magazins.

  • Bildschirmtastatur macht Eingabevorschläge

    Der Entwickler Thomas Thurman hat Prototypen eines On-Screen-Keyboards entwickelt, das den nächsten einzugebenden Buchstaben errät.

  • Komfortable Festung

    Trotz seiner Größe bleiben auf dem Groupware-Markt Systeme rar, die über ihren Webclient hinaus wenigstens einen Linux-Desktop-Client gut unterstützen. Die Ritter des aus der Internet-Vorzeit stammenden Citadel haben in ihre Trutzburg neben vielen anderen Funktionen eine stabile Brücke zu Kontact eingebaut.

  • Open-Xchange Partner Summit 2010

    Der Groupware-Hersteller lädt Wiederverkäufer und große Anwender zu einer Partner-Veranstaltung am 4. November 2010 in Köln ein.

  • Schnittstellen-Domino
comments powered by Disqus