© Serhii Radachynskyi, 123RF

Frühlingszeit, Bewerbungszeit! Der in Bewerbungsverfahren von Unternehmen im Silicon Valley erfahrene Mike Schilli gräbt eine beim Einstellungsgespräch für Google-Ingenieure gestellte Frage aus und erläutert eine mögliche Lösung dafür in Go.

Der TechLead [1] ist eine illustre Youtube-Persönlichkeit, deren Videos ich mir gerne anschaue. Der ehemalige Google-Mitarbeiter, der mittlerweile auch einen Gig bei Facebook hingelegt hat, plaudert in zahlreichen Episoden auf seinem Kanal über seine Erfahrungen als Software-Ingenieur im Silicon Valley. Sein Markenzeichen ist, dabei einen Becher Kaffee in der Hand zu halten und hin und wieder genüsslich daran zu nippen, während er nicht müde wird zu betonen, dass er der “Tech Lead” sei. So bezeichnet man bei Google Führungsingenieure, die den anderen Ingenieuren im Team die Richtung vorgeben. Der First-Line-Manager halten sich dort traditionell aus technischen Fragen heraus und kümmern sich in erster Linie um Personalfragen .

Eine Episode des TechLead dreht sich um Einstellungsfragen im Google-Interview, von denen der ehemalige Angestellte nach eigener Aussage schon Hunderte geführt hat. In dieser Snapshot-Ausgabe soll es um eine seiner angeblich selbst erfundenen und laufend gestellten Quiz-Fragen gehen, eine leicht abgewandelte Version des Floodfill-Problems [2]. Das gilt aber mittlerweile als derart bekannt, dass jeder Kandidat die Lösung im Schlaf herbeten kann. Deshalb hat Google es aus dem Fragenkatalog gestrichen, sodass der TechLead seine eigene Version kreierte [3].

Abbildung 1: Im Youtube-Kanal TechLead schwadroniert ein Ingenieur über den Alltag im Silicon Valley.

Vage Fragestellung

Als einzige Vorgabe für den Kandidaten dient dabei ein auf ein Whiteboard aufgemaltes Diagramm mit zwölf Rechtecken. Sie liegen in drei Reihen und vier Spalten aneinander und sind grün, blau oder rot schraffiert. Die Aufgabe lautet nun, ein Programm zu schreiben, das die meisten zusammenhängenden Rechtecke mit gleicher Schraffur ermittelt.

Wie immer im Job-Interview geht es zunächst darum herauszufinden, was der Interviewer, der oft ganz bewusst vage Fragen stellt, eigentlich im Sinn hat. Im vorliegenden Fall ist nicht ganz klar, was “zusammenhängend” eigentlich heißt: Hängt das blaue Quadrat in der dritten Spalte der ersten Reihe nun mit den darunterliegenden diagonal “verbundenen” zusammen oder nicht? Auf Nachfrage bestätigt der Interviewer, dass nur solche Rechtecke zusammenhängen, die eine ganze Seite mit ihrem Partner teilen. Das sechste blaue Rechteck ganz oben ist also kein Teil des weiter unten liegenden U-förmigen Verbunds aus fünf blauen Rechtecken. Die bilden aber trotzdem die zahlengrößte Gruppe im Diagramm, weswegen der Algorithmus ihre Koordinaten am Ende ausspucken sollte.

Abbildung 2: Welche Ansammlung von aneinandergrenzenden Rechtecken ist die größte?

Modell formen

Als Erstes bildet ein brauchbarer Kandidat das gestellte Problem auf ein Datenmodell ab. Da der Algorithmus später X/Y-Koordinaten als Einheit herumschickt, packt die Typ-Definition in Zeile 13 von Listing 1 die Integer-Koordinaten »x« und »y« in einen Typ namens »pos« (für Position). Für den vorliegenden Fall eignet sich ein zweidimensionales Array mit Integer-Werten für die Farben Grün, Blau und Rot. Die nummeriert die »const«-Anweisung ab Zeile 7 wegen des Schlüsselworts »iota« mit »0 «, »1« und »2« als Konstanten durch.

