de Anthony Sistilli

Ghid de întrebări pentru interviul Google: ștergeți caracterele recurente cu Python

Ghid de intrebari pentru interviul Google stergeti caracterele recurente cu
Fotografie de Tim Gouw de la Pexels

În zilele noastre, interviurile Google sunt la modă. Dar, uneori, interviurile ne pot obține tot ce este mai bun. Mai ales dacă este pentru o poziție pe care noi într-adevăr vrei.

Am avut plăcerea să intervievez la mai multe companii de top ca student și să obțin un loc de muncă în Silicon Valley ca inginer software.

Scopul meu este să ajut tu obține acel loc de muncă de vis pe care ți l-ai dorit dintotdeauna!

Vom trece peste o întrebare clasică care ar putea apărea la următorul dvs. interviu Google.

Atenție: dacă sunteți un veteran în codificare, probabil că știți deja cum să rezolvați această întrebare!

Dacă încerci să obții un Stagiu sau a Cu normă întreagă loc de muncă anul viitor, atunci veți beneficia cu siguranță de acest articol. ???

ÎNTREBARE: Având în vedere un șir ca intrare, ștergeți orice caracter recurent și returnați noul șir.

Dacă preferați un videoclip pentru a explica întrebarea, Am făcut una aici.

Ghid de intrebari pentru interviul Google stergeti caracterele recurente cu

După cum putem vedea din exemplul de mai sus, ieșirea este „abc” deoarece ștergem al doilea „a”, „b” și „c”.

În primul rând, să ne configurăm funcția în Python 2.7.

def deleteReoccurringCharacters(string):

Pentru a aborda această întrebare, vom folosi o structură de date specifică numită HashSet.

1612153568 652 Ghid de intrebari pentru interviul Google stergeti caracterele recurente cu
Un set

Vă puteți gândi la un set ca fiind similar cu un tablou, cu două excepții principale.

  1. Este complet neordonat
  2. Nu poate conține duplicate

Deoarece este neordonat, vom avea nevoie și de un șir gol pentru a stoca în ordine caracterele pe care le-am adăugat la set. Acesta va fi șirul pe care îl returnăm.

Să stabilim ambele lucruri.

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

Acum că am configurat structurile de date de care avem nevoie, să vorbim despre algoritmul nostru.

Datorită modului în care un set funcționează în memorie, are o complexitate de timp de căutare de 0 (1).

Aceasta înseamnă că îl putem folosi pentru a verifica dacă am vizitat deja un personaj sau nu!

Algoritmul nostru

Buclați toate caracterele din șirul inițial și efectuați următoarele:

Pasul 1: verificați dacă personajul se află deja în setul nostru

Pasul 2: dacă nu este în set, adăugați-l la set și adăugați-l la șir

Să vedem cum ar arăta asta în cod ???

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

Nu trebuie să ne facem griji cu privire la un caz „altceva”, pentru că nu facem nimic cu personajul recurent în sine.

Acum nu mai rămâne decât să returnăm outputString.

Iată cum arată codul finalizat:

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

Și iată-l!

Acum, dacă acesta ar fi un interviu, recrutorul tău te-ar întreba despre complexitatea timpului și spațiului.

Să facem o mică analiză.

Complexitatea timpului

Iterarea prin întregul șir de intrare are o complexitate de timp de O (n), deoarece există n caractere din șirul în sine.

Pentru fiecare dintre aceste caractere, trebuie să verificăm dacă am văzut sau nu … Cu toate acestea, deoarece un HashSet are un timp de căutare de O (1), complexitatea noastră de timp nu este afectată.

Lăsându-ne cu o complexitate temporală finală de Pe).

Complexitatea spațială

În cel mai rău caz, obținem un șir cu toate caracterele unice. De exemplu, „abcdef”.

În acest caz, am depozita toate n elemente din șirul nostru și setul nostru.

Cu toate acestea, suntem limitați și la dimensiunea alfabetului englezesc.

Aceasta este o șansă bună de a întreba intervievatorul nostru ce tip de caractere se consideră unic în șir (majuscule / minuscule / numere / simboluri).

Presupunând că șirul inițial va conține litere mici din alfabet, deoarece alfabetul este finit, șirul nostru de setare și ieșire nu poate fi niciodată mai mare de 26 de caractere.

Lăsându-ne un scenariu cel mai rău complexitatea spațiului O (1).

Acum știți cum să rezolvați o întrebare de interviu Google!

Probabil că această întrebare va apărea în primele etape ale interviului, datorită simplității sale … La fel ca testul online sau primul apel telefonic.

Dacă ești un elev vizual ca mine, vezi acest videoclip pe care l-am făcut explicând soluția în continuare. Creez zilnic un nou video tutorial care se învârte în jurul începutului carierei tale în software.

Am postat și codul terminat pe Github Aici.

Vă mulțumim pentru vizionare și mult succes!

.a # 33