Suosituimmat tietorakenteet, jotka sinun tulisi tietää seuraavaa koodaushaastattelua varten

Sveitsiläinen tietojenkäsittelytieteen tutkija Niklaus Wirth kirjoitti vuonna 1976 kirjan nimeltä Algoritmit + tietorakenteet = ohjelmat.

Yli 40 vuotta myöhemmin yhtälö on edelleen totta. Siksi ohjelmistotekniikan ehdokkaiden on osoitettava ymmärryksensä tietorakenteista yhdessä sovellustensa kanssa.

Lähes kaikki ongelmat edellyttävät ehdokkaalta syvällistä tietorakenteiden ymmärtämistä. Ei ole väliä oletko juuri valmistunut (yliopistosta vai koodaamalla bootcamp) vai onko sinulla vuosikymmenien kokemus.

Joskus haastattelukysymyksissä mainitaan nimenomaisesti tietorakenne, esimerkiksi "annettu binääripuu". Muina aikoina se on epäsuoraa, kuten "haluamme seurata kuhunkin kirjailijaan liittyvien kirjojen määrää".

Tietorakenteiden oppiminen on välttämätöntä, vaikka yrität vain päästä paremmin nykyiseen työhösi. Aloitetaan ymmärtämällä perusasiat.

Mikä on tietorakenne?

Yksinkertaisesti sanottuna tietorakenne on säilö, joka tallentaa tietoja tietylle asettelulle. Tämän "asettelun" avulla tietorakenne voi olla tehokas joissakin toiminnoissa ja tehoton toisissa. Tavoitteenasi on ymmärtää tietorakenteet, jotta voit valita tietorakenteen, joka on optimaalisin käsiteltävään ongelmaan.

Miksi tarvitsemme tietorakenteita?

Koska datarakenteita käytetään tietojen tallentamiseen organisoidussa muodossa, ja koska data on tietotekniikan tärkein kokonaisuus, tietorakenteiden todellinen arvo on selvä.

Riippumatta siitä, mitä ongelmaa ratkaiset, jollain tavalla tai toisella sinun on käsiteltävä tietoja - olipa kyseessä työntekijän palkka, osakekurssit, päivittäistavaraluettelo tai jopa yksinkertainen puhelinluettelo.

Eri skenaarioiden perusteella tiedot on tallennettava tietyssä muodossa. Meillä on kourallinen tietorakenteita, jotka kattavat tarpeen tallentaa tietoja eri muodoissa.

Yleisesti käytetyt tietorakenteet

Luetteloidaan ensin yleisimmin käytetyt tietorakenteet, ja sitten käsitellään ne yksitellen:

  1. Taulukot
  2. Pinot
  3. Jonot
  4. Linkitetyt luettelot
  5. Puut
  6. Kaaviot
  7. Kokeilee (ne ovat käytännössä puita, mutta on silti hyvä kutsua ne erikseen).
  8. Hash-taulukot

Taulukot

Matriisi on yksinkertaisin ja eniten käytetty tietorakenne. Muut tietorakenteet, kuten pinot ja jonot, johdetaan matriiseista.

Tässä on kuva yksinkertaisesta kokoisesta taulukosta, joka sisältää elementtejä (1, 2, 3 ja 4).

Jokaiselle tietoelementille on annettu positiivinen numeerinen arvo , jota kutsutaan hakemistoksi , joka vastaa kyseisen kohteen sijaintia taulukossa. Suurin osa kielistä määrittelee matriisin aloitusindeksiksi 0.

Seuraavat ovat kahden tyyppisiä taulukoita:

  • Yksiulotteiset taulukot (kuten yllä on esitetty)
  • Moniulotteiset taulukot (matriisit matriisien sisällä)

Taulukoiden perustoiminnot

  • Lisää - Lisää elementti tiettyyn hakemistoon
  • Hanki - Palauttaa elementin tietylle hakemistolle
  • Poista - poistaa elementin tietystä hakemistosta
  • Koko - Antaa taulukon elementtien kokonaismäärän

Yleisesti kysytyt Array-haastattelukysymykset

  • Etsi taulukon toinen minimielementti
  • Ensimmäiset ei-toistuvat kokonaisluvut taulukossa
  • Yhdistä kaksi lajiteltua taulukkoa
  • Järjestä uudelleen positiiviset ja negatiiviset arvot taulukossa

Pinot

Tunnemme kaikki kuuluisan Kumoa- vaihtoehdon, joka on lähes kaikissa sovelluksissa. Oletko koskaan miettinyt, miten se toimii? Ajatus: tallennat työsi aikaisemmat tilat (jotka on rajoitettu tiettyyn lukuun) muistiin siinä järjestyksessä, että viimeinen näkyy ensin. Tätä ei voida tehdä vain käyttämällä matriiseja. Siellä Stack on kätevä.

