Vrhunske strukture podataka koje biste trebali znati za sljedeći intervju za kodiranje

Niklaus Wirth, švicarski informatičar, 1976. godine napisao je knjigu pod nazivom Algoritmi + strukture podataka = programi.

40+ godina kasnije, ta jednadžba i dalje vrijedi. Zbog toga kandidati za softverski inženjering moraju pokazati svoje razumijevanje struktura podataka zajedno sa svojim aplikacijama.

Gotovo svi problemi zahtijevaju od kandidata da pokaže duboko razumijevanje struktura podataka. Nije važno jeste li upravo diplomirali (sveučilište ili kodirajući bootcamp) ili imate desetljeća iskustva.

Ponekad se u pitanjima iz intervjua izričito spominje struktura podataka, na primjer, „dato binarno stablo“. Ponekad je to implicitno, poput "želimo pratiti broj knjiga povezanih sa svakim autorom."

Učenje struktura podataka neophodno je čak i ako samo pokušavate poboljšati svoj trenutni posao. Krenimo s razumijevanjem osnova.

Što je struktura podataka?

Jednostavno rečeno, struktura podataka je spremnik koji pohranjuje podatke u određenom rasporedu. Ovaj "raspored" omogućuje da struktura podataka bude učinkovita u nekim operacijama, a neučinkovita u drugima. Vaš je cilj razumjeti podatkovne strukture kako biste mogli odabrati strukturu podataka koja je najoptimalnija za trenutni problem.

Zašto su nam potrebne strukture podataka?

Budući da se podatkovne strukture koriste za pohranu podataka u organiziranom obliku, a budući da su podaci najvažniji entitet u računalnoj znanosti, stvarna vrijednost podatkovnih struktura je jasna.

Bez obzira na problem koji rješavate, na ovaj ili onaj način morate se nositi s podacima - bilo da se radi o plaći zaposlenika, cijenama dionica, popisu namirnica ili čak jednostavnom telefonskom imeniku.

Na temelju različitih scenarija, podatke treba pohraniti u određenom formatu. Imamo pregršt struktura podataka koje pokrivaju našu potrebu za pohranom podataka u različitim formatima.

Uobičajene strukture podataka

Prvo navedimo najčešće korištene strukture podataka, a zatim ćemo ih pokriti jednu po jednu:

  1. Nizovi
  2. Stogovi
  3. Redovi
  4. Povezani popisi
  5. Drveće
  6. Grafikoni
  7. Pokušava (zapravo su drveće, ali svejedno ih je dobro pozvati odvojeno).
  8. Hash tablice

Nizovi

Niz je najjednostavnija i najčešće korištena struktura podataka. Druge strukture podataka poput stogova i redova izvode se iz nizova.

Evo slike jednostavnog niza veličine 4, koji sadrži elemente (1, 2, 3 i 4).

Svakom elementu podataka dodjeljuje se pozitivna numerička vrijednost koja se naziva Indeks , a koja odgovara položaju te stavke u polju. Većina jezika početni indeks niza definira kao 0.

Slijede dvije vrste nizova:

  • Jednodimenzionalni nizovi (kao što je prikazano gore)
  • Višedimenzionalni nizovi (nizovi unutar polja)

Osnovne operacije na nizovima

  • Umetni - umetne element s danim indeksom
  • Get - Vraća element prema zadanom indeksu
  • Delete - briše element u zadanom indeksu
  • Veličina - Dobiva ukupan broj elemenata u polju

Često postavljana pitanja za intervju za Array

  • Pronađite drugi minimalni element niza
  • Prve cjeline koje se ne ponavljaju u nizu
  • Spoji dva razvrstana niza
  • Preuredite pozitivne i negativne vrijednosti u niz

Stogovi

Svima nam je poznata poznata opcija Poništi koja je prisutna u gotovo svakoj aplikaciji. Jeste li se ikad zapitali kako to djeluje? Ideja: prethodna stanja svog rada (koja su ograničena na određeni broj) pohranjujete u memoriju takvim redoslijedom da se posljednji pojavi prvi. To se ne može učiniti samo pomoću nizova. Tu vam Stack dobro dođe.

