Najlepšie dátové štruktúry, ktoré by ste mali poznať pre svoj ďalší programovací rozhovor

Niklaus Wirth, švajčiarsky počítačový vedec, napísal v roku 1976 knihu s názvom Algoritmy + dátové štruktúry = programy.

O 40 rokov neskôr táto rovnica stále platí. Preto musia kandidáti na softvérové ​​inžinierstvo preukázať svoje pochopenie dátových štruktúr spolu s ich aplikáciami.

Takmer všetky problémy vyžadujú, aby kandidát preukázal hlboké pochopenie dátových štruktúr. Nezáleží na tom, či ste práve vyštudovali (univerzitu alebo kódovali bootcamp), alebo máte desaťročné skúsenosti.

Niekedy otázky z pohovoru výslovne spomínajú dátovú štruktúru, napríklad „daný binárny strom“. Inokedy je to implicitné, napríklad „chceme sledovať počet kníh spojených s každým autorom“.

Učenie sa dátových štruktúr je nevyhnutné, aj keď sa práve snažíte vylepšiť svoje súčasné zamestnanie. Začnime tým, že pochopíme základné veci.

Čo je to dátová štruktúra?

Jednoducho povedané, dátová štruktúra je kontajner, ktorý ukladá údaje v konkrétnom usporiadaní. Toto „usporiadanie“ umožňuje, aby dátová štruktúra bola efektívna v niektorých operáciách a neefektívna v iných. Vaším cieľom je porozumieť dátovým štruktúram, aby ste si mohli zvoliť dátovú štruktúru, ktorá je najoptimálnejšia pre daný problém.

Prečo potrebujeme dátové štruktúry?

Pretože sa dátové štruktúry používajú na ukladanie údajov v organizovanej podobe a keďže údaje sú najdôležitejšou entitou v oblasti informatiky, je skutočná hodnota dátových štruktúr jasná.

Bez ohľadu na to, aký problém riešite, tak či onak musíte narábať s údajmi - či už ide o plat zamestnanca, ceny akcií, zoznam potravín alebo dokonca jednoduchý telefónny zoznam.

Na základe rôznych scenárov je potrebné údaje ukladať v konkrétnom formáte. Máme niekoľko dátových štruktúr, ktoré pokrývajú našu potrebu ukladať údaje v rôznych formátoch.

Bežne používané dátové štruktúry

Najskôr si vymenujme najbežnejšie používané dátové štruktúry a potom ich postupne zahrnieme:

  1. Polia
  2. Stohy
  3. Fronty
  4. Prepojené zoznamy
  5. Stromy
  6. Grafy
  7. Pokusy (sú to skutočne stromy, ale aj tak je dobré ich zavolať osobitne).
  8. Hašovacie tabuľky

Polia

Pole je najjednoduchšia a najbežnejšie používaná dátová štruktúra. Ostatné dátové štruktúry, ako sú komíny a fronty, sú odvodené z polí.

Tu je obrázok jednoduchého poľa veľkosti 4, ktoré obsahuje prvky (1, 2, 3 a 4).

Každému údajovému prvku je priradená kladná číselná hodnota nazývaná Index , ktorá zodpovedá pozícii tejto položky v poli. Väčšina jazykov definuje počiatočný index poľa ako 0.

Nasledujú dva typy polí:

  • Jednorozmerné polia (ako je uvedené vyššie)
  • Viacrozmerné polia (polia v poliach)

Základné operácie s poľami

  • Vložiť - Vloží prvok do daného indexu
  • Získať - vráti prvok pri danom indexe
  • Odstrániť - Odstráni prvok v danom indexe
  • Veľkosť - Získa celkový počet prvkov v poli

Bežne kladené otázky týkajúce sa rozhovoru s Array

  • Nájdite druhý minimálny prvok poľa
  • Prvé neopakujúce sa celé čísla v poli
  • Zlúčte dve zoradené polia
  • Usporiadajte kladné a záporné hodnoty v poli

Stohy

Všetci dobre poznáme slávnu možnosť Späť , ktorá je prítomná takmer v každej aplikácii. Zaujímalo vás niekedy, ako to funguje? Myšlienka: predchádzajúce stavy svojej práce (ktoré sú obmedzené na určitý počet) ukladáte do pamäte v poradí, aby sa posledný zobrazil ako prvý. To sa nedá dosiahnuť iba použitím polí. To je miesto, kde sa Stack hodí.

Skutočným príkladom Stacka môže byť hromada kníh umiestnených vo zvislom poradí. Aby ste dostali knihu, ktorá je niekde uprostred, budete musieť odstrániť všetky knihy, ktoré sú na nej umiestnené. Takto funguje metóda LIFO (Last In First Out).

