Parsing eines Vorstellungsgesprächs bei Google: auch Abfragen

Published on January 28, 2019

Parsing eines Vorstellungsgesprächs bei Google: auch Abfragen

Ursprünglicher Autor: Alex Golec
  • Übersetzung


Dies ist ein neuer Artikel aus der Analyse von Aufgaben mit Interviews in Google . Als ich dort arbeitete, bot ich Kandidaten solche Aufgaben an. Dann gab es ein Leck und sie wurden verboten. Aber die Medaille hat einen Nachteil: Jetzt kann ich die Lösung frei erklären.

Zunächst eine gute Nachricht: Ich habe Google verlassen! Ich freue mich, Ihnen mitteilen zu können, dass ich jetzt als technischer Manager für Reddit in New York arbeite! Diese Artikelserie wird aber weitergeführt.

Haftungsausschluss: Obwohl es eine meiner beruflichen Pflichten ist, Kandidaten zu interviewen, teile ich auf diesem Blog persönliche Beobachtungen, Geschichten und persönliche Meinungen. Bitte betrachten Sie dies nicht als offizielle Erklärung von Google, Alphabet, Reddit oder einer anderen Person oder Organisation.

Frage


Nach den letzten beiden Artikeln über den Verlauf des Pferdes beim Wählen einer Telefonnummer erhielt ich kritische Kommentare, dass dies kein realistisches Problem ist. Egal wie nützlich es ist, die Denkfähigkeiten eines Kandidaten zu studieren, aber ich muss zugeben: Die Aufgabe ist in der Tat ein bisschen unrealistisch. Ich habe zwar einige Gedanken über den Zusammenhang zwischen den Fragen bei den Interviews und der Realität, aber vorerst werde ich sie bei mir behalten. Seien Sie sicher, ich lese überall Kommentare und habe etwas zu beantworten, aber nicht jetzt.

Aber als die Aufgabe bezüglich des Ritterzugs vor ein paar Jahren verboten wurde, nahm ich mir die Kritik zu Herzen und versuchte, sie durch eine Frage zu ersetzen, die etwas mehr mit Google zu tun hat. Und was könnte für Google relevanter sein als die Suchmaschinenmechanik? Also habe ich diese Frage gefunden und lange benutzt, bevor sie auch in die Öffentlichkeit kam und verboten wurde. Nach wie vor werde ich die Frage formulieren, mich in ihre Erklärung eintauchen und Ihnen dann sagen, wie ich sie in Interviews verwendet habe und warum sie mir gefällt.

Die Frage ist also.

Stellen Sie sich vor, Sie führen eine beliebte Suchmaschine aus und sehen zwei Anfragen in den Protokollen: Angenommen, Obamas Zustimmungswerte und Obamas Bekanntheitsgrad (wenn ich mich recht erinnere, sind dies echte Beispiele aus der Fragenbasis, obwohl sie jetzt etwas veraltet sind ...). . Wir sehen unterschiedliche Anfragen, aber alle sind sich einig: Benutzer suchen im Wesentlichen nach denselben Informationen, sodass Anfragen bei der Berechnung der Anzahl der Anfragen, der Anzeige der Ergebnisse usw. als gleichwertig angesehen werden sollten. Wie kann man feststellen, dass zwei Anfragen synonym sind?

Lassen Sie uns das Problem formalisieren. Angenommen, es gibt zwei Sätze von Zeilenpaaren: Paare von Synonymen und Paare von Abfragen.

Im Folgenden finden Sie ein Beispiel für die Eingabe zur Veranschaulichung:

SYNONYMS = [
  ('rate', 'ratings'),
  ('approval', 'popularity'),
]
QUERIES = [
  ('obama approval rate', 'obama popularity ratings'),
  ('obama approval rates', 'obama popularity ratings'),
  ('obama approval rate', 'popularity ratings obama')
]

Es muss eine Liste mit logischen Werten erstellt werden: Sind die Abfragen in jedem Paar gleichbedeutend?

Alle neuen Fragen ...


