Cele mai bune 30 de întrebări și răspunsuri la interviu cu structuri de date și algoritm [pentru cei proaspăți și cu experiență]

Structurile și algoritmii de date sunt printre cele mai importante subiecte din lumea informatică și inginerie. Dacă vă prezentați la un interviu de inginerie software, puteți fi sigur că vă confruntați cu o rundă de întrebări special dedicate structurilor de date și algoritmilor – atât de cruciale sunt acestea!

Algoritmii se află la baza a tot ceea ce se întâmplă în informatică și în știința datelor. De la Machine Learning la AI la Blockchain – toate tehnologiile rulează pe algoritmi. Și algoritmii au nevoie de structuri de date pentru a funcționa. Astfel, cunoștințele combinate despre Structuri de Date și Algoritmi vă pot ajuta să vă evidențiați din mulțime în timpul interviului.

Cu toate acestea, provocarea este că DSA este un domeniu extins. Aici, învățarea nu se oprește niciodată și există întotdeauna o nouă dezvoltare pe care trebuie să le înțelegi. Deși îmbunătățirea continuă a competențelor este obligatorie atunci când aveți de-a face cu structurile de date și algoritmii, astăzi vom analiza câteva elemente fundamentale ale DSA care vă vor ajuta să obțineți interviuri tehnice.

Structuri de date și algoritmi de top Întrebări și răspunsuri la interviu

1. Ce înțelegeți despre „Structurile de date”?

Structurile de date pot fi definite ca tehnici utilizate pentru definirea, stocarea și accesarea sistematică a datelor. Ele formează cea mai importantă componentă a oricărui algoritm. În funcție de tipul de structuri de date, acestea stochează diferite tipuri de date și sunt accesibile în moduri diferite. Pentru ca un algoritm să returneze un rezultat, trebuie să opereze și să manipuleze un set de structuri de date într-un mod organizat și eficient pentru a ajunge la rezultatul final.

2. Cum puteți face diferența între o structură de fișiere și o structură de date?

În Structuri de fișiere, datele sunt stocate pe discuri urmând politici standard de stocare a fișierelor și nu sunt compatibile cu aplicații externe, terțe. În Data Structures, pe de altă parte, datele sunt stocate atât pe disc, cât și pe RAM în politici de stocare personalizate, iar acestea sunt foarte compatibile cu aplicațiile externe.

3. Care sunt tipurile largi de structuri de date?

Structurile de date pot fi împărțite în linii mari în două categorii:

• Linear: în aceasta, toate elementele sunt stocate secvenţial, iar recuperarea are loc liniar. Aranjamentul este neierarhic și fiecare element are un succesor și un predecesor. Exemplu – tablouri, liste legate, stive, cozi etc.
• Neliniar: Aici stocarea nu are loc într-o secvență liniară – adică, toate elementele nu au neapărat un singur succesor și predecesor. În schimb, elementele din structurile de date neliniare sunt conectate la două sau mai multe elemente într-o manieră neliniară. Exemplu – Copaci, Grafice, grămezi.

4. Care sunt câteva domenii cheie de utilizare ale Structurii de date?

Structurile de date sunt destul de necesare în toate domeniile de calcul la care vă puteți gândi, în special algoritmi și optimizarea algoritmilor. Iată câteva alte domenii în care structurile de date sunt utilizate pe scară largă:

• Proiectarea sistemului de operare
• Analiza numerica
• Învățare automată și inteligență artificială
• Proiectarea și dezvoltarea compilatorului
• Managementul bazei de date
• Analiza lexicală
• Programare grafică
• Algoritmi de căutare și sortare și multe altele.

5. Explicați structura datelor stivei și menționați zonele de utilizare ale acesteia.

Stiva este pur și simplu o listă ordonată care permite inserarea și ștergerea doar de la unul dintre capete – care este cunoscut sub numele de „sus”. Este o structură de date recursivă care are un indicator către elementele sale „de sus” care ne informează despre elementul cel mai de sus al stivei. Pe baza strategiei de recuperare a elementelor, Stack este cunoscut și ca Last-In-First-Out, deoarece ultimul element împins în stivă va fi în partea de sus și va fi primul care va fi scos. Iată câteva utilizări ale structurii de date stive:

