Google Interview Question Guide: Löschen Sie wiederkehrende Zeichen mit Python

Heutzutage sind Google-Interviews der letzte Schrei. Aber manchmal können Interviews das Beste aus uns herausholen. Besonders wenn es um eine Position geht, die wir wirklich wollen.

Ich hatte das Vergnügen, als Student bei mehreren Top-Unternehmen zu interviewen und einen Job als Software Engineer im Silicon Valley zu bekommen.

Mein Ziel ist es, Ihnen zu helfen , den Traumjob zu bekommen, den Sie sich immer gewünscht haben!

Wir werden eine klassische Frage durchgehen, die in Ihrem nächsten Google-Interview auftauchen könnte.

Warnung: Wenn Sie ein Veteran der Codierung sind, wissen Sie wahrscheinlich bereits, wie Sie diese Frage lösen können!

Wenn Sie nächstes Jahr versuchen, ein Praktikum oder einen Vollzeitjob zu bekommen , werden Sie definitiv von diesem Artikel profitieren. ???

FRAGE: Wenn Sie eine Zeichenfolge als Eingabe angegeben haben, löschen Sie alle wiederkehrenden Zeichen und geben Sie die neue Zeichenfolge zurück.

Wenn Sie ein Video bevorzugen, um die Frage zu erklären, habe ich hier eines gemacht.

Wie wir aus dem obigen Beispiel sehen können, ist die Ausgabe "abc", da wir die zweiten 'a', 'b' und 'c' löschen.

Lassen Sie uns zuerst unsere Funktion in Python 2.7 einrichten.

def deleteReoccurringCharacters(string):

Um diese Frage zu beantworten, verwenden wir eine bestimmte Datenstruktur namens HashSet.

Sie können sich eine Menge mit zwei Hauptausnahmen als ähnlich wie ein Array vorstellen.

  1. Es ist völlig ungeordnet
  2. Es darf keine Duplikate enthalten

Da es ungeordnet ist, benötigen wir auch eine leere Zeichenfolge, um die Zeichen, die wir dem Satz hinzugefügt haben, in der richtigen Reihenfolge zu speichern. Dies ist die Zeichenfolge, die wir zurückgeben.

Lassen Sie uns beide Dinge einrichten.

def deleteReoccurringCharacters(string): seenCharacters = set() outputString = ''

Nachdem wir die benötigten Datenstrukturen eingerichtet haben, sprechen wir über unseren Algorithmus.

Aufgrund der Funktionsweise eines Satzes im Speicher hat er eine Komplexität der Suchzeit von 0 (1).

Dies bedeutet, dass wir damit überprüfen können, ob wir bereits einen Charakter besucht haben oder nicht!

Unser Algorithmus

Durchlaufen Sie alle Zeichen in der Anfangszeichenfolge und gehen Sie wie folgt vor:

Schritt 1: Überprüfen Sie, ob sich das Zeichen bereits in unserem Set befindet. Schritt 2: Wenn es nicht im Set enthalten ist, fügen Sie es dem Set hinzu und hängen Sie es an die Zeichenfolge an

Mal sehen, wie das im Code aussehen würde ???

for char in string: if char not in seenCharacters: seenCharacters.add(char) outputString += char

Wir müssen uns keine Sorgen um einen „anderen“ Fall machen, weil wir mit dem wiederkehrenden Charakter selbst nichts anfangen.

Jetzt müssen Sie nur noch den outputString zurückgeben.

So sieht der fertige Code aus:

def deleteReoccurringCharacters(string): seenCharacters = set() outputString = '' for char in string: if char not in seenCharacters: seenCharacters.add(char) outputString += char return outputString

Und da hast du es!

Wenn dies ein Interview wäre, würde Ihr Personalvermittler Sie nach der zeitlichen und räumlichen Komplexität fragen.

Lassen Sie uns eine kleine Analyse machen.

Zeitliche Komplexität

Das Durchlaufen der gesamten Eingabezeichenfolge hat eine zeitliche Komplexität von O (n), da die Zeichenfolge selbst n Zeichen enthält.

Für jedes dieser Zeichen müssen wir prüfen, ob wir das gesehen haben oder nicht. Da ein HashSet jedoch eine Suchzeit von O (1) hat, wird unsere Zeitkomplexität nicht beeinflusst.

Wir haben eine endgültige zeitliche Komplexität von O (n).

Raumkomplexität

Im schlimmsten Fall erhalten wir eine Zeichenfolge mit allen eindeutigen Zeichen. Zum Beispiel "abcdef".

In diesem Fall würden wir alle n Elemente in unserer Zeichenfolge und unserer Menge speichern .

Wir sind jedoch auch auf die Größe des englischen Alphabets beschränkt.

Dies ist eine gute Gelegenheit, unseren Interviewer zu fragen, welche Art von Zeichen in der Zeichenfolge als eindeutig gelten (Groß- / Kleinbuchstaben / Zahlen / Symbole).

Unter der Annahme, dass die Anfangszeichenfolge Kleinbuchstaben aus dem Alphabet enthält, kann unsere Set- und Ausgabezeichenfolge niemals größer als 26 Zeichen sein, da das Alphabet endlich ist.

Wir haben eine Worst-Case-Szenario-Raumkomplexität von O (1).

Sie wissen jetzt, wie Sie eine Google-Interviewfrage lösen können!

Diese Frage wird wahrscheinlich zu Beginn des Interviews gestellt, da sie unkompliziert ist. Wie der Online-Test oder der erste Anruf.

Wenn Sie wie ich visuell lernen, sehen Sie sich dieses Video an, in dem ich die Lösung näher erläutere. Ich erstelle jeden Tag ein neues Tutorial-Video, in dem es darum geht, Ihre Karriere in der Software zu beginnen.

Ich habe hier auch den fertigen Code auf Github gepostet.

Danke fürs Zuschauen und viel Glück!

.a # 33