Auf den ersten Blick ist dies eine einfache Aufgabe. Aber je länger Sie nachdenken, desto schwieriger wird es. Kann ein Wort mehrere Synonyme haben? Ist die Reihenfolge der Wörter wichtig? Sind Beziehungen synonym transitiv, dh wenn A synonym mit B ist und B synonym mit C ist, ist A ein Synonym für C? Können Synonyme einige Wörter abdecken, da „US“ ein Synonym für die Ausdrücke „Vereinigte Staaten von Amerika“ oder „Vereinigte Staaten von Amerika“ ist?

Eine solche Zweideutigkeit gibt sofort die Gelegenheit, sich als guter Kandidat zu beweisen. Das erste, was er tut, ist, solche Unklarheiten aufzuspüren und sie aufzulösen. Jeder macht es anders: Einige nähern sich der Tafel und versuchen, bestimmte Fälle manuell zu lösen, während andere sich die Frage ansehen und sofort die Leerzeichen sehen. In jedem Fall ist es entscheidend, diese Probleme frühzeitig zu erkennen.

Die Phase des „Problemverständnisses“ ist wichtig. Ich nenne Software Engineering gerne eine fraktale Disziplin. Wie bei Fraktalen offenbart die Approximation zusätzliche Komplexität. Sie glauben, das Problem zu verstehen, und schauen dann genauer hin - und stellen fest, dass Sie einige Feinheiten oder Implementierungsdetails übersehen haben, die verbessert werden können. Oder eine andere Herangehensweise an das Problem.


Das Mandelbrot

Calibre Engineer's Set wird maßgeblich davon bestimmt, wie tief er das Problem verstehen kann. Die Umwandlung einer vagen Formulierung des Problems in einen detaillierten Satz von Anforderungen ist der erste Schritt in diesem Prozess, und mit einer gezielten Andeutung können Sie beurteilen, wie gut der Kandidat in neue Situationen passt.

Lassen wir triviale Fragen wie „Macht es Großbuchstaben aus?“ Beiseite, die den grundlegenden Algorithmus nicht beeinflussen. Ich gebe auf diese Fragen immer die einfachste Antwort (in diesem Fall: "Angenommen, alle Buchstaben wurden bereits verarbeitet und auf Kleinbuchstaben reduziert.")

Teil 1. (Nicht wirklich) ein einfacher Fall.


Wenn Kandidaten Fragen stellen, beginne ich immer mit dem einfachsten Fall: Ein Wort kann mehrere Synonyme haben, die Reihenfolge der Wörter spielt eine Rolle, Synonyme sind nicht transitiv. Dies gibt der Suchmaschine eine ziemlich eingeschränkte Funktionalität, aber es hat genug Feinheiten für ein interessantes Interview.

Die allgemeine Überprüfung sieht folgendermaßen aus: Teilen Sie die Wortabfrage auf (z. B. nach Leerzeichen) und vergleichen Sie die entsprechenden Paare, um nach identischen Wörtern und Synonymen zu suchen. Optisch sieht es so aus:



Im Code:

def synonym_queries(synonym_words, queries):
    '''
    synonym_words: iterable of pairs of strings representing synonymous words
    queries: iterable of pairs of strings representing queries to be tested for 
             synonymous-ness
    '''
    output = []
    for q1, q2 in queries:
        q1, q2 = q1.split(), q2.split()
        if len(q1) != len(q2):
            output.append(False)
            continue
        result = True
        for i in range(len(q1)):
            w1, w2 = q1[i], q2[i]
            if w1 == w2:
                continue
            elif words_are_synonyms(w1, w2):
                continue
            result = False
            break
        output.append(result)
    return output

Einfach, richtig? Algorithmisch ist dies ziemlich einfach. Keine dynamische Programmierung, Rekursion, komplexe Strukturen usw. Einfache Manipulation der Standardbibliothek und eines Algorithmus, der in linearer Zeit arbeitet, oder?

Aber es gibt mehr Nuancen, als es auf den ersten Blick scheint. Die schwierigste Komponente ist natürlich der Vergleich von Synonymen. Obwohl die Komponente leicht zu verstehen und zu beschreiben ist, gibt es viele Möglichkeiten, Fehler zu machen. Ich erzähle Ihnen von den häufigsten Fehlern.

