de Fahim ul Haq

Niklaus Wirth, informatician elvețian, a scris în 1976 o carte intitulată Algoritmi + Structuri de date = Programe.

Peste 40 de ani mai târziu, acea ecuație este încă valabilă. De aceea, candidații la ingineria software trebuie să demonstreze înțelegerea structurilor de date împreună cu aplicațiile lor.

Aproape toate problemele impun candidatului să demonstreze o înțelegere profundă a structurilor de date. Nu contează dacă tocmai ați absolvit (de la o universitate sau bootcamp de codificare) sau dacă aveți zeci de ani de experiență.

Uneori, întrebările din interviu menționează în mod explicit o structură de date, de exemplu, „dat un arbore binar”. Alteori este implicit, cum ar fi „vrem să urmărim numărul cărților asociate fiecărui autor”.

Învățarea structurilor de date este esențială chiar dacă încercați doar să vă îmbunătățiți la locul de muncă actual. Să începem cu înțelegerea elementelor de bază.

ad-banner

Ce este o structură de date?

Pur și simplu, o structură de date este un container care stochează date într-un aspect specific. Acest „aspect” permite unei structuri de date să fie eficientă în unele operațiuni și ineficientă în altele. Scopul dvs. este să înțelegeți structurile de date, astfel încât să puteți alege structura de date care este cea mai optimă pentru problema în cauză.

De ce avem nevoie de structuri de date?

Deoarece structurile de date sunt folosite pentru a stoca date într-o formă organizată și, deoarece datele sunt entitatea cea mai importantă în informatică, adevărata valoare a structurilor de date este clară.

Indiferent ce problemă rezolvați, într-un fel sau altul trebuie să vă ocupați de date – fie că este vorba despre salariul unui angajat, prețurile acțiunilor, o listă de cumpărături sau chiar un simplu telefon.

Pe baza diferitelor scenarii, datele trebuie stocate într-un format specific. Avem o mână de structuri de date care acoperă nevoia noastră de a stoca date în diferite formate.

Structuri de date utilizate în mod obișnuit

Să listăm mai întâi cele mai utilizate structuri de date, apoi le vom acoperi unul câte unul:

  1. Matrice
  2. Stive
  3. Cozi
  4. Liste conectate
  5. Copaci
  6. Grafice
  7. Încearcă (sunt efectiv copaci, dar este totuși bine să-i chemi separat).
  8. Hash Tables

Matrice

O matrice este cea mai simplă și utilizată structură de date. Alte structuri de date cum ar fi stive și cozi sunt derivate din matrice.

Iată o imagine a unei matrice simple de dimensiunea 4, care conține elemente (1, 2, 3 și 4).

Structurile de date de top pe care ar trebui sa

Fiecărui element de date i se atribuie o valoare numerică pozitivă numită Index, care corespunde poziției acelui element din matrice. Majoritatea limbilor definesc indexul de pornire al matricei ca 0.

Următoarele sunt cele două tipuri de tablouri:

  • Tablouri unidimensionale (așa cum se arată mai sus)
  • Matrici multi-dimensionale (matrici în matrici)

Operațiuni de bază pe tablouri

  • Insert – Inserează un element la un index dat
  • Obține – Returnează elementul la un index dat
  • Șterge – Șterge un element la un index dat
  • Dimensiune – Obține numărul total de elemente dintr-o matrice

Întrebări frecvente la interviu Array

  • Găsiți al doilea element minim al unui tablou
  • Primii numere întregi care nu se repetă într-o matrice
  • Îmbinați două tablouri sortate
  • Rearanjați valorile pozitive și negative într-o matrice

Stive

Cu toții suntem familiarizați cu faimosul Anula opțiune, care este prezentă în aproape fiecare aplicație. V-ați întrebat vreodată cum funcționează? Ideea: stocați stările anterioare ale lucrării dvs. (care sunt limitate la un anumit număr) în memorie într-o astfel de ordine încât ultima să apară mai întâi. Acest lucru nu se poate face doar folosind tablouri. Acesta este locul în care Stack-ul este util.

Un exemplu real din Stack ar putea fi un teanc de cărți plasate într-o ordine verticală. Pentru a obține cartea care se află undeva la mijloc, va trebui să eliminați toate cărțile plasate deasupra ei. Așa funcționează metoda LIFO (Last In First Out).

Iată o imagine a stivei care conține trei elemente de date (1, 2 și 3), unde 3 este în partea de sus și va fi eliminat mai întâi:

1611711310 952 Structurile de date de top pe care ar trebui sa

Operațiuni de bază ale stivei:

  • Push – Inserează un element în partea de sus
  • Pop – Returnează elementul de sus după scoaterea din stivă
  • isEmpty – Returnează true dacă stiva este goală
  • Sus – Returnează elementul de sus fără a-l scoate din stivă

Întrebări frecvente ale interviului Stack

  • Evaluați expresia postfix utilizând o stivă
  • Sortați valorile într-un teanc
  • Verificați paranteze echilibrate într-o expresie

Cozi

Similar cu Stack, Coada este o altă structură de date liniară care stochează elementul într-o manieră secvențială. Singura diferență semnificativă între Stack și Queue este că, în loc să utilizeze metoda LIFO, Queue implementează FIFO metoda, care este prescurtarea pentru First in First Out.

Un exemplu perfect din viața reală de Coadă: un șir de oameni care așteaptă la un stand de bilete. Dacă vine o persoană nouă, se va alătura liniei de la sfârșit, nu de la început – și persoana care stă în față va fi prima care va primi biletul și, prin urmare, va părăsi linia.

Iată o imagine a cozii care conține patru elemente de date (1, 2, 3 și 4), unde 1 este în partea de sus și va fi eliminat mai întâi:

1611711310 395 Structurile de date de top pe care ar trebui sa

Operațiuni de bază ale cozii

  • Enqueue () – Inserează un element la sfârșitul cozii
  • Dequeue () – Elimină un element de la începutul cozii
  • isEmpty () – Returnează true dacă coada este goală
  • Sus () – Returnează primul element al cozii

Întrebări frecvente la interviu la Coadă

  • Implementați stiva utilizând o coadă
  • Inversați primele k elemente ale unei cozi
  • Generați numere binare de la 1 la n folosind o coadă

Listă legată

O listă legată este o altă structură de date liniară importantă care ar putea semăna cu matricele la început, dar diferă în ceea ce privește alocarea memoriei, structura internă și modul în care sunt efectuate operațiile de bază de inserare și ștergere.

O listă legată este ca un lanț de noduri, în care fiecare nod conține informații precum date și un pointer către nodul care urmează în lanț. Există un indicator de cap, care indică primul element al listei legate, iar dacă lista este goală, atunci pur și simplu indică nul sau nimic.

Listele legate sunt utilizate pentru a implementa sisteme de fișiere, tabele hash și liste de adiacență.

Iată o reprezentare vizuală a structurii interne a unei liste legate:

1611711311 161 Structurile de date de top pe care ar trebui sa

Următoarele sunt tipurile de liste legate:

  • Listă legată individual (unidirecțională)
  • Lista dublă legată (bidirecțională)

Operațiuni de bază ale Listei conectate:

  • InsertAtEnd – Inserează un element dat la sfârșitul listei conectate
  • InsertAtHead – Inserează un element dat la începutul / capul listei conectate
  • Șterge – Șterge un anumit element din lista legată
  • DeleteAtHead – Șterge primul element al listei conectate
  • Căutare – Returnează elementul dat dintr-o listă legată
  • este gol – Returnează adevărat dacă lista legată este goală

Întrebări frecvente ale interviului Listă legată

  • Inversați o listă legată
  • Detectați bucla într-o listă legată
  • Întoarceți al N-lea nod de la sfârșit într-o listă legată
  • Eliminați duplicatele dintr-o listă legată

Grafice

Un grafic este un set de noduri care sunt conectate între ele sub forma unei rețele. Nodurile sunt numite și vârfuri. A pereche (x, y) se numește an margine, ceea ce indică acel vârf X este conectat la vârf y. O margine poate conține greutate / cost, arătând cât cost este necesar pentru a trece de la vârful x la y.

1611711311 348 Structurile de date de top pe care ar trebui sa

Tipuri de grafice:

  • Grafic nedirectat
  • Grafic regizat

Într-un limbaj de programare, graficele pot fi reprezentate folosind două forme:

  • Matricea adiacenței
  • Lista adiacenței

Algoritmi comuni de parcurgere a graficului:

  • Lățimea întâi căutare
  • Căutare în adâncime

Întrebări frecvente despre interviuri cu Graph

  • Implementați Căutarea pentru lățime și adâncime
  • Verificați dacă un grafic este sau nu un copac
  • Numărați numărul de muchii dintr-un grafic
  • Găsiți cea mai scurtă cale între două vârfuri

