Der "Tech Lead" ([2]) 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, also der bei Google übliche Führungsingenieur, der den anderen Ingenieuren im Team die Richtung vorgibt, da First-Line-Manager bei Google sich traditionell aus technischen Fragen heraushalten, sondern in erster Linie für Personalfragen zuständig sind.
Eine Episode des "Tech Leads" 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. Dabei handelt es sich um eine leicht abgewandelte Version des Floodfill-Problems ([5]), das aber mittlerweile so bekannt ist, dass jeder Kandidat die Lösung im Schlaf herbeten kann, weshalb die Frage aus dem Fragenkatalog bei Google gestrichen wurde und der Tech Lead deswegen eben seine eigene Version kreierte ([3]).
| |
| Abbildung 1: Im Youtube-Kanal des "TechLead" schwadroniert ein Ingenieur über den Alltag im Silicon Valley. |
Als einzige Vorgabe dient dabei eine auf ein Whiteboard aufgemaltes Diagramm von 12 Rechtecken, die in drei Reihen und vier Spalten aneinander liegen, und die grüne, blaue oder rote Schraffuren tragen. Bei der gestellten Interviewfrage geht es nun darum, ein Programm zu schreiben, das die meisten zusammenhängenden Rechtecke mit gleicher Schraffur ermittelt.
Wie immer im Jobinterview 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, also ist das sechste blaue Rechteck oben kein Teil des weiter untenliegenden U-förmigen Verbunds aus fünf blauen Rechtecken, die aber trotzdem die zahlengrößte Gruppe im Diagramm bilden und deren Koordinaten der Algorithmus deswegen am Ende ausspucken sollte.
 |