Todellinen esimerkki pinosta voisi olla kasa kirjoja, jotka on asetettu pystysuoraan järjestykseen. Jos haluat saada kirjan, joka on keskellä, sinun on poistettava kaikki sen päälle asetetut kirjat. Näin LIFO (Last In First Out) -menetelmä toimii.

Tässä on kuva pinosta, joka sisältää kolme tietoelementtiä (1, 2 ja 3), jossa 3 on yläosassa ja poistetaan ensin:

Pinon perustoiminnot:

  • Työnnä - Lisää elementin yläosaan
  • Pop - Palauttaa ylimmän elementin poistamisen jälkeen pinosta
  • isEmpty - Palauttaa arvon true, jos pino on tyhjä
  • Yläosa - Palauttaa ylimmän elementin poistamatta pinosta

Yleisesti kysytyt Stack-haastattelukysymykset

  • Arvioi postfix-lauseke pinon avulla
  • Lajittele arvot pinossa
  • Tarkista tasapainotetut sulkeet lausekkeessa

Jonot

Stackin tapaan Queue on toinen lineaarinen tietorakenne, joka tallentaa elementin peräkkäin. Ainoa merkittävä ero pinon ja jonon välillä on se, että LIFO-menetelmän käyttämisen sijaan jono toteuttaa FIFOnmenetelmä, joka on lyhenne sanoista First in First Out.

Täydellinen tosielämän esimerkki jonosta: jono ihmisiä, jotka odottavat lippupisteessä. Jos uusi henkilö tulee, hän liittyy linjaan loppuun, ei alusta alkaen - ja edessä seisova henkilö saa ensimmäisenä lipun ja jättää siten linjan.

Tässä on kuva jonosta, joka sisältää neljä tietoelementtiä (1, 2, 3 ja 4), jossa 1 on yläosassa ja poistetaan ensin:

Jonon perustoiminnot

  • Enqueue () - Lisää elementin jonon loppuun
  • Hylkää () - Poistaa elementin jonon alusta
  • isEmpty () - Palauttaa arvon true, jos jono on tyhjä
  • Yläosa () - Palauttaa jonon ensimmäisen elementin

Yleisesti kysytyt jono-haastattelukysymykset

  • Toteuta pino jonossa
  • Käännä jonon ensimmäiset k elementit
  • Luo binääriluvut välillä 1 - n jonon avulla

Linkitetty luettelo

Linkitetty luettelo on toinen tärkeä lineaarinen tietorakenne, joka saattaa näyttää aluksi samanlaiselta kuin matriisit, mutta eroaa muistin allokoinnista, sisäisestä rakenteesta ja siitä, miten lisäyksen ja poistamisen perustoiminnot suoritetaan.

Linkitetty luettelo on kuin solmuketju, jossa kukin solmu sisältää tietoja, kuten tietoja, ja osoittimen ketjun seuraavaan solmuun. Siellä on pääosoitin, joka osoittaa linkitetyn luettelon ensimmäiseen elementtiin, ja jos luettelo on tyhjä, se osoittaa vain nollaa tai ei mitään.

Linkitettyjä luetteloita käytetään tiedostojärjestelmien, hash-taulukoiden ja vierekkäisyysluetteloiden toteuttamiseen.

Tässä on visuaalinen esitys linkitetyn luettelon sisäisestä rakenteesta:

Seuraavassa on linkitettyjen luetteloiden tyypit:

  • Yksin linkitetty luettelo (yksisuuntainen)
  • Kaksinkertaisesti linkitetty luettelo (kaksisuuntainen)

Linkitetyn luettelon perustoiminnot:

  • InsertAtEnd - Lisää tietyn elementin linkitetyn luettelon loppuun
  • InsertAtHead - Lisää tietyn elementin linkitetyn luettelon alkuun / päähän
  • Poista - Poistaa tietyn elementin linkitetystä luettelosta
  • DeleteAtHead - Poistaa linkitetyn luettelon ensimmäisen elementin
  • Haku - Palauttaa annetun elementin linkitetystä luettelosta
  • isEmpty - Palauttaa arvon true, jos linkitetty luettelo on tyhjä

Yleisesti kysytyt Linked List -haastattelukysymykset

  • Käännä linkitetty luettelo
  • Tunnista silmukka linkitetystä luettelosta
  • Palauta N-solmu linkitetyn luettelon päästä
  • Poista kaksoiskappaleet linkitetystä luettelosta

Kaaviot

Kaavio on joukko solmuja, jotka on kytketty toisiinsa verkon muodossa. Solmuja kutsutaan myös pisteiksi. Pari (x, y) kutsutaan reuna , joka osoittaa, että piste x on kytketty solmuun y . Reuna voi sisältää paino / kustannukset, mikä osoittaa kuinka paljon kustannuksia tarvitaan kulkemaan kärjestä x kohtaan y .

Kaavioiden tyypit:

  • Ohjaamaton kaavio
  • Ohjattu kaavio

Ohjelmointikielellä kaaviot voidaan esittää kahdella lomakkeella:

  • Adjacency Matrix
  • Adjacency-luettelo