Zur Verdeutlichung: Keine Fehler disqualifizieren einen Kandidaten. Wenn überhaupt, weise ich nur auf einen Fehler in der Implementierung hin, er behebt ihn und wir fahren fort. Ein Interview ist jedoch vor allem ein Kampf mit der Zeit. Sie werden Fehler machen, bemerken und korrigieren, aber es braucht Zeit, die für andere ausgegeben werden kann, um beispielsweise eine optimalere Lösung zu erstellen. Praktisch jeder macht Fehler, das ist normal, aber Kandidaten, die sie kleiner machen, zeigen einfach bessere Ergebnisse, weil sie weniger Zeit für die Korrektur aufwenden.

Deshalb mag ich dieses Problem. Wenn der Zug des Ritters Einsicht in das Verständnis des Algorithmus und dann (hoffentlich) eine einfache Implementierung erfordert, dann ist die Lösung hier eine Menge Schritte in die richtige Richtung. Jeder Schritt stellt ein winziges Hindernis dar, durch das der Kandidat entweder anmutig springen oder stolpern und klettern kann. Gute Kandidaten vermeiden aufgrund ihrer Erfahrung und Intuition diese kleinen Fallen - und erhalten eine detailliertere und korrektere Lösung, während die Schwächeren Zeit und Energie für Fehler aufwenden und in der Regel beim falschen Code bleiben.

Bei jedem Interview habe ich eine andere Kombination von Erfolgen und Misserfolgen gesehen, hier sind die häufigsten Fehler.

Zufällige Performance-Killer


Zunächst implementierten einige Kandidaten die Synonymerkennung durch einfaches Durchlaufen der Liste der Synonyme:

...
elif (w1, w2) in synonym_words:
  continue
...

Auf den ersten Blick erscheint dies vernünftig. Bei näherer Betrachtung stellt sich die Idee jedoch als sehr, sehr schlecht heraus. Für diejenigen von Ihnen , die Python nicht kennen, das Schlüsselwort in - syntaktischer Zucker für die Methode enthält und funktioniert auf allen Standard - Python - Container. Dies ist ein Problem, da es sich synonym_words um eine Liste handelt, die das Schlüsselwort in mit einer linearen Suche implementiert. Python-Benutzer reagieren besonders empfindlich auf diesen Fehler, da die Sprache Typen verbirgt, aber auch C ++ - und Java-Benutzer machten manchmal ähnliche Fehler.

In meiner gesamten Karriere habe ich nur ein paar Mal einen Code mit linearer Suche geschrieben, und jeder in einer Liste, die nicht länger als zwei Dutzend Elemente ist. Und selbst in diesem Fall schrieb er einen langen Kommentar, in dem er erklärte, warum er einen scheinbar nicht optimalen Ansatz gewählt hatte. Ich vermute, dass einige Kandidaten es verwendet haben, weil sie nicht wussten, wie das Schlüsselwort inin der Standard-Python-Bibliothek mit Listen funktioniert . Dies ist ein einfacher Fehler, nicht tödlich, aber eine schlechte Kenntnis Ihrer Lieblingssprache ist nicht sehr gut.

In der Praxis ist dieser Fehler leicht zu vermeiden. Vergessen Sie niemals Ihre Objekttypen, auch wenn Sie eine untypisierte Sprache wie Python verwenden! Zweitens, denken Sie daran , dass , wenn Sie ein Schlüsselwort inin der Liste startet eine lineare Suche. Wenn nicht garantiert wird, dass diese Liste immer sehr klein bleibt, wird die Leistung beeinträchtigt.

Damit der Kandidat zur Besinnung kommt, genügt es normalerweise, ihn daran zu erinnern, dass die Eingabestruktur eine Liste ist. Es ist sehr wichtig zu beobachten, wie der Kandidat auf den Hinweis reagiert. Die besten Kandidaten versuchen sofort, Synonyme vorab zu verarbeiten, was ein guter Anfang ist. Dieser Ansatz ist jedoch nicht frei von seinen Fallstricken ...

Verwenden Sie die richtige Datenstruktur


Aus dem obigen Code ist sofort ersichtlich, dass es zur Implementierung dieses Algorithmus in linearer Zeit erforderlich ist, Synonyme schnell zu finden. Und wenn wir über die Schnellsuche sprechen, handelt es sich immer um eine Karte oder eine Reihe von Hashes.

