Niklaus Wirth, svájci informatikus 1976-ban könyvet írt Algoritmusok + Adatszerkezetek = Programok címmel .
40+ évvel később ez az egyenlet még mindig igaz. Ezért a szoftvertechnikus pályázóknak bizonyítaniuk kell az adatstruktúrák és alkalmazásaik megértését.
Szinte minden probléma megköveteli, hogy a jelölt mélyen megértse az adatszerkezeteket. Nem számít, hogy most végzett (egyetemen vagy kódoló bootcampon), vagy évtizedes tapasztalattal rendelkezik.
Néha az interjúk kérdéseiben kifejezetten megemlítenek egy adatszerkezetet, például „adott egy bináris fát”. Máskor ez hallgatólagos, például „nyomon akarjuk követni az egyes szerzőkhöz társított könyvek számát”.
Az adatstruktúrák elsajátítása elengedhetetlen, még akkor is, ha éppen a jelenlegi munkájával próbál jobb lenni. Kezdjük az alapok megértésével.
Mi az adatstruktúra?
Egyszerűen fogalmazva: az adatstruktúra olyan tároló, amely egy adott elrendezésben tárolja az adatokat. Ez az „elrendezés” lehetővé teszi, hogy az adatstruktúra egyes műveletekben hatékony legyen, másokban nem hatékony. A cél az adatstruktúrák megértése, hogy kiválaszthassa az adott problémára legoptimálisabb adatstruktúrát.
Miért van szükségünk adatstruktúrákra?
Mivel az adatszerkezeteket az adatok szervezett formában történő tárolására használják, és mivel az adatok a számítástechnika legfontosabb elemei, az adatszerkezetek valódi értéke egyértelmű.
Nem számít, milyen problémát old meg, ilyen vagy olyan módon az adatokkal kell megküzdenie - legyen szó alkalmazotti fizetésről, részvényárfolyamokról, élelmiszerboltlistáról vagy akár egyszerű telefonkönyvről.
Különböző forgatókönyvek alapján az adatokat meghatározott formátumban kell tárolni. Van egy maroknyi adatstruktúránk, amely fedezi az adatok különböző formátumokban történő tárolásának szükségességét.
Általánosan használt adatstruktúrák
Először soroljuk fel a leggyakrabban használt adatstruktúrákat, majd egyesével lefedjük őket:
- Tömbök
- Verem
- Sorok
- Összekapcsolt listák
- Fák
- Grafikonok
- Próbálkozik (gyakorlatilag fák, de még mindig jó külön felhívni őket).
- Hash Tables
Tömbök
A tömb a legegyszerűbb és legszélesebb körben használt adatstruktúra. Más adatstruktúrák, például halmok és sorok, tömbökből származnak.
Itt egy egyszerű méretű 4 méretű tömb képe, amely (1, 2, 3 és 4) elemeket tartalmaz.
Minden adatelemhez hozzárendeljük az Index nevű pozitív számértéket , amely megfelel annak az elemnek a tömbben elfoglalt helyének. A nyelvek többsége a tömb kezdő indexét 0-ként határozza meg.
A következők a két típusú tömbök:
- Egydimenziós tömbök (a fenti ábra szerint)
- Többdimenziós tömbök (tömbök tömbökön belül)
A tömbök alapműveletei
- Beszúrás - Elem beszúrása egy adott indexbe
- Get - Az adott indexhez tartozó elemet adja eredményül
- Törlés - Elem törlése egy adott indexből
- Méret - Megkapja a tömb összes elemének számát
Gyakran feltett Array interjúk
- Keresse meg a tömb második minimum elemét
- Első nem ismétlődő egész szám egy tömbben
- Két rendezett tömböt egyesít
- Átrendezze a pozitív és a negatív értékeket egy tömbben
Verem
Mindannyian ismerjük a híres Visszavonás opciót, amely szinte minden alkalmazásban megtalálható. Elgondolkodott már azon, hogyan működik? Az ötlet: munkád előző állapotait (amelyek egy adott számra korlátozódnak) olyan sorrendben tárolod a memóriában, hogy az utolsó jelenjen meg először. Ez nem történhet csak tömbök használatával. Itt jön jól a Verem.
A Stack valóságos példája lehet egy halom könyv, függőleges sorrendben. Ahhoz, hogy a könyvet valahol középen lehessen elérni, el kell távolítania a tetején elhelyezett összes könyvet. Így működik a LIFO (Last In First Out) módszer.
Itt van egy három veremelemet (1, 2 és 3) tartalmazó verem képe, ahol a 3 van fent és először eltávolításra kerül:
A verem alapvető műveletei:
- Push - Beilleszt egy elemet a tetejére
- Pop - Visszaadja a legfelső elemet, miután eltávolította a veremből
- isEmpty - Igaz értéket ad vissza, ha a verem üres
- Top - Visszaadja a felső elemet anélkül, hogy eltávolítaná a veremből
Gyakran feltett Stack interjúk
- Értékelje a postfix kifejezést verem segítségével
- Értékek rendezése veremben
- Ellenőrizze a kifejezés kiegyensúlyozott zárójelét
Sorok
A Stackhez hasonlóan a Queue egy másik lineáris adatstruktúra, amely az elemet szekvenciálisan tárolja. Az egyetlen lényeges különbség a Stack és a Queue között az, hogy a LIFO módszer használata helyett a Queue végrehajtja a FIFO-tmódszer, amely rövid a First in First Out kifejezésből.
Tökéletes valós példa a várólistára: egy sor ember vár egy jegyfülkében. Ha új ember jön, akkor a végétől fogva csatlakozik a sorhoz, nem a kezdetektől fogva - és az elöl álló személy lesz az első, aki megkapja a jegyet, és így elhagyja a sort.
Itt van egy kép a várólistáról, amely négy adatelemet (1, 2, 3 és 4) tartalmaz, ahol az 1 van fent és először eltávolításra kerül:
A Queue alapvető műveletei
- Enqueue () - Beszúr egy elemet a sor végére
- Dequeue () - Elem eltávolítása a sor elejéről
- isEmpty () - Igaz értéket ad vissza, ha a sor üres
- Felső () - A sor első elemét adja eredményül
Gyakran feltett Queue interjúk
- A verem megvalósítása egy sor segítségével
- Fordítsa meg a sor első k elemét
- Generáljon bináris számokat 1-től n-ig egy sor segítségével
Összekapcsolt lista
A kapcsolt lista egy másik fontos lineáris adatstruktúra, amely elsőre hasonló lehet a tömbökhöz, de különbözik a memóriafoglalásban, a belső struktúrában és abban, hogy hogyan hajtják végre a beillesztés és törlés alapvető műveleteit.
A összekapcsolt lista olyan, mint a csomópontok lánca, ahol minden csomópont információt tartalmaz, például adatokat és a lánc következő csomópontjának mutatóját. Van egy fejmutató, amely a csatolt lista első elemére mutat, és ha a lista üres, akkor egyszerűen nullára vagy semmire mutat.
Az összekapcsolt listákat a fájlrendszerek, a hash táblák és a szomszédsági listák megvalósítására használják.
Az alábbiakban látható egy összekapcsolt lista belső felépítésének vizuális ábrázolása:
Az alábbiakban a csatolt listák típusai láthatók:
- Egyszerűen összekapcsolt lista (egyirányú)
- Kétszer összekapcsolt lista (kétirányú)
A kapcsolt lista alapvető műveletei:
- InsertAtEnd - Beszúr egy adott elemet a csatolt lista végére
- InsertAtHead - Beszúr egy adott elemet a csatolt lista elejére / fejére
- Törlés - Adott elem törlése a linkelt listából
- DeleteAtHead - Törli a csatolt lista első elemét
- Keresés - Visszaadja az adott elemet egy összekapcsolt listából
- isEmpty - Igaz értéket ad vissza, ha a csatolt lista üres
Gyakran feltett Linked List interjúk
- A linkelt lista megfordítása
- Hurkot észlelni egy összekapcsolt listában
- Az N-edik csomópontot adja vissza a csatolt lista végéről
- Távolítsa el az ismétlődéseket a csatolt listáról
Grafikonok
A grafikon olyan csomópontok összessége, amelyek hálózat formájában kapcsolódnak egymáshoz. A csomópontokat csúcsoknak is nevezzük. Az (x, y) párokat élnek nevezzük , ami azt jelzi, hogy az x csúcs kapcsolódik az y csúcshoz . Egy él tartalmazhat súlyt / költséget, amely megmutatja, hogy mekkora költségre van szükség az x csúcsból az y-be való haladáshoz .
Grafikonok típusai:
- Irányítatlan grafikon
- Irányított grafikon
Egy programozási nyelvben a grafikonok kétféle formában ábrázolhatók:
- Adjacency Matrix
- Adjacency List
Általános grafikonjáró algoritmusok:
- Szélesség Első keresés
- Mélység Első keresés
Gyakran feltett Graph interjúk
- Végezze el a Szélesség és Mélység Első Keresést
- Ellenőrizze, hogy a grafikon fa-e vagy sem
- Számolja meg az élek számát egy grafikonon
- Keresse meg a legrövidebb utat két csúcs között
Fák
A fa egy hierarchikus adatszerkezet, amely csúcsokból (csomópontokból) és az őket összekötő élekből áll. A fák hasonlóak a grafikonokhoz, de az a legfontosabb pont, amely megkülönbözteti a fát a gráftól, hogy ciklus nem létezhet egy fában.
A fákat széles körben használják a mesterséges intelligenciában és az összetett algoritmusokban, hogy hatékony tárolási mechanizmust biztosítsanak a problémamegoldáshoz.
Itt látható egy egyszerű fa képe és a fa adatszerkezetében használt alapvető terminológiák:
Az alábbiak a fafajták:
- N-ary fa
- Kiegyensúlyozott fa
- Bináris fa
- Bináris keresési fa
- AVL fa
- Piros fekete fa
- 2–3 fa
A fentiek közül a bináris fa és a bináris kereső fa a leggyakrabban használt fa.
Gyakran feltett fa interjúk
- Keresse meg a bináris fa magasságát
- Keresse meg a kth maximális értéket egy bináris keresési fában
- Keresse meg a csomópontokat a gyökértől „k” távolságra
- Keresse meg egy bináris fa adott csomópontjának őseit
Trie
A Trie, amely más néven „Prefix Trees”, egy faszerű adatszerkezet, amely elég hatékonynak bizonyul a húrokkal kapcsolatos problémák megoldásában. Gyors visszakeresést biztosít, és többnyire szavak keresésére szolgál egy szótárban, automatikus javaslatokkal szolgál a keresőmotorban, sőt IP-útválasztáshoz is.
Íme egy illusztráció arról, hogyan tárolják a Trie-ben három szót: „top”, „így” és „azok”:
A szavakat fentről lefelé tárolják, ahol a zöld színű „p”, „s” és „r” csomópontok a “top”, “így” és “azok” végét jelzik.
Gyakran feltett Trie interjúk:
- Számolja meg a Trie szavainak teljes számát
- Nyomtassa ki az összes Trie-ben tárolt szót
- Rendezzen egy tömb elemeit a Trie segítségével
- Formázzon szavakat egy szótárból a Trie segítségével
- Készítsen T9 szótárt
Hash táblázat
A hashelés olyan folyamat, amelyet az objektumok egyedi azonosítására és minden objektum tárolására használnak valamilyen előre kiszámított egyedi indexben, amelyet „kulcsának” neveznek. Tehát az objektumot „kulcs-érték” pár formájában tárolják, és az ilyen elemek gyűjteményét „szótárnak” nevezik. Minden objektum kereshető azzal a kulccsal. Különböző adatstruktúrák léteznek a hash alapján, de a leggyakrabban használt adatstruktúra a hash tábla .
A hash táblákat általában tömbök segítségével valósítják meg.
A kivonatoló adatstruktúra teljesítménye a következő három tényezőtől függ:
- Hash funkció
- A Hash táblázat mérete
- Ütközéskezelési módszer
Itt mutatjuk be, hogyan térképezik fel a hash-t egy tömbben. Ennek a tömbnek az indexét egy hasítási függvény segítségével számítják ki.
Gyakran feltett Hashing-interjúk
- Keressen szimmetrikus párokat egy tömbben
- Nyomon követheti az utazás teljes útvonalát
- Keresse meg, hogy egy tömb egy másik tömb részhalmaza-e
- Ellenőrizze, hogy az adott tömbök nincsenek-e összekapcsolva
A fenti a nyolc legfontosabb adatstruktúra, amelyet feltétlenül tudnia kell, mielőtt belépne egy kódoló interjúra.
Ha forrásokat keres az interjúk kódolásához szükséges adatstruktúrákról, tekintse meg az interaktív és kihívás alapú tanfolyamokat: Adatszerkezetek interjúk kódolásához (Python, Java vagy JavaScript).
Haladóbb kérdéseket a Coderust 3.0: Gyorsabb kódolási interjúkészítés interaktív kihívásokkal és vizualizációkkal című témakörben talál.
Ha szoftvertechnikai interjúkra készül, itt egy átfogó ütemterv az interjúk kódolására való felkészüléshez.
Sok szerencsét és boldog tanulást! :)