„Google“ interviu klausimų vadovas: pašalinkite pasikartojančius simbolius naudodami „Python“

Šiais laikais labai pyksta „Google“ interviu. Tačiau kartais interviu gali mums padėti. Ypač jei tai yra vieta, kurios mes tikrai norime.

Man buvo malonu apklausti daugybę geriausių bendrovių kaip studentas ir įsidarbinti Silicio slėnyje kaip programinės įrangos inžinierius.

Mano tikslas yra padėti jums gauti tą svajonių darbą, kurio visada norėjote!

Peržiūrėsime klasikinį klausimą, kuris galėtų pasirodyti kitame jūsų „Google“ interviu.

Įspėjimas: jei esate kodavimo veteranas, tikriausiai jau žinote, kaip išspręsti šį klausimą!

Jei kitais metais bandote įgyti praktikos ar visą darbo dieną, šis straipsnis jums tikrai pravers. ???

KLAUSIMAS: Įveskite eilutę kaip įvestį, ištrinkite visus pasikartojančius simbolius ir grąžinkite naują eilutę.

Jei norėtumėte, kad vaizdo įrašas paaiškintų klausimą, aš jį padariau čia.

Kaip matome iš aukščiau pateikto pavyzdžio, išvestis yra „abc“, nes mes ištriname antruosius „a“, „b“ ir „c“.

Pirmiausia nustatykime savo funkciją „Python 2.7“.

def deleteReoccurringCharacters(string):

Norėdami išspręsti šį klausimą, mes naudosime specialią duomenų struktūrą, vadinamą „HashSet“.

Galite manyti, kad rinkinys yra panašus į masyvą, išskyrus dvi pagrindines išimtis.

  1. Tai visiškai nesutvarkyta
  2. Joje negali būti dublikatų

Kadangi jis nėra sutvarkytas, mums taip pat reikės tuščios eilutės, kad būtų galima tvarkyti simbolius, kuriuos pridėjome prie rinkinio. Tai bus eilutė, kurią mes grąžinsime.

Nustatykime abu tuos dalykus.

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

Dabar, sukūrę mums reikalingas duomenų struktūras, pakalbėkime apie savo algoritmą.

Dėl rinkinio veikimo atmintyje jo paieškos laiko sudėtingumas yra 0 (1).

Tai reiškia, kad galime jį naudoti norėdami patikrinti, ar jau aplankėme personažą!

Mūsų algoritmas

Peržiūrėkite visus pradinės eilutės simbolius ir atlikite šiuos veiksmus:

1 veiksmas: patikrinkite, ar simbolis jau yra mūsų rinkinyje 2 žingsnis: jei jo nėra rinkinyje, pridėkite jį prie rinkinio ir pridėkite jį prie eilutės

Pažiūrėkime, kaip tai atrodytų kode ???

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

Mums nereikia jaudintis dėl „kitokio“ atvejo, nes nieko nedarome su pačiu pasikartojančiu personažu.

Dabar belieka grąžinti „outputString“.

Štai kaip baigtas kodas atrodo:

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

Ir jūs turite tai!

Jei tai buvo interviu, jūsų verbuotojas paklaus jūsų apie laiko ir erdvės sudėtingumą.

Atlikime nedidelę analizę.

Laiko kompleksiškumas

Kartojant visą įvesties eilutę, laiko sudėtingumas yra O (n), nes pačioje eilutėje yra n simbolių.

Kiekvienam iš šių simbolių turime patikrinti, ar mes matėme… Tačiau, kadangi „HashSet“ paieškos laikas yra O (1), tai neturi įtakos mūsų laiko sudėtingumui.

Paliekant mums galutinį laiko O (n) sudėtingumą .

Erdvės sudėtingumas

Blogiausiu atveju gauname eilutę su visais unikaliais simboliais. Pavyzdžiui, „abcdef“.

Tokiu atveju mes išsaugotume visus n elementus savo eilutėje ir rinkinyje.

Tačiau mes taip pat apsiribojame angliškos abėcėlės dydžiu.

Tai gera proga paklausti mūsų pašnekovo, kokio tipo simboliai yra unikalūs eilutėje (didžiosios / mažosios / skaičiai / simboliai).

Darant prielaidą, kad pradinėje eilutėje bus mažosios raidės iš abėcėlės, kadangi abėcėlė yra baigtinė, mūsų rinkinio ir išvesties eilutė niekada negali būti didesnė nei 26 simboliai.

Palikus mums blogiausio scenarijaus scenarijų kosminis O (1).

Dabar jūs žinote, kaip išspręsti „Google“ interviu klausimą!

Šis klausimas greičiausiai iškils ankstyvose interviu stadijose dėl jo tiesmukiškumo ... Kaip internetinis testas ar pirmasis telefono skambutis.

Jei esate vizualiai besimokantis kaip aš, peržiūrėkite šį mano sukurtą vaizdo įrašą, kuriame paaiškinau sprendimą toliau. Aš sukuriu naują mokomąjį vaizdo įrašą, kuris kasdien sukasi apie jūsų karjeros pradžią programinės įrangos srityje.

Aš taip pat čia paskelbiau gatavą kodą „Github“.

Ačiū, kad žiūrėjote, ir linkime sėkmės!

.a # 33