Es ist mir egal, ob der Kandidat eine Karte oder eine Reihe von Hashes auswählt. Wichtig ist, dass er dort investiert (benutze übrigens niemals dict / hashmap beim Übergang zu Trueoder False). Die meisten Kandidaten wählen eine Art Diktat / Hashmap. Der häufigste Fehler ist die unbewusste Annahme, dass jedes Wort nur ein Synonym enthält:

...
synonyms = {}
for w1, w2 in synonym_words:
  synonyms[w1] = w2
...
elif synonyms[w1] == w2:
  continue 

Ich bestrafe keine Kandidaten für diesen Fehler. Die Aufgabe ist speziell formuliert, um sich nicht auf die Tatsache zu konzentrieren, dass Wörter mehrere Synonyme haben können und einige Kandidaten einfach nicht auf eine solche Situation gestoßen sind. Beheben Sie den Fehler am schnellsten, wenn ich darauf hinweise. Gute Kandidaten merken es früh und verbringen in der Regel nicht viel Zeit.

Ein etwas gravierenderes Problem ist die Unwissenheit, dass sich die Beziehung der Synonyme in beide Richtungen ausbreitet. Beachten Sie, dass dies im obigen Code berücksichtigt wird. Es gibt aber Implementierungen mit einem Fehler:

...
synonyms = defaultdict(set)
for w1, w2 in synonym_words:
  synonyms[w1].append(w2)
  synonyms[w2].append(w1)
...
elif w2 in synonyms.get(w1, tuple()):
  continue

Warum zwei Einfügungen und doppelt so viel Speicher?

...
synonyms = defaultdict(set)
for w1, w2 in synonym_words:
  synonyms[w1].append(w2)
...
elif (w2 in synonyms.get(w1, tuple()) or
    w1 in synonyms.get(w2, tuple())):
  continue

Fazit: Überlegen Sie sich immer, wie Sie den Code optimieren können ! Rückblickend ist die Neuordnung der Suchfunktionen eine naheliegende Optimierung, ansonsten kann der Schluss gezogen werden, dass der Kandidat nicht über die Optimierungsmöglichkeiten nachgedacht hat. Auch hier gebe ich gerne einen Hinweis, aber es ist besser, selbst zu raten.

Sortieren?


Einige intelligente Kandidaten möchten die Liste der Synonyme sortieren und dann die binäre Suche verwenden. Tatsächlich hat dieser Ansatz einen wichtigen Vorteil: Er benötigt keinen zusätzlichen Speicherplatz, abgesehen von der Liste der Synonyme (vorausgesetzt, die Liste kann geändert werden).

Leider stört die Zeitkomplexität: Das Sortieren der Liste der Synonyme braucht Nlog(N)Zeit und dannlog(N)nach jedem Synonympaar zu suchen, während die beschriebene Vorverarbeitungslösung in linearer und dann konstanter Zeit auftritt. Außerdem bin ich entschieden dagegen, den Kandidaten zu zwingen, eine Sortierung und eine binäre Suche an der Tafel durchzuführen, weil: 1) die Sortieralgorithmen gut bekannt sind, daher kann der Kandidat sie meines Wissens ohne nachzudenken ausstellen; 2) Es ist äußerst schwierig, diese Algorithmen korrekt zu implementieren, und oft machen selbst die besten Kandidaten Fehler, die nichts über ihre Programmierkenntnisse aussagen.

Wann immer ein Kandidat eine solche Lösung vorschlug, war ich an der Ausführungszeit des Programms interessiert und fragte, ob es eine bessere Option gäbe. Zur Information: Wenn der Interviewer Sie fragt, ob es eine bessere Option gibt, lautet die Antwort fast immer Ja. Wenn ich Ihnen jemals diese Frage stelle, wird die Antwort definitiv sein.

Endlich die Lösung


Am Ende bietet der Kandidat etwas Richtiges und einigermaßen Optimales. Hier ist die Implementierung in linearer Zeit und linearem Raum für die gegebenen Bedingungen:

def synonym_queries(synonym_words, queries):
    '''
    synonym_words: iterable of pairs of strings representing synonymous words
    queries: iterable of pairs of strings representing queries to be tested for 
             synonymous-ness
    '''
    synonyms = defaultdict(set)
    for w1, w2 in synonym_words:
        synonyms[w1].add(w2)
    output = []
    for q1, q2 in queries:
        q1, q2 = q1.split(), q2.split()
        if len(q1) != len(q2):
            output.append(False)
            continue
        result = True
        for i in range(len(q1)):
            w1, w2 = q1[i], q2[i]
            if w1 == w2:
                continue
            elif ((w1 in synonyms and w2 in synonyms[w1]) 
                    or (w2 in synonyms and w1 in synonyms[w2])):
                continue
            result = False
            break
        output.append(result)
    return output

Ein paar kurze Notizen:

  • Achten Sie auf die Verwendung dict.get(). Sie können eine Prüfung durchführen, um festzustellen, ob der Schlüssel ein Diktat enthält, und diese dann abrufen. Dies ist jedoch ein komplizierter Ansatz, obwohl Sie auf diese Weise Ihre Kenntnisse der Standardbibliothek nachweisen können.
  • Ich persönlich bin kein Fan von häufigem Code continue, und einige Styleguides verbieten oder empfehlen sie . Ich selbst habe in der ersten Ausgabe dieses Codes den Operator vergessen, continuenachdem ich die Länge der Anfrage überprüft hatte. Dies ist kein schlechter Ansatz, wissen Sie nur, dass es fehleranfällig ist.

Teil 2: Es wird schwieriger!


Gute Kandidaten haben noch zehn bis fünfzehn Minuten Zeit, nachdem sie das Problem gelöst haben. Glücklicherweise gibt es viele zusätzliche Fragen, obwohl es unwahrscheinlich ist, dass wir in dieser Zeit viel Code schreiben. Dies ist jedoch nicht erforderlich. Ich möchte über den Kandidaten zwei Dinge wissen: Kann er Algorithmen entwickeln und kann er kodieren? Die Aufgabe mit dem Springerzug beantwortet zuerst die Frage nach der Entwicklung des Algorithmus und prüft dann die Codierung. Hier erhalten wir die Antworten in umgekehrter Reihenfolge.

Als der Kandidat den ersten Teil der Frage abschloss, hatte er das Problem bereits mit (überraschend nicht trivialer) Codierung gelöst. Zu diesem Zeitpunkt kann ich mit Zuversicht über seine Fähigkeit sprechen, rudimentäre Algorithmen zu entwickeln und Ideen in Code zu übersetzen, sowie über das Kennenlernen seiner Lieblingssprache und der Standardbibliothek. Jetzt wird das Gespräch viel interessanter, weil die Anforderungen an die Programmierung gemindert werden können und wir uns mit den Algorithmen befassen.

Kehren wir zu den Grundsätzen des ersten Teils zurück: Die Wortreihenfolge ist wichtig, Synonyme sind nicht-transitiv, und für jedes Wort können mehrere Synonyme vorhanden sein. Im weiteren Verlauf des Interviews ändere ich jede dieser Einschränkungen, und in dieser neuen Phase haben wir eine rein algorithmische Diskussion mit dem Kandidaten. Hier werde ich Beispiele für den Code geben, um meinen Standpunkt zu veranschaulichen, aber in einem realen Interview sprechen wir nur über Algorithmen.

Bevor Sie beginnen, werde ich meine Position erläutern: Alle nachfolgenden Aktionen in dieser Phase des Interviews sind hauptsächlich „Bonuspunkte“. Mein persönlicher Ansatz ist es, Kandidaten zu identifizieren, die die erste Stufe genau bestehen und für die Arbeit geeignet sind. Die zweite Stufe wird benötigt, um das Beste hervorzuheben. Die erste Bewertung ist bereits sehr gut und bedeutet, dass der Kandidat für das Unternehmen gut genug ist, und die zweite Bewertung besagt, dass der Kandidat ausgezeichnet ist und seine Einstellung für uns ein großer Sieg sein wird.

Transitivität: naive Ansätze


Zunächst möchte ich die Einschränkung der Transitivität aufheben. Wenn also die Synonyme die Paare A - B und B - C sind, dann sind die Wörter A und C auch Synonyme. Intelligente Kandidaten werden schnell verstehen, wie sie ihre vorherige Lösung anpassen können, obwohl die grundlegende Logik des Algorithmus nicht mehr funktioniert, wenn andere Einschränkungen weiter beseitigt werden.