Zeile 19 definiert dann ein zweidimensionales Array-Slice, das in Go als Slice von Slices vorliegt. Dabei bilden drei Unter-Slices mit jeweils vier Elementen die Reihen der Matrix (beginnend mit der ersten Reihe Green, Green, Blue, Red). Der Zugriff »squares[i][j]« referenziert zuerst mit »i« das Reihen-Slice und dann darin das Element an Spaltenposition »j«.

Die »x«-Koordinaten laufen innerhalb der Matrix dann (von null beginnend) von oben nach unten, die »y«-Koordinaten von links nach rechts. Der Zugriff »squares[2][3]« wählt also beispielsweise das Rechteck ganz rechts unten aus. Dank der Slice-Literals von Go kann der Programmierer in Listing 1 den Inhalt der gesamten Datenstruktur ab Zeile 19 innerhalb der geschweiften Klammern direkt hinschreiben, ohne sich um die Allokation der Unter-Slices Gedanken machen zu müssen.

Eine weitere Datenstruktur entsteht ab Zeile 28 in der Variablen »seen«: Beim späteren Durchforsten der Matrix möchte der Algorithmus mitprotokollieren, welche Rechtecke er schon erfasst hat, um Kreisläufe zu vermeiden. Dazu nutzt er eine Hilfsstruktur aus einem weiteren zweidimensionalen Slice aus Booleschen Werten. In einer Skriptsprache wäre es nun wahrscheinlich trivial, einfach eine weitere Matrix mit denselben Dimensionen anzulegen und mit Bool-Typen zu besetzen, aber Go verlangt hier wegen seiner strengen Typisierung einige Extraschritte.

Zeile 28 alloziert zunächst mit »make()« eine Matrix von Bool-Slices entsprechend der in »rows« liegenden Anzahl von Reihen in der Datenstruktur der Rechtecke (»tiles«). Dann iteriert die For-Schleife ab Zeile 29 mit »range« über die vorher erzeugten Bool-Reihen und weist jeder entsprechend der in »cols« liegenden Anzahl der Spalten der Orginalmatrix ein Bool-Slice zu.

Derart initialisiert, erlaubt die Struktur mit »seen[x][y]« die Abfrage, ob das Programm das Rechteck an der Position »x« und »y« schon besucht hat. Gemäß der in Go üblichen Zero-Values bei undefinierten Variablen sind die einzelnen Bool-Werte vom Fleck weg auf »false« voreingestellt – das erspart dem Programmierer die Initialisierung.

package main
import (
  "fmt"
)
const (
  Green = iota
  Blue
  Red
)
type pos struct {
  x int
  y int
}
func main() {
  tiles := [][]int{
    {Green, Green, Blue, Red},
    {Green, Blue, Red, Blue},
    {Red, Blue, Blue, Blue},
  }
  rows := len(tiles)
  cols := len(tiles[0])
  // create 2D-array with same dimensions
  seen := make([][]bool, rows)
  for i := range seen {
    seen[i] = make([]bool, cols)
  }
  max := []pos{}
  for x, row := range tiles {
    for y, _ := range row {
      connected := explore(tiles,
        pos{x, y}, seen)
      if len(connected) > len(max) {
        max = connected
      }
    }
  }
  fmt.Printf("Largest Group: %v\n", max)
  dump(tiles, max)
}

Maximalwert sichern

Als Ergebnis spuckt der Algorithmus später eine Liste von Koordinaten aus, an denen sich die Rechtecke der größten zusammenhängenden Gruppe befinden. Zeile 33 definiert dazu die Variable »max« vom Typ eines Slices aus »pos«-Strukturen, die vorher in Zeile 13 als X/Y-Werte definiert wurden. Die geschweiften Klammern des Slice Literals initialisieren die Variable dabei auf ein leeres Slice.

