Vejledningsvejledning til Google Interview: Slet tilbagevendende tegn med Python

I dag er Google-interviews alle raseri. Men nogle gange kan interviews få det bedste ud af os. Især hvis det er til en stilling, vi virkelig ønsker.

Jeg har haft fornøjelsen af ​​at interviewe hos flere topfirmaer som studerende og lande et job i Silicon Valley som softwareingeniør.

Mit mål er at hjælpe dig med at få det drømmejob, du altid har ønsket!

Vi vil gennemgå et klassisk spørgsmål, der kan vises i dit næste Google Interview.

Advarsel: hvis du er en kodningsveteran, ved du sandsynligvis allerede, hvordan man løser dette spørgsmål!

Hvis du prøver at få et praktikophold eller et fuldtidsjob næste år, så vil du helt sikkert drage fordel af denne artikel. ???

SPØRGSMÅL: Givet en streng som din input, skal du slette ethvert tilbagevendende tegn og returnere den nye streng.

Hvis du foretrækker en video til forklaring af spørgsmålet, lavede jeg en her.

Som vi kan se fra eksemplet ovenfor, er output “abc”, fordi vi sletter det andet 'a', 'b' og 'c'.

Første ting først, lad os opsætte vores funktion i Python 2.7.

def deleteReoccurringCharacters(string):

For at tackle dette spørgsmål skal vi bruge en bestemt datastruktur kaldet HashSet.

Du kan tænke på et sæt som ligner et array med to hovedundtagelser.

  1. Det er helt uordnet
  2. Det kan ikke indeholde dubletter

Da det ikke er ordnet, skal vi også bruge en tom streng for at gemme de tegn, vi har tilføjet til sættet i rækkefølge. Dette er den streng, vi returnerer.

Lad os sætte begge disse ting op.

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

Nu hvor vi har oprettet de datastrukturer, vi har brug for, lad os tale om vores algoritme.

På grund af den måde, hvorpå et sæt fungerer i hukommelsen, har det en opsøgningstidskompleksitet på 0 (1).

Dette betyder, at vi kan bruge det til at kontrollere, om vi allerede har besøgt et tegn!

Vores algoritme

Gennemse alle tegnene i den indledende streng, og gør følgende:

Trin 1: Kontroller, om tegnet allerede er i vores sæt Trin 2: Hvis det ikke er i sættet, skal du tilføje det til sættet og føje det til strengen

Lad os se, hvordan det ville se ud i kode ???

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

Vi behøver ikke bekymre os om en ”anden” sag, fordi vi ikke gør noget med selve den tilbagevendende karakter.

Nu er alt, hvad der er tilbage at gøre, at returnere outputString.

Sådan ser den færdige kode ud:

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

Og der har du det!

Hvis dette nu var et interview, ville din rekrutter spørge dig om tid og rumkompleksitet.

Lad os lave en lille analyse.

Tidskompleksitet

Iterering gennem hele inputstrengen har en tidskompleksitet på O (n), da der er n tegn i selve strengen.

For hver af disse tegn skal vi kontrollere, om vi har set ... Men da et HashSet har en opslagstid på O (1), påvirkes vores tidskompleksitet ikke.

Efterlader os med den endelige tidskompleksitet af O (n).

Rumkompleksitet

I værste fald får vi en streng med alle unikke tegn. For eksempel “abcdef”.

I så fald gemmer vi alle n- elementer i vores streng og vores sæt.

Vi er dog også begrænset til størrelsen på det engelske alfabet.

Dette er en god chance for at spørge vores interviewer, hvilken type tegn der tæller som unikke i strengen (store / små / tal / symboler).

Hvis vi antager, at den indledende streng indeholder små bogstaver fra alfabetet, da alfabetet er endeligt, kan vores sæt- og outputstreng aldrig være større end 26 tegn.

Efterlader os med et worst case scenario O- kompleksitet (1).

Du ved nu, hvordan du løser et spørgsmål om Google-interview!

Dette spørgsmål vil sandsynligvis komme op i de tidlige faser af interviewet på grund af det ligefremhed ... Som online-testen eller det første telefonopkald.

Hvis du er en visuel elev, som jeg er, så tjek denne video, jeg lavede, og forklar løsningen yderligere. Jeg opretter en ny tutorial-video hver dag, der drejer sig om at starte din karriere inden for software.

Jeg har også sendt den færdige kode på Github her.

Tak for at se, og held og lykke!

.a # 33