De beste datastrukturene du bør vite for ditt neste kodingsintervju

Niklaus Wirth, en sveitsisk informatiker, skrev en bok i 1976 med tittelen Algorithms + Data Structures = Programs.

40+ år senere holder likningen fremdeles til. Derfor må kandidatene til programvareteknikk demonstrere sin forståelse av datastrukturer sammen med applikasjonene.

Nesten alle problemer krever at kandidaten viser en dyp forståelse av datastrukturer. Det spiller ingen rolle om du nettopp har uteksaminert (fra et universitet eller kodende bootcamp), eller om du har flere tiårs erfaring.

Noen ganger nevner intervjuspørsmål eksplisitt en datastruktur, for eksempel "gitt et binært tre." Andre ganger er det implisitt, som "vi vil spore antall bøker som er knyttet til hver forfatter."

Å lære datastrukturer er viktig, selv om du bare prøver å bli bedre i din nåværende jobb. La oss begynne med å forstå det grunnleggende.

Hva er en datastruktur?

Enkelt sagt, en datastruktur er en container som lagrer data i en bestemt layout. Dette "oppsettet" gjør at datastrukturen kan være effektiv i noen operasjoner og ineffektiv i andre. Målet ditt er å forstå datastrukturer slik at du kan velge datastrukturen som er mest optimal for det aktuelle problemet.

Hvorfor trenger vi datastrukturer?

Siden datastrukturer brukes til å lagre data i en organisert form, og siden data er den mest avgjørende enheten innen datavitenskap, er den virkelige verdien av datastrukturer tydelig.

Uansett hvilket problem du løser, må du på en eller annen måte håndtere data - enten det er en ansattes lønn, aksjekurser, en dagligvareliste eller til og med en enkel telefonkatalog.

Basert på forskjellige scenarier, må data lagres i et bestemt format. Vi har en håndfull datastrukturer som dekker vårt behov for å lagre data i forskjellige formater.

Vanlige datastrukturer

La oss først liste opp de mest brukte datastrukturene, og så vil vi dekke dem en etter en:

  1. Arrays
  2. Stabler
  3. Køer
  4. Koblede lister
  5. Trær
  6. Grafer
  7. Forsøker (de er effektivt trær, men det er fortsatt bra å kalle dem ut separat).
  8. Hash-bord

Arrays

En matrise er den enkleste og mest brukte datastrukturen. Andre datastrukturer som stabler og køer kommer fra matriser.

Her er et bilde av et enkelt utvalg av størrelse 4, som inneholder elementer (1, 2, 3 og 4).

Hvert dataelement tildeles en positiv numerisk verdi kalt indeksen , som tilsvarer posisjonen til det elementet i matrisen. De fleste språk definerer startindeksen til matrisen som 0.

Følgende er de to typene matriser:

  • Endimensjonale matriser (som vist ovenfor)
  • Flerdimensjonale matriser (matriser innenfor matriser)

Grunnleggende operasjoner på arrays

  • Insert - Setter inn et element i en gitt indeks
  • Get - Returnerer elementet ved en gitt indeks
  • Slett - Sletter et element i en gitt indeks
  • Størrelse - Får det totale antallet elementer i en matrise

Vanlige spørsmål om Array-intervju

  • Finn det andre minimumselementet i en matrise
  • Første ikke-gjentatte heltall i en matrise
  • Slå sammen to sorterte matriser
  • Omorganisere positive og negative verdier i en matrise

Stabler

Vi er alle kjent med det berømte Angre- alternativet, som finnes i nesten alle applikasjoner. Har du noen gang lurt på hvordan det fungerer? Ideen: du lagrer de tidligere tilstandene til arbeidet ditt (som er begrenset til et bestemt nummer) i minnet i en slik rekkefølge at den siste vises først. Dette kan ikke gjøres bare ved å bruke matriser. Det er der Stack kommer godt med.

Et ekte eksempel på Stack kan være en bunke bøker plassert i vertikal rekkefølge. For å få boken som er et sted i midten, må du fjerne alle bøkene som er plassert på toppen av den. Slik fungerer LIFO (Last In First Out) -metoden.