Aber wie passt man es an? Ein gängiger Ansatz besteht darin, für jedes Wort einen vollständigen Satz von Synonymen auf der Grundlage transitiver Beziehungen zu führen. Jedes Mal, wenn wir ein Wort in eine Gruppe von Synonymen einfügen, fügen wir es den entsprechenden Gruppen für alle Wörter in dieser Gruppe hinzu:

synonyms = defaultdict(set)
for w1, w2 in synonym_words:
    for w in synonyms[w1]:
        synonyms[w].add(w2)
    synonyms[w1].add(w2)
    for w in synonyms[w2]:
        synonyms[w].add(w1)
    synonyms[w2].add(w1)

Bitte beachten Sie, dass wir uns beim Erstellen des Codes bereits eingehend mit dieser Lösung befasst haben.

Diese Lösung funktioniert, ist jedoch bei weitem nicht optimal. Um die Gründe zu verstehen, lassen Sie uns die räumliche Komplexität dieser Lösung abschätzen. Jedes Synonym muss nicht nur zum Satz des Anfangsworts, sondern auch zu den Sätzen aller seiner Synonyme hinzugefügt werden. Wenn das Synonym eins ist, wird ein Eintrag hinzugefügt. Wenn wir jedoch 50 Synonyme haben, müssen wir 50 Einträge hinzufügen. In der Abbildung sieht es so aus:



Beachten Sie, dass wir von drei Schlüsseln und sechs Datensätzen zu vier Schlüsseln und zwölf Datensätzen gewechselt haben. Für ein Wort mit 50 Synonymen sind 50 Schlüssel und fast 2500 Einträge erforderlich. Der für die Darstellung eines einzelnen Wortes erforderliche Platz wächst quadratisch mit einer Zunahme der Menge von Synonymen, was ziemlich verschwenderisch ist.

Es gibt andere Lösungen, aber ich werde nicht zu tief gehen, um den Artikel nicht aufzublasen. Am interessantesten ist die Verwendung der Synonymdatenstruktur zum Erstellen eines gerichteten Graphen und dann eine umfassende Suche, um den Pfad zwischen zwei Wörtern zu finden. Dies ist eine hervorragende Lösung, aber die Suche wird in der Größe der Synonymmenge für das Wort linear. Da wir diese Suche für jede Abfrage mehrmals durchführen, ist dieser Ansatz nicht optimal.

Transitivität: die Verwendung von disjunkten Mengen


Es stellt sich heraus, dass die Suche nach Synonymen dank einer Datenstruktur, die als disjunkte Mengen bezeichnet wird, in (fast) konstanter Zeit möglich ist. Diese Struktur bietet etwas andere Möglichkeiten als ein regulärer Datensatz (Set).

Eine reguläre Mengenstruktur (Hashset, TreeSet) ist ein Container, mit dem Sie schnell feststellen können, ob sich ein Objekt innerhalb oder außerhalb davon befindet. Nicht überlappende Mengen lösen ein völlig anderes Problem: Anstatt ein bestimmtes Element zu definieren, kann mit ihnen festgestellt werden, ob zwei Elemente zur gleichen Menge gehören . Darüber hinaus schafft es die Struktur in einer blitzschnellen Zeit O(a(n)), woa(n)- die Umkehrfunktion von Ackermann. Wenn Sie keine fortgeschrittenen Algorithmen studiert haben, kennen Sie möglicherweise diese Funktion nicht, die für alle sinnvollen Eingaben tatsächlich in konstanter Zeit ausgeführt wird.

Auf einer hohen Ebene arbeitet der Algorithmus wie folgt. Mengen werden durch Bäume mit übergeordneten Elementen für jedes Element dargestellt. Da jeder Baum eine Wurzel hat (ein Element, das selbst ein übergeordnetes Element ist), können wir feststellen, ob zwei Elemente zur gleichen Menge gehören, indem wir ihre übergeordneten Elemente zur Wurzel zurückverfolgen. Wenn zwei Elemente eine Wurzel haben, gehören sie zur gleichen Menge. Das Kombinieren von Mengen ist ebenfalls einfach: Finden Sie einfach die Wurzelelemente und machen Sie eines davon zur Wurzel des anderen.