Tu je obrázok zásobníka obsahujúceho tri dátové prvky (1, 2 a 3), kde 3 je na vrchu a bude odstránený ako prvý:

Základné operácie so zásobníkom:

  • Push - Vloží prvok hore
  • Pop - Vráti horný prvok po odstránení zo stohu
  • isEmpty - Vráti hodnotu true, ak je zásobník prázdny
  • Horná - Vráti horný prvok bez vybratia zo stohu

Bežne kladené otázky na rozhovor so Stackom

  • Vyhodnoťte výraz prípony pomocou stohu
  • Zoraďte hodnoty do stohu
  • Skontrolujte vyvážené zátvorky vo výraze

Fronty

Podobne ako v prípade Stack, Queue je ďalšia lineárna dátová štruktúra, ktorá ukladá prvok postupne. Jediný významný rozdiel medzi Stack a Queue je, že namiesto použitia metódy LIFO, Queue implementuje FIFOmetóda, čo je skratka pre First in First Out.

Perfektný príklad frontu v reálnom živote: rada ľudí čakajúcich v pokladni. Ak príde nová osoba, pripojí sa k linke od konca, nie od začiatku - a osoba stojaca vpredu bude prvá, ktorá získa lístok a teda opustí linku.

Tu je obrázok frontu obsahujúci štyri dátové prvky (1, 2, 3 a 4), kde 1 je na vrchu a bude odstránený ako prvý:

Základné operácie frontu

  • Enqueue () - Vloží prvok na koniec poradia
  • Dequeue () - Odstráni prvok od začiatku poradia
  • isEmpty () - Vráti hodnotu true, ak je rad prázdny
  • Top () - Vráti prvý prvok vo fronte

Najčastejšie kladené otázky na pohovor do frontu

  • Implementujte zásobník pomocou frontu
  • Obrátiť prvých k prvkov frontu
  • Generujte binárne čísla od 1 do n pomocou frontu

Prepojený zoznam

Prepojený zoznam je ďalšou dôležitou lineárnou dátovou štruktúrou, ktorá by na prvý pohľad mohla vyzerať podobne ako polia, ale líši sa v alokácii pamäte, vnútornej štruktúre a v tom, ako sa vykonávajú základné operácie vkladania a mazania.

Prepojený zoznam je ako reťazec uzlov, kde každý uzol obsahuje informácie, ako sú údaje, a ukazovateľ na nasledujúci uzol v reťazci. Existuje ukazovateľ hlavy, ktorý ukazuje na prvý prvok prepojeného zoznamu, a ak je zoznam prázdny, potom jednoducho ukazuje na nulu alebo na nič.

Prepojené zoznamy sa používajú na implementáciu súborových systémov, hašovacích tabuliek a zoznamov susednosti.

Tu je vizuálne znázornenie vnútornej štruktúry prepojeného zoznamu:

Nasledujú typy prepojených zoznamov:

  • Singly Linked List (jednosmerný)
  • Dvojnásobne prepojený zoznam (obojsmerný)

Základné operácie súvisiaceho zoznamu:

  • InsertAtEnd - Vloží daný prvok na koniec prepojeného zoznamu
  • InsertAtHead - Vloží daný prvok na začiatok / nadpis prepojeného zoznamu
  • Odstrániť - Odstráni daný prvok z prepojeného zoznamu
  • DeleteAtHead - Odstráni prvý prvok prepojeného zoznamu
  • Hľadať - Vráti daný prvok z prepojeného zoznamu
  • isEmpty - Vráti hodnotu true, ak je prepojený zoznam prázdny

Najčastejšie kladené otázky týkajúce sa rozhovorov so zoznamom Linked List

  • Obrátiť prepojený zoznam
  • Zistiť slučku v prepojenom zozname
  • Vráťte N-tý uzol z konca do prepojeného zoznamu
  • Odstráňte duplikáty z prepojeného zoznamu

Grafy

Graf je množina uzlov, ktoré sú navzájom spojené vo forme siete. Uzly sa tiež nazývajú vrcholy. Dvojica (x, y) sa nazýva hranu , čo znamená, že vrchol x je pripojený k vrcholu y . Okraj môže obsahovať hmotnosť / cenu, ktorá ukazuje, koľko nákladov je potrebných na prechod z vrcholu x do y .

Typy grafov:

  • Neusmernený graf
  • Nasmerovaný graf

V programovacom jazyku môžu byť grafy znázornené v dvoch formách:

  • Matica susedstva
  • Zoznam susedov

Bežné algoritmy prechodu grafov:

  • Šírka prvého vyhľadávania
  • Hĺbka prvého vyhľadávania