Primjer Stacka u stvarnom životu mogla bi biti hrpa knjiga smještena u okomitom redoslijedu. Da biste dobili knjigu koja je negdje u sredini, morat ćete ukloniti sve knjige postavljene na nju. Ovako funkcionira LIFO (Last In First Out) metoda.

Evo slike stoga koji sadrži tri podatkovna elementa (1, 2 i 3), gdje je 3 na vrhu i prvo će se ukloniti:

Osnovne operacije stoga:

  • Guranje - umeta element na vrh
  • Pop - Vraća gornji element nakon uklanjanja iz niza
  • isEmpty - Vraća true ako je stog prazan
  • Top - Vraća gornji element bez uklanjanja iz snopa

Uobičajena pitanja o intervjuu za Stack

  • Procijenite izraz postfiksa pomoću snopa
  • Poredaj vrijednosti u hrpi
  • Provjerite uravnotežene zagrade u izrazu

Redovi

Slično Stacku, Queue je još jedna linearna struktura podataka koja element pohranjuje u sekvencijalnom načinu. Jedina značajna razlika između Stacka i Queuea je u tome što umjesto LIFO metode Queue implementira FIFOmetoda, što je skraćenica od First in First Out.

Savršen stvarni primjer Queuea: red ljudi koji čekaju na blagajni. Ako dođe nova osoba, pridružit će se liniji s kraja, a ne od početka - a osoba koja stoji sprijeda prva će dobiti kartu i tako napustiti liniju.

Evo slike reda čekanja koji sadrži četiri podatkovna elementa (1, 2, 3 i 4), gdje je 1 na vrhu i prvo će biti uklonjen:

Osnovne operacije reda čekanja

  • Enqueue () - ubacuje element na kraj reda
  • Dequeue () - uklanja element s početka reda
  • isEmpty () - Vraća true ako je red prazan
  • Vrh () - Vraća prvi element reda

Često postavljana pitanja za razgovor u redu

  • Implementirajte stog pomoću reda
  • Obrni prvih k elemenata reda
  • Generirajte binarne brojeve od 1 do n pomoću reda

Povezani popis

Povezani popis je još jedna važna linearna struktura podataka koja u početku može izgledati slično nizovima, ali se razlikuje po dodjeli memorije, unutarnjoj strukturi i načinu na koji se provode osnovne operacije umetanja i brisanja.

Povezani popis je poput lanca čvorova, gdje svaki čvor sadrži informacije poput podataka i pokazivač na sljedeći čvor u lancu. Postoji pokazivač glave koji pokazuje na prvi element povezanog popisa, a ako je popis prazan, onda jednostavno pokazuje nulu ili ništa.

Povezani popisi koriste se za implementaciju datotečnih sustava, hash tablica i popisa susjednosti.

Evo vizualnog prikaza unutarnje strukture povezanog popisa:

Slijede vrste povezanih popisa:

  • Popis pojedinačno povezanih (jednosmjerni)
  • Popis dvostruko povezanih (dvosmjerni)

Osnovne operacije povezanog popisa:

  • InsertAtEnd - ubacuje zadani element na kraj povezanog popisa
  • InsertAtHead - ubacuje zadani element na početak / glavu povezanog popisa
  • Delete - briše zadani element s povezanog popisa
  • DeleteAtHead - briše prvi element povezanog popisa
  • Pretraživanje - daje zadani element s povezanog popisa
  • isEmpty - Vraća true ako je povezani popis prazan

Često postavljana pitanja o intervjuu na Povezanoj listi

  • Obrnite povezani popis
  • Otkrivanje petlje na povezanom popisu
  • Vrati N-i čvor s kraja na povezanom popisu
  • Uklonite duplikate sa povezanog popisa

Grafikoni

Grafikon je skup čvorova koji su međusobno povezani u obliku mreže. Čvorovi se nazivaju i vrhovima. Par (x, y) naziva se rub , što znači da vrh x je povezan s vrhom y . Rub može sadržavati težinu / cijenu, pokazujući koliko je troškova potrebno za prelazak iz vrha x u y .

Vrste grafikona:

  • Neusmjereni grafikon
  • Usmjereni grafikon

U programskom jeziku grafikoni se mogu predstaviti u dva oblika:

  • Matrica susjedstva
  • Popis susjedstva

Uobičajeni algoritmi za prelazak grafova:

  • Širina prvo pretraživanje
  • Dubina Prvo pretraživanje

