...
← Blog Interviuri

Structuri de date pe care trebuie să le știi la interviu: top 10

Simbolul cursului de algoritmi pe fundal roz, pentru o listă cu structuri de date de interviu

Structurile de date care apar cel mai des la interviul tehnic sunt zece: tabloul (lista), șirul de caractere, hash map-ul (dicționarul), setul, stiva, coada, lista înlănțuită, heap-ul, arborele și graful. La un interviu de junior, cele mai multe probleme se rezolvă cu primele șase; ultimele patru apar mai ales la firmele care pun accent pe algoritmi.

Structurile de date, cu exemple interactive: structuri de date explicate, stiva și coada și arbori binari.

Pentru fiecare structură afli ce este, cât costă operațiile de bază, la ce problemă clasică o folosești și ce nivel are. Trei dintre probleme le ai rezolvate în Python, cu cod care rulează, plus un tabel cu complexitățile pe care e bine să le știi pe de rost.

Ce sunt structurile de date și de ce le cer la interviu

O structură de date este un mod de a organiza informațiile în memorie astfel încât anumite operații să fie rapide: căutarea, adăugarea, ștergerea sau găsirea celui mai mare element. Aceeași listă de 100.000 de clienți poate fi căutată în 100.000 de pași sau într-unul singur, în funcție de structura aleasă.

La interviu nu ți se cere să recitești definiții. Ți se dă o problemă și se urmărește dacă recunoști structura potrivită și știi să explici de ce. De aceea, pentru fiecare structură de mai jos contează două lucruri: ce operații face repede și ce tip de problemă „strigă” după ea. Costul operațiilor se exprimă în notația O mare, explicată pe larg în articolul despre complexitatea algoritmilor (Big O).

Exemplele sunt în Python, limbajul ales de mulți candidați la interviuri pentru că se scrie repede și se citește ușor. Ideile sunt aceleași în Java, C++ sau JavaScript; doar numele claselor diferă. Același Python îl folosește și cursul de algoritmi pentru interviuri, unde rezolvi problemele clasice și le verifici automat pe teste.

Tabelul de complexități pe care îl știi pe de rost

Înainte de listă, iată costul operațiilor de bază pentru structurile cele mai folosite. Valorile pentru Python sunt cele din pagina oficială despre complexitatea operațiilor în Python.

StructuraAcces după pozițieCăutare după valoareAdăugareȘtergere
Tablou / listăO(1)O(n)O(1) la final, O(n) la începutO(1) la final, O(n) în rest
Hash map / dicționarnu areO(1) în medieO(1) în medieO(1) în medie
Setnu areO(1) în medieO(1) în medieO(1) în medie
Stivădoar vârfulO(n)O(1)O(1)
Coadă (deque)doar capeteleO(n)O(1) la ambele capeteO(1) la ambele capete
Listă înlănțuităO(n)O(n)O(1) dacă ai nodulO(1) dacă ai nodul
Heapminimul în O(1)O(n)O(log n)O(log n) pentru minim
Arbore binar de căutare echilibratnu areO(log n)O(log n)O(log n)

Cele 10 structuri de date pentru interviu

Ordinea de mai jos e cea în care merită să le înveți: de la ce apare la aproape orice interviu până la ce apare doar la cele axate pe algoritmi.

1. Tabloul (lista)

Un tablou ține elementele unul după altul în memorie, așa că ajungi la orice poziție instantaneu, după index. În Python îl folosești prin list. Adăugarea la final e rapidă, inserarea la început mută toate celelalte elemente.

Ce exersezi: parcurgeri cu doi indici (two pointers), ferestre glisante (sliding window), sume parțiale. Problemă clasică: suma maximă a unei subsecvențe de k elemente consecutive. Nivel: începător, apare la orice interviu.

2. Șirul de caractere (string)

Un string e, practic, un tablou de caractere, dar în Python și Java nu poate fi modificat pe loc. Fiecare „modificare” creează un string nou, iar asta contează când lipești bucăți într-o buclă.

Ce exersezi: palindroame, anagrame, numărarea caracterelor, inversarea cuvintelor. Problemă clasică: verifici dacă două cuvinte sunt anagrame. Nivel: începător.

3. Hash map (dicționarul)

Un hash map asociază o cheie unei valori și găsește valoarea după cheie, în medie, într-un singur pas. În Python e dict, în Java HashMap, în JavaScript Map sau obiectul simplu. E structura care transformă cele mai multe soluții din O(n²) în O(n). Termenul îl găsești explicat și în dicționarul de programare, la „dicționar”.

Ce exersezi: numărări de frecvențe, grupări, „am mai văzut valoarea asta?”. Problemă clasică: Two Sum, rezolvată mai jos. Nivel: începător, probabil cea mai importantă structură din toată lista.

4. Setul

Un set e un hash map doar cu chei: ține valori unice și îți spune instantaneu dacă o valoare e în el. Îl folosești când nu te interesează ordinea sau numărul de apariții, ci doar prezența.