• Întoarcere înapoi
• Gestionarea memoriei
• Funcția returnare și apelare
• Evaluarea expresiei

6. Care sunt operațiunile care pot fi efectuate pe o stivă?

Structura de date Stack acceptă următoarele trei operațiuni:

• push() — pentru a introduce un element în poziția de sus a Stivei.
• pop() — pentru a scoate un element din partea de sus a Stivei.
• peek() — pentru a verifica doar elementul prezent în partea de sus a stivei fără a-l scoate din stivă.

7. Ce înțelegeți despre expresiile Postfix?

Expresia Postfix este o expresie în care operatorii urmează operanzii. Acest lucru este extrem de benefic în termeni de calcul, deoarece nu necesită nicio grupare a sub-expresiilor în paranteze și nici măcar nu ia în considerare prioritatea operatorului. Expresia a+b este pur și simplu reprezentată ca ab+ în postfix.

8. Cum sunt stocate elementele matricei 2D în memorie?

Elementele unei matrice 2-D pot fi stocate în memorie în oricare dintre cele două moduri:

• Row-Major: în această metodă, mai întâi toate rândurile matricei sunt stocate contiguu în memorie. Mai întâi, primul rând este stocat complet, apoi al doilea rând și așa mai departe până la ultimul.
• Column-Major: În aceasta, toate coloanele matricei sunt stocate continuu în memorie. Mai întâi, prima coloană este stocată complet, apoi a doua coloană și așa mai departe.

9. Definiți structura de date a listei legate.

Listele legate sunt colecții de noduri – care sunt obiecte stocate aleatoriu. Fiecare nod are două elemente interne – un câmp de date și un câmp de legătură. Câmpul Date conține valoarea pe care o are acel nod, în timp ce câmpul Link are un pointer către următorul nod la care acesta este legat. În funcție de situație, o listă legată poate fi considerată atât ca o structură de date liniară, cât și ca neliniară.

10. În ce fel sunt mai bune listele legate decât matricele?

Listele legate sunt mai bune decât matricele în următoarele moduri:

• Dimensiunile matricelor sunt fixate în timpul execuției și nu pot fi modificate ulterior, dar listele conectate pot fi extinse în timp real, conform cerințelor.
• Listele legate nu sunt stocate contiguu în memorie, ca urmare, sunt mult mai eficiente în memorie decât matricele care sunt stocate static.
• Numărul de elemente care pot fi stocate în orice Listă Linked este limitat doar la spațiul de memorie disponibil, în timp ce numărul de elemente este limitat de dimensiunea matricei.

11. În limbajul de programare C, ce indicator ați folosi pentru a implementa o listă eterogenă legată?

Listele legate eterogene, după cum sugerează și numele, dețin diferite tipuri de date. Ca rezultat, nu este posibil să folosiți indicatori obișnuiți aici. Deci, indicatorii Void sunt utilizați în mod normal într-un astfel de scenariu, deoarece sunt capabili să indice orice tip de valoare.

12. Ce este o listă dublu legată?

După cum sugerează și numele, o listă dublu legată este o listă legată care are noduri legate atât la nodurile succesoare, cât și la cele precedente. Ca rezultat, nodurile Listei dublu legate au trei, nu două, câmpuri:

• Câmpul de date
• Următorul indicator (pentru a indica următorul nod)
• Indicatorul anterior (pentru a indica nodul anterior)

13. Explicați structura datelor din coadă cu unele dintre aplicațiile sale.

O coadă este o listă ordonată care permite inserarea și ștergerea elementelor nu de la unul, ci de la două capete – numite REAR și FRONT. Introducerea are loc de la capătul FRONT în timp ce ștergerea de la capătul SPATE. Ca urmare a acestui fapt, coada este adesea numită First-In-First-Out (FIFO). Iată câteva aplicații răspândite ale Cozilor ca structură de date:

• Pentru listele de așteptare pentru resurse partajate individual, cum ar fi CPU, imprimantă, disc etc.
• Pentru transferul asincron de date, exemplu fișier IO, socket, conducte.
• Ca tampon în majoritatea aplicațiilor media player.
• În sistemele de operare pentru gestionarea întreruperilor.

14. Puteți enumera câteva dezavantaje ale implementării Queues folosind matrice?

Există în principal două dezavantaje care apar la implementarea Cozilor cu matrice:

• Gestionarea greșită a memoriei, deoarece tablourile sunt structuri de date statice, astfel încât implementarea Cozilor cu matrice elimină o mulțime de funcționalități ale Cozilor.
• Problemă cu dimensiunea, deoarece dimensiunile matricei sunt definite în timpul definirii matricei. Deci, dacă vrem să adăugăm mai multe elemente la coada noastră decât dimensiunea matricei, nu va fi posibil.

15. Ce condiții trebuie îndeplinite pentru ca un element să fie introdus într-o coadă circulară?

Iată câteva condiții relevante privind inserarea în cozi circulare:

• Dacă (spate + 1)%maxsize == față -> asta înseamnă că coada este plină -> nu mai este posibilă introducerea.
• Dacă spate != max – 1, valoarea spate este crescută la dimensiunea maximă și o nouă valoare va fi inserată la capătul din spate.
• Dacă față != 0 și spate == max -1 –> înseamnă că coada nu este plină. Deci, valoarea rear este setată la 0 și un nou element este inserat în capătul din spate al cozii circulare.

16. Ce este o coadă?

Coada dublu sau deque este un set ordonat de elemente care facilitează inserarea și ștergerea de la ambele capete – din spate și din față. Drept urmare, aceasta este chiar mai flexibilă decât structura de date a cozii.

17. Definiți structura de date a arborelui și enumerați câteva tipuri de arbori.

Arborele este o structură de date neliniară, recursivă, care conține diverse noduri. Un anumit nod este desemnat ca rădăcină a arborelui de unde apar toate celelalte noduri. În afară de rădăcină, toate celelalte noduri sunt numite noduri copil. Există, în general, următoarele tipuri de structuri de date arbore:

• Copaci generali
• Arbori binari
• Arbori de căutare binari
• Păduri
• Arborele de expresie
• Arborele turneului

18. Cum funcționează sortarea cu bule?

Bubble Sort este unul dintre cei mai folosiți algoritmi de sortare și este folosit cu matrice prin compararea elementelor adiacente și schimbul de poziții pe baza valorilor lor. Se numește sortare cu bule, deoarece vizualizarea modului în care funcționează este ca bulele care plutesc din partea de sus a apei și entitățile mai mari care se scufundă.

Citiți: Structuri de date în C și Cum se utilizează?

19. Care este cel mai rapid algoritm de sortare disponibil?

Există mulți algoritmi de sortare diferiți, cum ar fi sortarea prin îmbinare, sortarea rapidă, sortarea cu bule și multe altele. Dintre acestea, nu putem alege un algoritm specific care este în mod obiectiv cel mai rapid, deoarece performanța lor variază foarte mult în funcție de datele de intrare, de reacția după ce algoritmul a procesat datele și de modul în care sunt stocate.

20. Ce sunt arborii binari?

Arborii binari sunt tipuri speciale de arbori în care fiecare nod poate avea CEL MULT doi copii. Pentru a ușura lucrurile, arborii binari sunt, în general, împărțiți în trei seturi disjunse - nodul rădăcină, subarborele din dreapta și subarborele din stânga.

21. Cum pot fi utilizați arborii AVL în diferite operațiuni în comparație cu BST?

Copacii AVL sunt copaci cu înălțime echilibrată, așa că nu permit ca copacul să fie înclinat din nicio parte. Timpul necesar pentru toate operațiile efectuate pe BST de înălțime h este O(h). Cu toate acestea, acesta poate continua să fie O(n) în cel mai rău scenariu – în care BST devine denaturată. AVL ajută la eliminarea acestei limitări prin restricționarea înălțimii copacului. Procedând astfel, impune o limită superioară tuturor operațiilor să fie maximă de O(log n) unde n = numărul de noduri.