Često postavljana pitanja za grafički intervju

  • Primijenite prvo pretraživanje širine i dubine
  • Provjerite je li graf stablo ili nije
  • Broji broj bridova u grafikonu
  • Pronađite najkraći put između dva vrha

Drveće

Stablo je hijerarhijska struktura podataka koja se sastoji od vrhova (čvorova) i bridova koji ih povezuju. Stabla su slična grafikonima, ali ključna točka koja razlikuje stablo od grafa je da u stablu ne može postojati ciklus.

Drveće se intenzivno koristi u umjetnoj inteligenciji i složenim algoritmima kako bi se osigurao učinkovit mehanizam pohrane za rješavanje problema.

Evo slike jednostavnog stabla i osnovnih terminologija koje se koriste u strukturi podataka stabla:

Slijede vrste drveća:

  • N-arno drvo
  • Uravnoteženo stablo
  • Binarno stablo
  • Binarno stablo pretraživanja
  • AVL stablo
  • Crno crno drvo
  • 2-3 stablo

Od navedenog, Binarno stablo i Binarno stablo pretraživanja najčešće su korištena stabla.

Uobičajena pitanja o intervjuu za Tree

  • Pronađite visinu binarnog stabla
  • Pronađite kth maksimalnu vrijednost u binarnom stablu pretraživanja
  • Pronađite čvorove na udaljenosti od "k" od korijena
  • Pronađite pretke datog čvora u binarnom stablu

Trie

Trie, koja je također poznata i kao „Stablo prefiksa“, struktura je podataka nalik stablu koja se pokazuje prilično učinkovitom za rješavanje problema povezanih sa nizovima. Omogućuje brzo pronalaženje i uglavnom se koristi za pretraživanje riječi u rječniku, pružanje automatskih prijedloga u tražilici, pa čak i za IP usmjeravanje.

Evo ilustracije kako se u Trie čuvaju tri riječi "vrh", "ovako" i "njihovo":

Riječi su pohranjene od vrha do dna, gdje čvorovi zelene boje "p", "s" i "r" označavaju kraj "vrha", "tako", odnosno "njihovog".

Česta pitanja o intervjuu za Trie:

  • Prebrojite ukupan broj riječi u Trie
  • Ispišite sve riječi pohranjene u Trie
  • Poredajte elemente niza pomoću Trie
  • Oblikujte riječi iz rječnika pomoću Trie
  • Izradite rječnik T9

Hash tablica

Hashing je postupak koji se koristi za jedinstvenu identifikaciju objekata i pohranu svakog objekta u neki unaprijed izračunati jedinstveni indeks koji se naziva njegov "ključ". Dakle, objekt je pohranjen u obliku para "ključ-vrijednost", a zbirka takvih predmeta naziva se "rječnikom". Pomoću tog ključa može se pretraživati ​​svaki objekt. Postoje različite podatkovne strukture temeljene na raspršivanju, ali najčešće korištena struktura podataka je raspršena tablica .

Hash tablice se obično implementiraju pomoću nizova.

Izvedba strukture podataka raspršivanja ovisi o ova tri čimbenika:

  • Hash funkcija
  • Veličina tablice raspršivanja
  • Metoda rukovanja sudarom

Evo ilustracije kako se heš preslikava u niz. Indeks ovog polja izračunava se putem Hash funkcije.

Često postavljana pitanja o intervjuu za Hashing

  • Pronađite simetrične parove u nizu
  • Ucrtajte kompletan put putovanja
  • Pronađite je li niz podskup drugog niza
  • Provjerite jesu li dati nizovi disjunktni

Gore je navedeno osam najboljih struktura podataka koje biste definitivno trebali znati prije ulaska u intervju za kodiranje.

Ako tražite resurse o podatkovnim strukturama za kodiranje intervjua, pogledajte interaktivne tečajeve koji se temelje na izazovima: Strukture podataka za kodiranje intervjua (Python, Java ili JavaScript).

Za naprednija pitanja pogledajte Coderust 3.0: Priprema bržeg kodiranja intervjua s interaktivnim izazovima i vizualizacijama.

Ako se pripremate za intervjue za softverski inženjering, evo opsežnog plana za pripremu kodiranja intervjua.

Sretno i sretno učenje! :)