Her er et bilde av stabelen som inneholder tre dataelementer (1, 2 og 3), hvor 3 er øverst og vil bli fjernet først:

Grunnleggende operasjoner av stack:

  • Push - Setter inn et element øverst
  • Pop - Returnerer toppelementet etter fjerning fra bunken
  • isEmpty - Returnerer sant hvis bunken er tom
  • Topp - Returnerer toppelementet uten å fjerne det fra bunken

Vanlige spørsmål om Stack-intervju

  • Evaluer postfix-uttrykk ved hjelp av en stabel
  • Sorter verdier i en bunke
  • Kontroller balanserte parenteser i et uttrykk

Køer

I likhet med Stack er kø en annen lineær datastruktur som lagrer elementet på en sekvensiell måte. Den eneste signifikante forskjellen mellom Stack og Queue er at i stedet for å bruke LIFO-metoden, implementerer Queue FIFOmetode, som er en forkortelse for First in First Out.

Et perfekt eksempel på kø i virkeligheten: en rekke mennesker som venter på en billettbås. Hvis en ny person kommer, vil de slutte seg til linjen fra slutten, ikke fra starten - og personen som står foran vil være den første som får billetten og dermed forlater linjen.

Her er et bilde av kø som inneholder fire dataelementer (1, 2, 3 og 4), hvor 1 er øverst og først blir fjernet:

Grunnleggende operasjoner i kø

  • Enqueue () - Setter inn et element til slutten av køen
  • Dequeue () - Fjerner et element fra starten av køen
  • isEmpty () - Returnerer sant hvis køen er tom
  • Topp () - Returnerer det første elementet i køen

Vanlige spørsmål om køintervju

  • Implementere stabelen ved hjelp av en kø
  • Omvend de første k-elementene i en kø
  • Generer binære tall fra 1 til n ved hjelp av en kø

Koblet liste

En koblet liste er en annen viktig lineær datastruktur som kan se ut som arrays i begynnelsen, men forskjellig i minnetildeling, intern struktur og hvordan grunnleggende operasjoner for innsetting og sletting utføres.

En koblet liste er som en kjede av noder, der hver node inneholder informasjon som data og en peker til den etterfølgende noden i kjeden. Det er en hodepeker som peker på det første elementet i den koblede listen, og hvis listen er tom, peker den ganske enkelt mot null eller ingenting.

Tilknyttede lister brukes til å implementere filsystemer, hashtabeller og nærhetslister.

Her er en visuell fremstilling av den interne strukturen til en koblet liste:

Følgende er typer lenkede lister:

  • Enkelinket liste (ensrettet)
  • Dobbeltkoblet liste (toveis)

Grunnleggende operasjoner for koblet liste:

  • InsertAtEnd - Setter inn et gitt element på slutten av den koblede listen
  • InsertAtHead - Setter inn et gitt element i starten / hodet til den koblede listen
  • Slett - Sletter et gitt element fra den koblede listen
  • DeleteAtHead - Sletter det første elementet i den koblede listen
  • Søk - Returnerer det gitte elementet fra en koblet liste
  • isEmpty - Returnerer sant hvis den koblede listen er tom

Vanlige spørsmål til spørsmål om koblede lister

  • Snu en koblet liste
  • Oppdag løkke i en koblet liste
  • Returner Nth node fra slutten i en koblet liste
  • Fjern duplikater fra en koblet liste

Grafer

En graf er et sett med noder som er koblet til hverandre i form av et nettverk. Noder kalles også hjørner. Et par (x, y) kalles en kant , som indikerer at toppunkt x er koblet til toppunkt y . En kant kan inneholde vekt / kostnad, som viser hvor mye kostnad som kreves for å krysse fra toppunkt x til y .

Typer av grafer:

  • Udirigert graf
  • Regissert graf

I et programmeringsspråk kan grafer vises med to former:

  • Adjacency Matrix
  • Tilstøtningsliste