| Abbildung 2: Welche Ansammlung von aneinandergrenzenden Rechtecken ist die größte? |
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 13 beide Integer-Koordinaten x und y in einen Typ namens pos (für Position). Im vorliegenden Fall eignet sich ein 2-dimensionaler Array mit Integerwerten für die Farben Grün, Blau und Rot, die die const-Anweisung ab Zeile 7 in Listing 1 wegen des Schlüsselworts iota mit 0 , 1 und 2 als Konstanten durchnumeriert. Zeile 19 definiert dann ein zweidimensionales Array-Slice, das in Go als Slice von Slices vorliegt. Dabei sind die drei Unter-Slices mit jeweils vier Elementen die Reihen der Matrix (beginnend mit der ersten Reihe Green, Green, Blue, Red) und der Zugriff squares[i][j] referenziert zuerst mit i das Reihen-Slice, und dann in diesem 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. Das Rechteck ganz rechts unten wählt so zum Beispiel der Zugriff squares[2][3] aus. Dank Gos Slice-Literals kann Listing 1 den Inhalt der gesamte 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 in einer Hilfsstruktur aus einem weiteren zweidimensionalen Slice aus Boolschen Werten mitprotokollieren, welche Rechtecke er schon erfasst hat, um Kreisläufe zu vermeiden. In einer Skriptsprache wäre es nun wahrscheinlich trivial, einfach eine weitere Matrix mit den gleichen Dimensionen anzulegen und mit Bool-Typen zu besetzen, aber Go verlangt hier wegen strenger Typisierung einige Extraschritte. Zeile 28 allokiert 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 allokiert für jede ein Bool-Slice entsprechend der in cols liegenden Anzahl der Spalten der Orginal-Matrix. 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 oder nicht. Gemäß der in Go üblichen "Zero-Values" bei undefinierten Variablen sind die einzelnen Bool-Werte vom Fleck weg auf false voreingestellt, das spart dem Programmierer die Initialisierung.
01 package main
02
03 import (
04 "fmt"
05 )
06
07 const (
08 Green = iota
09 Blue
10 Red
11 )
12
13 type pos struct {
14 x int
15 y int
16 }
17
18 func main() {
19 tiles := [][]int{
20 {Green, Green, Blue, Red},
21 {Green, Blue, Red, Blue},
22 {Red, Blue, Blue, Blue},
23 }
24 rows := len(tiles)
25 cols := len(tiles[0])
26
27 // create 2D-array with same dimensions
28 seen := make([][]bool, rows)
29 for i := range seen {
30 seen[i] = make([]bool, cols)
31 }
32
33 max := []pos{}
34
35 for x, row := range tiles {
36 for y, _ := range row {
37 connected := explore(tiles,
38 pos{x, y}, seen)
39 if len(connected) > len(max) {
40 max = connected
41 }
42 }
43 }
44
45 fmt.Printf("Largest Group: %v\n", max)
46 dump(tiles, max)
47 }
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 hierfür 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. Das 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 sie die Matrix, die Position des aktuellen Elements, sowie den Notizblock seen mitgeben, 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, was das Hauptprogramm aber nicht weiter kümmert, denn selbst wenn die For-Schleifen stur jedes Element abklappern, kann der nächste Aufruf von explore() sogleich feststellen, falls ein Element schon vorher erfasst wurde, und es blitzschnell ignorieren.
Der Rückgabewert der Funktion explore(), die weiter unten in Listing 2 definiert ist, liefert als Ergebnis ein Slice von Koordinaten zurück, an denen sich Rechtecke befinden, die sowohl mit dem vorgegebenen Rechteck verbunden sind, al auch dessen Farbe tragen. Ist die Ergebnisliste länger als die bislang in max gespeicherte, überschreibt Zeile 40 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. |
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. Die definiert eine Todo-Liste namens examine, ein anfangs leeres Array-Slice, an das sie zu untersuchende Kandidaten hinten mit append() anhängt und gerade bearbeitete vorne wegnimmt, indem es in Zeile 11 das am Anfang um ein Element verkürzte Slice (examine[1:]) wieder der Variablen examine zuweist. 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 in Listing 2 aufdröselt und der append()-Funktion zum Schlucken gibt, die das Kandidaten-Array-Slice examine verlängert.
01 package main
02
03 func explore(tiles [][]int, p pos,
04 seen [][]bool) []pos {
05 results := []pos{}
06 examine := []pos{p}
07 color := tiles[p.x][p.y]
08
09 for len(examine) > 0 {
10 curpos := examine[0]
11 examine = examine[1:]
12
13 if seen[curpos.x][curpos.y] {
14 continue
15 }
16
17 if tiles[curpos.x][curpos.y] ==
18 color {
19 results = append(results, curpos)
20 seen[curpos.x][curpos.y] = true
21 examine = append(examine,
22 neighbors(tiles,
23 pos{curpos.x, curpos.y})...)
24 }
25 }
26
27 return results
28 }
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 statt dessen 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"). Das gleiche Verhalten käme zum Tragen, falls der Algorithmus statt die Suche iterativ abzuarbeiten, rekursiv vorginge und sich bei neu gefundenen Nachbarn immer wieder selbst aufriefe -- alles verschiedene Implementierungsstrategien, die ein guter Kandidat gegeneinander abwägen kann, und der Interviewer 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 x/y-Koordinaten hinzuaddiert oder subtrahiert, und gleichzeitig in der Unterfunktion add() ab Zeile 21 sicherstellt, dass so gefundene Nachbarn auch wirkliche sind und nicht außerhalb des in max definierten Rahmens liegen oder Koordinaten mit Werten kleiner Null aufweisen.
01 package main
02
03 func neighbors(
04 tiles [][]int, cur pos) []pos {
05 var max pos
06 max.x = len(tiles) - 1
07 if max.x < 2 {
08 panic("Illegal array")
09 }
10 max.y = len(tiles[0]) - 1
11
12 found := []pos{}
13 add(&found, pos{cur.x - 1, cur.y}, max)
14 add(&found, pos{cur.x + 1, cur.y}, max)
15 add(&found, pos{cur.x, cur.y - 1}, max)
16 add(&found, pos{cur.x, cur.y + 1}, max)
17
18 return found
19 }
20
21 func add(
22 found *[]pos, cand pos, max pos) {
23 if cand.x > 0 && cand.y > 0 &&
24 cand.x <= max.x && cand.y <= max.y {
25 *found = append(*found, cand)
26 }
27 }
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-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 es den hereinkommenden Pointer erst mittels *found dereferenziert. Ohne diesen Umweg über den Pointer läge in found eine Kopie des Originals aus neighbors() vor, und add() könnte zwar lesend auf das Slice zugreifen, aber dessen Elemente nicht dauerhaft modifizieren, da alle Modifizierungen in der Kopie nach dem Verlassen der Unterfunktion verloren gehen.
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, und trotzdem von der Unterfunktion explore() so modifiziert werden konnte, dass die Änderungen oben im Hauptprogramm in Listing 1 sichtbar wurden? Das Geheimnis liegt darin, 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 Go nicht ausflacht, sondern eben als Pointer ans Unterprogramm übergibt. Letzteres kann deshalb1 die hinter den Pointern stehenden Werte modifizieren, und das Hauptprogramm bekommt die Änderungen in der Datenstruktur eins zu eins mit.
Für alle computerhistorisch Interessierten kann ich zum Thema "Wert oder Pointer", auch bekannt als "call-by-value" und "call-by-name", übrigens den nicht ganz ernst gemeinten aber seminalen Aufsatz "Real Programmers Don't use Pascal" von Ed Post aus dem Jahre 1982 empfehlen ([4]). Dort heißt es: "Nicklaus Wirth, der Erfinder von Pascal, wurde einmal bei einem Vortrag gefragt: "Wie sprechen Sie Ihren Namen aus?". Er antwortete "Sie können mich entweder beim Namen rufen, wenn Sie es 'Veert' betonen oder mich beim Wert rufen 'Worth'". Man kann anhand dieser Antwort sofort sagen, dass Nicklaus Wirth ein Quiche-Fresser ist. Der einzige Wert-Übergabe-Mechanismus, der von echten Programmieren gutgeheißen wird, ist call-by-value-return." Ja, Kinder, so war das in den wilden Achtzigern!
01 package main
02
03 import (
04 "fmt"
05 )
06
07 func dump(tiles [][]int, max []pos) {
08 disp := make([][]string, len(tiles))
09
10 for i, row := range tiles {
11 disp[i] = make([]string, len(row))
12 for j, _ := range disp[i] {
13 disp[i][j] = "o"
14 }
15 }
16
17 for _, pos := range max {
18 disp[pos.x][pos.y] = "X"
19 }
20
21 for _, row := range disp {
22 fmt.Printf("%v\n", row)
23 }
24 }
Listing 4 bleibt nun nur noch, eine Funktion dump() zur grafischen Ausgabe der Positionen der längsten Kette von zusammenhängenden Rechtecken auszugeben, indem es eine Matrix mit String-Einträgen anlegt, die genauso groß wie die ursprüngliche Rechteck-Matrix ist. Sie markiert die Felder der längsten gefundenen Kette mit "X" und weist alle anderen Positionen ein "o" zu. Die Matrix-Ausgabe auf der Kommandozeile in Abbildung 3 zeigt das Ergebnis, der Algorithmus hat korrekt das U-förmige Rechtecksammlung rechts unten als größte zusammenhängende Gruppe erkannt. Um die aus Übersichtlichkeitsgründen in vier Listings aufgesplitteten Go-Programme in ein Binary namens connected zu kompilieren, genügt der Aufruf
$ go build connected.go \
explore.go neighbors.go dump.goDa alle vier Listings das Paket package main definieren, können sie alle auf die in ihnen definierten Typ-Kontrukte und Funktionen zugreifen. So weiß Listing 4, was eine pos-Struktur ist, oder Listing 1, wo es die Funktion dump() findet.
In Vorstellungsgesprächen ist es weiterhin ü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 an einer Ecke einem gleichfarbigen Nachbarn zusammenstoß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(), die nicht nur in allen vier Himmelsrichtungen nach Kandidaten Ausschau halten, sondern auch diagonal vier weitere Richtungen abklappern müsste, in dem sie jeweils sowohl die x- als auch die y-Werte mit +1 und -1 durchpermutierte.
Zurück zum Tech-Lead: Leider nahm Facebooks Personalabteilung an der Youtube-Präsenz unseres Star-Ingenieurs Anstoß und setzte ihn Knall auf Fall fristlos vor die Tür. Kein Fliegenschiss, wenn man weiß, dass der Job des Tech-Leads mit 500.000 Dollar Jahresgehalt dotiert war ([6]). 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 draus und 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. Subscribe & Like!
Listings zu diesem Artikel: http://www.linux-magazin.de/static/listings/magazin/2020/05/snapshot/
"TechLead"-Kanal auf Youtube: https://www.youtube.com/channel/UC4xKdmAXFh4ACyhpiQ_3qBw
"Mock Google Interview", https://www.youtube.com/watch?v=IWvbPIYQPFM
"Real Programmers Don't Use PASCAL", Ed Post, Tektronix, Inc., 1982, https://web.mit.edu/humor/Computers/real.programmers
Floodfill-Algorithmus, https://de.wikipedia.org/wiki/Floodfill
500.000 Dollar Jahresgehalt für Lead-Entwickler bei Facebook: https://www.youtube.com/watch?v=LMchrEYphcE
 |
Michael Schilliarbeitet als Software-Engineer in der San Francisco Bay Area in Kalifornien. In seiner seit 1997 laufenden Kolumne forscht er jeden Monat nach praktischen Anwendungen verschiedener Programmiersprachen. Unter mschilli@perlmeister.com beantwortet er gerne Ihre Fragen. |
Hey! The above document had some coding errors, which are explained below:
Unknown directive: =desc