Ce exersezi: eliminarea duplicatelor, intersecții, „primul element care se repetă”. Problemă clasică: cea mai lungă secvență de numere consecutive dintr-un șir nesortat. Nivel: începător spre mediu.

5. Stiva

O stivă funcționează ca un teanc de farfurii: ultimul element pus e primul scos (LIFO, last in, first out). În Python folosești o listă simplă, cu append și pop. Apare oriunde ai ceva „deschis” care trebuie „închis” în ordine inversă.

Ce exersezi: paranteze, evaluarea expresiilor, butonul Undo, „următorul element mai mare”. Problemă clasică: verifici dacă parantezele dintr-un text sunt corecte, rezolvată mai jos. Nivel: începător spre mediu.

6. Coada

O coadă funcționează ca rândul de la ghișeul de la Poștă: primul venit e primul servit (FIFO, first in, first out). În Python folosești deque din modulul collections, nu o listă, pentru că list.pop(0) mută toate elementele și costă O(n).

Ce exersezi: procesarea în ordine, parcurgerea pe niveluri a arborilor și a grafurilor (BFS). Problemă clasică: drumul cel mai scurt într-un graf fără costuri, rezolvat mai jos. Nivel: mediu.

7. Lista înlănțuită

O listă înlănțuită e un șir de noduri, fiecare cu o valoare și o legătură spre nodul următor. Nu poți sări direct la poziția 50, dar poți insera sau șterge un nod fără să muți nimic altceva. În cod real o folosești rar; la interviu apare des, pentru că testează lucrul atent cu referințe.

Ce exersezi: inversarea listei, detectarea unui ciclu cu doi pointeri (unul lent, unul rapid), interclasarea a două liste sortate. Nivel: mediu.

8. Heap-ul (coada de priorități)

Un heap îți dă mereu cel mai mic (sau cel mai mare) element în O(1) și îl scoate în O(log n). E structura din spatele oricărei probleme cu „primele k”: cele mai mari 3 comenzi ale zilei, cele mai apropiate 5 magazine. În Python îl folosești prin modulul heapq, de exemplu heapq.nlargest(3, comenzi, key=...).

Ce exersezi: top k elemente, interclasarea a k liste sortate, mediana unui flux de numere. Nivel: mediu.

9. Arborele (și arborele binar de căutare)

Un arbore organizează datele ierarhic: o rădăcină, cu copii, care au la rândul lor copii, ca structura de foldere de pe calculator. Arborele binar de căutare păstrează la stânga valorile mai mici și la dreapta pe cele mai mari, așa că, dacă e echilibrat, găsește o valoare în O(log n). Aproape toate problemele de arbori se rezolvă recursiv.

Ce exersezi: parcurgerile (preordine, inordine, postordine, pe niveluri), înălțimea arborelui, verificarea că un arbore e de căutare. Nivel: mediu spre avansat.

10. Graful

Un graf e o mulțime de noduri legate prin muchii: orașe și drumuri, utilizatori și prietenii, cursuri și prerechizite. Îl reții de obicei ca listă de adiacență, adică un dicționar în care fiecare nod are lista vecinilor. Dacă ai trecut prin BAC-ul de informatică, terminologia îți e cunoscută din ghidul despre C++ pentru BAC.

Ce exersezi: BFS și DFS, numărarea componentelor (numărul de insule dintr-o hartă), ordonarea topologică (în ce ordine urmezi cursurile cu prerechizite). Nivel: avansat pentru un junior, frecvent la firmele mari.

Trei probleme clasice, rezolvate în Python

Codul de mai jos rulează exact așa cum e scris, cu Python 3, și acoperă trei dintre cele mai cerute structuri: hash map-ul, stiva și coada.

Two Sum cu un dicționar

Problema: într-o listă de prețuri, găsește pozițiile a două produse care împreună costă exact suma dată. Soluția cu două bucle face n² comparații; cu un dicționar, faci o singură trecere.

def doua_sume(numere, tinta):
    vazute = {}
    for i, x in enumerate(numere):
        if tinta - x in vazute:
            return vazute[tinta - x], i
        vazute[x] = i
    return None


print(doua_sume([120, 45, 80, 200, 35], 125))  # (1, 2)

Pentru fiecare preț verifici dacă „restul până la țintă” a apărut deja. Dicționarul ține valorile văzute și pozițiile lor, iar căutarea în el e O(1) în medie, deci totul e O(n).

Paranteze corecte cu o stivă

def paranteze_corecte(text):
    pereche = {")": "(", "]": "[", "}": "{"}
    stiva = []
    for c in text:
        if c in "([{":
            stiva.append(c)
        elif c in pereche:
            if not stiva or stiva.pop() != pereche[c]:
                return False
    return not stiva


print(paranteze_corecte("{[()()]}"))  # True
print(paranteze_corecte("([)]"))      # False
print(paranteze_corecte("(("))        # False