22. Care sunt proprietățile unui B-Tree?

Un arbore B de ordinul m conține următoarele proprietăți:

• Toate proprietățile unui arbore M-way.
• Fiecare nod al arborelui B va avea maximum m copii.
• Fiecare nod, cu excepția rădăcinii și a frunzei, va avea cel puțin m / 2 copii.
• Nodul rădăcină trebuie să aibă cel puțin 2 noduri copil.
• Toate nodurile frunzelor trebuie să se afle la același nivel orizontal.

23. Ce înțelegeți despre Structura datelor grafice?

Structura de date Graph (G) poate fi definită ca o mulțime ordonată G(V,E) unde V reprezintă mulțimea de vârfuri și E este muchiile care formează conexiunile. Practic, un grafic poate fi gândit ca un arbore ciclic în care nodurile pot menține relații complexe între ele și nu doar relații părinte-copil.

24. Faceți diferența între ciclu, cale și circuit cu referire la Structura de date grafică.

Diferențele dintre ciclu, cale și circuit sunt următoarele:

• Un patch este o ordine de vârfuri învecinate conectate prin muchii fără nicio restricție.
• Un ciclu este o cale închisă în care vârful inițial este același cu vârful final. Într-un ciclu, nicio verte anume nu poate fi vizitată de două ori.
• Un circuit, ca un ciclu, este o cale închisă cu vârful inițial la fel cu vârful final. Cu toate acestea, orice vârf particular dintr-un circuit poate fi vizitat de mai multe ori.

25. Cum funcționează algoritmul lui Kruskal?

Algoritmul lui Kruskal consideră graficul ca o pădure și fiecare dintre nodurile sale ca un arbore individual. Se spune că un arbore se conectează la un alt arbore dacă și numai dacă are cel mai mic cost dintre toate opțiunile și nu încalcă nicio proprietate a unui arbore de întindere minim (MST).

Înrudit: Arborele binar în structura datelor

26. Cum găsește algoritmul lui Prim arborele de întindere?

Algoritmul lui Prim funcționează considerând nodurile ca arbori unici. Apoi, continuă să adauge noi noduri la arborele de întindere din graficul dat, care trebuie convertite în arborele de întindere necesar.

27. Ce este un arbore de întindere minim (MST)?

MST-urile, în graficele ponderate, sunt arbori care au greutate minimă, dar se întind pe toate vârfurile.

28. Ce este o funcție recursivă?

Prin definiție, o funcție recursivă se autoapelează sau apelează direct o funcție care o apelează. Fiecare funcție recursivă are niște criterii de bază, după care funcția încetează să se mai apeleze.

29. Care este tehnica de căutare prin interpolare?

Tehnica de căutare prin interpolare este o modificare față de metoda de căutare binară. Algoritmul de căutare prin interpolare funcționează pe poziția de sondare a valorilor dorite.

30. Ce este hashingul?

Hashing este o tehnică foarte utilă folosită pentru a converti o serie de perechi cheie-valoare în indecși ai unui tablou. Tabelele hash sunt utile în timp ce creează stocarea de date asociativă în care indexul de date poate fi găsit cu ușurință doar furnizând perechea cheie-valoare!

În concluzie

Structurile de date sunt cu adevărat fundamentul a tot ceea ce se întâmplă în informatică. Chiar și aplicațiile mai complexe ale informaticii, adică Data Science, Machine Learning, Artificial Intelligence, IoT sunt toate construite pe baza structurilor și algoritmilor de date.

Așadar, dacă ești un începător care dorește să facă o carieră în oricare dintre domeniile new-age, ți se recomandă să începi prin a stăpâni Structurile și algoritmii de date. Sau, altfel, puteți consulta și cursul nostru despre Programul Executive PG în Știința datelor, care este conceput pentru începători. Învățați de la zero și deveniți un expert în știința datelor. Înscrie-te astăzi!