Vanlige grafkryssingsalgoritmer:

  • Bredde første søk
  • Dybde første søk

Vanlige spørsmål om grafintervju

  • Implementere bredde og dybde første søk
  • Sjekk om en graf er et tre eller ikke
  • Tell antall kanter i en graf
  • Finn den korteste stien mellom to hjørner

Trær

Et tre er en hierarkisk datastruktur som består av hjørner (noder) og kanter som forbinder dem. Trær ligner på grafer, men nøkkelpunktet som skiller et tre fra grafen er at en syklus ikke kan eksistere i et tre.

Trær brukes mye i kunstig intelligens og komplekse algoritmer for å gi en effektiv lagringsmekanisme for problemløsning.

Her er et bilde av et enkelt tre og grunnleggende terminologier som brukes i tredatastrukturen:

Følgende er typer trær:

  • N-ary Tree
  • Balansert tre
  • Binært tre
  • Binært søketre
  • AVL Tree
  • Rødt svart tre
  • 2–3 Tre

Av det ovennevnte er Binary Tree og Binary Search Tree de mest brukte trærne.

Vanlige spørsmål om treintervju

  • Finn høyden på et binært tre
  • Finn kth maksimumsverdi i et binært søketre
  • Finn noder i “k” avstand fra roten
  • Finn forfedre til en gitt node i et binært tre

Trie

Trie, som også er kjent som "Prefix Trees", er en trelignende datastruktur som viser seg å være ganske effektiv for å løse problemer knyttet til strenger. Det gir rask gjenfinning, og brukes mest til å søke etter ord i en ordbok, gi automatiske forslag i en søkemotor, og til og med for IP-ruting.

Her er en illustrasjon av hvordan tre ord "topp", "dermed" og "deres" er lagret i Trie:

Ordene lagres øverst til nederst, der grønne noder "p", "s" og "r" indikerer slutten på henholdsvis "topp", "dermed" og "deres".

Vanlige spørsmål om Trie-intervju:

  • Telle totalt antall ord i Trie
  • Skriv ut alle ordene som er lagret i Trie
  • Sorter elementer i en matrise ved hjelp av Trie
  • Form ord fra en ordbok ved hjelp av Trie
  • Bygg en T9-ordbok

Hash-bord

Hashing er en prosess som brukes til å identifisere objekter og lagre hvert objekt på en forhåndsberegnet unik indeks som kalles "nøkkel". Så objektet lagres i form av et "nøkkelverdi" -par, og samlingen av slike gjenstander kalles en "ordbok". Hvert objekt kan søkes med den tasten. Det er forskjellige datastrukturer basert på hashing, men den mest brukte datastrukturen er hash-tabellen .

Hash-tabeller implementeres vanligvis ved hjelp av arrays.

Ytelsen til hashing datastruktur avhenger av disse tre faktorene:

  • Hash-funksjon
  • Størrelse på Hash-bordet
  • Kollisjonshåndteringsmetode

Her er en illustrasjon av hvordan hashen er kartlagt i en matrise. Indeksen til denne matrisen beregnes gjennom en Hash-funksjon.

Vanlige spørsmål om Hashing-intervju

  • Finn symmetriske par i en matrise
  • Spor hele veien for en reise
  • Finn ut om en matrise er en delmengde av en annen matrise
  • Sjekk om gitte matriser ikke er sammenhengende

Ovenstående er de åtte beste datastrukturene som du absolutt bør vite før du går inn i et kodingsintervju.

Hvis du leter etter ressurser på datastrukturer for kodingsintervjuer, kan du se på de interaktive og utfordringsbaserte kursene: Datastrukturer for kodingsintervjuer (Python, Java eller JavaScript).

For mer avanserte spørsmål, se Coderust 3.0: Raskere kodingsintervjuforberedelse med interaktive utfordringer og visualiseringer.

Hvis du forbereder deg på et programvareteknisk intervju, er det en omfattende veikart for å forberede deg på kodende intervjuer.

Lykke til og lykkelig læring! :)