De bedste datastrukturer, du skal kende til dit næste kodningssamtale

Niklaus Wirth, en schweizisk computerforsker, skrev en bog i 1976 med titlen Algorithms + Data Structures = Programs.

40+ år senere gælder denne ligning stadig. Derfor er softwareudviklingskandidater nødt til at demonstrere deres forståelse af datastrukturer sammen med deres applikationer.

Næsten alle problemer kræver, at kandidaten demonstrerer en dyb forståelse af datastrukturer. Det betyder ikke noget, om du lige er uddannet (fra et universitet eller kodende bootcamp), eller om du har årtiers erfaring.

Nogle gange nævnes interviewspørgsmål eksplicit en datastruktur, for eksempel "givet et binært træ." Andre gange er det implicit, som "vi vil spore antallet af bøger, der er knyttet til hver forfatter."

At lære datastrukturer er afgørende, selvom du bare prøver at blive bedre på dit nuværende job. Lad os starte med at forstå det grundlæggende.

Hvad er en datastruktur?

Kort sagt, en datastruktur er en container, der gemmer data i et specifikt layout. Dette "layout" gør det muligt for en datastruktur at være effektiv i nogle operationer og ineffektiv i andre. Dit mål er at forstå datastrukturer, så du kan vælge den datastruktur, der er mest optimal for det aktuelle problem.

Hvorfor har vi brug for datastrukturer?

Da datastrukturer bruges til at gemme data i en organiseret form, og da data er den mest vigtige enhed inden for datalogi, er datastrukturenes sande værdi klar.

Uanset hvilket problem du løser, skal du på en eller anden måde beskæftige dig med data - uanset om det er en medarbejders løn, aktiekurser, en købmandsliste eller endda en simpel telefonkatalog.

Baseret på forskellige scenarier skal data gemmes i et specifikt format. Vi har en håndfuld datastrukturer, der dækker vores behov for at gemme data i forskellige formater.

Almindeligt anvendte datastrukturer

Lad os først liste de mest anvendte datastrukturer, og så dækker vi dem en efter en:

  1. Arrays
  2. Stakke
  3. Køer
  4. Tilknyttede lister
  5. Træer
  6. Grafer
  7. Forsøger (de er effektivt træer, men det er stadig godt at kalde dem separat).
  8. Hash-borde

Arrays

En matrix er den enkleste og mest anvendte datastruktur. Andre datastrukturer som stakke og køer stammer fra arrays.

Her er et billede af et simpelt array i størrelse 4, der indeholder elementer (1, 2, 3 og 4).

Hvert dataelement tildeles en positiv numerisk værdi kaldet indekset , der svarer til positionen for det pågældende element i arrayet. De fleste sprog definerer matrixens startindeks som 0.

Følgende er de to typer arrays:

  • Endimensionelle arrays (som vist ovenfor)
  • Multidimensionelle arrays (arrays inden for arrays)

Grundlæggende operationer på arrays

  • Indsæt - Indsætter et element i et givet indeks
  • Get - Returnerer elementet ved et givet indeks
  • Slet - Sletter et element i et givet indeks
  • Størrelse - Henter det samlede antal elementer i en matrix

Ofte stillede spørgsmål om Array-interview

  • Find det andet minimumselement i en matrix
  • Første ikke-gentagne heltal i en matrix
  • Flet to sorterede arrays
  • Omarranger positive og negative værdier i en matrix

Stakke

Vi er alle fortrolige med den berømte Fortryd- indstilling, som findes i næsten alle applikationer. Har du nogensinde spekuleret på, hvordan det fungerer? Ideen: du gemmer de tidligere tilstande for dit arbejde (som er begrænset til et bestemt nummer) i hukommelsen i en sådan rækkefølge, at den sidste vises først. Dette kan ikke gøres bare ved hjælp af arrays. Det er her stakken kommer til nytte.

Et virkeligt eksempel på Stack kan være en bunke bøger placeret i lodret rækkefølge. For at få bogen, der er et sted i midten, skal du fjerne alle bøgerne placeret oven på den. Sådan fungerer LIFO-metoden (Last In First Out).

