Parimad andmestruktuurid, mida peaksite teadma oma järgmise kodeerimisintervjuu jaoks

Šveitsi arvutiteadlane Niklaus Wirth kirjutas 1976. aastal raamatu " Algoritmid + andmestruktuurid = programmid".

40+ aastat hiljem kehtib see võrrand endiselt. Sellepärast peavad tarkvaratehnika kandidaadid näitama oma arusaama andmestruktuuridest koos oma rakendustega.

Peaaegu kõik probleemid nõuavad kandidaadilt andmestruktuuride sügavat mõistmist. Pole tähtis, kas olete just lõpetanud (ülikooli või kodeerinud bootcampi) või on teil aastakümnete pikkune kogemus.

Mõnikord mainitakse intervjuuküsimustes sõnaselgelt andmestruktuuri, näiteks "antakse binaarne puu". Teinekord on see kaudne, näiteks "me tahame jälgida iga autoriga seotud raamatute arvu".

Andmestruktuuride õppimine on hädavajalik isegi siis, kui proovite lihtsalt oma praegusel töökohal paremaks saada. Alustame põhitõdede mõistmisega.

Mis on andmestruktuur?

Lihtsamalt öeldes on andmestruktuur konteiner, mis salvestab andmeid kindlas paigutuses. See „paigutus” võimaldab andmestruktuuril olla mõnes operatsioonis tõhus ja mõnes teises osas ebaefektiivne. Teie eesmärk on mõista andmestruktuure, et saaksite valida antud probleemile kõige optimaalsema andmestruktuuri.

Miks me vajame andmestruktuure?

Kuna andmestruktuure kasutatakse andmete organiseeritud kujul salvestamiseks ja kuna andmed on arvutiteaduses kõige olulisem üksus, on andmestruktuuride tegelik väärtus selge.

Ükskõik, mis probleemi te ka ei lahendaks, peate ühel või teisel viisil tegelema andmetega - olgu see siis töötaja palk, aktsiahinnad, toidukaupade nimekiri või isegi lihtne telefoniraamat.

Erinevate stsenaariumide põhjal tuleb andmed salvestada kindlas vormingus. Meil on käputäis andmestruktuure, mis hõlmavad meie vajadust salvestada andmeid erinevates vormingutes.

Tavaliselt kasutatavad andmestruktuurid

Kõigepealt loetleme kõige sagedamini kasutatavad andmestruktuurid ja seejärel käsitleme neid ükshaaval:

  1. Massiivid
  2. Virnad
  3. Järjekorrad
  4. Lingitud loendid
  5. Puud
  6. Graafikud
  7. Proovib (nad on tegelikult puud, kuid siiski on hea neid eraldi välja kutsuda).
  8. Hash tabelid

Massiivid

Massiiv on lihtsaim ja enimkasutatav andmestruktuur. Muud andmestruktuurid, nagu virnad ja järjekorrad, on saadud massiividest.

Siin on pilt lihtsa massiivi 4 suurusest, mis sisaldab elemente (1, 2, 3 ja 4).

Igale andmeelemendile määratakse positiivne arvväärtus , mida nimetatakse indeksiks , mis vastab selle üksuse positsioonile massiivis. Enamik keeli määratleb massiivi algindeksiks 0.

Järgmised on kahte tüüpi massiivid:

  • Ühemõõtmelised massiivid (nagu eespool näidatud)
  • Mitmemõõtmelised massiivid (massiivid massiivides)

Põhitoimingud massiividel

  • Insert - lisab elemendi antud indeksisse
  • Hangi - tagastab antud indeksi elemendi
  • Kustuta - kustutab antud indeksi elemendi
  • Suurus - saab massiivi elementide koguarvu

Array intervjuu küsimused

  • Leidke massiivi teine ​​minimaalne element
  • Esimesed mittekorduvad täisarvud massiivis
  • Ühendage kaks sorteeritud massiivi
  • Järjestage massiivi positiivsed ja negatiivsed väärtused

Virnad

Meile kõigile on tuntud kuulus Undo valik, mis on olemas peaaegu igas rakenduses. Kas olete mõelnud, kuidas see töötab? Idee: salvestate oma töö eelmised olekud (mis on piiratud kindla numbriga) mällu sellises järjekorras, et viimane ilmuks esimesena. Seda ei saa teha ainult massiivide abil. Seal tuleb Stack kasuks.

