Coding Challenge

Performance-Defizite in Software-Systemen verursachen in vielen Unternehmen jährliche Ausgaben in Millionenhöhe. Eine gezielte Performance-Optimierung spart häufig über 30% der Infrastrukturkosten, sichert die rechtzeitige Verarbeitung wichtiger Daten und reduziert Wartezeiten für Anwender. Dabei gibt es immer wieder verschiedene Ansatzpunkte zur Verbesserung — aber nicht überall sind dies die gleichen.

Gleichzeitig liegt über einen Großteil der produktiven Software keine (brauchbare/aktuelle) Dokumentation vor, so dass gilt: “The implementation is the specification.”

So sei es auch im vorliegenden Fall: In einem größeren Prozessablauf eines Flugzeugbauers zur Modellprüfung hat sich ein Programm als Bottle-Neck herausgestellt und es deine Aufgabe, hier Abhilfe zu schaffen. Das Programm bekommt dabei eine Inputdatei als Programmargument und gibt ein Ergebnis auf der Standardausgabe aus.

#!/usr/bin/python3
import sys
from collections import defaultdict

acc = set()
succs = defaultdict(list)
reds = set()

class Abort(Exception):
    def __init__(self, st):
        self.st = st

def fmt(st):
    print(len(st))
    print(' '.join(map(str, st)))

def red(start, seed):
    wl, st = [], []
    def add(x): wl.append(set(succs[x])); st.append(x); reds.add(x)
    add(start)
    while wl:
        if wl[-1]:
            cur = wl[-1].pop()
            if cur not in reds: add(cur)
            elif cur == seed: raise Abort(st + [cur])
        else: del st[-1]; del wl[-1]

def blue(start):
    wl, st, disc = [], [], set()
    def add(x): wl.append(set(succs[x])); st.append(x); disc.add(x)
    add(start)
    while wl:
        if wl[-1]:
            cur = wl[-1].pop()
            if cur not in disc: add(cur)
        else:
            del wl[-1]
            lvl = st.pop()
            if lvl in acc:
                try:
                    red(lvl, lvl)
                except Abort as abrt:
                    abrt.st = st + abrt.st
                    raise abrt

if __name__ == "__main__":
    assert len(sys.argv) > 1

    with open(sys.argv[1], 'r') as f:
        items = None
        acc_items = None
        start_item = None
        for cnt, line in enumerate(f):
            if cnt == 0:
                items = int(line)
            elif cnt == 1:
                start_item = int(line)
            elif cnt == 2:
                acc_items = int(line)
            elif cnt == 3:
                acc.update(map(int, line.split()))
                assert len(acc) == acc_items
            elif 3 < cnt < items + 4:
                fro, to = map(int, line.split())
                succs[fro].append(to)
            else:
                assert False, "line count does not match"

    assert items is not None and acc_items is not None and start_item is not None

    res = []
    try:
        blue(start_item)
    except Abort as abrt:
        res = abrt.st

    # output
    fmt(res)

Der Auftraggeber hat dabei keine weiteren Anforderungen an die Ablösung, insbesondere keine Vorgaben zur Programmiersprache. Einzig aus Betriebs- und Lizenzgründen ist erforderlich, dass Laufzeitumgebung und ggf. Compiler in den Standardrepositories der aktuellen Ubuntu Version (19.04) zu finden sind; außerdem darf kein weiterer Prozess (wie z.B. Datenbankserver) gestartet oder benutzt werden.

Bei der ersten Analyse des Programms fällt dir auf, dass hier u.a. über Mengen iteriert wird, die Ausgabe daher nicht deterministisch ist. Darauf angesprochen, findet der Auftraggeber im Nachlass des ehemaligen Entwicklers noch ein Programm (‘oracle’) um die Korrektheit des Ergebnisses zu überprüfen. Außerdem hat der Auftraggeber in weiser Voraussicht schon die Produktionsdaten des letzten Monats abgezogen, so dass ein Testset zur Verfügung steht.
Du denkst dir: „Immerhin, wenn es schon keine sonstige Beschreibung gibt.“ Die Kollegen aus anderen Projekten sind neidisch…

Download + Einreichung

Download Code + Beispiele (19 MB, tar.xz)

Einreichung und Nachfragen an: code-challenge2019@itestra.de

Lösungshinweise