Der For-Schleifen-Zweierpack in den Zeilen 35 und 36 iteriert über die Reihen und Spalten der Matrix und ruft für jedes Element die Funktion »explore()« auf. Der gibt er die Matrix, die Position des aktuellen Elements sowie den Notizblock »seen« mit, in dem die Funktion bereits besuchte Elemente markiert und bei späteren Aufrufen überspringt. So schnüffelt »explore()«, beginnend beim aktuellen Element, intern auch noch weiter nach passenden Rechtecken. Das kümmert das Hauptprogramm aber nicht weiter, denn selbst wenn die For-Schleifen stur jedes Element abklappern, kann der nächste Aufruf von »explore()« sogleich feststellen, ob ein Element schon erfasst wurde, und es blitzschnell ignorieren.

Die in Listing 2 definierte Funktion »explore()« liefert als Ergebnis ein Slice von Koordinaten zurück, an denen sich Rechtecke befinden, die sowohl mit dem vorgegebenen Rechteck verbunden sind als auch dessen Farbe tragen. Ist die Ergebnisliste länger als die bislang in »max« gespeicherte, überschreibt Zeile 40 von Listing 1 die Variable »max« mit der neuen Rekordlänge. Am Ende des Programms bleibt Zeile 45 nur noch, die Rekordliste auszugeben und die Funktion »dump()« aus Listing 4 aufzurufen, die das Ergebnis grafisch illustriert (Abbildung 3).

Abbildung 3: Der Algorithmus hat die größte zusammenhängende Gruppe gefunden und im Raster markiert.

Auf Expedition

Wie nun findet der Algorithmus, ausgehend von einem bestimmten Rechteck, alle anliegenden Nachbarn? Die Funktion »explore()« in Listing 2 nimmt hierzu die Gesamtmenge aller Rechtecke, die Startposition sowie den Notizblock »seen« entgegen. Sie definiert eine Todo-Liste namens »examine«. An dieses anfangs leere Array-Slice hängt sie zu untersuchende Kandidaten hinten mit »append()« an und nimmt gerade bearbeitete vorne weg, indem sie in Zeile 11 das am Anfang um ein Element verkürzte Slice (»examine[1:]«) wieder der Variablen »examine« zuweist.

package main
func explore(tiles [][]int, p pos,
  seen [][]bool) []pos {
  results := []pos{}
  examine := []pos{p}
  color := tiles[p.x][p.y]
  for len(examine) > 0 {
    curpos := examine[0]
    examine = examine[1:]
    if seen[curpos.x][curpos.y] {
      continue
    }
    if tiles[curpos.x][curpos.y] ==
      color {
      results = append(results, curpos)
      seen[curpos.x][curpos.y] = true
      examine = append(examine,
        neighbors(tiles,
          pos{curpos.x, curpos.y})...)
    }
  }
  return results
}

Die in Zeile 22 aufgerufene Funktion »neighbors()« ist in Listing 3 definiert und sucht alle anliegenden Rechtecke. Sie liefert ein Array-Slice zurück, dessen Elemente der »…«-Operator in Zeile 23 von Listing 2 aufdröselt und der »append()«-Funktion zum Schlucken gibt, die das Kandidaten-Array-Slice »examine« verlängert.

Das Verfahren implementiert also eine Warteschlange, die neue Einträge ans Ende anhängt und alte vom Slice-Anfang Schritt für Schritt mit jedem Durchgang der For-Schleife ab Zeile 9 abarbeitet. Eine Warteschlange (Queue) funktioniert nach dem Prinzip “first in, first out”, breitet sich also flächig im Rechteck-Labyrinth aus (“breadth first”). Käme stattdessen ein Stack (“first in, last out”) zum Einsatz, würde »explore()« erst in die Tiefe bohren, bevor es weitere direkt anliegende Nachbarn fände (“depth first”). Dasselbe Verhalten käme zum Tragen, falls der Algorithmus rekursiv vorginge, statt die Suche iterativ abzuarbeiten, und sich bei neu gefundenen Nachbarn immer wieder selbst aufriefe. Alle diese verschiedenen Implementierungsstrategien kann ein guter Kandidat gegeneinander abwägen, was der Interviewer sicherlich erfreut zur Kenntnis nimmt.