Bežne kladené otázky z rozhovoru pre Graph

  • Implementujte vyhľadávanie šírky a hĺbky ako prvé
  • Skontrolujte, či je graf strom alebo nie
  • Spočítajte počet hrán v grafe
  • Nájdite najkratšiu cestu medzi dvoma vrcholmi

Stromy

Strom je hierarchická dátová štruktúra pozostávajúca z vrcholov (uzlov) a hrán, ktoré ich spájajú. Stromy sú podobné grafom, ale kľúčovým bodom, ktorý odlišuje strom od grafu, je to, že v strome nemôže existovať cyklus.

Stromy sa vo veľkej miere používajú v umelej inteligencii a zložité algoritmy poskytujú efektívny mechanizmus ukladania na riešenie problémov.

Tu je obrázok jednoduchého stromu a základné terminológie používané v stromovej dátovej štruktúre:

Toto sú typy stromov:

  • N-árny strom
  • Vyvážený strom
  • Binárny strom
  • Binárny vyhľadávací strom
  • Strom AVL
  • Červený čierny strom
  • 2–3 Strom

Z vyššie uvedeného sú najčastejšie používané stromy binárny strom a binárny vyhľadávací strom.

Najčastejšie kladené otázky týkajúce sa rozhovorov so spoločnosťou Tree

  • Nájdite výšku binárneho stromu
  • Nájdite k-tú maximálnu hodnotu v binárnom vyhľadávacom strome
  • Nájdite uzly vo vzdialenosti „k“ od koreňa
  • Nájdite predkov daného uzla v binárnom strome

Trie

Trie, ktorý je tiež známy ako „Prefix Trees“, je stromová dátová štruktúra, ktorá sa ukazuje ako veľmi efektívna pri riešení problémov súvisiacich s reťazcami. Poskytuje rýchle načítanie a väčšinou sa používa na hľadanie slov v slovníku, poskytuje automatické návrhy vo vyhľadávači a dokonca aj na smerovanie IP.

Tu je ilustrácia toho, ako sú v Trie uložené tri slová „top“, „takto“ a „ich“:

Slová sú uložené zhora nadol spôsobom, kde zelené zafarbené uzly „p“, „s“ a „r“ označujú koniec slov „hore“, „teda“ a „ich“.

Najčastejšie kladené otázky týkajúce sa rozhovoru s Trie:

  • Spočítajte celkový počet slov v Trie
  • Vytlačte všetky slová uložené v Trie
  • Zoraďte prvky poľa pomocou Trie
  • Tvorte slová zo slovníka pomocou Trie
  • Zostavte si slovník T9

Hash tabuľka

Hašovanie je proces, ktorý sa používa na jednoznačnú identifikáciu objektov a ukladanie každého objektu do nejakého vopred vypočítaného jedinečného indexu, ktorý sa nazýva jeho „kľúč“. Objekt je teda uložený vo forme dvojice „kľúč - hodnota“ a zbierka takýchto položiek sa nazýva „slovník“. Pomocou tohto kľúča je možné prehľadať každý objekt. Existujú rôzne dátové štruktúry založené na hašovaní, ale najbežnejšie používanou dátovou štruktúrou je hašovacia tabuľka .

Hašovacie tabuľky sa všeobecne implementujú pomocou polí.

Výkonnosť hašovacej dátovej štruktúry závisí od týchto troch faktorov:

  • Funkcia hash
  • Veľkosť tabuľky hash
  • Metóda riešenia kolízií

Tu je ilustrácia toho, ako je hash mapovaný v poli. Index tohto poľa sa počíta pomocou funkcie hash.

Bežne kladené otázky týkajúce sa hašovacieho pohovoru

  • Nájdite symetrické páry v poli
  • Vystopovať úplnú cestu cesty
  • Zistite, či je pole podmnožinou iného poľa
  • Skontrolujte, či sú dané polia disjunktné

Vyššie je uvedených osem najlepších dátových štruktúr, ktoré by ste mali určite poznať skôr, ako vstúpite do programovacieho rozhovoru.

Ak hľadáte zdroje pre dátové štruktúry na kódovanie rozhovorov, pozrite si interaktívne kurzy založené na výzvach: Dátové štruktúry pre kódovacie rozhovory (Python, Java alebo JavaScript).

Pokročilejšie otázky nájdete v dokumente Coderust 3.0: Príprava rozhovoru na rýchlejší kódovanie s interaktívnymi výzvami a vizualizáciami.

Ak sa pripravujete na rozhovory so softvérovým inžinierstvom, tu je komplexný plán prípravy na kódovanie rozhovorov.

Veľa šťastia a šťastné učenie! :)