Stacki tegelik näide võiks olla vertikaalses järjekorras asetatud raamatuhunnik. Kusagil keskel oleva raamatu saamiseks peate eemaldama kõik selle kohale asetatud raamatud. Nii töötab meetod LIFO (Last In First Out).

Siin on virna pilt, mis sisaldab kolme andmeelementi (1, 2 ja 3), kus 3 on ülaosas ja eemaldatakse kõigepealt:

Virna põhitoimingud:

  • Push - lisab ülaosasse elemendi
  • Pop - tagastab pärast virnast eemaldamist ülemise elemendi
  • isEmpty - tagastab tõese, kui virn on tühi
  • Ülemine - tagastab ülemise elemendi virnast eemaldamata

Stacki intervjuu küsimused

  • Postfixi avaldise hindamine virna abil
  • Sorteeri väärtused virnas
  • Kontrollige avaldises tasakaalustatud sulge

Järjekorrad

Sarnaselt virnaga on järjekord veel üks lineaarne andmestruktuur, mis salvestab elementi järjestikku. Ainus oluline erinevus virna ja järjekorra vahel on see, et LIFO meetodi kasutamise asemel rakendab järjekord FIFOmeetod, mis on lühend sõnast First in First Out.

Ideaalne näide järjekorrast reaalses elus: rida inimesi, kes ootavad piletiputkas. Kui tuleb uus inimene, liituvad nad liiniga otsast, mitte algusest peale - ja ees seisev inimene saab esimesena pileti ja lahkub seega liinilt.

Siin on pilt järjekorrast, mis sisaldab nelja andmeelementi (1, 2, 3 ja 4), kus 1 on ülaosas ja eemaldatakse kõigepealt:

Järjekorra põhitoimingud

  • Enqueue () - lisab elemendi järjekorra lõppu
  • Dequeue () - eemaldab elemendi järjekorra algusest
  • isEmpty () - tagastab tõene, kui järjekord on tühi
  • Top () - tagastab järjekorra esimese elemendi

Tavaliselt küsitavad Queue intervjuu küsimused

  • Rakendage virna järjekorra abil
  • Pöörake järjekorra esimesed k elemendid
  • Genereerige järjekorra abil kahendarvud vahemikus 1 kuni n

Lingitud loend

Lingitud loend on veel üks oluline lineaarne andmestruktuur, mis võib esmalt sarnaneda massiividega, kuid erineb mälu jaotamise, sisemise struktuuri ja sisestamise ja kustutamise põhitoimingute teostamise poolest.

Lingitud loend on nagu sõlmede ahel, kus iga sõlm sisaldab sellist teavet nagu andmed ja osuti ahela järgmisele sõlmele. Seal on peaosuti, mis osutab lingitud loendi esimesele elemendile ja kui loend on tühi, siis see näitab lihtsalt nulli või mitte midagi.

Lingitud loendeid kasutatakse failisüsteemide, räsitabelite ja külgnevusloendite juurutamiseks.

Siin on visuaalne esitus lingitud loendi sisemisest struktuurist:

Järgmised on lingitud loendite tüübid:

  • Üksikult lingitud loend (ühesuunaline)
  • Kahekordse lingiga loend (kahesuunaline)

Lingitud loendi põhitoimingud:

  • InsertAtEnd - lisab lingitud loendi lõppu antud elemendi
  • InsertAtHead - lisab antud elemendi lingitud loendi algusesse / otsa
  • Kustuta - kustutab antud elemendi lingitud loendist
  • DeleteAtHead - kustutab lingitud loendi esimese elemendi
  • Otsing - tagastab antud elemendi lingitud loendist
  • isEmpty - tagastab tõene, kui lingitud loend on tühi

Lingitud loendi intervjuu küsimused

  • Lingitud loendi ümberpööramine
  • Tuvasta silmus lingitud loendis
  • Tagastab lingitud loendis N-nda sõlme
  • Duplikaatide eemaldamine lingitud loendist

Graafikud

Graafik on sõlmede kogum, mis on omavahel ühendatud võrgu kujul. Sõlmi nimetatakse ka tippudeks. Paar (x, y) nimetatakse serva , mis näitab, et tipu x on ühendatud tipu y . Serv võib sisaldada kaalu / kulu, mis näitab, kui palju kulub tipust x kuni y läbimiseks .

Graafikute tüübid:

  • Suunamata graafik
  • Suunatud graafik

Programmeerimiskeeles saab graafikuid esitada kahe vormi abil:

  • Adjacency Matrix
  • Adjacency nimekiri

Üldised graafi läbivad algoritmid:

  • Laiuse esimene otsing
  • Esimene sügavus