Copaci

Un copac este o structură de date ierarhică formată din vârfuri (noduri) și margini care le conectează. Copacii sunt similari graficelor, dar punctul cheie care diferențiază un copac de grafic este că un ciclu nu poate exista într-un copac.

Copacii sunt folosiți pe scară largă în inteligența artificială și în algoritmi complexi pentru a oferi un mecanism de stocare eficient pentru rezolvarea problemelor.

Iată o imagine a unui arbore simplu și terminologiile de bază utilizate în structura datelor arborelui:

1611711311 324 Structurile de date de top pe care ar trebui sa

Următoarele sunt tipurile de copaci:

  • N-ary Tree
  • Copac echilibrat
  • Arborele binar
  • Arborele de căutare binar
  • Arborele AVL
  • Copac negru roșu
  • 2-3 Arbore

Din cele de mai sus, arborele binar și arborele de căutare binar sunt arborii cei mai des folosiți.

Întrebări frecvente despre interviul Tree

  • Găsiți înălțimea unui copac binar
  • Găsiți valoarea maximă a k-a într-un arbore de căutare binar
  • Găsiți noduri la distanța „k” de rădăcină
  • Găsiți strămoșii unui nod dat într-un copac binar

Trie

Trie, care este, de asemenea, cunoscut sub numele de „Prefix Trees”, este o structură de date în formă de copac, care se dovedește a fi destul de eficientă pentru rezolvarea problemelor legate de șiruri. Acesta oferă regăsire rapidă și este utilizat în principal pentru căutarea cuvintelor într-un dicționar, oferind sugestii automate într-un motor de căutare și chiar pentru rutare IP.

Iată o ilustrare a modului în care sunt stocate trei cuvinte „sus”, „astfel” și „lor” în Trie:

1611711311 524 Structurile de date de top pe care ar trebui sa

Cuvintele sunt stocate de sus în jos, în cazul în care nodurile de culoare verde „p”, „s” și „r” indică sfârșitul „top”, „astfel” și „lor”.

Întrebări frecvente la interviu cu Trie:

  • Numărați numărul total de cuvinte din Trie
  • Imprimați toate cuvintele stocate în Trie
  • Sortați elementele unui tablou folosind Trie
  • Formați cuvinte dintr-un dicționar folosind Trie
  • Construiți un dicționar T9

Hash Table

Hashing-ul este un proces utilizat pentru identificarea obiectelor în mod unic și stocarea fiecărui obiect la un index unic precalculat numit „cheia” acestuia. Deci, obiectul este stocat sub forma unei perechi „cheie-valoare”, iar colecția de astfel de articole se numește „dicționar”. Fiecare obiect poate fi căutat folosind acea cheie. Există diferite structuri de date bazate pe hashing, dar cea mai frecvent utilizată structură de date este masa de hash.

Tabelele Hash sunt în general implementate utilizând matrici.

Performanța structurii datelor de hashing depinde de acești trei factori:

  • Funcția Hash
  • Dimensiunea tabelului Hash
  • Metoda de manipulare a coliziunilor

Iată o ilustrare a modului în care hash-ul este mapat într-o matrice. Indicele acestei matrice este calculat printr-o funcție Hash.

1611711312 116 Structurile de date de top pe care ar trebui sa

Întrebări frecvente la interviu cu Hashing

  • Găsiți perechi simetrice într-o matrice
  • Urmăriți calea completă a unei călătorii
  • Găsiți dacă un tablou este un subset al unui alt tablou
  • Verificați dacă matricile date sunt disjuncte

Cele de mai sus sunt primele opt structuri de date pe care ar trebui să le cunoașteți cu siguranță înainte de a intra într-un interviu de codare.

Dacă sunteți în căutarea de resurse privind structurile de date pentru codificarea interviurilor, consultați cursurile interactive și bazate pe provocări: Structuri de date pentru codificarea interviurilor (Piton, Java, sau JavaScript).

Pentru întrebări mai avansate, uitați-vă la Coderust 3.0: Pregătirea mai rapidă a interviului de codificare cu provocări interactive și vizualizări.

Dacă vă pregătiți pentru un interviu de inginerie software, iată un foaie de parcurs cuprinzătoare pentru pregătirea codificării Interviurilor.

Mult succes si invatare fericita! 🙂