Her er et billede af stakken, der indeholder tre dataelementer (1, 2 og 3), hvor 3 er øverst og først fjernes:

Grundlæggende funktioner i stack:

  • Push - Indsætter et element øverst
  • Pop - Returnerer det øverste element efter fjernelse fra stakken
  • isEmpty - Returnerer sandt, hvis stakken er tom
  • Top - Returnerer det øverste element uden at fjerne det fra stakken

Ofte stillede spørgsmål om Stack-interview

  • Evaluer postfix-udtryk ved hjælp af en stak
  • Sorter værdier i en stak
  • Kontroller afbalancerede parenteser i et udtryk

Køer

I lighed med Stack er kø en anden lineær datastruktur, der gemmer elementet sekventielt. Den eneste signifikante forskel mellem stak og kø er, at kø i stedet for at bruge LIFO-metoden implementerer FIFOmetode, som er en forkortelse for First in First Out.

Et perfekt eksempel på kø i det virkelige liv: en række mennesker, der venter på en billetboks. Hvis en ny person kommer, vil de slutte sig til linjen fra slutningen, ikke fra starten - og den person, der står forrest, vil være den første til at få billetten og dermed forlade linjen.

Her er et billede af kø, der indeholder fire dataelementer (1, 2, 3 og 4), hvor 1 er øverst og først fjernes:

Grundlæggende funktioner i kø

  • Enqueue () - Indsætter et element i slutningen af ​​køen
  • Dequeue () - Fjerner et element fra køens start
  • isEmpty () - Returnerer sandt, hvis køen er tom
  • Top () - Returnerer det første element i køen

Ofte stillede spørgsmål til køinterview

  • Implementere stakken ved hjælp af en kø
  • Vend de første k-elementer i en kø
  • Generer binære tal fra 1 til n ved hjælp af en kø

Tilknyttet liste

En sammenkædet liste er en anden vigtig lineær datastruktur, der måske ligner arrays i starten, men adskiller sig i hukommelsesallokering, intern struktur og hvordan grundlæggende operationer til indsættelse og sletning udføres.

En linket liste er som en kæde af noder, hvor hver node indeholder information som data og en markør til den efterfølgende node i kæden. Der er en hovedmarkør, der peger på det første element på den linkede liste, og hvis listen er tom, peger den simpelthen på null eller intet.

Tilknyttede lister bruges til at implementere filsystemer, hash-tabeller og nærhedslister.

Her er en visuel repræsentation af den interne struktur på en linket liste:

Følgende er de typer af sammenkædede lister:

  • Enkeltkædet liste (ensrettet)
  • Dobbeltkoblet liste (tovejs)

Grundlæggende operationer for sammenkædet liste

  • InsertAtEnd - Indsætter et givet element i slutningen af ​​den linkede liste
  • InsertAtHead - Indsætter et givet element i starten / hovedet af den linkede liste
  • Slet - Sletter et givet element fra den linkede liste
  • DeleteAtHead - Sletter det første element på den linkede liste
  • Søg - Returnerer det givne element fra en linket liste
  • isEmpty - Returnerer sandt, hvis den linkede liste er tom

Ofte stillede spørgsmål om linkede interviewinterviews

  • Vend en sammenkædet liste
  • Registrer sløjfe på en linket liste
  • Returner N-node fra slutningen på en linket liste
  • Fjern dubletter fra en linket liste

Grafer

En graf er et sæt noder, der er forbundet til hinanden i form af et netværk. Noder kaldes også hjørner. Et par (x, y) kaldes en kant , hvilket indikerer, at toppunkt x er forbundet med toppunkt y . En kant kan indeholde vægt / pris, der viser, hvor store omkostninger der kræves for at krydse fra toppunkt x til y .

Typer af grafer:

  • Udirigeret graf
  • Regisseret graf

På et programmeringssprog kan grafer repræsenteres ved hjælp af to former:

  • Adjacency Matrix
  • Tilstødelsesliste

