Google interjúkkal kapcsolatos útmutató: Ismétlődő karakterek törlése a Python használatával

Manapság a Google-interjúk dühöngenek. De néha az interjúk a legjobbat hozhatják ki belőlünk. Különösen, ha egy olyan pozícióra vonatkozik, amelyet nagyon szeretnénk.

Örömömre szolgált, hogy hallgatóként több topcégnél interjút készítettem, és Szilícium-völgyben helyezkedtem el szoftvermérnökként.

A célom az, hogy segítsen neked , hogy ez az álom munka, amit mindig is szeretett volna!

Áttérünk egy klasszikus kérdésre, amely megjelenhet a következő Google-interjún.

Figyelem: ha kódoló veterán vagy, akkor valószínűleg már tudod, hogyan kell megoldani ezt a kérdést!

Ha jövőre szakmai gyakorlatot vagy teljes munkaidős munkát szeretne szerezni , akkor ez a cikk mindenképpen profitálni fog. ???

KÉRDÉS: Adjon meg egy karakterláncot bemenetként, töröljön minden ismétlődő karaktert, és adja vissza az új karakterláncot.

Ha inkább egy videóval szeretné megmagyarázni a kérdést, itt készítettem egyet.

Amint a fenti példából láthatjuk, a kimenet „abc”, mert töröljük a második „a”, „b” és „c” karaktert.

Először állítsuk be a függvényünket a Python 2.7-ben.

def deleteReoccurringCharacters(string):

A kérdés megválaszolásához egy speciális adatstruktúrát fogunk használni, az úgynevezett HashSet-et.

Úgy gondolhatja, hogy egy halmaz hasonló egy tömbhöz, két fő kivételtől eltekintve.

  1. Teljesen rendezetlen
  2. Nem tartalmazhat másolatokat

Mivel nem rendezett, szükségünk lesz egy üres karakterláncra is a készletbe felvett karakterek sorrendben történő tárolásához. Ez lesz az a karakterlánc, amelyet visszaadunk.

Állítsuk be mindkettőt.

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

Most, hogy beállítottuk a szükséges adatszerkezeteket, beszéljünk az algoritmusunkról.

A halmaz memóriában való működése miatt a keresési idő bonyolultsága 0 (1).

Ez azt jelenti, hogy ellenőrizhetjük, hogy meglátogattunk-e már egy karaktert!

Algoritmusunk

Hurkolja végig a kezdeti karakterlánc összes karakterét, és tegye a következőket:

1. lépés: Ellenőrizze, hogy a karakter már szerepel-e a készletünkben 2. lépés: Ha nem szerepel a készletben, adja hozzá a halmazhoz, és csatolja a karakterlánchoz

Lássuk, hogy nézne ki ez a kódban ???

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

Nem kell aggódnunk egy „más” eset miatt, mert magával az ismétlődő karakterrel nem teszünk semmit.

Most már csak az outputString visszaadása szükséges.

Így néz ki a kész kód:

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

És itt van!

Ha ez egy interjú volt, a toborzója megkérdezte Önt az idő és a tér összetettségéről.

Tegyünk egy kis elemzést.

Idő komplexitás

A teljes bemeneti karakterláncon keresztül történő iterálás időbeli összetettsége O (n), mivel magában a karakterláncban n karakter van.

Ezeknek a karaktereknek mindegyikénél ellenőriznünk kell, hogy láttuk-e a… Azonban, mivel egy HashSet keresési ideje O (1), időbeli összetettségünket ez nem befolyásolja.

Az O (n) végső időbeli bonyolultsága hagy minket .

Tér komplexitás

Legrosszabb esetben egy karakterláncot kapunk minden egyedi karakterrel. Például: „abcdef”.

Ebben az esetben mind az n elemet tároljuk a karakterláncunkban és a készletünkben.

Az angol ábécé méretére is korlátozódunk.

Ez jó esély arra, hogy megkérdezzük interjúztatónkat, hogy a karakterek milyen típusúnak számítanak egyedinek a karakterláncban (nagybetűk / kisbetűk / számok / szimbólumok).

Feltéve, hogy a kezdeti karakterlánc tartalmazni fogja az ábécé kisbetűit, mivel az ábécé véges, a beállított és a kimeneti karakterláncunk soha nem lehet nagyobb, mint 26 karakter.

A legrosszabb forgatókönyv szerint O (1) térbonyolultsága.

Most már tudja, hogyan oldja meg a Google interjúval kapcsolatos kérdéseket!

Ez a kérdés valószínűleg az interjú korai szakaszában fog felmerülni az egyszerűsége miatt ... Mint például az online teszt vagy az első telefonhívás.

Ha vizuális tanuló vagy, mint én, nézd meg ezt a videót, amelyet a megoldás további ismertetésével készítettem. Készítek egy mindennapos új oktatóvideót, amely a szoftveres karrier megkezdését járja körül.

I’ve also posted the finished code on Github here.

Thanks for watching, and good luck!

.a #33