Die Funktion »neighbors()« in Listing 3 nimmt die Gesamtmenge aller Rechtecke (»tiles«) sowie die aktuelle Startposition als X/Y-Koordinaten (»cur«) entgegen und liefert alle anliegenden Nachbarn als Array-Slice von »pos«-Typen zurück. Sie klappert alle in Richtung Norden, Süden, Westen und Osten liegenden Rechtecke ab, indem sie jeweils den Wert »1« zu den Koordinaten addiert oder davon subtrahiert. Gleichzeitig stellt sie in der Unterfunktion »add()« ab Zeile 21 sicher, dass es sich bei den so gefundenen Nachbarn auch wirklich um solche handelt, sie also nicht außerhalb des in »max« definierten Rahmens liegen oder Koordinaten mit Werten kleiner null aufweisen.

package main
func neighbors(
    tiles [][]int, cur pos) []pos {
  var max pos
  max.x = len(tiles) - 1
  if max.x < 2 {
    panic("Illegal array")
  }
  max.y = len(tiles[0]) - 1
  found := []pos{}
  add(&found, pos{cur.x - 1, cur.y}, max)
  add(&found, pos{cur.x + 1, cur.y}, max)
  add(&found, pos{cur.x, cur.y - 1}, max)
  add(&found, pos{cur.x, cur.y + 1}, max)
  return found
}
func add(
    found *[]pos, cand pos, max pos) {
  if cand.x > 0 && cand.y > 0 &&
     cand.x <= max.x && cand.y <= max.y {
    *found = append(*found, cand)
  }
}

Damit die Funktion »add()« ab Zeile 21 in Listing 3 das ihr überreichte Array-Slice nicht nur lesen, sondern auch modifizieren kann, übergeben die Aufrufer in den Zeilen 13 bis 16 die Slice-Variable »found« nicht als Wert, sondern mittels der “&”-Notation als Pointer. In der Funktionsdeklaration von »add()« ab Zeile 21 steht »found« deshalb ebenfalls als Pointer auf ein Array-Slice von »pos«-Strukturen (»found *[]pos«).

Die in Go eingebaute »append()«-Funktion ab Zeile 25 greift auf das Array-Slice zu, indem sie den hereinkommenden Pointer erst mittels »*found« dereferenziert. Ohne diesen Umweg über den Pointer läge in »found« eine Kopie des Originals aus »neighbors()« vor. Dann könnte »add()« zwar lesend auf das Slice zugreifen, aber dessen Elemente nicht dauerhaft modifizieren, da alle Änderungen an der Kopie nach dem Verlassen der Unterfunktion verloren gehen.

Pointer oder Wert?

Der aufmerksame Leser wird sich aber nun vielleicht fragen, warum das zweidimensionale Array-Slice »seen« aus dem Hauptprogramm in Listing 1 vorher nicht als Pointer übergeben wurde? Wie konnte die Unterfunktion »explore()« es trotzdem so modifizieren, dass die Änderungen oben im Hauptprogramm in Listing 1 sichtbar wurden?

Das liegt daran, dass Go Array-Slices zwar als Werte übergibt, die zweite Dimension der Datenstruktur »seen« in Listing 1 aber aus Pointern auf Array-Slices bestand. Die flacht Go nicht aus, sondern übergibt sie eben als Pointer ans Unterprogramm. Das kann deshalb die hinter den Pointern stehenden Werte modifizieren, sodass das Hauptprogramm die Änderungen in der Datenstruktur eins zu eins mitbekommt.