Graafiku intervjuu küsimused

  • Rakendage laiuse ja sügavuse esimene otsing
  • Kontrollige, kas graafik on puu või mitte
  • Loendage graafi servade arv
  • Leidke lühim tee kahe tipu vahel

Puud

Puu on hierarhiline andmestruktuur, mis koosneb tippudest (sõlmedest) ja neid ühendavatest servadest. Puud sarnanevad graafikutega, kuid põhipunkt, mis eristab puud graafikust, on see, et tsükkel ei saa puus eksisteerida.

Puid kasutatakse tehisintellektis ja keerukates algoritmides laialdaselt, et pakkuda probleemide lahendamiseks tõhusat salvestusmehhanismi.

Siin on pilt lihtsast puust ja puuandmete struktuuris kasutatavad põhiterminid:

Puude tüübid on järgmised:

  • N-ary puu
  • Tasakaalus puu
  • Binaarne puu
  • Binaarotsingupuu
  • AVL puu
  • Punane must puu
  • 2–3 Puu

Eeltoodust on kõige sagedamini kasutatavad kahendpuud ja kahendotsingupuud.

Puu intervjuu küsimused

  • Leidke binaarse puu kõrgus
  • Leidke binaarotsingupuust k maksimaalne väärtus
  • Leidke sõlmed juurest k kaugusel
  • Leidke binaarpuust antud sõlme esivanemad

Trie

Trie, mida tuntakse ka nimetusega „Prefix Trees“, on puulaadne andmestruktuur, mis osutub stringidega seotud probleemide lahendamiseks üsna tõhusaks. See tagab kiire otsimise ja seda kasutatakse enamasti sõnastikust sõnade otsimiseks, otsimootoris automaatsete soovituste pakkumiseks ja isegi IP-marsruutimiseks.

Siin on illustratsioon selle kohta, kuidas kolm sõna "top", "seega" ja "nende" on Trie'is salvestatud:

Sõnad salvestatakse ülevalt alla, kus rohelised värvilised sõlmed “p”, “s” ja “r” tähistavad vastavalt “ülemise”, “seega” ja “nende” lõppu.

Trie intervjuu korduma kippuvad küsimused:

  • Lugege Trie sõnade koguarv
  • Prindi kõik Trie'sse salvestatud sõnad
  • Sorteeri massiivi elemendid Trie abil
  • Moodustage sõnad sõnastikust Trie abil
  • Ehitage sõnastik T9

Hash tabel

Räsimine on protsess, mida kasutatakse objektide kordumatuks tuvastamiseks ja iga objekti salvestamiseks mingisse eelnevalt arvutatud unikaalsesse indeksisse, mida nimetatakse selle võtmeks. Niisiis, objekt on salvestatud paari "võti-väärtus" kujul ja selliste üksuste kogumit nimetatakse "sõnastikuks". Iga objekti saab selle klahvi abil otsida. Räsimisel põhinevad erinevad andmestruktuurid, kuid kõige sagedamini kasutatakse andmestruktuuri räsitabelit .

Räsi tabelid rakendatakse tavaliselt massiivide abil.

Andmestruktuuri toimivus sõltub neist kolmest tegurist:

  • Räsifunktsioon
  • Hash tabeli suurus
  • Kokkupõrke käsitlemise meetod

Siin on illustratsioon selle kohta, kuidas räsi massiivis kaardistatakse. Selle massiivi indeks arvutatakse läbi räsimisfunktsiooni.

Hashhi intervjuu küsimused

  • Leidke massiivist sümmeetrilised paarid
  • Jälgige reisi täielikku rada
  • Leidke, kas massiiv on teise massiivi alamhulk
  • Kontrollige, kas antud massiivid on lahus

Ülaltoodud on kaheksa parimat andmestruktuuri, mida peaksite kindlasti enne kodeerimisintervjuule astumist teadma.

Kui otsite intervjuude kodeerimiseks ressursse andmestruktuuride kohta, vaadake interaktiivseid ja väljakutsetel põhinevaid kursusi: Andmestruktuurid intervjuude kodeerimiseks (Python, Java või JavaScript).

Täpsemate küsimuste saamiseks vaadake Coderust 3.0: Intervjuu kiirem kodeerimine koos interaktiivsete väljakutsete ja visualiseerimistega.

Kui valmistute tarkvaratehnikaintervjuudeks, on siin põhjalik teekaart intervjuude kodeerimiseks valmistumiseks.

Edu ja head õppimist! :)