Almindelige grafkørselsalgoritmer:

  • Bredde første søgning
  • Dybde første søgning

Ofte stillede spørgsmål om grafinterview

  • Implementere første søgning i bredde og dybde
  • Kontroller, om en graf er et træ eller ikke
  • Tæl antallet af kanter i en graf
  • Find den korteste sti mellem to hjørner

Træer

Et træ er en hierarkisk datastruktur bestående af hjørner (noder) og kanter, der forbinder dem. Træer ligner grafer, men nøglepunktet, der adskiller et træ fra grafen, er at en cyklus ikke kan eksistere i et træ.

Træer anvendes i vid udstrækning i kunstig intelligens og komplekse algoritmer for at give en effektiv lagermekanisme til problemløsning.

Her er et billede af et simpelt træ og grundlæggende terminologier, der bruges i trædatastruktur:

Følgende er typer træer:

  • N-ary træ
  • Balanceret træ
  • Binært træ
  • Binært søgetræ
  • AVL-træ
  • Rødt sort træ
  • 2–3 træ

Ud af ovenstående er Binary Tree og Binary Search Tree de mest anvendte træer.

Ofte stillede spørgsmål om træinterview

  • Find højden på et binært træ
  • Find kth maksimumsværdi i et binært søgetræ
  • Find noder i “k” afstand fra roden
  • Find forfædre til en given node i et binært træ

Trie

Trie, som også er kendt som “Prefix Trees”, er en trelignende datastruktur, der viser sig at være ret effektiv til at løse problemer relateret til strenge. Det giver hurtig hentning og bruges mest til at søge ord i en ordbog, levere automatiske forslag i en søgemaskine og endda til IP-routing.

Her er en illustration af, hvordan tre ord "top", "således" og "deres" er gemt i Trie:

Ordene er gemt øverst til nederst, hvor grønfarvede noder “p”, “s” og “r” angiver slutningen af ​​henholdsvis “top”, “således” og “deres”.

Ofte stillede spørgsmål om Trie-interview:

  • Tæl det samlede antal ord i Trie
  • Udskriv alle ord, der er gemt i Trie
  • Sorter elementer i en matrix ved hjælp af Trie
  • Form ord fra en ordbog ved hjælp af Trie
  • Byg en T9-ordbog

Hash-bord

Hashing er en proces, der bruges til entydigt at identificere objekter og gemme hvert objekt på et forudberegnet unikt indeks kaldet dets "nøgle". Så objektet gemmes i form af et "nøgleværdipar", og samlingen af ​​sådanne genstande kaldes en "ordbog". Hvert objekt kan søges ved hjælp af denne tast. Der er forskellige datastrukturer baseret på hashing, men den mest anvendte datastruktur er hash-tabellen .

Hash-tabeller implementeres generelt ved hjælp af arrays.

Udførelsen af ​​hashing-datastruktur afhænger af disse tre faktorer:

  • Hash-funktion
  • Størrelsen på Hash-bordet
  • Metode til håndtering af kollision

Her er en illustration af, hvordan hashen kortlægges i en matrix. Indekset for denne matrix beregnes gennem en Hash-funktion.

Ofte stillede spørgsmål om Hashing-interview

  • Find symmetriske par i en matrix
  • Spor hele rejsen
  • Find ud af, om et array er et undersæt af et andet array
  • Kontroller, om givne arrays er uensartede

Ovenstående er de øverste otte datastrukturer, som du helt sikkert bør kende, inden du går ind i et kodningssamtale.

Hvis du leder efter ressourcer til datastrukturer til kodning af interviews, skal du se på de interaktive og udfordringsbaserede kurser: Datastrukturer til kodningsinterviews (Python, Java eller JavaScript).

For mere avancerede spørgsmål, se Coderust 3.0: Hurtigere kodning af interviewforberedelse med interaktive udfordringer og visualiseringer.

Hvis du forbereder dig på software-engineering-interviews, her er en omfattende køreplan for at forberede dig på kodning af interviews.

Held og lykke og god læring! :)