So weit so gut, aber noch nicht blendende Geschwindigkeit gesehen. Das Genie dieser Struktur liegt in einem Verfahren, das als Komprimierung bezeichnet wird. Angenommen, Sie haben den folgenden Baum:



Stellen Sie sich vor, Sie möchten herausfinden, ob die Wörter speedy und hasty synonym sind . Folge den Eltern eines jeden und finde die gleiche schnelle Wurzel . Nehmen wir nun an, wir führen einen ähnlichen Test für die Wörter speedy und swift durch . Wieder steigen wir zur Wurzel auf, und von speedy gehen wir den gleichen Weg. Kann Doppelarbeit vermieden werden?

Es stellt sich heraus, dass Sie können. In gewisser Weise ist jedes Element in diesem Baum dazu bestimmt, zu fasten . Anstatt jedes Mal den ganzen Baum zu durchlaufen, sollten Sie die Eltern für alle Nachkommen von fast ändernden Weg zur Wurzel verkürzen? Dieser Vorgang wird als Komprimierung bezeichnet und ist in sich nicht überschneidenden Mengen in die Stammsuchoperation eingebettet. Beispielsweise wird die Struktur nach der ersten Operation im Vergleich zu schnell und hastig verstehen, dass sie synonym ist, und den Baum wie folgt komprimieren:


Für alle Wörter zwischen speedy und fast wurde das übergeordnete

Element aktualisiert, dasselbe geschah mit hasty. Jetzt werden alle nachfolgenden Aufrufe in konstanter Zeit ausgeführt, da jeder Knoten in diesem Baum fast angibt. Es ist nicht sehr einfach, die zeitliche Komplexität von Vorgängen zu beurteilen: Sie ist in der Tat nicht konstant, da sie von der Tiefe der Bäume abhängt, sondern nahezu konstant, da die Struktur schnell optimiert wird. Der Einfachheit halber nehmen wir an, dass die Zeit konstant ist.

Mit diesem Konzept implementieren wir unabhängige Mengen für unser Problem:

class DisjointSet(object):
    def __init__(self):
        self.parents = {}
    def get_root(self, w):
        words_traversed = []
        while self.parents[w] != w:
            words_traversed.append(w)
            w = self.parents[w]
        for word in words_traversed:
            self.parents[word] = w
        return w
    def add_synonyms(self, w1, w2):
        if w1 not in self.parents:
            self.parents[w1] = w1
        if w2 not in self.parents:
            self.parents[w2] = w2
        w1_root = self.get_root(w1)
        w2_root = self.get_root(w2)
        if w1_root < w2_root:
            w1_root, w2_root = w2_root, w1_root
        self.parents[w2_root] = w1_root
    def are_synonymous(self, w1, w2):
        return self.get_root(w1) == self.get_root(w2)

Mit dieser Struktur können Sie Synonyme vorverarbeiten und das Problem in linearer Zeit lösen.

Bewertung und Hinweise


Zu diesem Zeitpunkt haben wir die Grenze dessen erreicht, was der Kandidat in 40 bis 45 Minuten eines Interviews zeigen kann. Für alle Kandidaten, die den einleitenden Teil gemeistert und bedeutende Fortschritte bei der Beschreibung (nicht Implementierung) nicht verwandter Sets erzielt haben, habe ich die Bewertung „Es wird dringend empfohlen, Mitarbeiter einzustellen“ vergeben und ihnen gestattet, Fragen zu stellen. Ich habe noch nie einen Kandidaten gesehen, der so weit gegangen ist und noch viel Zeit hat.

Grundsätzlich gibt es immer noch Varianten des Problems der Transitivität: Entfernen Sie beispielsweise die Einschränkung der Wortreihenfolge oder mehrerer Synonyme für ein Wort. Jede Entscheidung wird schwierig und erfreulich sein, aber ich werde sie für später aufheben.