Yleiset kaavion kulkualgoritmit:

  • Leveys ensimmäinen haku
  • Syvyys Ensimmäinen haku

Yleisesti kysytyt Graph-haastattelukysymykset

  • Toteuta Leveys ja syvyys -haku
  • Tarkista, onko kaavio puu tai ei
  • Laske kaavion reunojen määrä
  • Etsi lyhin polku kahden kärjen välillä

Puut

Puu on hierarkkinen tietorakenne, joka koostuu pisteistä (solmuista) ja niitä yhdistävistä reunoista. Puut ovat samanlaisia ​​kuin kaaviot, mutta avainkohta, joka erottaa puun kaaviosta, on se, että jaksoa ei voi olla puussa.

Puuta käytetään laajasti tekoälyssä ja monimutkaisissa algoritmeissa tehokkaan tallennusmekanismin tarjoamiseksi ongelmanratkaisuun.

Tässä on kuva yksinkertaisesta puusta ja puun tietorakenteessa käytetyistä perustermeistä:

Seuraavat ovat puulajeja:

  • Pohjoinen puu
  • Tasapainoinen puu
  • Binaarinen puu
  • Binaarinen hakupuu
  • AVL-puu
  • Punainen musta puu
  • 2–3 Puu

Edellä mainituista binääripuu ja binäärihakupuu ovat yleisimmin käytettyjä puita.

Puun haastattelukysymykset

  • Etsi binäärisen puun korkeus
  • Etsi k: n suurin arvo binäärihakupuusta
  • Etsi solmut k-etäisyydeltä juuresta
  • Etsi tietyn solmun esi-isät binääripuusta

Trie

Trie, joka tunnetaan myös nimellä "Prefix Trees", on puumainen tietorakenne, joka osoittautuu melko tehokkaaksi kieliin liittyvien ongelmien ratkaisemisessa. Se tarjoaa nopean haun, ja sitä käytetään enimmäkseen sanojen hakemiseen sanakirjasta, automaattisten ehdotusten tarjoamiseen hakukoneessa ja jopa IP-reititykseen.

Tässä on esimerkki siitä, kuinka kolme sanaa "ylhäältä", "siten" ja "heidän" tallennetaan Trie:

Sanat tallennetaan ylhäältä alas siten, että vihreät solmut “p”, “s” ja “r” tarkoittavat vastaavasti ”ylhäältä”, “siten” ja “niiden” loppua.

Yleisimmät Trie-haastattelukysymykset:

  • Laske Trie-sanojen kokonaismäärä
  • Tulosta kaikki Trieen tallennetut sanat
  • Lajittele matriisin elementit Trie: n avulla
  • Muodosta sanoja sanakirjasta käyttämällä Trieä
  • Rakenna T9-sanakirja

Hash-taulukko

Hajautus on prosessi, jota käytetään esineiden yksilöimiseen ja kunkin objektin tallentamiseen ennalta laskettuun yksilölliseen hakemistoon, jota kutsutaan sen "avaimeksi". Joten objekti tallennetaan "avain-arvo" -parin muodossa, ja tällaisten kohteiden kokoelmaa kutsutaan "sanakirjaksi". Jokaista objektia voidaan etsiä tällä näppäimellä. Hajautukseen perustuvia tietorakenteita on erilaisia, mutta yleisimmin käytetty tietorakenne on hash-taulukko .

Hash-taulukot toteutetaan yleensä taulukoiden avulla.

Hajautusdatarakenteen suorituskyky riippuu näistä kolmesta tekijästä:

  • Hash-toiminto
  • Hash-taulukon koko
  • Törmäysten käsittelymenetelmä

Tässä on esimerkki siitä, miten hajautus kartoitetaan taulukossa. Tämän taulukon indeksi lasketaan Hash-funktion avulla.

Yleisesti kysyttyjä Hashingin haastattelukysymyksiä

  • Löydä symmetriset parit taulukosta
  • Seuraa matkan täydellinen polku
  • Selvitä, onko matriisi toisen ryhmän osajoukko
  • Tarkista, ovatko annetut matriisit irti

Yllä olevat ovat kahdeksan tärkeintä tietorakennetta, jotka sinun tulisi ehdottomasti tietää ennen kuin kävelet koodaushaastatteluun.

Jos etsit resursseja tietorakenteista haastattelujen koodaamista varten, tutustu interaktiivisiin ja haasteisiin perustuviin kursseihin: Tietorakenteet haastattelujen koodaamiseen (Python, Java tai JavaScript).

Edistyneempiä kysymyksiä on artikkelissa Coderust 3.0: Nopeampi koodaushaastattelun valmistelu interaktiivisilla haasteilla ja visualisoinneilla.

Jos valmistaudut ohjelmistotekniikan haastatteluihin, tässä on kattava etenemissuunnitelma haastattelujen koodaamiseksi.

Onnea ja onnellista oppimista! :)