Fiecare paranteză deschisă intră în stivă. La o paranteză închisă, vârful stivei trebuie să fie perechea ei. La final, stiva trebuie să fie goală; altfel au rămas paranteze neînchise, ca în al treilea exemplu.

Drumul cel mai scurt cu o coadă (BFS)

from collections import deque


def drum_minim(graf, start, final):
    distanta = {start: 0}
    coada = deque([start])
    while coada:
        oras = coada.popleft()
        if oras == final:
            return distanta[oras]
        for vecin in graf[oras]:
            if vecin not in distanta:
                distanta[vecin] = distanta[oras] + 1
                coada.append(vecin)
    return -1


graf = {
    "Cluj": ["Oradea", "Alba Iulia", "Târgu Mureș"],
    "Oradea": ["Cluj", "Arad"],
    "Arad": ["Oradea", "Timișoara"],
    "Timișoara": ["Arad", "Deva"],
    "Alba Iulia": ["Cluj", "Deva", "Sibiu"],
    "Deva": ["Alba Iulia", "Timișoara"],
    "Sibiu": ["Alba Iulia", "Brașov"],
    "Târgu Mureș": ["Cluj", "Brașov"],
    "Brașov": ["Sibiu", "Târgu Mureș"],
}
print(drum_minim(graf, "Cluj", "Timișoara"))  # 3

BFS vizitează orașele în ordinea distanței față de start: întâi vecinii, apoi vecinii vecinilor. Coada asigură exact această ordine, iar dicționarul distanta ține minte și ce oraș a fost deja vizitat. Primul moment în care scoți destinația din coadă îți dă numărul minim de drumuri: 3, fie prin Oradea și Arad, fie prin Alba Iulia și Deva.

Cum vorbești despre structuri de date la interviu

La interviu contează la fel de mult cum explici soluția ca și codul. Un tipar care funcționează în aproape orice situație are patru pași:

  1. Spune soluția simplă și costul ei: „Pot verifica toate perechile, O(n²).”
  2. Arată ce operație o face lentă: „Partea scumpă e căutarea perechii pentru fiecare element.”
  3. Alege structura care face operația aceea rapidă: „Cu un dicționar, căutarea devine O(1), deci totul e O(n), cu O(n) memorie în plus.”
  4. Scrie codul și testează-l cu voce tare pe un exemplu mic și pe un caz limită: listă goală, un singur element, valori duplicate.

Pentru întrebările teoretice care apar lângă probleme, vezi și lista cu întrebări tehnice comune la interviurile IT.

Întrebări frecvente

Ce structuri de date trebuie să știu pentru un interviu de junior?

Tablouri, string-uri, hash map-uri, seturi, stive și cozi acoperă majoritatea problemelor de la interviurile de junior. Listele înlănțuite, heap-urile, arborii și grafurile apar mai ales la firmele care pun accent pe algoritmi, așa că le adaugi după ce le stăpânești pe primele.

În ce limbaj e mai bine să dau interviul de algoritmi?

În limbajul pe care îl știi cel mai bine, dacă firma nu impune altul. Python e popular pentru că are dicționare, seturi, deque și heapq gata făcute și se scrie repede. Java și C++ sunt la fel de bune, doar mai lungi la scris.

Trebuie să implementez de la zero un hash map sau un heap?

Rar. De obicei folosești structurile din biblioteca standard și ți se cere să explici cum funcționează și cât costă operațiile. Excepția frecventă e lista înlănțuită, pe care e bine să știi s-o scrii și s-o inversezi de mână.

Cât timp îmi ia să învăț structurile de date pentru interviu?

Aproximativ 6–10 săptămâni de exercițiu regulat, dacă știi deja un limbaj de programare. Primele șase structuri se învață în 2–3 săptămâni; arborii și grafurile cer mai mult timp, pentru că se bazează pe recursivitate și pe parcurgeri.

Ce diferență e între o stivă și o coadă?

Stiva scoate ultimul element adăugat (LIFO), coada scoate primul element adăugat (FIFO). Stiva o folosești pentru paranteze, Undo și DFS, coada pentru procesare în ordine și BFS.

Primul pas: rezolvă Two Sum fără să te uiți

Închide articolul și scrie din memorie soluția cu dicționar pentru Two Sum, apoi pe cea cu stiva pentru paranteze. Dacă le scrii corect pe amândouă, ai deja baza pentru o treime din problemele de interviu de junior. Pentru restul, cursul de algoritmi pentru interviuri are 150 de lecții, de la Big O la grafuri și programare dinamică, plus patru interviuri simulate; la fiecare modul poți încerca gratuit primele două lecții, cu cont. Dacă abia începi cu Python, pornește cu variabilele și tipurile de date din Python.

Logo Curs Python Interactiv · 15 lecții gratuite

Curs Python

Programare Python pentru începători, cu exerciții practice în browser

Începe gratuit

Citește și

Primul tău program e la 5 minute distanță.

Creează-ți contul gratuit și începe primele 15 lecții. Fără card, fără instalări.

Începe gratuit