Der Vorteil dieser Aufgabe ist, dass die Kandidaten Fehler machen können. Die tägliche Softwareentwicklung besteht aus endlosen Zyklen von Analyse, Ausführung und Verfeinerung. Dieses Problem ermöglicht es den Kandidaten, in jeder Phase ihre Fähigkeiten unter Beweis zu stellen. Berücksichtigen Sie die Fähigkeiten, die erforderlich sind, um die maximale Punktzahl für dieses Problem zu erzielen:

  • Analysieren Sie die Formulierung des Problems und stellen Sie fest, wo es nicht klar formuliert ist. Entwickeln Sie eine eindeutige Formulierung. Fahren Sie damit fort, wenn neue Probleme behoben sind. Um eine maximale Effizienz zu erzielen, führen Sie diese Vorgänge so früh wie möglich aus, da die Behebung des Fehlers umso länger dauert, je weiter die Arbeit zurückliegt.
  • Formulieren Sie das Problem so, dass es einfacher zu lösen und anzugehen ist. In unserem Fall ist die Beobachtung am wichtigsten, dass die entsprechenden Wörter in den Abfragen relativ zueinander ausgerichtet sind.
  • Setzen Sie Ihre Entscheidung um . Dies beinhaltet die Auswahl der optimalen Datenstruktur und Algorithmen sowie das Entwerfen einer Logik, die in Zukunft lesbar und leicht änderbar ist.
  • Gehen Sie zurück und versuchen Sie, Fehler und Fehler zu finden . Dies können tatsächliche Fehler sein, da ich vergessen habe, die continueobige Anweisung einzufügen , oder Leistungsfehler, wie die Verwendung der falschen Datenstruktur.
  • Wenn sich die Definition eines Problems ändert, wiederholen Sie den gesamten Vorgang: Passen Sie Ihre Lösung bei Bedarf an , oder verwerfen Sie sie, wenn sie nicht passt. Das Verstehen, wann die eine oder andere Sache zu tun ist, ist sowohl im Interview als auch in der realen Welt eine entscheidende Fähigkeit.
  • Beherrsche die Datenstrukturen und Algorithmen . Sich nicht überschneidende Mengen sind keine sehr bekannte Struktur, aber in der Tat nicht so selten und raffiniert. Der einzige Weg, um das Wissen über die Werkzeuge für den Job zu gewährleisten - um so viel wie möglich zu lernen.

Keine dieser Fähigkeiten kann aus Lehrbüchern gelernt werden (mit der möglichen Ausnahme von Datenstrukturen und Algorithmen). Der einzige Weg, diese zu erwerben, ist ihre regelmäßige und umfassende Praxis, die gut mit den Bedürfnissen des Arbeitgebers übereinstimmt: erfahrene Kandidaten, die in der Lage sind, ihr Wissen effektiv anzuwenden. Die Bedeutung von Interviews ist es, solche Leute zu finden, und die Aufgabe aus diesem Artikel hat mir lange geholfen.

Pläne für die Zukunft


Wie Sie verstehen konnten, wurde die Aufgabe schließlich der Öffentlichkeit bekannt . Seitdem habe ich verschiedene andere Fragen gestellt, je nachdem, was von früheren Interviewern und je nach Stimmung gestellt wurde (es ist langweilig, die ganze Zeit eine Frage zu stellen). Ich benutze noch einige Fragen, damit ich sie geheim halte, aber nicht einige! Sie können sie in den folgenden Artikeln lernen.

In naher Zukunft plane ich zwei Artikel. Zunächst erkläre ich, wie oben versprochen, die Lösung der beiden verbleibenden Probleme für dieses Problem. Ich habe sie nie bei Interviews gefragt, aber sie sind an sich interessant. Außerdem werde ich meine Gedanken und persönlichen Ansichten zum Verfahren zur Suche nach Mitarbeitern in der IT mitteilen, die mich jetzt besonders interessieren, da ich Ingenieure für mein Team in Reddit suche.

Wenn Sie mehr über neue Artikel erfahren möchten, folgen Sie mir wie immer auf Twitter oder auf Medium . Wenn Ihnen dieser Artikel gefallen hat, vergessen Sie nicht, dafür zu stimmen oder einen Kommentar abzugeben.

Danke fürs Lesen!

P. S:. Sie können den Code aller Artikel in untersuchen Repository GitHub oder mit ihnen live spielen dank meiner guten Freunde von repl.it .