Für alle computerhistorisch Interessierten kann ich zum Thema “Wert oder Pointer” (auch bekannt als “call-by-value” und “call-by-name”) den nicht bierernst gemeinten, aber stilbildenden Aufsatz “Real Programmers Don’t use Pascal” [4] von Ed Post aus dem Jahr 1982 empfehlen. Dort heißt es, Nicklaus Wirth, der Erfinder von Pascal, sei einmal bei einem Vortrag gefragt worden, wie er seinen Namen ausspreche. “He replied: ‘You can either call me by name, pronouncing it “Veert”, or call me by value, “Worth”‘. One can tell immediately from this comment that Nicklaus Wirth is a Quiche Eater. The only parameter passing mechanism endorsed by Real Programmers is call-by-value-return.”

Listing 4 implementiert zu guter Letzt eine Funktion »dump()« zur grafischen Ausgabe der Positionen der längsten Kette von zusammenhängenden Rechtecken. Dazu legt es eine Matrix mit String-Einträgen an, die genauso groß ist wie die ursprüngliche Rechteck-Matrix. Der Algorithmus markiert die Felder der längsten gefundenen Kette mit »X« und weist allen anderen Positionen ein »o« zu. Die Matrix-Ausgabe auf der Kommandozeile in Abbildung 3 zeigt das Ergebnis: Der Algorithmus hat korrekt die U-förmige Rechtecksammlung rechts unten als größte zusammenhängende Gruppe erkannt.

package main
import (
  "fmt"
)
func dump(tiles [][]int, max []pos) {
  disp := make([][]string, len(tiles))
  for i, row := range tiles {
    disp[i] = make([]string, len(row))
    for j, _ := range disp[i] {
      disp[i][j] = "o"
    }
  }
  for _, pos := range max {
    disp[pos.x][pos.y] = "X"
  }
  for _, row := range disp {
    fmt.Printf("%v\n", row)
  }
}

Um die aus Gründen der Übersichtlichkeit in vier Listings aufgesplitteten Go-Programme in ein Binary namens »connected« zu kompilieren, genügt der Aufruf aus Listing 5. Da alle vier Listings das Paket »package main« definieren, können sie alle auf die in ihnen definierten Typ-Konstrukte und Funktionen zugreifen. So weiß Listing 4, was eine »pos«-Struktur ist, oder Listing 1, wo es die Funktion »dump()« findet.

$ go build connected.go \
explore.go neighbors.go dump.go

Abgewandelte Frage

In Vorstellungsgesprächen ist es nicht unüblich, nach der gefundenen Lösung alternative Fragestellungen ins Spiel zu bringen: Was wäre zu ändern, falls “zusammenhängend” nun nicht nur auf Rechtecke zuträfe, die sich eine Seite teilen, sondern auch auf solche, die nur mit einer Ecke an einen gleichfarbigen Nachbarn stoßen?

In diesem Fall würde der Algorithmus ebenfalls die blaue Gruppe als größte finden, allerdings mit einem zusätzlichen Element, dem Rechteck der dritten Spalte in der ersten Reihe. Abzuändern wäre dafür im Code nur die Funktion »neighbors()«: Sie müsste nicht nur in allen vier Himmelsrichtungen nach Kandidaten Ausschau halten, sondern auch diagonal vier weitere Richtungen abklappern, indem sie jeweils sowohl die X- als auch die Y-Werte mit »+1« und »-1« durchpermutiert.

Epilog

Zurück zum “Tech Lead”: Leider nahm Facebooks Personalabteilung an der Youtube-Präsenz unseres Star-Ingenieurs Anstoß und setzte ihn Knall auf Fall vor die Tür – kein Fliegenschiss, wenn man weiß, dass der Job mit 500 000 Dollar Jahresgehalt dotiert war [5]. Aber der leicht überhebliche Patrick Shyu, von dem man nie weiß, ob er nun tatsächlich so eingebildet ist oder einfach nur zur Selbstironie neigt, machte sich nichts daraus. Er lebt nun von seinen Ersparnissen und den Erträgen aus dem Youtube-Kanal. Ein Ende der Hunderte Videos langen Serie ist noch nicht in Sicht, mit 671 000 Subscribern klingeln sicher auch die Kassen ordentlich.