...
Pregătire interviuri

100 de întrebări de interviu Algoritmi și structuri de date, cu răspunsuri

Întrebările despre Algoritmi și structuri de date care apar des la interviurile tehnice, fiecare cu un răspuns scurt, explicația pe larg și ce urmărește intervievatorul. Citește-le sau exersează cu răspunsurile ascunse. Înveți de la zero cu Curs Algoritmi pentru interviuri: primele 2 lecții sunt gratuite.

Pagină coordonată de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la

  • 100întrebări
  • 50junior
  • 35mid
  • 15senior
  • 150 minde citit
Întrebări de interviu Algoritmi și structuri de date cu răspunsuri

La un interviu tehnic de algoritmi și structuri de date primești de obicei una sau două probleme de rezolvat live, la tablă sau într-un editor partajat, uneori precedate de un test online cu limită de timp. Intervievatorul nu urmărește doar dacă ajungi la soluție, ci cum ajungi acolo: dacă pui întrebări de clarificare, dacă pornești de la o soluție brută corectă, dacă știi să o optimizezi cu structura de date potrivită, dacă îi poți calcula complexitatea de timp și de memorie și dacă îți testezi singur codul pe cazuri limită.

Pentru un post de junior se așteaptă să stăpânești Big O, tablourile, șirurile, dicționarele și seturile, stivele și cozile, recursivitatea, sortarea și căutarea binară, plus parcurgerile de bază pe arbori și grafuri. La nivel mid apar tiparele mai fine (fereastră glisantă, stivă monotonă, sortare topologică, union-find, Dijkstra, programare dinamică pe una și două dimensiuni) și se cere argumentarea corectitudinii. Întrebările de senior adaugă probleme grele, alegerea între mai multe soluții cu compromisuri diferite și întrebări de scalare: date care nu încap în memorie, fluxuri, sisteme distribuite.

Codul de pe pagină este în Python 3, limbajul folosit și în cursul de algoritmi de pe site, și rulează așa cum este scris. Folosește pagina ca pe un set de exerciții: citește întrebarea, încearcă să rezolvi singur problema cu voce tare, cu cronometrul pornit, apoi compară cu răspunsul scurt și cu explicația detaliată. Atenție mai ales la secțiunile despre complexitate, cazuri limită și variante, pentru că acolo se fac cele mai multe greșeli la interviu.

Complexitate și Big O

1 Junior

Ce înseamnă notația Big O și de ce spunem că 3n + 5 și n au aceeași complexitate?

Răspuns scurt: Big O descrie cum crește timpul (sau memoria) unui algoritm când crește dimensiunea intrării n, ca limită superioară. Constantele și termenii mai mici se ignoră, pentru că nu schimbă forma creșterii pentru n mare.

Big O nu măsoară secunde, ci rata de creștere. Întrebarea la care răspunde este: dacă dublez intrarea, cât de mult crește munca? Pentru 3n + 5, dublarea lui n aproape dublează numărul de operații, exact ca pentru n. De aceea ambele sunt O(n).

Regulile practice:

  • ignori constantele multiplicative: O(3n) devine O(n), O(n/2) devine O(n);
  • păstrezi doar termenul dominant: O(n² + n log n + 100) devine O(n²);
  • intrări diferite au variabile diferite: două bucle succesive pe liste diferite sunt O(n + m), nu O(n).

De ce ignorăm constantele? Pentru că depind de limbaj, de procesor și de implementare, pe când forma creșterii nu depinde. Un algoritm O(n log n) scris lent va bate, de la un n suficient de mare, un algoritm O(n²) scris foarte eficient.

Constantele contează totuși în practică pentru n mic: o sortare prin inserție poate fi mai rapidă decât merge sort pe 20 de elemente, motiv pentru care Timsort, sortarea din Python, folosește inserția pe bucăți mici. La interviu spui complexitatea în Big O, iar dacă ai două soluții cu aceeași complexitate, poți discuta și constantele.

Ordinea uzuală, de la rapid la lent: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ), O(n!).

Ce urmărește intervievatorul: Verifică dacă înțelegi ce măsoară Big O, nu doar dacă recunoști notația. Greșeala tipică este să spui „O(2n)” sau să aduni complexitățile a două intrări diferite într-un singur n.

2 Junior

Ce complexitate de timp are funcția de mai jos? Bucla interioară nu merge până la n, deci este mai bună decât O(n²)?

PYTHON
def perechi(a):
    n = len(a)
    total = 0
    for i in range(n):
        for j in range(i + 1, n):
            if a[i] + a[j] == 0:
                total += 1
    return total

Răspuns scurt: Este tot O(n²). Bucla interioară face n−1, n−2, …, 0 pași, adică n(n−1)/2 comparații în total, iar împărțirea la 2 este o constantă care dispare în Big O.

Mulți candidați se uită la range(i + 1, n) și cred că au „înjumătățit” munca. Au, dar doar ca factor constant. Numărul exact de execuții ale lui if este:

(n−1) + (n−2) + … + 1 + 0 = n(n−1)/2

Asta este (n² − n)/2. Păstrăm termenul dominant, n², și scoatem constanta 1/2, deci complexitatea este O(n²). Dacă n crește de 10 ori, timpul crește de aproximativ 100 de ori, la fel ca la o buclă completă n × n.

Tehnica generală pentru bucle imbricate: numeri de câte ori se execută corpul cel mai interior, ca sumă, apoi simplifici. Câteva tipare utile:

  • bucla interioară de la 0 la n: n · n = O(n²);
  • bucla interioară de la i la n: n²/2 = O(n²);
  • bucla interioară care înjumătățește: n · log n = O(n log n);
  • bucla interioară de lungime fixă, de exemplu 26 de litere: O(26n) = O(n).

Memoria suplimentară a funcției este O(1): doar câteva variabile, indiferent de n.

Dacă intervievatorul cere optimizarea, pentru numărarea perechilor cu suma 0 poți folosi un dicționar cu frecvențe: pentru fiecare x adaugi la total de câte ori ai văzut deja −x, apoi incrementezi frecvența lui x. Rezultă O(n) timp și O(n) memorie.

Ce urmărește intervievatorul: Intervievatorul vrea să vadă că știi să numeri pașii, nu să ghicești după aspectul codului. Capcana este să răspunzi O(n log n) sau „O(n²/2)”.

3 Junior

Ce înseamnă complexitatea de memorie (space complexity)? Câtă memorie folosește o funcție recursivă care nu creează nicio listă?

Răspuns scurt: Este memoria suplimentară de care are nevoie algoritmul în funcție de n, fără intrarea însăși. O funcție recursivă folosește memorie pe stiva de apeluri: O(adâncimea recursivității), chiar dacă nu alocă structuri.

Complexitatea de memorie numără de obicei spațiul auxiliar: liste, dicționare, seturi create de algoritm, plus stiva de apeluri. Intrarea nu se socotește, decât dacă intervievatorul cere explicit spațiul total.

Exemple:

  • inversarea unei liste cu doi indici, pe loc (in-place): O(1);
  • a[::-1] sau sorted(a): O(n), pentru că se creează o listă nouă;
  • un set cu elementele văzute: O(n) în cel mai rău caz.

Recursivitatea este capcana clasică. Fiecare apel neterminat ține un cadru pe stivă (parametri, variabile locale, adresa de întoarcere):

PYTHON
def suma(a, i=0):
    if i == len(a):
        return 0
    return a[i] + suma(a, i + 1)

Funcția nu creează liste, dar are n apeluri active simultan, deci memoria este O(n). În Python, CPython are o limită implicită de aproximativ 1000 de apeluri (sys.getrecursionlimit()), așa că pentru n = 10.000 primești RecursionError. Versiunea iterativă cu o buclă are O(1) memorie.

La căutarea binară recursivă, adâncimea este log n, deci memoria este O(log n). La DFS pe un arbore, memoria este O(h), înălțimea arborelui, care poate fi O(n) pentru un arbore degenerat.

Ca obicei la interviu: spune mereu ambele complexități, timp și memorie, fără să aștepți să fii întrebat.

Ce urmărește intervievatorul: Verifică dacă iei în calcul stiva de apeluri. Mulți candidați declară O(1) memorie pentru orice soluție recursivă fără structuri auxiliare.

4 Junior

De ce o buclă care împarte n la 2 la fiecare pas are complexitatea O(log n)? Dă un exemplu de algoritm care se bazează pe asta.

Răspuns scurt: Pentru că după k pași din n rămâne n/2ᵏ, iar bucla se oprește când n/2ᵏ ajunge la 1, adică după k = log₂ n pași. Căutarea binară, ridicarea rapidă la putere și operațiile pe un heap folosesc această idee.

Ia bucla:

PYTHON
def pasi(n):
    k = 0
    while n > 1:
        n //= 2
        k += 1
    return k

Pentru n = 1024 face 10 pași, pentru n = 1.048.576 face 20 de pași. Când intrarea se dublează, se adaugă un singur pas. Asta este semnătura lui O(log n): de un milion de ori mai multe date costă doar de aproximativ 20 de ori mai mulți pași decât un singur element.

Formal, după k iterații valoarea este n/2ᵏ. Bucla se termină când n/2ᵏ ≤ 1, adică 2ᵏ ≥ n, deci k ≥ log₂ n. Baza logaritmului nu contează în Big O, pentru că log₂ n și log₁₀ n diferă doar printr-o constantă.

Unde apare:

  • căutarea binară: la fiecare pas elimini jumătate din intervalul rămas;
  • ridicarea la putere prin înjumătățirea exponentului: xⁿ = (x^(n/2))²;
  • heap: push și pop urcă sau coboară pe înălțimea arborelui, care este log n;
  • arbori echilibrați: căutarea coboară câte un nivel.

Nu orice buclă care „scade” este logaritmică: n -= 2 dă tot O(n), pentru că reduci cu o constantă, nu cu un factor. Logaritmul apare doar când reduci cu o fracție fixă.

Ce urmărește intervievatorul: Intervievatorul verifică intuiția din spatele lui log n, pe care se bazează multe întrebări ulterioare. Greșeala tipică este confuzia dintre reducerea cu o constantă și reducerea cu un factor.

5 Junior

Ce complexitate au în Python operațiile lista.append(x), lista.insert(0, x), lista.pop(), lista.pop(0), x in lista și x in set_?

Răspuns scurt: append și pop() de la final sunt O(1) amortizat, insert(0, x) și pop(0) sunt O(n) pentru că mută toate elementele, x in lista este O(n), iar x in set_ este O(1) în medie.

În CPython, list este un tablou dinamic de referințe, adică elementele stau unul după altul în memorie. De aici rezultă costurile:

  • append(x): scrie la final, O(1) amortizat (ocazional se realocă tabloul);
  • pop(): scoate de la final, O(1);
  • insert(0, x) și pop(0): toate celelalte n elemente trebuie mutate cu o poziție, O(n);
  • a[i] și a[i] = v: O(1), acces direct după index;
  • x in a, a.index(x), a.remove(x): parcurgere liniară, O(n);
  • a[i:j]: copiază j − i elemente;
  • a.sort(): O(n log n).

set și dict sunt tabele de dispersie (hash tables): in, adăugarea și ștergerea sunt O(1) în medie și O(n) în cel mai rău caz, când multe chei ajung în aceeași zonă a tabelei.

Consecința practică: o coadă implementată cu pop(0) pe o listă face ca un BFS pe n noduri să devină O(n²). Folosește collections.deque, care are append, appendleft, pop și popleft în O(1).

PYTHON
from collections import deque
coada = deque([1, 2, 3])
coada.append(4)
primul = coada.popleft()   # O(1)

La fel, dacă verifici apartenența într-o buclă (if x in vazute), transformă vazute într-un set: soluția trece de la O(n²) la O(n).

Ce urmărește intervievatorul: Cursul și interviurile de algoritmi folosesc Python, iar intervievatorul vrea să vadă că știi costul ascuns al operațiilor de bibliotecă. Capcana tipică este pop(0) sau in lista într-o buclă.

Eroarea, în practică:x in lista în buclă: soluție prea lentă

6 Mid

Ce înseamnă complexitate amortizată? Explică de ce append pe o listă Python este O(1) amortizat, deși uneori durează O(n).

Răspuns scurt: Complexitatea amortizată este costul mediu pe operație într-o secvență lungă de operații, în cel mai rău caz pentru secvență. La append, realocările costisitoare sunt rare, iar costul lor total împărțit la numărul de operații rămâne constant.

O listă Python are o capacitate rezervată mai mare decât numărul de elemente. Cât timp există loc, append doar scrie la final. Când capacitatea se umple, CPython alocă un tablou mai mare și copiază toate elementele, ceea ce costă O(n).

Cheia este că noua capacitate crește proporțional cu dimensiunea curentă, nu cu o constantă. Ca model simplu, presupune dublarea: copierile au loc la dimensiunile 1, 2, 4, 8, …, n. Costul total al copierilor este 1 + 2 + 4 + … + n < 2n. Deci n operații append costă în total O(n), adică O(1) pe operație, în medie pe secvență. (CPython crește cu un factor mai mic decât 2, aproximativ 1,125, dar argumentul este același: orice factor geometric dă cost amortizat constant.)

Dacă tabloul ar crește cu o constantă fixă, de exemplu +10 locuri, copierile ar costa 10 + 20 + 30 + … ≈ n²/20, deci O(n) amortizat. De aceea creșterea geometrică este esențială.

Diferența față de „caz mediu”: amortizarea nu depinde de date aleatoare sau de noroc. Garantează că orice secvență de n operații costă O(n). Un singur append poate totuși să dureze mult, lucru important în sisteme cu latență strictă.

Alte exemple de cost amortizat: coada din două stive, union-find cu path compression, dict care își mărește tabela internă.

Ce urmărește intervievatorul: Verifică dacă știi să justifici o complexitate, nu doar să o reciți. Greșeala tipică este confuzia dintre amortizat și caz mediu probabilist.

7 Mid

Care este diferența dintre Big O, Big Omega și Big Theta? Ce înseamnă „cazul cel mai rău” față de „cazul mediu” la quicksort?

Răspuns scurt: O este o limită superioară, Ω una inferioară, iar Θ înseamnă ambele. Separat de notație, analizezi un caz anume: quicksort este Θ(n log n) în medie și Θ(n²) în cel mai rău caz.

Sunt două întrebări diferite care se amestecă des.

Prima: notația spune cum compari o funcție de cost cu alta.

  • f(n) = O(g(n)): f crește cel mult ca g (limită superioară);
  • f(n) = Ω(g(n)): f crește cel puțin ca g (limită inferioară);
  • f(n) = Θ(g(n)): f crește exact ca g, până la constante.

Tehnic, căutarea liniară este și O(n²), pentru că n ≤ n², dar asta nu e o informație utilă. La interviuri, „O” se folosește de obicei cu sensul de Θ: cea mai strânsă limită superioară.

A doua: cazul spune pe ce intrări analizezi.

  • cel mai bun caz: căutarea liniară găsește elementul pe prima poziție, Θ(1);
  • cel mai rău caz: elementul lipsește, Θ(n);
  • cazul mediu: o medie pe o distribuție a intrărilor.

Quicksort cu pivot ales prost (primul element) pe un tablou deja sortat produce partiții de dimensiuni 0 și n−1, deci Θ(n²). Cu pivot aleator, timpul așteptat este Θ(n log n) pentru orice intrare.

O limită inferioară cunoscută: orice sortare bazată pe comparații are nevoie de Ω(n log n) comparații în cel mai rău caz, pentru că trebuie să distingă între n! ordonări posibile, iar log₂(n!) ≈ n log₂ n.

La interviu, spune explicit cazul: „O(n log n) în medie, O(n²) în cel mai rău caz”.

Ce urmărește intervievatorul: Intervievatorul verifică precizia. Mulți candidați spun „quicksort e O(n log n)” fără să precizeze cazul sau cred că Big O înseamnă automat cazul mediu.

8 Mid

Funcția de mai jos pare liniară, dar e lentă pe date mari. Care este complexitatea reală și cum o repari?

PYTHON
def unice_in_ordine(cuvinte):
    rezultat = []
    for c in cuvinte:
        if c not in rezultat:
            rezultat.append(c)
    return ", ".join(rezultat)

Răspuns scurt: Este O(n²) în cel mai rău caz, pentru că c not in rezultat parcurge lista la fiecare pas. Repari ținând un set separat cu elementele văzute, iar complexitatea devine O(n) în medie.

Bucla are n iterații, iar în fiecare c not in rezultat face o căutare liniară într-o listă care poate ajunge la n elemente. Dacă toate cuvintele sunt distincte, costul total este 1 + 2 + … + n = O(n²). Pentru 100.000 de cuvinte, asta înseamnă miliarde de comparații.

Varianta corectă păstrează ordinea și folosește un set pentru testul de apartenență:

PYTHON
def unice_in_ordine(cuvinte):
    vazute = set()
    rezultat = []
    for c in cuvinte:
        if c not in vazute:
            vazute.add(c)
            rezultat.append(c)
    return ", ".join(rezultat)

Acum fiecare test este O(1) în medie, deci totalul este O(n) timp și O(n) memorie. O variantă idiomatică, valabilă din Python 3.7, când dicționarele păstrează ordinea inserării:

PYTHON
def unice_in_ordine(cuvinte):
    return ", ".join(dict.fromkeys(cuvinte))

join este deja eficient: calculează lungimea totală și construiește șirul o singură dată. Opusul lui ar fi s = s + c într-o buclă, care poate copia șirul de fiecare dată și devine O(n²) pe lungimea totală. CPython optimizează uneori acest caz, dar nu te baza pe asta.

Lecția generală: o operație care pare O(1) în cod (in, +, slicing, remove) poate ascunde o parcurgere completă.

Ce urmărește intervievatorul: Verifică dacă vezi costul ascuns al operatorilor de bibliotecă, nu doar buclele explicite. Greșeala tipică este să declari O(n) uitându-te doar la for.

Eroarea, în practică:x in lista în buclă: soluție prea lentă

9 Senior

Enunțul unei probleme spune 1 ≤ n ≤ 2·10⁵. Cum folosești această limită ca să alegi abordarea înainte să scrii cod?

Răspuns scurt: Limitele îți spun ce complexitate e acceptabilă. Pentru n = 2·10⁵, O(n²) înseamnă 4·10¹⁰ operații, prea mult, deci cauți O(n log n) sau O(n): sortare, hash map, two pointers, heap sau căutare binară.

Ca regulă empirică, un limbaj compilat face în jur de 10⁸ operații simple pe secundă, iar Python este de obicei de câteva zeci de ori mai lent. Nu e o cifră exactă, dar e suficientă pentru estimări de ordin de mărime. Din limita lui n deduci ce tip de algoritm se așteaptă:

  • n ≤ 10–12: O(n!) sau O(n · 2ⁿ), adică permutări și backtracking complet;
  • n ≤ 20–25: O(2ⁿ), submulțimi, eventual cu meet-in-the-middle;
  • n ≤ 500: O(n³), de exemplu DP pe intervale sau Floyd–Warshall;
  • n ≤ 5000: O(n²), DP pe două dimensiuni, perechi;
  • n ≤ 10⁵–10⁶: O(n log n) sau O(n), adică sortare, heap, two pointers, prefix sums, hash;
  • n ≤ 10⁹ sau mai mult: O(log n) sau O(1), căutare binară pe răspuns sau o formulă.

Procesul la interviu:

  • citești limitele și spui cu voce tare complexitatea țintă;
  • formulezi soluția brută și complexitatea ei, ca punct de plecare;
  • te întrebi ce structură de date elimină bucla interioară: un set în loc de căutare, un heap în loc de sortarea repetată, prefix sums în loc de sume recalculate;
  • verifici și memoria: o matrice DP de 2·10⁵ × 2·10⁵ nu încape, deci ai nevoie de o dimensiune redusă.

Limitele mici sunt și ele un indiciu: dacă n ≤ 15, intervievatorul acceptă probabil exponențial și se uită la corectitudine. Dacă valorile sunt mici (de exemplu 0 ≤ a[i] ≤ 1000), te poți gândi la counting sort sau la DP pe valori.

Ce urmărește intervievatorul: Intervievatorul vede dacă știi să-ți alegi abordarea din constrângeri, cum face un candidat cu experiență. Greșeala tipică este să ignori limitele și să optimizezi la întâmplare.

Tablouri, two pointers și sliding window

10 Junior

Scrie o funcție care inversează o listă pe loc, fără reverse() și fără slicing. Ce complexitate are?

Răspuns scurt: Folosești doi indici, unul la început și unul la final, interschimbi elementele și îi apropii până se întâlnesc. Timpul este O(n), iar memoria suplimentară O(1).

Aceasta este cea mai simplă aplicație a tehnicii two pointers: doi indici care se mișcă unul spre celălalt.

PYTHON
def inverseaza(a):
    st, dr = 0, len(a) - 1
    while st < dr:
        a[st], a[dr] = a[dr], a[st]
        st += 1
        dr -= 1
    return a

print(inverseaza([1, 2, 3, 4, 5]))  # [5, 4, 3, 2, 1]

De ce st < dr și nu st <= dr? Când indicii se întâlnesc pe elementul din mijloc (lungime impară), interschimbarea lui cu el însuși e inutilă, dar nu greșită. Important este să te oprești când s-au întâlnit, altfel interschimbi înapoi și refaci ordinea inițială.

Cazuri limită de verificat: lista goală (dr = -1, bucla nu pornește), un singur element, lungime pară și impară.

Complexitate: fiecare pas apropie indicii cu 2 poziții, deci n/2 interschimbări, adică O(n). Memoria este O(1), pentru că lucrezi direct în listă.

Pentru șiruri de caractere, în Python str este imuabil, deci nu poți inversa pe loc. Varianta corectă este să convertești la listă, să inversezi și să faci "".join(...), cu O(n) memorie. În practică scrii s[::-1], dar la interviu ți se cere de obicei să arăți tehnica.

Același tipar stă la baza verificării unui palindrom: compari a[st] cu a[dr] în loc să le interschimbi.

Ce urmărește intervievatorul: Este o întrebare de încălzire care verifică dacă stăpânești indicii și condiția de oprire. Greșelile tipice sunt <= cu efect dublu sau uitarea că str e imuabil.

Eroarea, în practică:IndexError la două pointere

11 Junior

Scrie o funcție care mută toate zerourile la finalul unei liste, păstrând ordinea celorlalte elemente, pe loc.

Răspuns scurt: Ții un indice scrie pentru următoarea poziție a unui element nenul. Parcurgi lista, iar fiecare element nenul îl interschimbi cu a[scrie] și avansezi scrie. O(n) timp, O(1) memorie.

Este tiparul read/write pointers: un indice citește fiecare element, altul marchează unde scrii următorul element „bun”.

PYTHON
def muta_zerourile(a):
    scrie = 0
    for citeste in range(len(a)):
        if a[citeste] != 0:
            a[scrie], a[citeste] = a[citeste], a[scrie]
            scrie += 1
    return a

print(muta_zerourile([0, 1, 0, 3, 12]))  # [1, 3, 12, 0, 0]

De ce funcționează: invariantul este că a[0:scrie] conține, în ordine, toate elementele nenule văzute până acum, iar între scrie și citeste sunt doar zerouri. Când găsești un nenul, îl aduci la scrie prin interschimbare, iar zeroul ajunge în locul lui.

Ordinea relativă a elementelor nenule se păstrează, pentru că le scrii în ordinea în care le citești.

O variantă în doi pași: copiezi întâi nenulele pe pozițiile 0, 1, 2, …, apoi umpli restul cu zerouri. Face mai puține scrieri când zerourile sunt puține.

Ce nu e acceptat de obicei: sorted(a, key=lambda x: x == 0). E corect (sortarea Python e stabilă), dar e O(n log n) și creează o listă nouă, deci nu respectă cerința „pe loc”.

Același tipar rezolvă și „elimină toate aparițiile unei valori” sau „elimină duplicatele dintr-o listă sortată”.

Ce urmărește intervievatorul: Verifică dacă știi tiparul cu doi indici în aceeași direcție și dacă poți formula invariantul. Greșeala frecventă este ștergerea cu remove în timpul parcurgerii, care e O(n²) și sare elemente.

12 Junior

Primești o listă sortată crescător. Elimină duplicatele pe loc și întoarce numărul de elemente unice; primele k poziții trebuie să conțină valorile unice.

Răspuns scurt: Cu doi indici: k arată lungimea zonei de valori unice, iar un al doilea indice parcurge lista. Când valoarea curentă diferă de a[k-1], o scrii pe poziția k și incrementezi k. O(n) timp, O(1) memorie.

Pentru că lista este sortată, duplicatele sunt mereu vecine. E suficient să compari elementul curent cu ultimul element unic păstrat.

PYTHON
def elimina_duplicate(a):
    if not a:
        return 0
    k = 1
    for i in range(1, len(a)):
        if a[i] != a[k - 1]:
            a[k] = a[i]
            k += 1
    return k

a = [1, 1, 2, 3, 3, 3, 4]
k = elimina_duplicate(a)
print(k, a[:k])  # 4 [1, 2, 3, 4]

Invariantul: a[0:k] conține valorile unice întâlnite până la i, în ordine. Primul element e mereu unic, de aceea k pornește de la 1.

De ce nu un set? list(set(a)) pierde ordinea (setul nu garantează ordinea) și folosește O(n) memorie. sorted(set(a)) repară ordinea, dar e O(n log n) și nu e pe loc.

De ce nu del a[i] în buclă? Fiecare ștergere mută restul listei, deci O(n²), iar indicii devin greu de urmărit.

Varianta „permite cel mult două apariții” se rezolvă cu aceeași idee, comparând cu a[k-2]:

PYTHON
def cel_mult_doua(a):
    k = 0
    for x in a:
        if k < 2 or x != a[k - 2]:
            a[k] = x
            k += 1
    return k

Generalizarea pentru cel mult m apariții: compari cu a[k-m].

Ce urmărește intervievatorul: Intervievatorul verifică dacă folosești proprietatea „sortat” și dacă știi tiparul read/write. Varianta cu cel mult două apariții separă candidații care au înțeles de cei care au memorat.

13 Junior

Într-o listă sortată crescător, găsește doi indici ale căror valori au suma egală cu tinta. Cum folosești faptul că lista e sortată?

Răspuns scurt: Pui un indice la început și unul la final. Dacă suma e prea mică, muți stânga la dreapta; dacă e prea mare, muți dreapta la stânga. O(n) timp și O(1) memorie, față de O(n) memorie la soluția cu dicționar.

PYTHON
def doua_numere(a, tinta):
    st, dr = 0, len(a) - 1
    while st < dr:
        s = a[st] + a[dr]
        if s == tinta:
            return st, dr
        if s < tinta:
            st += 1
        else:
            dr -= 1
    return None

print(doua_numere([1, 3, 4, 6, 9, 11], 13))  # (2, 4)

De ce nu ratezi soluția? Dacă a[st] + a[dr] < tinta, atunci a[st] plus orice element din stânga lui dr dă o sumă și mai mică, deci a[st] nu poate face parte din nicio soluție cu elementele rămase. Îl elimini în siguranță. Simetric, când suma e prea mare, a[dr] nu mai poate fi folosit. La fiecare pas elimini un candidat, deci cel mult n pași.

Comparație cu alte abordări:

  • forță brută cu două bucle: O(n²);
  • pentru fiecare element, căutare binară după complement: O(n log n);
  • dicționar cu valorile văzute: O(n) timp, dar O(n) memorie și nu are nevoie de sortare;
  • doi indici: O(n) timp, O(1) memorie, dar cere listă sortată.

Dacă lista nu e sortată și ți se cer indicii originali, sortarea îi strică, deci dicționarul e alegerea naturală. Dacă ți se cer doar valorile, poți sorta în O(n log n) și apoi aplica doi indici.

Tehnica este baza pentru 3Sum și pentru „perechi cu suma cel mult k”.

Ce urmărește intervievatorul: Verifică dacă știi să argumentezi corectitudinea mutării pointerilor, nu doar să scrii codul. Mulți candidați sar direct la dicționar și ignoră informația „sortat”.

Eroarea, în practică:IndexError la două pointere

14 Junior

Ai o listă de numere și multe întrebări de forma „care este suma elementelor dintre pozițiile i și j?”. Cum răspunzi la fiecare în O(1)?

Răspuns scurt: Precalculezi sumele prefix: p[k] este suma primelor k elemente. Atunci suma pe intervalul [i, j] este p[j+1] - p[i]. Construirea costă O(n), fiecare întrebare O(1).

Fără precalculare, fiecare întrebare parcurge intervalul, deci q întrebări costă O(n · q). Cu sume prefix plătești O(n) o singură dată.

PYTHON
def construieste_prefix(a):
    p = [0] * (len(a) + 1)
    for i, x in enumerate(a):
        p[i + 1] = p[i] + x
    return p

def suma_interval(p, i, j):   # inclusiv i și j
    return p[j + 1] - p[i]

a = [3, -1, 4, 1, 5]
p = construieste_prefix(a)   # [0, 3, 2, 6, 7, 12]
print(suma_interval(p, 1, 3))  # -1 + 4 + 1 = 4

De ce lista are lungime n + 1, cu p[0] = 0? Ca formula să funcționeze și pentru intervale care încep la 0, fără un if special. Este o sursă frecventă de erori off-by-one, deci merită spus explicit.

Biblioteca standard oferă itertools.accumulate(a, initial=0) (parametrul initial există din Python 3.8).

Extensii care apar la interviu:

  • sume prefix 2D pentru suma unui dreptunghi dintr-o matrice: P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1];
  • tablou de diferențe, inversul ideii: adaugi o valoare pe un interval în O(1) (d[i] += v, d[j+1] -= v), apoi refaci valorile cu o sumă prefix;
  • combinația cu un dicționar pentru „numărul de subtablouri cu suma k”.

Limita: dacă lista se modifică între întrebări, prefixele trebuie recalculate. Atunci ai nevoie de un Fenwick tree sau de un segment tree, cu O(log n) pe operație.

Ce urmărește intervievatorul: Este o tehnică de bază care apare ca pas în multe probleme. Intervievatorul urmărește indicii, iar greșeala tipică este off-by-one la capătul intervalului.

Eroarea, în practică:Sume prefix: interval cu un element lipsă

15 Junior

Scrie o funcție care găsește suma maximă a unei subsecvențe contigue dintr-o listă care poate conține numere negative (algoritmul lui Kadane).

Răspuns scurt: Parcurgi lista și ții cea mai bună sumă care se termină la poziția curentă: ori continui secvența anterioară, ori începi una nouă de la elementul curent. Rezultatul este maximul acestor valori. O(n) timp, O(1) memorie.

Ideea lui Kadane: dacă suma secvenței care se termină la elementul anterior este negativă, ea doar strică orice continuare, deci e mai bine să începi de la zero cu elementul curent.

PYTHON
def suma_maxima(a):
    curent = maxim = a[0]
    for x in a[1:]:
        curent = max(x, curent + x)
        maxim = max(maxim, curent)
    return maxim

print(suma_maxima([-2, 1, -3, 4, -1, 2, 1, -5, 4]))  # 6, din [4, -1, 2, 1]
print(suma_maxima([-3, -1, -2]))                     # -1

curent răspunde la întrebarea: care e cea mai mare sumă a unei secvențe care se termină exact aici? Relația curent = max(x, curent + x) este o recurență de programare dinamică cu o singură stare, de aceea memoria rămâne O(1).

Capcana clasică: inițializarea cu 0 în loc de a[0]. Pentru o listă numai cu negative, varianta cu 0 întoarce 0, adică o subsecvență goală, ceea ce de obicei nu e permis. Clarifică cu intervievatorul dacă secvența goală e acceptată.

a[1:] creează o copie, deci O(n) memorie; dacă vrei strict O(1), iterezi cu for i in range(1, len(a)).

Variante frecvente:

  • întoarce și indicii: reții start când resetezi și actualizezi capetele când crește maxim;
  • produsul maxim: ții și minimul curent, pentru că un negativ înmulțit cu un negativ devine maxim;
  • listă circulară: maximul dintre Kadane normal și total - suma_minima, cu atenție la cazul în care toate sunt negative.

Ce urmărește intervievatorul: Este o problemă clasică care verifică gândirea incrementală. Intervievatorul urmărește cazul cu toate valorile negative și dacă poți explica de ce resetarea e corectă.

Eroarea, în practică:Kadane: 0 în loc de maximul negativ

16 Junior

Primești prețurile unei acțiuni pe zile. Poți cumpăra o dată și vinde o dată, mai târziu. Scrie funcția care calculează profitul maxim.

Răspuns scurt: Parcurgi prețurile o dată, ții minimul de până acum și, pentru fiecare zi, calculezi profitul dacă ai vinde azi. Răspunsul este maximul acestor profituri. O(n) timp, O(1) memorie.

Forța brută încearcă fiecare pereche (cumpăr în ziua i, vând în ziua j > i), deci O(n²). Observația care o reduce la O(n): pentru o zi de vânzare fixă, cea mai bună zi de cumpărare este cea cu prețul minim dinaintea ei. Deci e suficient să ții acel minim pe parcurs.

PYTHON
def profit_maxim(preturi):
    minim = float("inf")
    profit = 0
    for p in preturi:
        minim = min(minim, p)
        profit = max(profit, p - minim)
    return profit

print(profit_maxim([7, 1, 5, 3, 6, 4]))  # 5: cumperi la 1, vinzi la 6
print(profit_maxim([7, 6, 4, 3, 1]))     # 0: nu tranzacționezi

Ordinea celor două actualizări contează puțin: dacă actualizezi minimul înainte, p - minim poate fi 0 (cumperi și vinzi în aceeași zi), ceea ce nu afectează maximul, pentru că profitul pornește oricum de la 0.

Problema este echivalentă cu Kadane aplicat pe diferențele zilnice preturi[i] - preturi[i-1]: profitul unei tranzacții este suma diferențelor dintre ziua de cumpărare și cea de vânzare.

Variante care apar ca follow-up:

  • tranzacții nelimitate: aduni toate diferențele pozitive, o abordare greedy;
  • cel mult k tranzacții sau cu perioadă de așteptare: programare dinamică cu stări (am acțiunea / nu o am);
  • cu comision: tot DP cu două stări, comisionul se scade la vânzare.

Ce urmărește intervievatorul: Verifică dacă găsești invariantul „minimul până acum”, care transformă O(n²) în O(n). Follow-up-urile arată dacă poți trece la DP cu stări.

17 Mid

Ai o listă h cu înălțimile unor pereți verticali. Alege doi pereți care, împreună cu axa, formează recipientul cu cea mai multă apă. De ce e corect să muți mereu pointerul de la peretele mai mic?

Răspuns scurt: Pornești cu pereții de la capete și muți mereu peretele mai scund spre interior. Peretele scund nu poate forma un recipient mai bun cu niciun alt perete rămas, pentru că lățimea scade și înălțimea e limitată de el. O(n) timp.

Aria dintre pereții i și j este min(h[i], h[j]) * (j - i).

PYTHON
def apa_maxima(h):
    st, dr = 0, len(h) - 1
    best = 0
    while st < dr:
        best = max(best, min(h[st], h[dr]) * (dr - st))
        if h[st] < h[dr]:
            st += 1
        else:
            dr -= 1
    return best

print(apa_maxima([1, 8, 6, 2, 5, 4, 8, 3, 7]))  # 49

Argumentul de corectitudine este ce așteaptă intervievatorul. Să zicem că h[st] < h[dr]. Orice recipient care folosește peretele st cu un perete k, unde st < k < dr, are:

  • lățimea k - st, mai mică decât dr - st;
  • înălțimea min(h[st], h[k]) ≤ h[st].

Deci aria lui este mai mică decât aria curentă, h[st] * (dr - st). Peretele st și-a dat deja cel mai bun rezultat posibil, așa că îl elimini. Dacă ai muta în schimb peretele mai înalt, ai putea pierde soluția optimă.

La egalitate poți muta oricare: niciunul dintre cei doi nu poate forma o arie mai mare cu un perete interior, pentru că înălțimea rămâne limitată la h[st] iar lățimea scade.

Fiecare pas elimină un perete, deci cel mult n − 1 pași: O(n) timp, O(1) memorie, față de O(n²) la forța brută.

Nu confunda cu „apa captată între clădiri”, unde apa se adună peste toate pozițiile, nu doar între doi pereți.

Ce urmărește intervievatorul: Intervievatorul nu se mulțumește cu codul: vrea demonstrația că mutarea pointerului mic nu pierde soluția. Fără ea, soluția pare o euristică ghicită.

18 Mid

Găsește toate tripletele unice dintr-o listă care au suma 0 (problema 3Sum). Cum eviți tripletele duplicate fără un set de tupluri?

Răspuns scurt: Sortezi lista, fixezi primul element și rezolvi 2Sum cu doi indici pe restul. Duplicatele le eviți sărind peste valori egale consecutive, atât pentru elementul fixat, cât și după ce găsești un triplet. O(n²) timp.

PYTHON
def trei_suma(a):
    a.sort()
    rez = []
    n = len(a)
    for i in range(n - 2):
        if i > 0 and a[i] == a[i - 1]:
            continue              # același prim element, aceleași triplete
        if a[i] > 0:
            break                 # toate cele de după sunt pozitive
        st, dr = i + 1, n - 1
        while st < dr:
            s = a[i] + a[st] + a[dr]
            if s < 0:
                st += 1
            elif s > 0:
                dr -= 1
            else:
                rez.append([a[i], a[st], a[dr]])
                st += 1
                dr -= 1
                while st < dr and a[st] == a[st - 1]:
                    st += 1
    return rez

print(trei_suma([-1, 0, 1, 2, -1, -4]))  # [[-1, -1, 2], [-1, 0, 1]]

De ce sortarea: face posibil 2Sum cu doi indici și grupează valorile egale, deci duplicatele devin vecine și le poți sări.

Cele două locuri unde sari duplicate:

  • la i: dacă a[i] este egal cu precedentul, toate tripletele lui au fost deja găsite;
  • după un triplet găsit: avansezi st peste valorile egale, altfel ai produce același triplet de mai multe ori. Pe dr nu e nevoie să-l sari separat: cu a[i] și a[st] fixate, valoarea lui a[dr] e determinată.

Complexitate: sortarea O(n log n), plus n iterații × O(n) pentru doi indici, deci O(n²). Memoria este O(1) în afară de rezultat și de sortare (Timsort folosește până la O(n)).

Soluția cu set de tupluri sortate funcționează, dar consumă memorie suplimentară și ascunde logica. Generalizarea la kSum este recursivă: fixezi un element și reduci la (k−1)Sum, cu O(n^(k−1)).

Ce urmărește intervievatorul: Verifică dacă poți compune tehnici (sortare + two pointers) și dacă gestionezi corect duplicatele. Cele mai multe soluții greșite produc triplete repetate sau pierd unele.

Eroarea, în practică:Permutări duplicate la elemente repetate

19 Mid

Scrie o funcție care întoarce lungimea celui mai lung subșir de caractere consecutive fără caractere repetate. Explică tehnica de fereastră glisantă variabilă.

Răspuns scurt: Ții o fereastră [st, dr] fără repetiții și un dicționar cu ultima poziție a fiecărui caracter. Când caracterul nou apare deja în fereastră, muți st imediat după apariția anterioară. Fiecare caracter intră și iese o dată: O(n) timp.

Fereastra glisantă variabilă (sliding window) se folosește când cauți cel mai lung sau cel mai scurt interval contiguu care respectă o condiție. Capătul drept avansează mereu, iar capătul stâng avansează doar când fereastra devine invalidă.

PYTHON
def cel_mai_lung_fara_repetari(s):
    ultima = {}
    st = 0
    best = 0
    for dr, c in enumerate(s):
        if c in ultima and ultima[c] >= st:
            st = ultima[c] + 1
        ultima[c] = dr
        best = max(best, dr - st + 1)
    return best

print(cel_mai_lung_fara_repetari("abcabcbb"))  # 3, "abc"
print(cel_mai_lung_fara_repetari("abba"))      # 2

Condiția ultima[c] >= st este bug-ul pe care îl caută intervievatorul. Pe exemplul „abba”, când ajungi la ultimul „a”, apariția anterioară a lui „a” (poziția 0) este deja în afara ferestrei, care începe la 2. Fără verificare, st ar sări înapoi la 1 și fereastra ar conține două „b”-uri.

O variantă la fel de corectă folosește un set și mută st câte un pas, scoțând caractere până dispare duplicatul. Rămâne O(n), pentru că st avansează în total cel mult n pași.

Complexitate: O(n) timp, O(min(n, σ)) memorie, unde σ este mărimea alfabetului.

Tiparul general:

  • extinzi la dreapta și actualizezi starea (frecvențe, sumă);
  • cât timp fereastra e invalidă, micșorezi din stânga;
  • actualizezi răspunsul.

Același schelet rezolvă „cel mai lung bloc după k înlocuiri” și „cel mai scurt subtablou cu suma ≥ S” (doar pentru numere pozitive).

Ce urmărește intervievatorul: Este una dintre cele mai frecvente probleme de interviu. Intervievatorul verifică dacă stăpânești tiparul de fereastră și cazul „abba”, unde mulți candidați mută st înapoi.

Eroarea, în practică:Fereastra variabilă: if în loc de while

20 Mid

Scrie o funcție care întoarce, pentru fiecare poziție i, produsul tuturor elementelor în afară de a[i], fără să folosești împărțirea, în O(n).

Răspuns scurt: Rezultatul la i este produsul elementelor din stânga lui i înmulțit cu produsul celor din dreapta. Le calculezi în două treceri: una de la stânga la dreapta, care scrie prefixele în rezultat, și una inversă, care înmulțește cu sufixele.

Împărțirea (produsul total / a[i]) pare soluția evidentă, dar eșuează când lista conține zerouri și e interzisă explicit în enunț. Ideea corectă folosește produse prefix și sufix.

PYTHON
def produs_fara_curent(a):
    n = len(a)
    rez = [1] * n
    stanga = 1
    for i in range(n):
        rez[i] = stanga
        stanga *= a[i]
    dreapta = 1
    for i in range(n - 1, -1, -1):
        rez[i] *= dreapta
        dreapta *= a[i]
    return rez

print(produs_fara_curent([1, 2, 3, 4]))   # [24, 12, 8, 6]
print(produs_fara_curent([2, 0, 3]))      # [0, 6, 0]

În prima trecere, rez[i] primește produsul a[0] * … * a[i-1]. Observă ordinea: întâi scrii, apoi înmulțești cu a[i], ca elementul curent să nu intre în propriul produs. A doua trecere face același lucru de la dreapta.

Complexitate: O(n) timp, iar memoria suplimentară este O(1) dacă nu socotești lista rezultat, care oricum trebuie întoarsă. Varianta cu două liste separate, prefix și sufix, e mai ușor de explicat întâi, apoi o optimizezi.

Ce discuți la follow-up:

  • în Python întregii nu dau overflow, dar în Java sau C++ produsul poate depăși long;
  • dacă împărțirea ar fi permisă: cu un singur zero, doar poziția lui are rezultat nenul; cu două zerouri, totul e 0.

Tiparul prefix/sufix apare și la „apa captată între clădiri” (maximul din stânga și din dreapta).

Ce urmărește intervievatorul: Verifică dacă găsești descompunerea în stânga și dreapta și dacă știi să elimini memoria suplimentară. Greșeala tipică este soluția cu împărțire care cade pe zerouri.

21 Mid

Rotește o listă la dreapta cu k poziții, pe loc, cu O(1) memorie suplimentară. Ce se întâmplă dacă k este mai mare decât lungimea listei?

Răspuns scurt: Faci k = k % n, apoi trei inversări: întreaga listă, primele k elemente și restul. Rezultatul este lista rotită, în O(n) timp și O(1) memorie.

Soluția simplă în Python, a[:] = a[-k:] + a[:-k], este corectă dar creează liste noi, deci O(n) memorie. Când se cere O(1), trucul clasic este triplă inversare.

PYTHON
def inverseaza(a, i, j):
    while i < j:
        a[i], a[j] = a[j], a[i]
        i += 1
        j -= 1

def roteste(a, k):
    n = len(a)
    if n == 0:
        return a
    k %= n
    inverseaza(a, 0, n - 1)
    inverseaza(a, 0, k - 1)
    inverseaza(a, k, n - 1)
    return a

print(roteste([1, 2, 3, 4, 5, 6, 7], 3))  # [5, 6, 7, 1, 2, 3, 4]

De ce funcționează: rotirea la dreapta cu k mută ultimele k elemente în față. Inversarea totală le aduce în față, dar în ordine inversă, iar restul ajunge și el inversat. A doua și a treia inversare refac ordinea internă a fiecărui bloc.

k %= n rezolvă cazul k ≥ n: rotirea cu n poziții lasă lista neschimbată, deci contează doar restul. Fără el, indicii ies din listă. Verifici separat lista goală, pentru că k % 0 aruncă ZeroDivisionError.

Alte abordări:

  • rotirea câte o poziție de k ori: O(n · k), prea lent pentru k mare;
  • listă auxiliară cu b[(i + k) % n] = a[i]: O(n) memorie;
  • collections.deque.rotate(k) face exact asta, dar la interviu ți se cere de obicei algoritmul.

Rotirea la stânga cu k este echivalentă cu rotirea la dreapta cu n − k.

Ce urmărește intervievatorul: Intervievatorul verifică dacă știi trucul inversărilor și dacă tratezi k ≥ n și lista goală. Mulți candidați uită de k % n.

Eroarea, în practică:Rotire cu k > len(lista): rezultat greșit

22 Senior

Primești înălțimile unor clădiri de lățime 1. Câtă apă rămâne captată între ele după ploaie? Dă o soluție O(n) timp și O(1) memorie.

Răspuns scurt: Apa deasupra poziției i este min(maxStânga, maxDreapta) - h[i]. Cu doi indici, procesezi mereu partea cu maximul mai mic, pentru că acolo nivelul apei e deja determinat. O(n) timp, O(1) memorie.

Observația de bază: deasupra unei poziții, apa urcă până la cel mai scund dintre cei doi pereți maximi din stânga și din dreapta, minus înălțimea poziției.

Prima soluție O(n) folosește două liste, max_st[i] și max_dr[i], calculate în două treceri, plus o a treia trecere pentru sumă. Memoria este O(n). Optimizarea la O(1) memorie folosește doi indici:

PYTHON
def apa_captata(h):
    st, dr = 0, len(h) - 1
    max_st = max_dr = 0
    apa = 0
    while st < dr:
        if h[st] < h[dr]:
            max_st = max(max_st, h[st])
            apa += max_st - h[st]
            st += 1
        else:
            max_dr = max(max_dr, h[dr])
            apa += max_dr - h[dr]
            dr -= 1
    return apa

print(apa_captata([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))  # 6

De ce poți calcula apa la st știind doar max_st? Când h[st] < h[dr], există în dreapta un perete (h[dr]) cel puțin la fel de înalt ca orice a văzut stânga până acum, deci maximul real din dreapta poziției st este mai mare decât max_st. Atunci minimul dintre cele două maxime este chiar max_st. Valoarea max_st - h[st] nu e niciodată negativă, pentru că max_st include h[st].

O a treia soluție folosește o stivă monotonă descrescătoare și adună apa pe „straturi” orizontale când găsește un perete mai înalt. Tot O(n), dar O(n) memorie.

La interviu, un drum bun este: forță brută O(n²) (pentru fiecare i cauți maximele), apoi prefix/sufix O(n) cu O(n) memorie, apoi doi indici. Fiecare pas arată de unde vine optimizarea.

Ce urmărește intervievatorul: Este o problemă grea, clasică la interviurile de mid și senior. Intervievatorul urmărește progresia de la soluția brută și argumentul pentru care ajunge max_st.

Hash maps, sets și șiruri

Exersează capitolul cu exerciții reale: Curs algoritmi pentru începători →
23 Junior

Scrie o funcție care spune dacă o listă conține duplicate. Compară trei abordări: forță brută, sortare și set.

Răspuns scurt: Forța brută compară fiecare pereche, O(n²) timp și O(1) memorie. Sortarea aduce duplicatele alăturat, O(n log n). Setul reține ce ai văzut, O(n) timp mediu și O(n) memorie. De obicei setul este răspunsul așteptat.

Este un exemplu bun pentru compromisul dintre timp și memorie (time-memory trade-off).

PYTHON
def are_duplicate_brut(a):          # O(n²) timp, O(1) memorie
    for i in range(len(a)):
        for j in range(i + 1, len(a)):
            if a[i] == a[j]:
                return True
    return False

def are_duplicate_sortare(a):       # O(n log n) timp
    b = sorted(a)
    return any(b[i] == b[i + 1] for i in range(len(b) - 1))

def are_duplicate_set(a):           # O(n) timp mediu, O(n) memorie
    vazute = set()
    for x in a:
        if x in vazute:
            return True
        vazute.add(x)
    return False

Varianta scurtă, len(set(a)) != len(a), este corectă, dar construiește mereu setul întreg. Bucla explicită se oprește la primul duplicat, ceea ce contează când lista e mare și duplicatul apare devreme.

Când alegi altceva decât setul:

  • memoria e limitată și ai voie să modifici lista: sortezi pe loc cu a.sort();
  • elementele nu sunt hashable (de exemplu liste de liste): setul nu le acceptă, deci sortezi sau le convertești la tupluri;
  • valorile sunt întregi într-un interval mic, de exemplu 0..1000: o listă de frecvențe de dimensiune fixă este mai rapidă decât un set.

Variantă de follow-up: „există două valori egale la distanță cel mult k?”. Ții un set doar cu ultimele k elemente, o fereastră glisantă, și scoți elementul care iese din fereastră la fiecare pas.

Ce urmărește intervievatorul: Verifică dacă știi să compari variante și să explici compromisul timp/memorie. Un candidat bun pomenește și cazul elementelor care nu sunt hashable.

24 Junior

Scrie o funcție care verifică dacă două șiruri sunt anagrame (au aceleași litere, de același număr de ori).

Răspuns scurt: Compari frecvențele caracterelor: Counter(s) == Counter(t), în O(n) timp. Alternativa sorted(s) == sorted(t) este O(n log n), dar nu are nevoie de dicționar.

Două șiruri sunt anagrame dacă au același multiset de caractere. Sunt două abordări standard.

Prin sortare:

PYTHON
def anagrame_sort(s, t):
    return sorted(s) == sorted(t)

O(n log n) timp, O(n) memorie pentru listele sortate. E scurtă și ușor de verificat.

Prin numărare:

PYTHON
from collections import Counter

def anagrame(s, t):
    if len(s) != len(t):
        return False
    return Counter(s) == Counter(t)

O(n) timp. Verificarea lungimii la început e o optimizare ieftină: șiruri de lungimi diferite nu pot fi anagrame.

La interviu ți se poate cere varianta fără Counter, cu un singur dicționar: incrementezi pentru caracterele din s, decrementezi pentru cele din t și verifici că toate valorile au ajuns la 0. Dacă alfabetul e fix (de exemplu doar litere mici a–z), o listă de 26 de întregi, indexată cu ord(c) - ord("a"), folosește O(1) memorie.

Întrebări de clarificare care arată maturitate:

  • contează majusculele? Normalizezi cu s.lower(), sau mai robust cu s.casefold();
  • se ignoră spațiile și punctuația? Filtrezi cu c.isalnum();
  • textul are diacritice sau caractere Unicode compuse? „ș” poate fi scris ca un singur caracter sau ca „s” plus un semn combinat; unicodedata.normalize("NFC", s) le aduce la aceeași formă.

Follow-up frecvent: găsește toate pozițiile din s unde începe o anagramă a lui p. Se rezolvă cu o fereastră fixă de lungime len(p) și frecvențe actualizate incremental.

Ce urmărește intervievatorul: Verifică dacă știi abordarea prin frecvențe și dacă pui întrebări despre majuscule, spații și Unicode. Candidații care întreabă de normalizare ies în evidență.

Eroarea, în practică:KeyError la numărarea cu frecv[x] += 1

25 Junior

Scrie o funcție care întoarce indicele primului caracter care nu se repetă într-un șir, sau -1 dacă nu există.

Răspuns scurt: Faci două treceri: prima numără aparițiile fiecărui caracter, a doua parcurge șirul în ordine și întoarce primul caracter cu frecvența 1. O(n) timp și O(σ) memorie, unde σ este numărul de caractere distincte.

PYTHON
from collections import Counter

def primul_unic(s):
    frecv = Counter(s)
    for i, c in enumerate(s):
        if frecv[c] == 1:
            return i
    return -1

print(primul_unic("leetcode"))      # 0
print(primul_unic("loveleetcode"))  # 2
print(primul_unic("aabb"))          # -1

De ce două treceri? Dicționarul îți spune câte apariții are fiecare caracter, dar ordinea în care le-ai inserat nu ajută: un caracter poate fi inserat primul și să se dovedească repetat mai târziu. A doua trecere pe șirul original îți dă ordinea corectă.

Soluția greșită tipică este s.count(c) == 1 în buclă. count parcurge șirul de fiecare dată, deci O(n²).

Complexitatea: O(n) timp. Memoria este O(σ), mărginită de alfabet. Pentru litere mici a–z este O(1), adică maxim 26 de chei.

Variantă de follow-up: flux de caractere, în care trebuie să spui oricând care este primul caracter unic de până acum. Nu poți parcurge din nou tot fluxul. Ții frecvențele într-un dicționar și o coadă (deque) cu candidații în ordinea apariției. La fiecare interogare, scoți din fața cozii caracterele care au devenit repetate. Fiecare caracter intră și iese din coadă cel mult o dată, deci costul amortizat pe operație este O(1).

O altă variantă: un dict simplu păstrează ordinea inserării (din Python 3.7), deci poți parcurge frecv.items() în loc de șir, dacă ai nevoie de caracter și nu de indice.

Ce urmărește intervievatorul: Este o problemă ușoară care verifică tiparul „numără, apoi caută”. Greșeala tipică este str.count în buclă, care transformă soluția în O(n²).

Eroarea, în practică:KeyError la numărarea cu frecv[x] += 1

26 Junior

Lista nu este sortată. Găsește indicii a două elemente care au suma egală cu tinta, într-o singură trecere.

Răspuns scurt: Parcurgi lista și ții un dicționar valoare → indice pentru elementele văzute. Pentru fiecare x, verifici dacă tinta - x e deja în dicționar; dacă da, ai perechea. O(n) timp, O(n) memorie.

PYTHON
def two_sum(a, tinta):
    vazute = {}
    for i, x in enumerate(a):
        complement = tinta - x
        if complement in vazute:
            return vazute[complement], i
        vazute[x] = i
    return None

print(two_sum([2, 7, 11, 15], 9))  # (0, 1)
print(two_sum([3, 3], 6))          # (0, 1)

Ordinea operațiilor contează: verifici complementul înainte să adaugi elementul curent. Altfel, pentru tinta = 6 și x = 3 l-ai împerechea pe 3 cu el însuși. Și cazul [3, 3] funcționează corect: primul 3 intră în dicționar, al doilea îl găsește.

Complexitate: n căutări și inserări în dicționar, fiecare O(1) în medie, deci O(n) timp și O(n) memorie.

Ce e diferit față de varianta cu listă sortată: acolo doi indici dau O(1) memorie, dar aici sortarea ar strica indicii originali. Ai putea sorta perechi (valoare, indice), cu O(n log n), dar dicționarul e mai simplu și mai rapid.

Variante care apar ca follow-up:

  • toate perechile, nu doar una: dicționarul ține frecvențe și aduni de câte ori ai văzut complementul;
  • perechi unice de valori: folosești un set de perechi sortate sau sortezi și sari duplicatele;
  • date mari, care nu încap în memorie: sortare externă și apoi doi indici, sau partiționare după hash.

Clarifică întotdeauna dacă se garantează existența unei soluții și ce întorci când nu există.

Ce urmărește intervievatorul: Este probabil cea mai cunoscută problemă de interviu. Intervievatorul urmărește dacă verifici complementul înainte de inserare și dacă poți explica de ce dicționarul face soluția liniară.

Eroarea, în practică:Two Sum: același element folosit de două ori

27 Junior

Scrie o funcție care verifică dacă două șiruri sunt izomorfe: caracterele din primul pot fi înlocuite consecvent ca să obții al doilea („egg” și „add” da, „foo” și „bar” nu).

Răspuns scurt: Ai nevoie de o corespondență unu-la-unu, deci verifici în ambele sensuri: un dicționar s → t și unul t → s. Dacă vreo pereche contrazice o corespondență deja stabilită, întorci False. O(n) timp.

Capcana este să verifici doar într-un sens. Cu un singur dicționar s → t, perechea „ab” și „cc” ar trece: a → c, b → c. Dar două caractere diferite nu pot ajunge în același caracter, deci corespondența trebuie să fie bijectivă.

PYTHON
def izomorfe(s, t):
    if len(s) != len(t):
        return False
    st, ts = {}, {}
    for a, b in zip(s, t):
        if st.get(a, b) != b or ts.get(b, a) != a:
            return False
        st[a] = b
        ts[b] = a
    return True

print(izomorfe("egg", "add"))    # True
print(izomorfe("foo", "bar"))    # False
print(izomorfe("ab", "cc"))      # False

st.get(a, b) != b înseamnă: dacă a are deja o pereche, ea trebuie să fie b; dacă nu are, valoarea implicită b face testul să treacă.

O soluție alternativă, elegantă: compari „tiparul” celor două șiruri, înlocuind fiecare caracter cu indicele primei lui apariții.

PYTHON
def tipar(s):
    prima = {}
    return [prima.setdefault(c, i) for i, c in enumerate(s)]

def izomorfe2(s, t):
    return tipar(s) == tipar(t)

Pentru „egg” tiparul este [0, 1, 1], iar pentru „add” la fel. Varianta e ușor de reutilizat: „word pattern” (tiparul „abba” față de „câine pisică pisică câine”) se rezolvă identic, aplicând tipar pe listă de cuvinte. De asemenea, grupezi șirurile izomorfe folosind tuple(tipar(s)) drept cheie.

Complexitate: O(n) timp, O(σ) memorie.

Ce urmărește intervievatorul: Verifică dacă te gândești la ambele sensuri ale corespondenței. Majoritatea soluțiilor greșite folosesc un singur dicționar și pică pe „ab” / „cc”.

28 Mid

Primești o listă de cuvinte. Grupează-le pe anagrame. Ce folosești drept cheie în dicționar și ce complexitate are fiecare variantă?

Răspuns scurt: Grupezi într-un defaultdict(list) după o cheie care e identică pentru anagrame: șirul sortat, O(k log k) pe cuvânt, sau un tuplu cu cele 26 de frecvențe, O(k) pe cuvânt. Totalul este O(n·k log k), respectiv O(n·k).

Ideea este să găsești o formă canonică: o valoare care e egală pentru două cuvinte dacă și numai dacă ele sunt anagrame.

PYTHON
from collections import defaultdict

def grupeaza_anagrame(cuvinte):
    grupuri = defaultdict(list)
    for c in cuvinte:
        cheie = "".join(sorted(c))
        grupuri[cheie].append(c)
    return list(grupuri.values())

print(grupeaza_anagrame(["eat", "tea", "tan", "ate", "nat", "bat"]))
# [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

Pentru n cuvinte de lungime maximă k, sortarea fiecărui cuvânt costă O(k log k), deci total O(n · k log k).

Cheia cu frecvențe evită sortarea:

PYTHON
def cheie_frecvente(c):
    f = [0] * 26
    for ch in c:
        f[ord(ch) - ord("a")] += 1
    return tuple(f)

Total O(n · k). Cheia trebuie să fie un tuplu, nu o listă, pentru că listele nu sunt hashable și nu pot fi chei de dicționar. Varianta merge doar dacă alfabetul e cunoscut și mic; pentru Unicode arbitrar, sortarea rămâne mai sigură, sau poți folosi frozenset(Counter(c).items()).

În practică, pentru cuvinte scurte, varianta cu sortare e adesea la fel de rapidă în Python, pentru că sorted rulează în C, iar bucla cu 26 de poziții rulează în Python. Merită spus, dar complexitatea teoretică favorizează frecvențele.

Memoria este O(n · k) pentru grupuri și chei.

Ideea de formă canonică se reutilizează: șiruri izomorfe, puncte pe aceeași dreaptă (panta redusă cu cmmdc), forme geometrice echivalente după translație.

Ce urmărește intervievatorul: Verifică dacă știi să construiești o cheie canonică și de ce cheia trebuie să fie imuabilă. Un candidat bun compară cele două chei și știe când contează diferența.

29 Mid

Dintr-o listă nesortată de întregi, găsește lungimea celei mai lungi secvențe de numere consecutive (de exemplu [100, 4, 200, 1, 3, 2] dă 4), în O(n).

Răspuns scurt: Pui toate numerele într-un set. Pornești numărătoarea doar de la numerele x pentru care x - 1 nu e în set, adică începuturi de secvență, și avansezi cât timp x + 1 există. Fiecare număr e vizitat de cel mult două ori, deci O(n).

Sortarea rezolvă problema în O(n log n): după sortare, numeri secvențele de valori care cresc cu 1, ignorând duplicatele. Pentru O(n), cerința tipică, folosești un set.

PYTHON
def cea_mai_lunga_secventa(a):
    s = set(a)
    best = 0
    for x in s:
        if x - 1 not in s:          # x începe o secvență
            y = x
            while y + 1 in s:
                y += 1
            best = max(best, y - x + 1)
    return best

print(cea_mai_lunga_secventa([100, 4, 200, 1, 3, 2]))       # 4
print(cea_mai_lunga_secventa([0, 3, 7, 2, 5, 8, 4, 6, 0, 1]))  # 9

De ce e liniar, deși are o buclă while în for? Bucla interioară pornește doar de la începuturi de secvență. Fiecare număr este parcurs de while exact o dată, ca parte a secvenței lui, plus o verificare din for. Totalul este O(n), nu O(n²). Fără condiția x - 1 not in s, pe [1, 2, …, n] ai porni secvența din fiecare punct și ai ajunge la O(n²).

Iterarea pe s, nu pe a, contează și ea: duplicatele din a ar declanșa aceeași secvență de mai multe ori.

Complexitate: O(n) timp mediu, O(n) memorie.

O alternativă e union-find: unești x cu x + 1 când ambele există și cauți componenta cea mai mare. E tot aproape liniar, dar mai complicat. Merită menționat doar dacă problema devine dinamică (numerele sosesc pe rând).

Ce urmărește intervievatorul: Este un exemplu clasic de analiză amortizată la nivel de interviu. Intervievatorul vrea să explici de ce bucla imbricată e totuși O(n).

30 Mid

Câte subtablouri contigue au suma exact k? Lista poate conține și numere negative. De ce nu merge o fereastră glisantă?

Răspuns scurt: Folosești sume prefix și un dicționar cu frecvența fiecărei sume prefix văzute. La poziția curentă, numărul de subtablouri care se termină aici cu suma k este frecvența lui prefix - k. O(n) timp. Fereastra nu merge pentru că, cu negative, suma nu crește monoton.

Suma subtabloului (i, j] este P[j] - P[i]. Vrei P[j] - P[i] = k, adică P[i] = P[j] - k. Deci, mergând de la stânga la dreapta, la fiecare j întrebi: de câte ori am văzut până acum suma prefix P[j] - k?

PYTHON
from collections import defaultdict

def subtablouri_suma_k(a, k):
    frecv = defaultdict(int)
    frecv[0] = 1          # prefixul gol
    prefix = 0
    total = 0
    for x in a:
        prefix += x
        total += frecv[prefix - k]
        frecv[prefix] += 1
    return total

print(subtablouri_suma_k([1, 1, 1], 2))       # 2
print(subtablouri_suma_k([3, 4, -7, 3, 1, 3, 1, -4, -2, -2], 7))  # 3

frecv[0] = 1 reprezintă prefixul gol, ca să numeri subtablourile care încep de la poziția 0. Fără el, pierzi exact acele soluții, o greșeală frecventă.

Ordinea „întâi numeri, apoi adaugi prefixul curent” evită subtablourile goale, care ar apărea pentru k = 0.

De ce nu fereastra glisantă: ea presupune că extinderea ferestrei crește suma și micșorarea o scade. Cu numere negative, o fereastră cu suma prea mare poate deveni corectă după ce mai adaugi un element. Nu mai știi ce capăt să muți. Pentru numere strict pozitive, fereastra merge și folosește O(1) memorie.

Complexitate: O(n) timp, O(n) memorie.

Același tipar (prefix + dicționar) rezolvă: cel mai lung subtablou cu suma k (reții prima poziție a fiecărei sume, nu frecvența), subtablouri cu suma divizibilă cu m (cheia este prefix % m), cel mai lung subtablou cu număr egal de 0 și 1 (înlocuiești 0 cu −1).

Ce urmărește intervievatorul: Verifică dacă știi combinația prefix sums + hash map și dacă înțelegi limitele ferestrei glisante. Greșeala tipică este uitarea lui frecv[0] = 1.

Eroarea, în practică:Sume prefix: interval cu un element lipsă

31 Mid

Găsește cele mai frecvente k elemente dintr-o listă. Compară soluția cu sortare, cea cu heap și cea cu bucket sort.

Răspuns scurt: După ce numeri frecvențele cu Counter: sortarea după frecvență e O(n log n), un heap de mărime k dă O(n log k), iar bucket sort pe frecvențe (frecvența e cel mult n) dă O(n).

Primul pas este mereu același: frecv = Counter(a), în O(n). Diferența este cum alegi cele k chei cu frecvența maximă dintre cele m chei distincte.

Sortare completă, O(m log m):

PYTHON
sorted(frecv, key=frecv.get, reverse=True)[:k]

Heap de mărime k, O(m log k). Biblioteca standard o face direct:

PYTHON
import heapq
heapq.nlargest(k, frecv, key=frecv.get)

Intern, ține un min-heap cu k elemente: un element nou intră doar dacă e mai frecvent decât minimul din heap. E avantajos când k este mult mai mic decât m. Counter.most_common(k) folosește tot nlargest când primește k.

Bucket sort, O(n). Frecvența unui element este între 1 și n, deci poți face n + 1 „găleți”:

PYTHON
from collections import Counter

def top_k(a, k):
    frecv = Counter(a)
    galeti = [[] for _ in range(len(a) + 1)]
    for x, f in frecv.items():
        galeti[f].append(x)
    rez = []
    for f in range(len(galeti) - 1, 0, -1):
        for x in galeti[f]:
            rez.append(x)
            if len(rez) == k:
                return rez
    return rez

print(top_k([1, 1, 1, 2, 2, 3], 2))  # [1, 2]

Când alegi ce:

  • date care încap în memorie, k mic: heap, cod scurt și clar;
  • se cere explicit O(n): bucket sort sau quickselect pe frecvențe;
  • flux de date sau date care nu încap în memorie: heap de mărime k, eventual cu structuri aproximative de numărare.

Discută și departajarea la egalitate de frecvență: dacă se cere o ordine anume (de exemplu alfabetică), cheia devine (-frecvență, cuvânt).

Ce urmărește intervievatorul: Intervievatorul vrea să vadă că știi mai multe soluții și compromisurile lor. Este o întrebare de mid unde contează mai mult discuția decât codul.

32 Senior

Primești șirurile s și t. Găsește cel mai scurt subșir contiguu din s care conține toate caracterele din t, cu tot cu repetiții (minimum window substring).

Răspuns scurt: Fereastră glisantă cu frecvențe: extinzi la dreapta până fereastra conține tot ce cere t, apoi o strângi din stânga cât timp rămâne validă, reținând cea mai scurtă. Un contor lipsa evită compararea dicționarelor la fiecare pas. O(|s| + |t|).

PYTHON
from collections import Counter

def fereastra_minima(s, t):
    if not t or not s:
        return ""
    nevoie = Counter(t)
    lipsa = len(t)            # câte caractere mai lipsesc, cu repetiții
    st = 0
    best = (float("inf"), 0, 0)
    for dr, c in enumerate(s):
        if nevoie[c] > 0:
            lipsa -= 1
        nevoie[c] -= 1
        while lipsa == 0:     # fereastra [st, dr] e validă
            if dr - st + 1 < best[0]:
                best = (dr - st + 1, st, dr + 1)
            nevoie[s[st]] += 1
            if nevoie[s[st]] > 0:
                lipsa += 1
            st += 1
    return "" if best[0] == float("inf") else s[best[1]:best[2]]

print(fereastra_minima("ADOBECODEBANC", "ABC"))  # "BANC"
print(fereastra_minima("a", "aa"))               # ""

Trucul este semnificația lui nevoie[c]: câte apariții ale lui c mai trebuie adăugate în fereastră. Poate deveni negativ, ceea ce înseamnă surplus. Caracterele care nu apar în t ajung imediat negative și nu afectează niciodată lipsa.

lipsa scade doar când adaugi un caracter care chiar era necesar și crește doar când scoți un caracter fără de care fereastra devine invalidă. Astfel, testul de validitate costă O(1), nu O(σ).

De ce e liniar: dr avansează de n ori, st avansează în total de cel mult n ori, iar fiecare pas e O(1). Total O(|s| + |t|) timp, O(σ) memorie.

Dacă ai scrie while all(...) comparând două Counter-e la fiecare pas, soluția ar deveni O(n · σ). Pentru un alfabet mic e acceptabil, dar intervievatorul o va observa.

Varianta cu best ca tuplu evită feliile repetate (s[st:dr+1] la fiecare îmbunătățire), care ar copia șiruri inutil.

Ce urmărește intervievatorul: Este o problemă grea care verifică stăpânirea completă a ferestrei glisante. Intervievatorul urmărește contorul de validitate în O(1) și tratarea repetițiilor din t.

Eroarea, în practică:Fereastra variabilă: if în loc de while

Liste înlănțuite, stive și cozi

33 Junior

Scrie o funcție care verifică dacă un șir cu parantezele ()[]{} este corect închis.

Răspuns scurt: Folosești o stivă: pui pe ea fiecare paranteză deschisă, iar la una închisă verifici că vârful stivei este perechea ei și îl scoți. La final, stiva trebuie să fie goală. O(n) timp și O(n) memorie.

Stiva (LIFO, ultimul intrat, primul ieșit) se potrivește perfect, pentru că ultima paranteză deschisă trebuie închisă prima.

PYTHON
def paranteze_valide(s):
    pereche = {")": "(", "]": "[", "}": "{"}
    stiva = []
    for c in s:
        if c in "([{":
            stiva.append(c)
        elif c in pereche:
            if not stiva or stiva[-1] != pereche[c]:
                return False
            stiva.pop()
    return not stiva

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

Trei moduri de a greși, toate verificate de intervievator:

  • uiți să verifici stiva goală înainte de stiva[-1], deci un șir care începe cu „)” aruncă IndexError;
  • uiți verificarea finală, deci „((” e raportat corect;
  • numeri doar parantezele deschise și închise, fără stivă: „([)]” are numerele corecte, dar este invalid.

În Python, o listă simplă este o stivă eficientă: append și pop() sunt O(1) la final.

Pentru un singur tip de paranteză, nu ai nevoie de stivă: un contor care crește la „(” și scade la „)” e suficient, cu condiția să nu devină negativ niciodată și să fie 0 la final. Memoria scade la O(1).

Variante de follow-up: numărul minim de paranteze de adăugat ca șirul să devină valid, cea mai lungă subsecvență validă (stivă cu indici), generarea tuturor combinațiilor valide de n perechi (backtracking).

Ce urmărește intervievatorul: Este o problemă de încălzire foarte frecventă. Intervievatorul urmărește cazurile limită: stiva goală la închidere și stiva nevidă la final.

Eroarea, în practică:IndexError: pop from empty listParanteze: True pentru „((” (stivă nevidă)

34 Junior

Care este diferența dintre o stivă și o coadă? Cum le implementezi eficient în Python și de ce nu folosești list.pop(0) pentru coadă?

Răspuns scurt: Stiva este LIFO (ultimul intrat iese primul), coada este FIFO (primul intrat iese primul). Stiva o faci cu list (append/pop), coada cu collections.deque (append/popleft). list.pop(0) este O(n), pentru că mută toate elementele.

Ambele sunt structuri de date abstracte definite prin operațiile lor:

  • stiva: push pune un element deasupra, pop scoate elementul de deasupra. Folosită la apeluri de funcții, undo, paranteze, DFS iterativ, evaluarea expresiilor;
  • coada: enqueue pune la final, dequeue scoate de la început. Folosită la BFS, procesarea sarcinilor în ordinea sosirii, buffere.

În Python:

PYTHON
stiva = []
stiva.append(1)
stiva.append(2)
print(stiva.pop())      # 2, O(1)

from collections import deque
coada = deque()
coada.append(1)
coada.append(2)
print(coada.popleft())  # 1, O(1)

O listă Python este un tablou contiguu. pop(0) scoate primul element și trebuie să mute toate celelalte cu o poziție la stânga: O(n). Un BFS pe un graf cu un milion de noduri care folosește pop(0) ajunge la ordinul a 10¹² mutări în cel mai rău caz.

deque (double-ended queue) este implementat în CPython ca o listă dublu înlănțuită de blocuri de dimensiune fixă. Operațiile la ambele capete sunt O(1). Compromisul: accesul după index la mijloc, d[i], este O(n), nu O(1) ca la listă.

Alte structuri înrudite:

  • queue.Queue: coadă thread-safe, pentru producători și consumatori pe thread-uri diferite; mai lentă din cauza sincronizării;
  • heapq: coadă cu priorități, unde iese mereu elementul minim;
  • deque(maxlen=k): păstrează doar ultimele k elemente, util pentru ferestre și istoric.

Ce urmărește intervievatorul: Verifică dacă știi structurile de bază și costul lor în Python. Folosirea pop(0) într-un BFS este una dintre cele mai frecvente greșeli de performanță.

Eroarea, în practică:'list' object has no attribute 'popleft'IndexError: pop from an empty deque

35 Junior

Cum detectezi dacă o listă înlănțuită are un ciclu, cu O(1) memorie? Cum găsești, cu aceeași idee, nodul din mijloc?

Răspuns scurt: Algoritmul lui Floyd: un pointer lent avansează câte un nod, unul rapid câte două. Dacă există ciclu, se întâlnesc; dacă nu, rapidul ajunge la None. Pentru mijloc, când rapidul ajunge la final, lentul e la jumătate.

Un set cu nodurile vizitate detectează ciclul în O(n) timp și O(n) memorie. Cu doi pointeri cu viteze diferite (tortoise and hare) memoria scade la O(1).

PYTHON
class Nod:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

def are_ciclu(cap):
    lent = rapid = cap
    while rapid and rapid.next:
        lent = lent.next
        rapid = rapid.next.next
        if lent is rapid:
            return True
    return False

def mijloc(cap):
    lent = rapid = cap
    while rapid and rapid.next:
        lent = lent.next
        rapid = rapid.next.next
    return lent

De ce se întâlnesc: odată ce ambii sunt în ciclu, distanța dintre ei scade cu 1 la fiecare pas, pentru că rapidul câștigă un nod. Deci se întâlnesc în cel mult lungimea ciclului pași, iar timpul total este O(n).

Compararea se face cu is (aceeași instanță), nu cu == pe valori: două noduri diferite pot avea aceeași valoare.

La mijloc, pentru un număr par de noduri, codul de mai sus întoarce al doilea dintre cele două noduri de mijloc. Pentru primul, condiția devine while rapid.next and rapid.next.next. Clarifică cu intervievatorul ce variantă vrea.

Follow-up clasic: unde începe ciclul? După întâlnire, muți un pointer înapoi la cap și le avansezi pe amândouă câte un pas; se întâlnesc exact la începutul ciclului. Motivul: dacă a este distanța de la cap la intrarea în ciclu și c lungimea ciclului, la întâlnire lentul a parcurs a + b, rapidul 2(a + b), iar diferența a + b este un multiplu de c. Deci a ≡ c − b (mod c).

Aceeași idee găsește și un număr duplicat într-o listă cu valori 1..n tratate ca pointeri.

Ce urmărește intervievatorul: Intervievatorul verifică dacă știi tehnica celor doi pointeri cu viteze diferite. Follow-up-ul cu începutul ciclului separă candidații care pot explica matematica.

36 Junior

Scrie o funcție care interclasează două liste înlănțuite sortate într-o singură listă sortată, fără să creezi noduri noi (în afară de un nod santinelă).

Răspuns scurt: Folosești un nod santinelă (dummy) și un pointer coada. Compari capetele celor două liste, legi nodul mai mic după coada și avansezi. La final, legi restul listei rămase. O(n + m) timp, O(1) memorie.

PYTHON
class Nod:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

def interclaseaza(a, b):
    santinela = Nod(0)
    coada = santinela
    while a and b:
        if a.val <= b.val:
            coada.next = a
            a = a.next
        else:
            coada.next = b
            b = b.next
        coada = coada.next
    coada.next = a if a else b
    return santinela.next

Nodul santinelă elimină cazul special al capului: fără el, ar trebui să decizi separat care nod devine primul și să tratezi listele goale cu if-uri suplimentare. La final întorci santinela.next, adevăratul cap.

Ultima linie leagă restul listei care n-a fost epuizată. Nu trebuie parcurs: e deja sortat și toate valorile lui sunt mai mari decât ultimul nod legat.

Folosirea lui <= (nu <) păstrează stabilitatea: la valori egale, nodul din prima listă vine primul. Contează când nodurile au și alte date în afară de cheie.

Complexitate: fiecare nod e legat o dată, deci O(n + m) timp. Memoria suplimentară este O(1), pentru că refolosești nodurile existente.

Versiunea recursivă e mai scurtă, dar folosește O(n + m) stivă și poate atinge limita de recursivitate din Python pe liste lungi:

PYTHON
def interclaseaza_rec(a, b):
    if not a or not b:
        return a or b
    if a.val <= b.val:
        a.next = interclaseaza_rec(a.next, b)
        return a
    b.next = interclaseaza_rec(a, b.next)
    return b

Această funcție este pasul de bază pentru merge sort pe liste înlănțuite și pentru interclasarea a k liste.

Ce urmărește intervievatorul: Verifică dacă stăpânești manipularea de pointeri și tehnica nodului santinelă. Fără santinelă, codul se umple de cazuri speciale și apar bug-uri la liste goale.

Eroarea, în practică:'NoneType' object has no attribute 'urm'Lista înlănțuită: capul nu se șterge

37 Junior

Implementează o stivă care, pe lângă push, pop și top, întoarce minimul curent în O(1).

Răspuns scurt: Ții o a doua informație pe stivă: pentru fiecare element, minimul de la baza stivei până la el. Poți stoca perechi (valoare, minim) sau o stivă paralelă de minime. Toate operațiile rămân O(1).

Un singur câmp minim nu ajunge: dacă scoți elementul minim, nu mai știi care e următorul minim fără să parcurgi stiva. Soluția este să memorezi minimul la fiecare nivel.

PYTHON
class StivaMin:
    def __init__(self):
        self.s = []          # perechi (valoare, minimul până aici)

    def push(self, x):
        m = min(x, self.s[-1][1]) if self.s else x
        self.s.append((x, m))

    def pop(self):
        return self.s.pop()[0]

    def top(self):
        return self.s[-1][0]

    def get_min(self):
        return self.s[-1][1]

st = StivaMin()
for x in [5, 3, 7, 3, 1]:
    st.push(x)
print(st.get_min())  # 1
st.pop()
print(st.get_min())  # 3
st.pop(); st.pop()
print(st.get_min())  # 3

De ce e corect: stiva își schimbă vârful doar prin push și pop. Minimul elementelor de sub un nivel nu se schimbă cât timp acel nivel e în stivă, deci îl poți calcula o dată, la push.

Optimizare de memorie: o stivă separată de minime în care pui doar când x <= minimul curent și scoți doar când elementul scos este egal cu minimul. Folosirea lui <= (nu <) este esențială pentru duplicate: pe exemplul de mai sus, cu < al doilea 3 n-ar intra în stiva de minime, iar după scoaterea lui ai pierde minimul corect.

Complexitate: O(1) pentru toate operațiile, O(n) memorie.

Generalizare: o coadă cu minim în O(1) amortizat se obține din două stive cu minim, folosind tehnica de coadă din două stive.

Ce urmărește intervievatorul: Verifică dacă înțelegi de ce un singur câmp nu ajunge și cum se tratează duplicatele. Varianta optimizată cu < în loc de <= este bug-ul clasic.

38 Junior

Implementează o coadă folosind doar două stive. Ce complexitate au operațiile?

Răspuns scurt: O stivă de intrare primește elementele noi, iar o stivă de ieșire le servește. Când ieșirea e goală, muți tot din intrare în ieșire, ceea ce inversează ordinea. Fiecare element e mutat o singură dată, deci operațiile sunt O(1) amortizat.

PYTHON
class CoadaDinStive:
    def __init__(self):
        self.intrare = []
        self.iesire = []

    def push(self, x):
        self.intrare.append(x)

    def _muta(self):
        if not self.iesire:
            while self.intrare:
                self.iesire.append(self.intrare.pop())

    def pop(self):
        self._muta()
        return self.iesire.pop()

    def peek(self):
        self._muta()
        return self.iesire[-1]

    def empty(self):
        return not self.intrare and not self.iesire

c = CoadaDinStive()
c.push(1); c.push(2); c.push(3)
print(c.pop())   # 1
c.push(4)
print(c.pop())   # 2

De ce ordinea e corectă: mutarea din intrare în iesire inversează elementele, deci cel mai vechi ajunge în vârful lui iesire. Important este să muți doar când iesire e goală. Dacă ai muta și când mai are elemente, cele noi ar ajunge peste cele vechi și ordinea FIFO s-ar strica.

Analiza amortizată: un pop poate costa O(n) când are loc mutarea. Dar fiecare element trece prin exact patru operații în viața lui: push în intrare, pop din intrare, push în iesire, pop din iesire. Pentru n operații, costul total este O(n), deci O(1) amortizat pe operație.

Varianta naivă, care mută totul înapoi după fiecare pop, face fiecare operație O(n).

Unde contează în practică: în limbaje funcționale, cozile imuabile se construiesc exact așa, din două liste. Iar întrebarea inversă, stiva din două cozi, are o operație O(n), pentru că nu există o inversare echivalentă.

Ce urmărește intervievatorul: Este un test clasic de analiză amortizată. Intervievatorul urmărește condiția „mută doar când ieșirea e goală” și explicația de ce costul mediu e constant.

39 Mid

Elimină al n-lea nod de la finalul unei liste înlănțuite, într-o singură parcurgere.

Răspuns scurt: Doi pointeri pornesc de la un nod santinelă. Îl avansezi pe primul cu n + 1 pași, apoi îi miști pe amândoi până când primul ajunge la None. Al doilea este acum chiar înaintea nodului de eliminat. O(L) timp, O(1) memorie.

Varianta în două treceri calculează lungimea L, apoi elimină nodul de pe poziția L − n de la început. Cerința „o singură trecere” se rezolvă cu doi pointeri aflați la distanță fixă.

PYTHON
class Nod:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

def elimina_de_la_final(cap, n):
    santinela = Nod(0, cap)
    rapid = lent = santinela
    for _ in range(n + 1):
        rapid = rapid.next
    while rapid:
        rapid = rapid.next
        lent = lent.next
    lent.next = lent.next.next
    return santinela.next

def din_lista(vals):
    cap = None
    for v in reversed(vals):
        cap = Nod(v, cap)
    return cap

def in_lista(cap):
    rez = []
    while cap:
        rez.append(cap.val)
        cap = cap.next
    return rez

print(in_lista(elimina_de_la_final(din_lista([1, 2, 3, 4, 5]), 2)))  # [1, 2, 3, 5]
print(in_lista(elimina_de_la_final(din_lista([1]), 1)))              # []

De ce n + 1 pași: vrei ca lent să se oprească pe nodul dinaintea celui eliminat, ca să poți modifica lent.next. Distanța dintre pointeri trebuie să fie n + 1.

Santinela rezolvă cazul în care trebuie eliminat chiar capul (n = L). Fără ea, lent ar trebui să fie înaintea capului, ceea ce nu există, și ai avea nevoie de un if separat.

Ce trebuie clarificat cu intervievatorul: este n garantat valid (1 ≤ n ≤ L)? Dacă nu, verifici în bucla for că rapid nu devine None prea devreme.

Notă practică: „o singură trecere” e o cerință mai mult teoretică. Ambele variante sunt O(L) și parcurg aproximativ același număr de noduri. Tehnica distanței fixe e utilă însă în fluxuri, unde nu poți reveni la început.

Ce urmărește intervievatorul: Verifică tehnica pointerilor la distanță fixă și folosirea santinelei pentru eliminarea capului. Greșelile tipice sunt off-by-one și cazul listei cu un singur nod.

Eroarea, în practică:'NoneType' object has no attribute 'urm'Lista înlănțuită: capul nu se șterge

40 Mid

Primești temperaturile pe zile. Pentru fiecare zi, câte zile trebuie să aștepți până la o zi mai caldă? Scrie o soluție O(n) cu o stivă monotonă.

Răspuns scurt: Ții o stivă cu indicii zilelor care încă așteaptă o zi mai caldă, cu temperaturi descrescătoare de la bază la vârf. Când ziua curentă e mai caldă decât vârful, scoți vârful și îi calculezi răspunsul. Fiecare indice intră și iese o dată: O(n).

Forța brută caută spre dreapta pentru fiecare zi, deci O(n²). Stiva monotonă rezolvă clasa de probleme „următorul element mai mare / mai mic” în O(n).

PYTHON
def zile_pana_la_cald(t):
    rez = [0] * len(t)
    stiva = []                      # indici, temperaturi descrescătoare
    for i, temp in enumerate(t):
        while stiva and t[stiva[-1]] < temp:
            j = stiva.pop()
            rez[j] = i - j
        stiva.append(i)
    return rez

print(zile_pana_la_cald([73, 74, 75, 71, 69, 72, 76, 73]))
# [1, 1, 4, 2, 1, 1, 0, 0]

Invariantul: stiva conține zilele pentru care nu s-a găsit încă o zi mai caldă, iar temperaturile lor descresc de jos în sus (sau sunt egale). Când sosește o zi mai caldă, toate zilele din vârf mai reci decât ea și-au găsit răspunsul. Zilele care rămân în stivă la final nu au o zi mai caldă, deci rămân 0.

Pe stivă pui indici, nu valori, pentru că ai nevoie de distanță și de poziția în rezultat.

De ce e O(n) deși are while în for: fiecare indice e pus pe stivă o dată și scos cel mult o dată. Totalul operațiilor pe stivă este cel mult 2n.

Variante cu același schelet:

  • următorul element mai mare (valoarea, nu distanța);
  • listă circulară: parcurgi de două ori, cu i % n;
  • cel mai mare dreptunghi dintr-o histogramă: stivă crescătoare, iar la scoatere calculezi aria;
  • span-ul prețului unei acțiuni: câte zile consecutive anterioare au avut prețul mai mic sau egal.

Condiția strictă < față de <= decide cum tratezi valorile egale. Aici, o zi cu aceeași temperatură nu e „mai caldă”, deci < e corect.

Ce urmărește intervievatorul: Verifică dacă recunoști tiparul de stivă monotonă și poți argumenta complexitatea liniară. Candidații care nu-l cunosc rămân de obicei la O(n²).

Eroarea, în practică:Stiva monotonă cu valori, nu indici

41 Senior

Pentru o listă și o fereastră de lungime k, întoarce maximul fiecărei ferestre glisante, în O(n). De ce nu ajunge un heap?

Răspuns scurt: Un deque de indici cu valori descrescătoare: scoți din spate indicii cu valori mai mici decât elementul nou și din față indicele ieșit din fereastră. Maximul e mereu în față. Fiecare indice intră și iese o dată, deci O(n).

PYTHON
from collections import deque

def maxime_fereastra(a, k):
    dq = deque()          # indici, valori a[i] descrescătoare
    rez = []
    for i, x in enumerate(a):
        while dq and a[dq[-1]] <= x:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            rez.append(a[dq[0]])
    return rez

print(maxime_fereastra([1, 3, -1, -3, 5, 3, 6, 7], 3))  # [3, 3, 5, 5, 6, 7]

De ce putem scoate elementele mai mici din spate: dacă a[j] <= x și j < i, atunci j iese din fereastră înaintea lui i și, cât timp sunt amândoi în fereastră, i este cel puțin la fel de mare. Deci j nu mai poate fi niciodată maximul. Coada păstrează doar candidații care ar putea deveni maxim, ordonați descrescător.

Din față scoți indicele care a ieșit din fereastră. E suficientă o singură verificare pe pas, pentru că fereastra avansează cu o poziție.

Complexitate: fiecare indice intră o dată și iese cel mult o dată, deci O(n) total, cu O(k) memorie.

Cu un heap: pui (-a[i], i) și, la fiecare pas, scoți din vârf elementele cu indice ieșit din fereastră (ștergere leneșă, lazy deletion). Este corect, dar O(n log n), iar heap-ul poate crește până la n elemente, pentru că elementele vechi nu sunt scoase imediat. Ștergerea unui element arbitrar dintr-un heapq nu e eficientă.

Alternativă O(n) fără deque: împarți lista în blocuri de k, calculezi maximele prefix și sufix în fiecare bloc, iar maximul ferestrei [i, i+k−1] este max(sufix[i], prefix[i+k-1]).

Aceeași structură, numită coadă monotonă, apare ca optimizare în DP: „dp[i] = max(dp[j]) pentru j în ultimele k poziții”.

Ce urmărește intervievatorul: Este o problemă de nivel avansat care verifică dacă stăpânești coada monotonă și poți argumenta de ce elementele scoase nu mai contează. Comparația cu heap-ul arată maturitatea.

Eroarea, în practică:Sliding window: lipsește ultima fereastră

Recursivitate și backtracking

42 Junior

Ce trebuie să aibă orice funcție recursivă corectă? Ce se întâmplă în Python dacă recursivitatea e prea adâncă?

Răspuns scurt: Un caz de bază care se rezolvă fără apel recursiv și un pas recursiv care se apropie mereu de cazul de bază. În Python, depășirea limitei implicite (aproximativ 1000 de apeluri) aruncă RecursionError.

O funcție recursivă se definește prin ea însăși pe o problemă mai mică. Pentru a fi corectă:

  • cazul de bază se rezolvă direct și oprește recursivitatea;
  • pasul recursiv reduce problema spre cazul de bază, la fiecare apel;
  • rezultatele subproblemelor se combină corect.
PYTHON
def suma_cifrelor(n):
    if n < 10:              # cazul de bază
        return n
    return n % 10 + suma_cifrelor(n // 10)

print(suma_cifrelor(9875))  # 29

Fiecare apel neterminat ocupă un cadru pe stiva de apeluri (call stack). Pentru suma_cifrelor(9875) sunt 4 cadre active în momentul cel mai adânc. Dacă uiți cazul de bază sau pasul nu se apropie de el (de exemplu n // 1), stiva crește la nesfârșit.

În CPython, sys.getrecursionlimit() întoarce implicit 1000. Depășirea dă RecursionError: maximum recursion depth exceeded. Poți ridica limita cu sys.setrecursionlimit, dar riști să epuizezi stiva reală a procesului și să-l oprești brusc. Python nu face nici optimizarea apelurilor de coadă (tail call optimization), deci nici recursivitatea de coadă nu scapă de limită.

Consecințe practice la interviu:

  • pentru un DFS pe un graf sau pe un arbore degenerat cu 10⁵ noduri, scrii varianta iterativă, cu stivă explicită;
  • pentru recursivitate cu adâncime logaritmică (merge sort, căutare binară, arbori echilibrați), limita nu e o problemă;
  • memoria unei soluții recursive este cel puțin O(adâncime).

Orice recursivitate poate fi transformată în iterație cu o stivă explicită; uneori codul devine mai lung, dar e mai robust.

Ce urmărește intervievatorul: Verifică înțelegerea mecanismului de apel și a limitei concrete din Python. Mulți candidați nu știu că Python nu are tail call optimization.

Eroarea, în practică:RecursionError: maximum recursion depthunsupported operand: 'int' and 'NoneType'

43 Junior

De ce este lentă implementarea recursivă directă a lui Fibonacci? Arată cum ajungi de la O(2ⁿ) la O(n) timp și O(1) memorie.

Răspuns scurt: Varianta directă recalculează aceleași valori de un număr exponențial de ori. Memoizarea reține fiecare rezultat, deci O(n) timp și memorie. Varianta iterativă cu două variabile păstrează doar ultimele două valori: O(n) timp, O(1) memorie.

PYTHON
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

Arborele de apeluri se ramifică în două la fiecare nivel: fib(5) calculează fib(3) de două ori, fib(2) de trei ori și așa mai departe. Numărul de apeluri crește aproximativ ca φⁿ (φ ≈ 1,618), deci exponențial. fib(40) face peste o sută de milioane de apeluri.

Pasul 1, memoizare (top-down): reții rezultatele deja calculate.

PYTHON
from functools import lru_cache

@lru_cache(maxsize=None)
def fib_memo(n):
    if n < 2:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)

Fiecare valoare se calculează o singură dată: O(n) timp, O(n) memorie (cache plus stiva de apeluri). Din Python 3.9 poți scrie @functools.cache.

Pasul 2, tabulare (bottom-up): calculezi de la mic la mare, într-o buclă, fără recursivitate și fără limită de adâncime.

Pasul 3, reducerea memoriei: fib(i) depinde doar de ultimele două valori.

PYTHON
def fib_iter(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

print(fib_iter(50))  # 12586269025

O(n) timp, O(1) memorie.

Există și O(log n): ridicarea la putere a matricei [[1, 1], [1, 0]] prin înjumătățirea exponentului. Rar se cere la interviu, dar merită menționată.

Atenție: în Python întregii sunt de precizie arbitrară, deci numerele Fibonacci mari nu dau overflow, dar adunarea numerelor foarte lungi nu mai e O(1).

Ce urmărește intervievatorul: Este introducerea standard în programarea dinamică. Intervievatorul urmărește dacă poți explica de ce recursivitatea e exponențială și dacă știi să reduci memoria.

Eroarea, în practică:fib(40) recursiv nu se termină (fără memo)Fibonacci: a = b; b = a + b pe linii separate

44 Junior

Scrie o funcție care calculează xⁿ în O(log n) înmulțiri, fără ** și fără pow. Cum tratezi exponenții negativi?

Răspuns scurt: Folosești înjumătățirea exponentului: xⁿ = (x^(n/2))² pentru n par și x · xⁿ⁻¹ pentru n impar. La fiecare pas exponentul se înjumătățește, deci O(log n). Pentru n negativ calculezi 1 / x^(−n).

Înmulțirea repetată face n − 1 înmulțiri. Ridicarea rapidă la putere (exponentiation by squaring) folosește faptul că x¹⁰ = (x⁵)² și x⁵ = x · (x²)².

Varianta recursivă:

PYTHON
def putere(x, n):
    if n < 0:
        return 1 / putere(x, -n)
    if n == 0:
        return 1
    jumatate = putere(x, n // 2)
    if n % 2 == 0:
        return jumatate * jumatate
    return jumatate * jumatate * x

print(putere(2, 10))   # 1024
print(putere(2, -2))   # 0.25

Greșeala clasică este return putere(x, n // 2) * putere(x, n // 2): două apeluri recursive în loc de unul fac complexitatea înapoi O(n). Calculezi jumătatea o dată și o refolosești.

Varianta iterativă, bazată pe biții exponentului:

PYTHON
def putere_iter(x, n):
    if n < 0:
        x, n = 1 / x, -n
    rez = 1
    while n:
        if n & 1:
            rez *= x
        x *= x
        n >>= 1
    return rez

Fiecare bit de 1 din n contribuie cu un factor x^(2^k). Numărul de iterații este numărul de biți ai lui n, adică O(log n), cu O(1) memorie.

Cazuri de discutat: x = 0 și n negativ (împărțire la zero), 0⁰ (convenția din Python este 1), erorile de rotunjire la float.

Unde se folosește: aritmetica modulară (pow(baza, exp, mod) din Python o face nativ, de exemplu în criptografia RSA), puteri de matrice pentru recurențe liniare precum Fibonacci, numărarea drumurilor de lungime k într-un graf.

Ce urmărește intervievatorul: Verifică dacă știi tehnica divide et impera și dacă eviți capcana celor două apeluri recursive. Tratarea exponentului negativ e un caz limită pe care mulți îl uită.

45 Junior

Scrie o funcție care generează toate permutările unei liste de elemente distincte. Câte sunt și ce complexitate are generarea?

Răspuns scurt: Prin backtracking: construiești permutarea poziție cu poziție, alegi un element nefolosit, continui recursiv și apoi îl eliberezi. Există n! permutări, iar generarea lor costă O(n · n!), pentru că fiecare permutare are lungimea n.

PYTHON
def permutari(a):
    rez = []
    curent = []
    folosit = [False] * len(a)

    def bt():
        if len(curent) == len(a):
            rez.append(curent[:])      # copie!
            return
        for i in range(len(a)):
            if not folosit[i]:
                folosit[i] = True
                curent.append(a[i])
                bt()
                curent.pop()           # anulezi alegerea
                folosit[i] = False

    bt()
    return rez

print(permutari([1, 2, 3]))
# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Schema de backtracking are trei pași, care apar la toate problemele din această familie: alegi, explorezi, anulezi alegerea. Anularea (pop și folosit[i] = False) readuce starea exact cum era, ca următoarea ramură să pornească curat.

rez.append(curent[:]) este bug-ul clasic: fără copie, adaugi aceeași listă de n! ori, iar la final toate intrările sunt goale, pentru că curent a fost golită prin pop.

Complexitate: n! frunze, iar copierea fiecărei permutări costă O(n), deci O(n · n!) timp. Memoria suplimentară, fără rezultat, este O(n) pentru recursivitate și folosit.

Pentru n = 10 sunt 3.628.800 de permutări. Generarea completă devine impracticabilă rapid, ceea ce e util de spus când intervievatorul întreabă de scalare.

Variante:

  • elemente duplicate: sortezi și sari peste a[i] dacă a[i] == a[i-1] și a[i-1] nu e folosit în ramura curentă;
  • următoarea permutare în ordine lexicografică, pe loc, în O(n);
  • în practică: itertools.permutations(a), care generează leneș, fără să țină totul în memorie.

Ce urmărește intervievatorul: Este testul de bază pentru backtracking. Intervievatorul urmărește pasul de anulare și copia la salvarea rezultatului, unde se fac cele mai multe greșeli.

Eroarea, în practică:Backtracking: rezultatul conține liste goaleBacktracking fără pop(): lipsesc soluții

46 Mid

Generează toate submulțimile unei liste de elemente distincte. Arată varianta cu backtracking și pe cea cu măști de biți. Ce complexitate au?

Răspuns scurt: Fiecare element e inclus sau nu, deci 2ⁿ submulțimi. Backtracking-ul salvează starea curentă la fiecare nod; varianta cu biți parcurge măștile 0..2ⁿ − 1, unde bitul i indică elementul i. Ambele sunt O(n · 2ⁿ).

Backtracking, unde fiecare nod al arborelui de recursivitate este o submulțime:

PYTHON
def submultimi(a):
    rez = []
    curent = []

    def bt(start):
        rez.append(curent[:])
        for i in range(start, len(a)):
            curent.append(a[i])
            bt(i + 1)
            curent.pop()

    bt(0)
    return rez

print(submultimi([1, 2, 3]))
# [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

Parametrul start asigură că elementele se aleg doar în ordine crescătoare a indicilor, deci {1, 2} nu apare și ca {2, 1}. Asta deosebește submulțimile (combinații) de permutări.

Varianta cu măști de biți (bitmask):

PYTHON
def submultimi_biti(a):
    n = len(a)
    return [[a[i] for i in range(n) if masca >> i & 1]
            for masca in range(1 << n)]

Numărul masca de la 0 la 2ⁿ − 1 codifică o submulțime: bitul i este 1 dacă a[i] e inclus. 1 << n este 2ⁿ. Precedența în Python face ca masca >> i & 1 să se evalueze ca (masca >> i) & 1.

Complexitate: 2ⁿ submulțimi, fiecare copiată în O(n), deci O(n · 2ⁿ) timp și memorie pentru rezultat. Pentru n = 20 sunt peste un milion de submulțimi, deci e o limită practică.

Variante frecvente:

  • cu duplicate: sortezi și, în bucla for, sari a[i] dacă i > start și a[i] == a[i-1];
  • doar submulțimile de mărime k (combinări): adaugi la rezultat doar când len(curent) == k și tai ramurile care nu mai pot ajunge la k;
  • masca de biți devine stare în DP pe submulțimi, de exemplu în problema comis-voiajorului cu O(2ⁿ · n²).

Ce urmărește intervievatorul: Verifică dacă înțelegi arborele de decizie și diferența dintre submulțimi și permutări. Varianta cu biți arată dacă poți lega două tehnici diferite.

Eroarea, în practică:Backtracking: rezultatul conține liste goaleBacktracking fără pop(): lipsesc soluții

47 Mid

Primești o listă de numere pozitive distincte și o țintă. Găsește toate combinațiile cu suma egală cu ținta, în care fiecare număr poate fi folosit de oricâte ori. Cum tai ramurile inutile?

Răspuns scurt: Backtracking cu un parametru start: la fiecare pas încerci numerele de la start încolo și reapelezi tot cu i (nu i + 1), pentru că poți refolosi numărul. Sortezi lista și te oprești din buclă când numărul depășește suma rămasă.

PYTHON
def combinatii_suma(candidati, tinta):
    candidati.sort()
    rez = []
    curent = []

    def bt(start, ramas):
        if ramas == 0:
            rez.append(curent[:])
            return
        for i in range(start, len(candidati)):
            c = candidati[i]
            if c > ramas:
                break                 # restul sunt și mai mari
            curent.append(c)
            bt(i, ramas - c)          # i, nu i + 1: poți refolosi
            curent.pop()

    bt(0, tinta)
    return rez

print(combinatii_suma([2, 3, 6, 7], 7))  # [[2, 2, 3], [7]]
print(combinatii_suma([2, 3, 5], 8))     # [[2, 2, 2, 2], [2, 3, 3], [3, 5]]

Trei decizii de proiectare contează:

  • start evită permutările aceleiași combinații: [2, 2, 3] apare, dar [2, 3, 2] și [3, 2, 2] nu, pentru că numerele se aleg doar în ordine nedescrescătoare;
  • apelul cu i permite refolosirea; cu i + 1 obții varianta „fiecare număr o singură dată”;
  • tăierea ramurilor (pruning) cu break funcționează doar dacă lista e sortată. Dacă numărul curent e prea mare, toate de după el sunt la fel, deci nu are rost să le încerci.

Complexitatea e greu de exprimat exact. O limită superioară este O(n^(T/m)), unde T este ținta și m cel mai mic candidat, adică adâncimea maximă a arborelui. În practică, tăierea ramurilor o reduce mult.

Variante:

  • „fiecare număr o dată, lista are duplicate”: apel cu i + 1 și sari candidati[i] == candidati[i-1] când i > start;
  • doar numărul de combinații, nu lista lor: devine programare dinamică (problema restului cu monede), în O(n · T), mult mai rapid decât enumerarea;
  • numere negative: tăierea cu break nu mai e validă, iar problema poate avea o infinitate de soluții.

Ce urmărește intervievatorul: Verifică dacă stăpânești variațiile de backtracking (refolosire, ordine, tăiere). Intervievatorul urmărește diferența dintre i și i + 1 și condiția pentru break.

48 Mid

Rezolvă problema celor N regine: în câte moduri poți așeza N regine pe o tablă N × N fără ca două să se atace? Cum verifici conflictele în O(1)?

Răspuns scurt: Pui câte o regină pe fiecare rând, prin backtracking pe coloane. Ții trei seturi: coloane ocupate, diagonale r - c și antidiagonale r + c. Verificarea și actualizarea sunt O(1), iar ramurile cu conflict se taie imediat.

Observația care reduce mult spațiul de căutare: două regine nu pot fi pe același rând, deci pui exact una pe fiecare rând. Mai rămâne de ales coloana.

PYTHON
def n_regine(n):
    coloane, diag, antidiag = set(), set(), set()
    numar = 0

    def bt(r):
        nonlocal numar
        if r == n:
            numar += 1
            return
        for c in range(n):
            if c in coloane or r - c in diag or r + c in antidiag:
                continue
            coloane.add(c); diag.add(r - c); antidiag.add(r + c)
            bt(r + 1)
            coloane.remove(c); diag.remove(r - c); antidiag.remove(r + c)

    bt(0)
    return numar

print(n_regine(4))  # 2
print(n_regine(8))  # 92

De ce r - c și r + c: pe o diagonală care coboară spre dreapta, rândul și coloana cresc împreună, deci diferența lor e constantă. Pe o antidiagonală, rândul crește când coloana scade, deci suma e constantă. Astfel, fiecare diagonală are un identificator unic, iar verificarea devine un test de apartenență într-un set, O(1), în loc de o parcurgere a tablei.

Pentru a întoarce tablele, nu doar numărul lor, ții o listă poz[r] = c și construiești la final reprezentarea, de exemplu un șir cu „Q” și „.” pe fiecare rând.

Complexitate: limita grosieră este O(n!), pentru că pe rândul r ai cel mult n − r coloane libere. Tăierea pe diagonale reduce mult numărul real de noduri vizitate. Memoria este O(n).

Optimizări pentru n mare: măști de biți în locul seturilor (coloanele, diagonalele și antidiagonalele devin trei întregi), simetria tablei (calculezi doar jumătate din pozițiile primului rând și dublezi). Pentru o singură soluție, nu toate, există construcții directe care nu folosesc căutarea.

Ce urmărește intervievatorul: Este un exercițiu clasic de backtracking cu tăiere. Intervievatorul urmărește identificarea diagonalelor prin r - c și r + c și restaurarea corectă a stării.

49 Senior

Primești o grilă de litere și un cuvânt. Spune dacă se poate forma cuvântul din celule vecine pe orizontală sau verticală, fără să refolosești o celulă. Ce complexitate are și cum o optimizezi?

Răspuns scurt: DFS cu backtracking din fiecare celulă: potrivești litera curentă, marchezi celula ca vizitată, explorezi cei patru vecini pentru litera următoare și apoi o demarchezi. Complexitatea în cel mai rău caz este O(R · C · 3^L), unde L este lungimea cuvântului.

PYTHON
def exista_cuvant(grila, cuvant):
    R, C = len(grila), len(grila[0])

    def dfs(r, c, k):
        if k == len(cuvant):
            return True
        if not (0 <= r < R and 0 <= c < C) or grila[r][c] != cuvant[k]:
            return False
        litera = grila[r][c]
        grila[r][c] = "#"                 # marcăm vizitat
        gasit = (dfs(r + 1, c, k + 1) or dfs(r - 1, c, k + 1) or
                 dfs(r, c + 1, k + 1) or dfs(r, c - 1, k + 1))
        grila[r][c] = litera              # restaurăm
        return gasit

    return any(dfs(r, c, 0) for r in range(R) for c in range(C))

g = [list("ABCE"), list("SFCS"), list("ADEE")]
print(exista_cuvant(g, "ABCCED"))  # True
print(exista_cuvant(g, "ABCB"))    # False

Marcarea pe loc cu „#” evită un set separat de celule vizitate. Restaurarea este obligatorie: aceeași celulă poate fi folosită de o altă ramură. Dacă nu ai voie să modifici intrarea, folosești un set, cu cost puțin mai mare.

Complexitate: pornești din R · C celule. Primul pas are 4 vecini, iar următorii cel mult 3, pentru că nu te întorci de unde ai venit. Deci O(R · C · 3^L) timp și O(L) memorie pentru recursivitate.

Optimizări care contează în practică:

  • verificare rapidă de frecvență: dacă grila nu conține destule apariții ale fiecărei litere din cuvânt, întorci False imediat;
  • inversarea cuvântului: dacă prima literă e mult mai frecventă în grilă decât ultima, cauți cuvântul inversat, ca să tai ramurile mai devreme;
  • mai multe cuvinte (Word Search II): în loc de un DFS per cuvânt, construiești un trie din toate cuvintele și faci un singur DFS din fiecare celulă, coborând simultan în trie. Scoți din trie cuvintele găsite, ca să nu le cauți iar.

or se evaluează leneș în Python, deci celelalte direcții nu se mai explorează odată ce una a reușit.

Ce urmărește intervievatorul: Verifică backtracking-ul pe grile, restaurarea stării și analiza complexității exponențiale. Extensia cu trie arată dacă poți combina structuri de date.

Sortare și căutare binară

Exersează capitolul cu exerciții reale: Curs algoritmi pentru începători →
50 Junior

Compară sortarea prin metoda bulelor, prin selecție și prin inserție. Când ar fi sortarea prin inserție o alegere bună în practică?

Răspuns scurt: Toate trei sunt O(n²) în cel mai rău caz și sortează pe loc. Inserția este O(n) pe date aproape sortate, este stabilă și are constante mici, de aceea e folosită pentru bucăți mici chiar în Timsort, sortarea din Python.

Pe scurt:

  • bubble sort: compară vecinii și îi interschimbă; după fiecare trecere, cel mai mare element ajunge la final. Stabil. Cu oprire când o trecere nu face nicio interschimbare, devine O(n) pe date deja sortate;
  • selection sort: caută minimul din partea nesortată și îl pune la început. Face mereu O(n²) comparații, dar doar O(n) interschimbări. Nu e stabil în varianta clasică;
  • insertion sort: ia fiecare element și îl inserează la locul lui în prefixul deja sortat.
PYTHON
def sortare_insertie(a):
    for i in range(1, len(a)):
        x = a[i]
        j = i - 1
        while j >= 0 and a[j] > x:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = x
    return a

print(sortare_insertie([5, 2, 4, 6, 1, 3]))  # [1, 2, 3, 4, 5, 6]

Numărul de mutări din inserție este egal cu numărul de inversiuni (perechi i < j cu a[i] > a[j]). Pe o listă aproape sortată sunt puține inversiuni, deci timpul este aproape liniar. Condiția strictă a[j] > x păstrează stabilitatea: elementele egale nu se depășesc între ele.

Când alegi inserția:

  • liste mici, de ordinul zecilor de elemente: overhead-ul algoritmilor O(n log n) nu se mai justifică;
  • date care sosesc aproape în ordine, de exemplu evenimente cu mici întârzieri;
  • ca parte a unui algoritm hibrid: Timsort sortează prin inserție (binară) rulaje scurte, apoi le interclasează; introsort din multe implementări C++ trece la inserție pe partiții mici.

Selection sort este util doar când scrierile sunt foarte scumpe, pentru că face cele mai puține interschimbări. Bubble sort are în principal valoare didactică.

Ce urmărește intervievatorul: Verifică dacă înțelegi algoritmii elementari dincolo de „sunt O(n²)”. Un candidat bun știe de ce inserția e rapidă pe date aproape sortate și unde e folosită în realitate.

Eroarea, în practică:IndexError la sortarea prin inserție (j >= 0)

51 Junior

Implementează merge sort. Ce complexitate de timp și de memorie are și de ce este garantat O(n log n)?

Răspuns scurt: Împarți lista în două jumătăți, le sortezi recursiv și le interclasezi. Sunt log n niveluri de împărțire, iar interclasarea pe fiecare nivel costă O(n), deci O(n log n) în orice caz. Memoria suplimentară este O(n), pentru listele auxiliare.

PYTHON
def merge_sort(a):
    if len(a) <= 1:
        return a
    mij = len(a) // 2
    st = merge_sort(a[:mij])
    dr = merge_sort(a[mij:])
    return interclaseaza(st, dr)

def interclaseaza(st, dr):
    rez = []
    i = j = 0
    while i < len(st) and j < len(dr):
        if st[i] <= dr[j]:
            rez.append(st[i]); i += 1
        else:
            rez.append(dr[j]); j += 1
    rez.extend(st[i:])
    rez.extend(dr[j:])
    return rez

print(merge_sort([38, 27, 43, 3, 9, 82, 10]))  # [3, 9, 10, 27, 38, 43, 82]

Este exemplul standard de divide et impera. Recurența este T(n) = 2T(n/2) + O(n). Arborele de recursivitate are log₂ n niveluri, iar pe fiecare nivel interclasările procesează în total n elemente. Deci O(n log n), indiferent de date: nu există un caz rău ca la quicksort.

Memoria: listele auxiliare de la interclasare însumează O(n) pe nivelul curent, iar stiva de apeluri are adâncimea O(log n). Totalul este O(n). Feliile a[:mij] creează copii; o implementare mai economă lucrează cu indici și un singur buffer auxiliar.

<= la interclasare face sortarea stabilă: la egalitate, elementul din stânga vine primul.

Unde e merge sort alegerea bună:

  • liste înlănțuite: interclasarea nu are nevoie de memorie suplimentară, iar accesul secvențial e natural;
  • sortare externă: datele nu încap în memorie, deci sortezi bucăți și le interclasezi de pe disc;
  • când ai nevoie de stabilitate și garanție O(n log n).

Bonus: numărul de inversiuni dintr-o listă se calculează în aceeași trecere. Când iei un element din dreapta, toate elementele rămase în stânga formează inversiuni cu el, deci aduni len(st) - i.

Ce urmărește intervievatorul: Este algoritmul de referință pentru divide et impera. Intervievatorul urmărește recurența, memoria O(n) și dacă știi de ce e stabil.

Eroarea, în practică:RecursionError în merge sort sau quicksortInterclasarea pierde elementele rămase

52 Junior

Scrie căutarea binară iterativă într-o listă sortată. Care sunt bug-urile clasice și cum le eviți?

Răspuns scurt: Ții intervalul [st, dr], compari cu mijlocul și elimini jumătatea fără soluție. Bug-uri clasice: condiția de oprire greșită, st = mij în loc de mij + 1 (buclă infinită) și overflow-ul mijlocului în Java sau C++.

PYTHON
def cautare_binara(a, x):
    st, dr = 0, len(a) - 1          # interval închis [st, dr]
    while st <= dr:
        mij = (st + dr) // 2
        if a[mij] == x:
            return mij
        if a[mij] < x:
            st = mij + 1
        else:
            dr = mij - 1
    return -1

a = [1, 3, 5, 7, 9, 11]
print(cautare_binara(a, 7))   # 3
print(cautare_binara(a, 4))   # -1

Cheia este un invariant clar: dacă x există, se află în [st, dr]. Toate deciziile decurg din el:

  • intervalul e închis, deci bucla continuă cât timp nu e gol: st <= dr. Cu st < dr ai rata cazul cu un singur element rămas;
  • a[mij] a fost deja verificat, deci îl excluzi: mij + 1 și mij - 1. Cu st = mij, când st și dr sunt vecini, mijlocul rămâne st și bucla nu se mai termină;
  • în Java sau C++, (st + dr) / 2 poate depăși int pentru liste uriașe, motiv pentru care se scrie st + (dr - st) / 2. În Python întregii nu au overflow, dar e bine să știi motivul.

Alt stil des folosit este intervalul semi-deschis [st, dr), cu dr = len(a), while st < dr și dr = mij. Ambele sunt corecte; important e să nu le amesteci.

Complexitate: O(log n) timp, O(1) memorie. Pentru un milion de elemente, cel mult 20 de comparații.

În Python, modulul bisect oferă bisect_left și bisect_right, implementate în C. La interviu ți se cere de obicei implementarea manuală, dar merită spus că în cod real le-ai folosi pe acestea.

Precondiția e esențială: lista trebuie să fie sortată după aceeași ordine pe care o folosește comparația.

Ce urmărește intervievatorul: Căutarea binară pare ușoară, dar e una dintre cele mai frecvente surse de bug-uri. Intervievatorul urmărește invariantul și condițiile de margine, nu doar ideea.

Eroarea, în practică:Căutarea binară intră în buclă infinităIndexError la căutarea binară

53 Junior

Ce înseamnă că o sortare este stabilă? Cum sortezi în Python o listă de angajați după departament crescător și, în cadrul departamentului, după salariu descrescător?

Răspuns scurt: O sortare este stabilă dacă elementele cu chei egale își păstrează ordinea relativă. Sortarea din Python (Timsort) este stabilă. Pentru mai multe criterii folosești o cheie tuplu, key=lambda e: (e.dep, -e.salariu), sau două sortări succesive, de la criteriul secundar la cel principal.

Stabilitatea contează când sortezi înregistrări după un câmp, iar ele au și alte câmpuri. Dacă o listă de comenzi e deja ordonată după dată și o sortezi stabil după client, comenzile fiecărui client rămân în ordinea datei.

Stabile: merge sort, insertion sort, Timsort, counting sort (implementat corect). Instabile în varianta clasică: quicksort, heap sort, selection sort.

sorted() și list.sort() sunt garantat stabile în Python. Pentru sortarea pe mai multe criterii ai două variante:

PYTHON
from dataclasses import dataclass

@dataclass
class Angajat:
    nume: str
    dep: str
    salariu: int

lista = [Angajat("Ana", "IT", 9000), Angajat("Dan", "HR", 6000),
         Angajat("Ion", "IT", 12000), Angajat("Eva", "HR", 7000)]

# 1. cheie tuplu; minus inversează doar criteriul numeric
r1 = sorted(lista, key=lambda e: (e.dep, -e.salariu))

# 2. două sortări stabile: întâi criteriul secundar, apoi cel principal
r2 = sorted(lista, key=lambda e: e.salariu, reverse=True)
r2 = sorted(r2, key=lambda e: e.dep)

print([e.nume for e in r1])  # ['Eva', 'Dan', 'Ion', 'Ana']
print(r1 == r2)              # True

Trucul cu minus merge doar pentru numere. Pentru un șir în ordine descrescătoare combinat cu alt criteriu crescător, varianta cu sortări succesive e singura simplă, și funcționează tocmai datorită stabilității. Parametrul reverse=True păstrează și el stabilitatea: elementele egale nu sunt inversate între ele.

key este calculată o singură dată pe element, deci e mai eficientă decât un comparator. Dacă ai totuși un comparator scris ca funcție cu două argumente, îl adaptezi cu functools.cmp_to_key.

Complexitate: O(n log n), dar Timsort profită de rulajele deja sortate și ajunge la O(n) pe date ordonate.

Ce urmărește intervievatorul: Verifică dacă știi ce e stabilitatea și cum o folosești concret. Mulți candidați nu știu că sortarea Python e stabilă sau că două sortări succesive rezolvă criteriile mixte.

Eroarea, în practică:sort() takes no positional argumentsbad operand type for unary -: 'str'

54 Junior

Primești o listă de intervale [start, final]. Unește intervalele care se suprapun și întoarce lista rezultată.

Răspuns scurt: Sortezi intervalele după început. Parcurgi lista și, dacă intervalul curent începe înainte de finalul ultimului interval din rezultat, extinzi acel final; altfel adaugi un interval nou. O(n log n) timp, din cauza sortării.

PYTHON
def uneste_intervale(intervale):
    if not intervale:
        return []
    intervale = sorted(intervale, key=lambda x: x[0])
    rez = [list(intervale[0])]
    for s, f in intervale[1:]:
        if s <= rez[-1][1]:
            rez[-1][1] = max(rez[-1][1], f)
        else:
            rez.append([s, f])
    return rez

print(uneste_intervale([[1, 3], [2, 6], [8, 10], [15, 18]]))
# [[1, 6], [8, 10], [15, 18]]
print(uneste_intervale([[1, 4], [2, 3]]))
# [[1, 4]]

De ce sortarea după început: după sortare, intervalele care se pot uni sunt consecutive. Dacă intervalul curent nu atinge ultimul interval din rezultat, nu poate atinge nici unul dintre cele anterioare, pentru că toate se termină mai devreme.

Două detalii pe care le verifică intervievatorul:

  • max(rez[-1][1], f): un interval poate fi conținut complet în altul, ca [1, 4] și [2, 3]. Fără max, ai micșora greșit finalul la 3;
  • s <= rez[-1][1] față de <: dacă [1, 2] și [2, 3] se consideră suprapuse depinde de enunț (intervale închise sau semi-deschise). Clarifică înainte să scrii.

list(intervale[0]) creează o copie, ca să nu modifici intervalele primite. Sortarea cu sorted lasă și ea lista originală neatinsă.

Complexitate: O(n log n) pentru sortare, O(n) pentru parcurgere, O(n) memorie pentru rezultat.

Variante înrudite:

  • inserarea unui interval într-o listă deja sortată și disjunctă: O(n), fără sortare;
  • numărul minim de săli pentru ședințe: sortezi după început și ții un min-heap cu orele de final;
  • numărul minim de intervale de eliminat ca restul să nu se suprapună: greedy, sortare după final.

Ce urmărește intervievatorul: Este o problemă foarte frecventă, inclusiv în variante de business (programări, rezervări). Intervievatorul urmărește intervalul conținut în altul și clarificarea capetelor.

55 Junior

Într-o listă sortată cu valori care se repetă, găsește prima și ultima poziție a unei valori x în O(log n). Cum te ajută bisect?

Răspuns scurt: Faci două căutări binare: una pentru prima poziție cu valoare ≥ x (lower bound) și una pentru prima poziție cu valoare > x (upper bound). Ultima apariție este cu una înaintea celei de-a doua. În Python, bisect_left și bisect_right fac exact asta.

O căutare binară obișnuită se oprește la prima egalitate găsită, care poate fi oriunde în blocul de valori egale. Ca să găsești marginea, nu te oprești la egalitate, ci continui spre stânga.

PYTHON
def lower_bound(a, x):
    st, dr = 0, len(a)              # interval semi-deschis [st, dr)
    while st < dr:
        mij = (st + dr) // 2
        if a[mij] < x:
            st = mij + 1
        else:
            dr = mij
    return st                        # primul indice cu a[i] >= x

def prima_ultima(a, x):
    st = lower_bound(a, x)
    if st == len(a) or a[st] != x:
        return -1, -1
    dr = lower_bound(a, x + 1) - 1   # merge pentru întregi
    return st, dr

a = [5, 7, 7, 8, 8, 8, 10]
print(prima_ultima(a, 8))   # (3, 5)
print(prima_ultima(a, 6))   # (-1, -1)

lower_bound(a, x + 1) funcționează doar pentru întregi. Varianta generală este un upper bound, cu condiția a[mij] <= x.

Biblioteca standard le are gata:

PYTHON
from bisect import bisect_left, bisect_right
st = bisect_left(a, 8)        # 3
dr = bisect_right(a, 8) - 1   # 5
numar = bisect_right(a, 8) - bisect_left(a, 8)   # 3 apariții

bisect_left întoarce poziția la care ai insera x înaintea valorilor egale, iar bisect_right după ele. Diferența dintre ele este numărul de apariții, calculat în O(log n), fără parcurgerea blocului. Parcurgerea blocului ar fi O(k) și, dacă toată lista are aceeași valoare, O(n).

Din Python 3.10, funcțiile din bisect acceptă și un parametru key.

Utilizări practice: câte valori sunt într-un interval [lo, hi] (bisect_right(a, hi) - bisect_left(a, lo)), inserarea într-o listă sortată (insort, deși inserarea propriu-zisă e O(n)), căutarea celui mai apropiat element.

Ce urmărește intervievatorul: Verifică dacă știi lower bound și upper bound, pe care se bazează multe alte probleme. Greșeala tipică este căutarea binară urmată de o parcurgere liniară a blocului.

Eroarea, în practică:Căutarea binară intră în buclă infinităCăutarea binară ratează ultimul element

56 Mid

Cum funcționează quicksort? De ce are cazul cel mai rău O(n²) și cum îl eviți în practică?

Răspuns scurt: Alegi un pivot, partiționezi în elemente mai mici și mai mari și sortezi recursiv părțile. Dacă pivotul e mereu minimul sau maximul, partițiile sunt dezechilibrate: O(n²). Îl eviți cu pivot aleator, mediana din trei sau introsort.

Varianta pe loc, cu partiționarea Lomuto:

PYTHON
import random

def quicksort(a, st=0, dr=None):
    if dr is None:
        dr = len(a) - 1
    if st >= dr:
        return a
    p = random.randint(st, dr)
    a[p], a[dr] = a[dr], a[p]       # pivot aleator la final
    pivot = a[dr]
    i = st
    for j in range(st, dr):
        if a[j] < pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[dr] = a[dr], a[i]       # pivotul la locul final
    quicksort(a, st, i - 1)
    quicksort(a, i + 1, dr)
    return a

print(quicksort([3, 6, 1, 8, 2, 9, 2]))  # [1, 2, 2, 3, 6, 8, 9]

După partiționare, pivotul este exact pe poziția lui finală, iar toate elementele din stânga sunt mai mici.

Analiza:

  • partiții echilibrate: T(n) = 2T(n/2) + O(n) = O(n log n);
  • pivotul este primul sau ultimul element, iar lista e deja sortată: partiții de 0 și n − 1, deci T(n) = T(n − 1) + O(n) = O(n²), cu recursivitate de adâncime n;
  • cu pivot aleator, timpul așteptat este O(n log n) pentru orice intrare.

Alte probleme practice:

  • multe valori egale: Lomuto le pune pe toate într-o parte, deci tot O(n²). Soluția este partiționarea în trei (mai mici, egale, mai mari), ca la steagul olandez;
  • adâncimea stivei: recursezi pe partea mai mică și iterezi pe cea mare, ca stiva să rămână O(log n);
  • introsort (folosit de std::sort în implementările uzuale de C++) trece la heap sort când recursivitatea devine prea adâncă, deci garantează O(n log n).

De ce e totuși popular: sortează pe loc, are acces secvențial la memorie, deci folosește bine cache-ul procesorului, și constante mici. Dezavantaj: nu e stabil.

Ce urmărește intervievatorul: Intervievatorul verifică dacă înțelegi partiționarea și cauza cazului rău, nu doar complexitatea medie. Candidații buni pomenesc pivotul aleator și valorile duplicate.

Eroarea, în practică:RecursionError în quicksort (pivotul în sublistă)

57 Mid

Orice sortare prin comparații are nevoie de Ω(n log n) comparații. Cum reușește counting sort să sorteze în O(n + k) și când nu e o alegere bună?

Răspuns scurt: Counting sort nu compară elemente, ci numără câte apariții are fiecare valoare într-un interval cunoscut de dimensiune k. E liniar când k e comparabil cu n, dar devine nepractic când valorile acoperă un interval mare sau nu sunt întregi.

Limita Ω(n log n) se aplică doar algoritmilor care află ordinea exclusiv prin comparații a două elemente. Există n! ordonări posibile, iar fiecare comparație dă cel mult un bit de informație, deci ai nevoie de cel puțin log₂(n!) ≈ n log₂ n comparații.

Counting sort ocolește limita folosind valorile ca indici:

PYTHON
def counting_sort(a, max_val):
    numar = [0] * (max_val + 1)
    for x in a:
        numar[x] += 1
    rez = []
    for v, c in enumerate(numar):
        rez.extend([v] * c)
    return rez

print(counting_sort([4, 2, 2, 8, 3, 3, 1], 8))  # [1, 2, 2, 3, 3, 4, 8]

Timpul este O(n + k), unde k este numărul de valori posibile, iar memoria O(k). Pentru note de la 1 la 10 sau vârste de la 0 la 150, e excelent.

Varianta de mai sus pierde identitatea elementelor. Pentru a sorta înregistrări după o cheie întreagă, calculezi sume prefix pe numar, care îți spun poziția finală a fiecărei chei, și plasezi elementele parcurgând lista de la final spre început. Astfel sortarea rămâne stabilă.

Când nu merge:

  • intervalul e mare față de n: 1000 de numere între 0 și 10⁹ ar cere un miliard de contoare;
  • valorile nu sunt întregi discrete (numere reale, șiruri arbitrare);
  • valori negative: merge, dar trebuie decalate cu minimul.

Rude apropiate:

  • radix sort: sortează cifră cu cifră, cu counting sort stabil pe fiecare cifră; O(d · (n + b)) pentru d cifre în baza b, util pentru întregi mari sau șiruri de lungime fixă;
  • bucket sort: împarte valorile în găleți pe intervale, eficient pentru date distribuite uniform.

La interviu, recunoaște indiciul „valorile sunt între 0 și 100” sau „doar 0, 1 și 2”: e invitația la o soluție liniară.

Ce urmărește intervievatorul: Verifică dacă știi de unde vine limita n log n și când poți să o ocolești. Mulți candidați cred că nicio sortare nu poate fi liniară.

58 Mid

O listă sortată crescător a fost rotită într-un punct necunoscut (de exemplu [4, 5, 6, 7, 0, 1, 2]). Caută o valoare în O(log n).

Răspuns scurt: Faci căutare binară, dar la fiecare pas cel puțin una dintre jumătăți este sortată. Verifici care jumătate e sortată (comparând capetele) și dacă ținta se află în intervalul ei; dacă da, cauți acolo, altfel în cealaltă jumătate.

PYTHON
def cauta_rotit(a, x):
    st, dr = 0, len(a) - 1
    while st <= dr:
        mij = (st + dr) // 2
        if a[mij] == x:
            return mij
        if a[st] <= a[mij]:                 # stânga [st, mij] e sortată
            if a[st] <= x < a[mij]:
                dr = mij - 1
            else:
                st = mij + 1
        else:                               # dreapta [mij, dr] e sortată
            if a[mij] < x <= a[dr]:
                st = mij + 1
            else:
                dr = mij - 1
    return -1

a = [4, 5, 6, 7, 0, 1, 2]
print(cauta_rotit(a, 0))  # 4
print(cauta_rotit(a, 3))  # -1

De ce o jumătate e mereu sortată: punctul de rotire (unde valoarea scade brusc) se află într-o singură jumătate. Cealaltă nu îl conține, deci e crescătoare. Pe o jumătate sortată poți verifica în O(1) dacă ținta e în intervalul ei.

a[st] <= a[mij] cu egalitate tratează cazul în care st = mij, adică intervalul are două elemente.

Complexitate: O(log n) timp, O(1) memorie.

O abordare alternativă în doi pași: găsești întâi indicele minimului (punctul de rotire) cu o căutare binară care compară a[mij] cu a[dr], apoi faci o căutare binară normală în jumătatea potrivită. E tot O(log n) și uneori mai ușor de explicat.

PYTHON
def indice_minim(a):
    st, dr = 0, len(a) - 1
    while st < dr:
        mij = (st + dr) // 2
        if a[mij] > a[dr]:
            st = mij + 1
        else:
            dr = mij
    return st

Cu duplicate, de exemplu [1, 1, 1, 0, 1], nu mai poți decide ce jumătate e sortată când a[st] == a[mij] == a[dr]. Scazi atunci capetele cu câte un pas, iar cazul cel mai rău devine O(n). Merită spus explicit.

Ce urmărește intervievatorul: Verifică dacă poți adapta căutarea binară la o structură „aproape sortată” și dacă argumentezi de ce o jumătate e mereu sortată. Varianta cu duplicate e un follow-up frecvent.

59 Senior

O bandă transportă colete în ordinea dată, cu greutățile w. Care este capacitatea minimă a camionului ca toate coletele să fie livrate în cel mult D zile? Explică tehnica „căutare binară pe răspuns”.

Răspuns scurt: Răspunsul se află între max(w) și sum(w), iar funcția „se poate în D zile cu capacitatea c?” este monotonă: dacă merge pentru c, merge pentru orice capacitate mai mare. Faci căutare binară pe c, iar fiecare verificare e greedy, O(n). Total O(n log(sum(w))).

Căutarea binară nu se aplică doar pe liste. Se aplică pe orice predicat monoton pe un domeniu ordonat: false, false, …, false, true, true, …. Cauți primul true.

PYTHON
def zile_necesare(w, cap):
    zile, incarcat = 1, 0
    for g in w:
        if incarcat + g > cap:
            zile += 1
            incarcat = 0
        incarcat += g
    return zile

def capacitate_minima(w, D):
    st, dr = max(w), sum(w)
    while st < dr:
        mij = (st + dr) // 2
        if zile_necesare(w, mij) <= D:
            dr = mij            # mij merge, poate și mai puțin
        else:
            st = mij + 1        # mij nu merge
    return st

print(capacitate_minima([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5))  # 15
print(capacitate_minima([3, 2, 2, 4, 1, 4], 3))              # 6

Elementele argumentului:

  • marginile: sub max(w) cel mai greu colet nu încape; la sum(w) totul pleacă într-o zi;
  • monotonia: mai multă capacitate nu poate crește numărul de zile;
  • verificarea greedy: încarci colete cât încap, apoi treci la ziua următoare. Este optimă pentru o capacitate fixă, pentru că ordinea e impusă și umplerea maximă a zilei curente nu poate strica zilele următoare.

Complexitate: O(n · log S), unde S = sum(w). Pentru n = 5·10⁴ și greutăți până la 500, sunt aproximativ 25 de verificări a câte n pași.

Indiciile din enunț că ai de-a face cu acest tipar: „minimul maximului” sau „maximul minimului”, „cea mai mică valoare pentru care e posibil”, plus o verificare ușoară pentru o valoare dată.

Probleme din aceeași familie: Koko care mănâncă banane (viteza minimă), împărțirea unei liste în k subtablouri cu suma maximă minimă, distanța minimă maximă între k vaci plasate în grajduri, rădăcina pătrată întreagă.

Ce urmărește intervievatorul: Este o tehnică de nivel avansat pe care mulți candidați nu o recunosc. Intervievatorul urmărește identificarea predicatului monoton și a marginilor corecte.

60 Senior

Găsește al k-lea cel mai mic element dintr-o listă nesortată. Compară sortarea, heap-ul și quickselect. De ce are quickselect O(n) în medie?

Răspuns scurt: Sortarea dă O(n log n), un heap de mărime k O(n log k). Quickselect partiționează ca quicksort, dar continuă doar în partea cu poziția k: în medie n + n/2 + n/4 + … ≈ 2n pași, deci O(n), cu cazul rău O(n²).

PYTHON
import random

def quickselect(a, k):              # k indexat de la 0
    a = list(a)
    st, dr = 0, len(a) - 1
    while True:
        if st == dr:
            return a[st]
        p = random.randint(st, dr)
        a[p], a[dr] = a[dr], a[p]
        pivot, i = a[dr], st
        for j in range(st, dr):
            if a[j] < pivot:
                a[i], a[j] = a[j], a[i]
                i += 1
        a[i], a[dr] = a[dr], a[i]
        if k == i:
            return a[i]
        if k < i:
            dr = i - 1
        else:
            st = i + 1

print(quickselect([7, 10, 4, 3, 20, 15], 2))  # 7, al treilea cel mai mic

Diferența față de quicksort: după partiționare, pivotul este pe poziția lui finală i. Dacă k = i, ai terminat. Altfel, continui doar într-o parte. Cu pivot aleator, partea rămasă are în medie o fracție constantă din n, deci suma pașilor este o serie geometrică: O(n) așteptat.

Comparație:

  • sortare: O(n log n), cod de o linie, sorted(a)[k];
  • heap: heapq.nsmallest(k + 1, a)[-1], O(n log k). Avantaje: nu modifică lista, merge pe un flux de date, unde nu ai toată lista deodată, și are performanță garantată;
  • quickselect: O(n) mediu, O(n²) cel mai rău caz, modifică lista (de aceea codul de mai sus o copiază) și are nevoie de toate datele în memorie;
  • median of medians: garantează O(n) în cel mai rău caz alegând pivotul determinist, dar constantele sunt mari și rar se implementează în practică.

Exemple reale: std::nth_element din C++ este un quickselect cu protecție (introselect). În Python, pentru date mari, numpy.partition face aceeași operație.

La interviu, de obicei se acceptă heap-ul ca primă soluție, iar quickselect e follow-up-ul. Spune explicit compromisul: medie mai bună contra garanții și flux de date.

Ce urmărește intervievatorul: Verifică dacă știi trei soluții cu compromisuri diferite și poți justifica O(n) mediu. Candidații de nivel senior discută și fluxul de date și cazul cel mai rău.

Arbori, trie și heap

61 Junior

Care sunt parcurgerile în adâncime ale unui arbore binar (preordine, inordine, postordine)? Ce obții dacă parcurgi în inordine un arbore binar de căutare?

Răspuns scurt: Preordine: rădăcină, stânga, dreapta. Inordine: stânga, rădăcină, dreapta. Postordine: stânga, dreapta, rădăcină. Inordinea unui BST produce valorile în ordine crescătoare.

PYTHON
class Nod:
    def __init__(self, val, st=None, dr=None):
        self.val, self.st, self.dr = val, st, dr

def preordine(n, rez):
    if n:
        rez.append(n.val)
        preordine(n.st, rez)
        preordine(n.dr, rez)

def inordine(n, rez):
    if n:
        inordine(n.st, rez)
        rez.append(n.val)
        inordine(n.dr, rez)

def postordine(n, rez):
    if n:
        postordine(n.st, rez)
        postordine(n.dr, rez)
        rez.append(n.val)

#        4
#      2   6
#     1 3 5 7
r = Nod(4, Nod(2, Nod(1), Nod(3)), Nod(6, Nod(5), Nod(7)))
for f in (preordine, inordine, postordine):
    rez = []
    f(r, rez)
    print(f.__name__, rez)
# preordine [4, 2, 1, 3, 6, 5, 7]
# inordine [1, 2, 3, 4, 5, 6, 7]
# postordine [1, 3, 2, 5, 7, 6, 4]

Numele spun când vizitezi rădăcina față de subarbori. Utilizări tipice:

  • preordine: copierea sau serializarea unui arbore (rădăcina întâi, ca să o poți reconstrui), afișarea unei structuri de directoare;
  • inordine: valorile sortate dintr-un BST, al k-lea cel mai mic element, validarea unui BST;
  • postordine: calcule care au nevoie de rezultatele copiilor înainte de părinte, de exemplu înălțimea, dimensiunea unui director, ștergerea unui arbore, evaluarea unui arbore de expresie.

Complexitate: fiecare nod e vizitat o dată, deci O(n) timp și O(h) memorie pentru stiva de apeluri, unde h este înălțimea: O(log n) pentru un arbore echilibrat, O(n) pentru unul degenerat.

Pe arbori adânci, în Python treci la varianta iterativă cu stivă explicită, ca să eviți RecursionError. Inordinea iterativă e un follow-up frecvent: cobori la stânga punând nodurile pe stivă, scoți un nod, îl vizitezi și treci la subarborele lui drept.

Ce urmărește intervievatorul: Este o întrebare de bază despre arbori. Intervievatorul verifică ordinea vizitelor și dacă știi la ce folosește fiecare parcurgere, nu doar definiția.

Eroarea, în practică:'NoneType' object has no attribute 'stanga'Inordinea returnează doar rădăcina

62 Junior

Scrie o funcție care întoarce valorile unui arbore binar grupate pe niveluri (parcurgerea în lățime).

Răspuns scurt: Folosești o coadă (deque) pornind cu rădăcina. La fiecare pas procesezi exact atâtea noduri câte sunt în coadă la începutul nivelului, le adaugi valorile într-o listă și pui copiii lor în coadă. O(n) timp, O(w) memorie, unde w este lățimea maximă.

PYTHON
from collections import deque

class Nod:
    def __init__(self, val, st=None, dr=None):
        self.val, self.st, self.dr = val, st, dr

def pe_niveluri(radacina):
    if not radacina:
        return []
    rez = []
    coada = deque([radacina])
    while coada:
        nivel = []
        for _ in range(len(coada)):
            n = coada.popleft()
            nivel.append(n.val)
            if n.st:
                coada.append(n.st)
            if n.dr:
                coada.append(n.dr)
        rez.append(nivel)
    return rez

r = Nod(3, Nod(9), Nod(20, Nod(15), Nod(7)))
print(pe_niveluri(r))  # [[3], [9, 20], [15, 7]]

Trucul este for _ in range(len(coada)): len(coada) se evaluează o singură dată, la începutul buclei, deci procesezi doar nodurile nivelului curent, chiar dacă între timp adaugi copiii lor în coadă.

De ce coadă și nu stivă: coada (FIFO) garantează că toate nodurile de la adâncimea d sunt procesate înaintea celor de la adâncimea d + 1. Cu o stivă ai obține o parcurgere în adâncime.

Complexitate: O(n) timp, pentru că fiecare nod intră și iese o dată din coadă. Memoria este O(w), lățimea maximă a unui nivel, care pentru un arbore complet ajunge la aproximativ n/2 pe ultimul nivel.

Variante construite pe același schelet:

  • vederea din dreapta: ultimul element din fiecare nivel;
  • zigzag: inversezi nivel pe nivelurile impare;
  • adâncimea minimă: te oprești la prima frunză întâlnită, ceea ce poate fi mult mai rapid decât un DFS;
  • media fiecărui nivel, cel mai lat nivel, conectarea nodurilor de pe același nivel.

În grafuri, aceeași idee dă BFS și cel mai scurt drum în număr de muchii.

Ce urmărește intervievatorul: Verifică dacă știi BFS pe arbori și trucul cu dimensiunea nivelului. Mulți candidați folosesc o listă cu pop(0) sau pierd separarea pe niveluri.

Eroarea, în practică:BFS pe niveluri: nivelurile se amestecă

63 Junior

Scrie o funcție care inversează în oglindă un arbore binar și una care verifică dacă un arbore este simetric față de rădăcină.

Răspuns scurt: Oglindirea interschimbă copiii fiecărui nod, recursiv, în O(n). Simetria se verifică comparând simultan doi subarbori: rădăcinile au aceeași valoare, iar copilul stâng al unuia e oglinda copilului drept al celuilalt, și invers.

PYTHON
class Nod:
    def __init__(self, val, st=None, dr=None):
        self.val, self.st, self.dr = val, st, dr

def oglinda(n):
    if n:
        n.st, n.dr = oglinda(n.dr), oglinda(n.st)
    return n

def simetric(radacina):
    def oglinzi(a, b):
        if not a and not b:
            return True
        if not a or not b or a.val != b.val:
            return False
        return oglinzi(a.st, b.dr) and oglinzi(a.dr, b.st)
    return oglinzi(radacina, radacina) if radacina else True

r = Nod(1, Nod(2, Nod(3), Nod(4)), Nod(2, Nod(4), Nod(3)))
print(simetric(r))   # True

La oglindire, atribuirea tuplului din Python evaluează întâi partea dreaptă, deci ambii subarbori sunt oglindiți înainte de a fi legați invers. E o variantă compactă; într-un limbaj fără atribuire multiplă, ai salva un copil într-o variabilă temporară.

La simetrie, greșeala frecventă este să verifici doar dacă fiecare nod are copiii egali între ei. Simetria e o proprietate a întregului arbore: compari exteriorul cu exteriorul (a.st cu b.dr) și interiorul cu interiorul (a.dr cu b.st).

Ordinea testelor din oglinzi contează: verifici întâi cazurile cu None, abia apoi valorile, altfel accesezi .val pe None.

Complexitate: O(n) timp pentru ambele, O(h) memorie pentru recursivitate.

Variante iterative: oglindirea se face cu o coadă sau o stivă, interschimbând copiii fiecărui nod scos. Simetria se verifică cu o coadă de perechi (a, b), adăugând perechile (a.st, b.dr) și (a.dr, b.st).

Probleme din aceeași familie, cu recursivitate pe doi arbori deodată: doi arbori identici, un arbore este subarbore al altuia, combinarea a doi arbori prin adunarea valorilor.

Ce urmărește intervievatorul: Verifică gândirea recursivă pe structuri arborescente. Varianta cu simetria arată dacă poți ține în minte două noduri în paralel.

64 Junior

Ce este un arbore binar de căutare (BST)? Cum cauți și inserezi o valoare, ce complexitate au operațiile și ce se întâmplă dacă inserezi valori deja sortate?

Răspuns scurt: Un BST are, pentru fiecare nod, toate valorile din subarborele stâng mai mici și toate din cel drept mai mari. Căutarea și inserarea coboară pe un singur drum, deci O(h). Dacă inserezi valori sortate, arborele degenerează într-o listă și h devine n.

Proprietatea unui BST se referă la tot subarborele, nu doar la copiii direcți. De aceea, la căutare poți elimina la fiecare pas o întreagă parte a arborelui.

PYTHON
class Nod:
    def __init__(self, val):
        self.val, self.st, self.dr = val, None, None

def cauta(n, x):
    while n and n.val != x:
        n = n.st if x < n.val else n.dr
    return n

def insereaza(n, x):
    if not n:
        return Nod(x)
    if x < n.val:
        n.st = insereaza(n.st, x)
    elif x > n.val:
        n.dr = insereaza(n.dr, x)
    return n            # duplicatele sunt ignorate

r = None
for v in [8, 3, 10, 1, 6, 14]:
    r = insereaza(r, v)
print(cauta(r, 6) is not None, cauta(r, 7))  # True None

Complexitate: căutarea, inserarea și ștergerea sunt O(h). Pentru un arbore echilibrat h ≈ log₂ n, deci O(log n). Dacă inserezi 1, 2, 3, …, n în ordine, fiecare nod nou devine copilul drept al precedentului: arborele e de fapt o listă înlănțuită, iar h = n. Operațiile devin O(n), iar o funcție recursivă pe el atinge limita de recursivitate din Python.

Soluțiile sunt arborii auto-echilibrați (AVL, roșu-negru), care fac rotații după inserări și ștergeri ca să mențină h = O(log n).

Ștergerea are trei cazuri: nod frunză (îl elimini), nod cu un copil (îl înlocuiești cu copilul), nod cu doi copii (îl înlocuiești cu succesorul în inordine, cel mai mic nod din subarborele drept, apoi ștergi succesorul).

Ce oferă un BST față de un hash map: ordinea. Minim, maxim, succesor, „toate cheile între a și b”, „cea mai mare cheie ≤ x” sunt O(log n) într-un BST echilibrat și O(n) într-un dicționar.

Duplicatele trebuie tratate explicit: le ignori, le pui mereu pe o parte sau ții un contor în nod.

Ce urmărește intervievatorul: Verifică dacă înțelegi proprietatea BST și dependența complexității de înălțime. Mulți candidați spun „O(log n)” fără să menționeze cazul degenerat.

Eroarea, în practică:Validare BST: doar copiii direcțiInserare BST: rezultatul recursiv nu e salvat

65 Junior

Ce este un heap și cum îl folosești în Python? Cum obții un max-heap, dacă heapq oferă doar min-heap?

Răspuns scurt: Un heap binar este un arbore complet stocat într-o listă, în care fiecare părinte e mai mic sau egal cu copiii (min-heap). heapq oferă heappush și heappop în O(log n), iar minimul e mereu h[0]. Pentru max-heap pui valorile cu semn schimbat.

Heap-ul este structura folosită pentru cozi cu priorități: vrei mereu elementul cel mai mic (sau cel mai urgent), dar nu ai nevoie ca restul să fie sortat.

Fiind un arbore complet, se stochează compact într-o listă: copiii nodului i sunt la 2i + 1 și 2i + 2, iar părintele la (i − 1) // 2. Nu ai nevoie de pointeri.

PYTHON
import heapq

h = []
for x in [5, 1, 8, 3, 2]:
    heapq.heappush(h, x)          # O(log n)
print(h[0])                       # 1, minimul în O(1)
print(heapq.heappop(h))           # 1, O(log n)

a = [9, 4, 7, 1]
heapq.heapify(a)                  # O(n), pe loc

# max-heap cu valori negate
mx = []
for x in [5, 1, 8]:
    heapq.heappush(mx, -x)
print(-heapq.heappop(mx))         # 8

# priorități cu tupluri: (prioritate, contor, obiect)
sarcini = []
heapq.heappush(sarcini, (2, 0, "raport"))
heapq.heappush(sarcini, (1, 1, "bug urgent"))
print(heapq.heappop(sarcini)[2])  # bug urgent

Operațiile urcă sau coboară pe înălțimea arborelui, care este log n. heapify construiește heap-ul în O(n), nu O(n log n), pentru că majoritatea nodurilor sunt aproape de frunze și coboară puțin.

Contorul din tuplu are un rol concret: dacă două sarcini au aceeași prioritate, Python compară următorul element din tuplu. Fără contor, ar compara obiectele, ceea ce poate arunca TypeError sau poate da o ordine arbitrară.

Ce nu face un heap eficient: căutarea unui element arbitrar (O(n)), ștergerea unui element din mijloc, iterarea în ordine sortată (doar prin pop-uri repetate, adică heap sort).

Utilizări tipice: Dijkstra, top k, interclasarea a k liste, mediana unui flux, planificarea evenimentelor după timp.

Ce urmărește intervievatorul: Verifică dacă știi structura internă și API-ul concret din Python. Trucul cu valori negate și contorul pentru egalități sunt detaliile care arată experiență reală.

Eroarea, în practică:'<' not supported between 'Nod' and 'Nod'IndexError: index out of range la heappop

66 Mid

Unde e bug-ul în funcția de mai jos care verifică dacă un arbore binar este BST? Scrie varianta corectă.

PYTHON
def este_bst(n):
    if not n:
        return True
    if n.st and n.st.val >= n.val:
        return False
    if n.dr and n.dr.val <= n.val:
        return False
    return este_bst(n.st) and este_bst(n.dr)

Răspuns scurt: Funcția compară fiecare nod doar cu copiii direcți, dar proprietatea BST se referă la toți strămoșii. Un nod adânc din subarborele stâng poate fi mai mare decât rădăcina. Corect: transmiți în recursivitate intervalul permis (min, max) sau verifici că inordinea e strict crescătoare.

Contraexemplul care pică funcția:

      5
     / \
    1   6
       / \
      3   7

Fiecare nod e corect față de copiii lui, dar 3 se află în subarborele drept al lui 5, deși este mai mic decât 5. Funcția întoarce True, greșit.

Varianta corectă cu interval:

PYTHON
class Nod:
    def __init__(self, val, st=None, dr=None):
        self.val, self.st, self.dr = val, st, dr

def este_bst(n, lo=float("-inf"), hi=float("inf")):
    if not n:
        return True
    if not (lo < n.val < hi):
        return False
    return este_bst(n.st, lo, n.val) and este_bst(n.dr, n.val, hi)

r = Nod(5, Nod(1), Nod(6, Nod(3), Nod(7)))
print(este_bst(r))   # False

Când cobori la stânga, valoarea nodului devine limita superioară; când cobori la dreapta, devine limita inferioară. Fiecare nod primește intervalul impus de toți strămoșii săi.

Variantă cu inordine: într-un BST valid, inordinea e strict crescătoare. Parcurgi iterativ și compari fiecare valoare cu cea precedentă, fără să construiești lista:

PYTHON
def este_bst_inordine(radacina):
    stiva, prev, n = [], None, radacina
    while stiva or n:
        while n:
            stiva.append(n)
            n = n.st
        n = stiva.pop()
        if prev is not None and n.val <= prev:
            return False
        prev = n.val
        n = n.dr
    return True

Ambele sunt O(n) timp și O(h) memorie.

Detalii de clarificat: sunt permise duplicatele și, dacă da, pe ce parte? Inegalitățile stricte de mai sus le interzic. Folosirea lui float("-inf") evită problema din alte limbaje, unde inițializarea cu Integer.MIN_VALUE pică dacă arborele chiar conține acea valoare.

Ce urmărește intervievatorul: Este una dintre cele mai frecvente capcane la arbori. Intervievatorul vrea să vezi contraexemplul și să explici de ce verificarea locală nu ajunge.

Eroarea, în practică:Validare BST: doar copiii direcți

67 Mid

Găsește cel mai apropiat strămoș comun (LCA) a două noduri, întâi într-un BST, apoi într-un arbore binar oarecare.

Răspuns scurt: În BST cobori de la rădăcină spre partea în care se află ambele valori; nodul unde se despart este LCA, O(h). Într-un arbore oarecare, recursiv: nodul în ai cărui subarbori diferiți se află p și q este LCA, O(n).

Într-un BST, ordinea îți spune unde sunt nodurile:

PYTHON
def lca_bst(n, p, q):
    while n:
        if p < n.val and q < n.val:
            n = n.st
        elif p > n.val and q > n.val:
            n = n.dr
        else:
            return n

Nodul unde p și q „se despart” (unul în stânga, altul în dreapta, sau unul dintre ele e chiar nodul curent) este strămoșul comun cel mai adânc. O(h) timp, O(1) memorie.

Într-un arbore binar oarecare nu ai această informație, deci cauți în ambii subarbori:

PYTHON
class Nod:
    def __init__(self, val, st=None, dr=None):
        self.val, self.st, self.dr = val, st, dr

def lca(n, p, q):
    if n is None or n is p or n is q:
        return n
    stanga = lca(n.st, p, q)
    dreapta = lca(n.dr, p, q)
    if stanga and dreapta:
        return n
    return stanga or dreapta

a, b = Nod(6), Nod(4)
r = Nod(3, Nod(5, a, Nod(2, Nod(7), b)), Nod(1))
print(lca(r, a, b).val)   # 5

Fiecare apel întoarce p, q, LCA-ul lor sau None. Dacă ambele părți întorc ceva, p și q sunt în subarbori diferiți, deci nodul curent e LCA. Dacă doar o parte întoarce ceva, propagi acel rezultat în sus.

Funcția presupune că ambele noduri există în arbore. Dacă unul lipsește, întoarce celălalt nod, ceea ce e greșit. Pentru cazul general, numeri câte noduri ai găsit și verifici la final că sunt două.

Complexitate: O(n) timp, O(h) memorie.

Variante pentru multe interogări: dacă ai pointeri la părinte, urci din ambele noduri, ca la intersecția a două liste înlănțuite. Pentru mii de interogări pe același arbore, binary lifting precalculează strămoșii la distanțe 2ᵏ și răspunde în O(log n) pe interogare.

Ce urmărește intervievatorul: Verifică dacă folosești proprietatea BST când există și dacă știi tiparul recursiv general. Intervievatorul urmărește și presupunerea că ambele noduri există.

68 Mid

Calculează diametrul unui arbore binar: numărul maxim de muchii pe un drum între oricare două noduri. De ce nu trece neapărat prin rădăcină?

Răspuns scurt: Pentru fiecare nod, cel mai lung drum care trece prin el este înălțimea stângă plus înălțimea dreaptă. Faci o singură parcurgere postordine care întoarce înălțimea și actualizează un maxim global. O(n) timp. Drumul maxim poate sta în întregime într-un subarbore.

PYTHON
class Nod:
    def __init__(self, val, st=None, dr=None):
        self.val, self.st, self.dr = val, st, dr

def diametru(radacina):
    best = 0

    def inaltime(n):            # numărul de noduri pe cel mai lung drum în jos
        nonlocal best
        if not n:
            return 0
        hs = inaltime(n.st)
        hd = inaltime(n.dr)
        best = max(best, hs + hd)   # muchii pe drumul care trece prin n
        return 1 + max(hs, hd)

    inaltime(radacina)
    return best

r = Nod(1, Nod(2, Nod(4), Nod(5)), Nod(3))
print(diametru(r))   # 3: 4 - 2 - 1 - 3

De ce nu prin rădăcină: imaginează-ți o rădăcină cu un singur copil, sub care se află un subarbore mare și stufos. Drumul cel mai lung leagă două frunze adânci din acel subarbore și nici nu atinge rădăcina. De aceea calculezi candidatul la fiecare nod.

Soluția naivă apelează o funcție separată de înălțime pentru fiecare nod, ceea ce înseamnă O(n²) pe un arbore degenerat. Soluția de mai sus combină cele două calcule într-o singură postordine: fiecare apel întoarce o valoare părintelui (înălțimea) și actualizează separat răspunsul global (diametrul).

Tiparul „întoarce un lucru, actualizează altul” este foarte des întâlnit:

  • suma maximă a unui drum între oricare două noduri (cu valori negative, ignori contribuțiile negative ale copiilor);
  • verificarea dacă arborele e echilibrat (întoarce înălțimea sau −1 dacă un subarbore e deja dezechilibrat);
  • cel mai lung drum cu valori egale.

Atenție la unități: unele enunțuri cer diametrul în noduri, altele în muchii. Clarifică.

Complexitate: O(n) timp, O(h) memorie. Pentru arbori generali, nu doar binari, diametrul se poate găsi și cu două BFS: din orice nod găsești cel mai îndepărtat nod u, apoi din u cel mai îndepărtat nod.

Ce urmărește intervievatorul: Verifică dacă știi tiparul postordine cu răspuns global și dacă eviți soluția O(n²). Mulți candidați presupun greșit că drumul trece prin rădăcină.

69 Mid

Implementează un trie (arbore de prefixe) cu operațiile insert, search și starts_with. Când e mai potrivit decât un set de cuvinte?

Răspuns scurt: Fiecare nod are un dicționar de copii (literă → nod) și un marcaj de sfârșit de cuvânt. Toate operațiile sunt O(L), unde L este lungimea cuvântului. Trie-ul câștigă față de set când ai multe interogări pe prefixe, autocomplete sau căutare simultană a mai multor cuvinte.

PYTHON
class NodTrie:
    __slots__ = ("copii", "final")
    def __init__(self):
        self.copii = {}
        self.final = False

class Trie:
    def __init__(self):
        self.radacina = NodTrie()

    def insert(self, cuvant):
        n = self.radacina
        for c in cuvant:
            n = n.copii.setdefault(c, NodTrie())
        n.final = True

    def _nod(self, prefix):
        n = self.radacina
        for c in prefix:
            n = n.copii.get(c)
            if n is None:
                return None
        return n

    def search(self, cuvant):
        n = self._nod(cuvant)
        return n is not None and n.final

    def starts_with(self, prefix):
        return self._nod(prefix) is not None

t = Trie()
for w in ["apa", "apus", "arc"]:
    t.insert(w)
print(t.search("ap"), t.starts_with("ap"), t.search("apus"))  # False True True

Marcajul final este esențial: fără el, nu poți distinge cuvântul „ap” (dacă nu a fost inserat) de un simplu prefix al lui „apa”.

Comparație cu un set:

  • cuvant in set_ este O(L) în medie (calculul hash-ului parcurge șirul), deci la fel de rapid pentru căutarea exactă;
  • „există vreun cuvânt cu prefixul p?” costă O(n · L) cu un set și O(|p|) cu trie;
  • toate cuvintele cu un prefix: cobori la nodul prefixului și faci DFS doar pe subarborele lui.

Când trie-ul e alegerea bună: autocomplete, corectare ortografică, căutarea mai multor cuvinte într-o grilă (Word Search II), cel mai lung prefix comun, rutarea IP după prefix.

Dezavantajul este memoria: fiecare nod are un dicționar, deci în Python un trie pentru sute de mii de cuvinte poate ocupa de multe ori mai mult decât un set. __slots__ reduce puțin costul per nod. Alternativele compacte sunt radix tree (comprimă lanțurile fără ramificații) și listele de 26 de copii pentru un alfabet fix.

Ce urmărește intervievatorul: Verifică dacă poți implementa o structură de date de la zero și dacă știi când se justifică. Marcajul de final și costul de memorie sunt detaliile urmărite.

70 Mid

Găsește al k-lea cel mai mare element dintr-o listă folosind un heap de dimensiune k. De ce un min-heap și nu un max-heap?

Răspuns scurt: Ții un min-heap cu cele mai mari k elemente văzute. Pentru fiecare element nou, îl adaugi și, dacă heap-ul depășește k, scoți minimul. La final, vârful heap-ului este al k-lea cel mai mare. O(n log k) timp și O(k) memorie.

PYTHON
import heapq

def al_k_lea_mare(a, k):
    h = []
    for x in a:
        heapq.heappush(h, x)
        if len(h) > k:
            heapq.heappop(h)
    return h[0]

print(al_k_lea_mare([3, 2, 1, 5, 6, 4], 2))           # 5
print(al_k_lea_mare([3, 2, 3, 1, 2, 4, 5, 5, 6], 4))  # 4

De ce min-heap: heap-ul păstrează „clubul” celor mai mari k elemente. Ca să decizi cine iese când intră cineva nou, ai nevoie rapid de cel mai mic membru al clubului. Exact asta îți dă un min-heap. Iar la final, cel mai mic dintre cele mai mari k este chiar al k-lea cel mai mare.

O variantă puțin mai eficientă evită push urmat de pop: dacă x e mai mic decât h[0] și heap-ul e plin, x nu intră deloc. Altfel, heapq.heapreplace(h, x) scoate minimul și pune x într-o singură operație.

Alternativa cu max-heap: heapify pe toată lista (O(n)) și k pop-uri, deci O(n + k log k). E bună când k e mic, dar folosește O(n) memorie și cere toate datele de la început.

Avantajul real al variantei cu heap de dimensiune k este că funcționează pe un flux: datele vin pe rând, poate nu încap în memorie, și ai oricând răspunsul curent în O(1). Problema „al k-lea cel mai mare dintr-un flux” e exact această clasă.

Comparație:

  • sorted(a)[-k]: O(n log n), simplu;
  • heap de mărime k: O(n log k), O(k) memorie, merge pe flux;
  • quickselect: O(n) mediu, dar modifică lista și are nevoie de toate datele.

În Python, heapq.nlargest(k, a)[-1] face același lucru, cu implementare optimizată.

Ce urmărește intervievatorul: Verifică dacă înțelegi de ce heap-ul are mărime k și de ce e min-heap. Confuzia min/max este greșeala clasică, iar fluxul de date este follow-up-ul obișnuit.

71 Mid

Interclasează k liste sortate într-o singură listă sortată. Ce complexitate are soluția cu heap față de interclasarea pe rând?

Răspuns scurt: Pui în heap primul element din fiecare listă, ca (valoare, indice listă, poziție), scoți minimul și pui următorul element din aceeași listă. Cu N elemente în total, O(N log k), față de O(N · k) la interclasarea pe rând.

PYTHON
import heapq

def interclaseaza_k(liste):
    h = [(l[0], i, 0) for i, l in enumerate(liste) if l]
    heapq.heapify(h)
    rez = []
    while h:
        val, i, j = heapq.heappop(h)
        rez.append(val)
        if j + 1 < len(liste[i]):
            heapq.heappush(h, (liste[i][j + 1], i, j + 1))
    return rez

print(interclaseaza_k([[1, 4, 5], [1, 3, 4], [2, 6]]))
# [1, 1, 2, 3, 4, 4, 5, 6]

Heap-ul conține mereu cel mult k elemente, câte unul din fiecare listă încă nevidă. Fiecare dintre cele N elemente intră și iese o dată, deci O(N log k) timp și O(k) memorie suplimentară, plus rezultatul.

Indicele listei i din tuplu are un rol dublu: îți spune de unde iei următorul element și departajează valorile egale, ca Python să nu compare a treia componentă sau, în varianta cu liste înlănțuite, nodurile, care nu sunt comparabile.

Comparație cu alte strategii:

  • pe rând: interclasezi prima listă cu a doua, rezultatul cu a treia și așa mai departe. Elementele primei liste sunt copiate de k ori, deci O(N · k);
  • pe perechi, ca în merge sort: interclasezi listele două câte două, în log k runde, fiecare rundă costă O(N). Tot O(N log k), fără heap;
  • concatenare și sortare: O(N log N), mai lent când k e mic față de N, dar banal de scris. În practică, Timsort detectează rulajele sortate și se descurcă bine.

În Python, heapq.merge(*liste) face exact asta, leneș, ca generator.

Unde apare în realitate: sortarea externă (interclasezi k fișiere sortate de pe disc), combinarea rezultatelor de la k servere sau shard-uri, motoarele de căutare care unesc liste de documente.

Ce urmărește intervievatorul: Verifică dacă știi să folosești heap-ul pentru interclasare și dacă poți compara strategiile. Departajarea egalităților în tuplu e detaliul care arată experiență în Python.

72 Senior

Proiectează o structură care primește numere dintr-un flux și întoarce oricând mediana celor primite. Ce complexitate au operațiile?

Răspuns scurt: Folosești două heap-uri: un max-heap cu jumătatea mică și un min-heap cu jumătatea mare, echilibrate ca dimensiune (diferență de cel mult 1). Mediana este vârful heap-ului mai mare sau media celor două vârfuri. Adăugarea costă O(log n), mediana O(1).

PYTHON
import heapq

class MedianaFlux:
    def __init__(self):
        self.mici = []      # max-heap, valori negate
        self.mari = []      # min-heap

    def adauga(self, x):
        heapq.heappush(self.mici, -x)
        # cel mai mare din jumătatea mică trece în jumătatea mare
        heapq.heappush(self.mari, -heapq.heappop(self.mici))
        # jumătatea mică are cel puțin cât cea mare
        if len(self.mari) > len(self.mici):
            heapq.heappush(self.mici, -heapq.heappop(self.mari))

    def mediana(self):
        if len(self.mici) > len(self.mari):
            return -self.mici[0]
        return (-self.mici[0] + self.mari[0]) / 2

m = MedianaFlux()
for x in [5, 15, 1, 3]:
    m.adauga(x)
    print(m.mediana())   # 5, 10.0, 5, 4.0

Două invariante trebuie menținute după fiecare adăugare:

  • ordinea: orice element din mici ≤ orice element din mari;
  • echilibrul: len(mici) este egal cu len(mari) sau mai mare cu 1.

Pasul „pune în mici, mută maximul în mari” garantează ordinea fără comparații explicite. Pasul de reechilibrare garantează dimensiunile. Fiecare adauga face cel mult trei operații pe heap, deci O(log n). Mediana citește doar vârfurile, O(1).

Alternative și compromisuri:

  • listă sortată cu bisect.insort: căutarea poziției e O(log n), dar inserarea mută elemente, deci O(n);
  • sortedcontainers.SortedList (bibliotecă externă): O(log n) pentru inserare și acces după index; mediana devine sl[len(sl) // 2];
  • dacă valorile sunt într-un interval mic (de exemplu 0–100), un vector de frecvențe dă inserare în O(1) și mediană în O(100).

Follow-up-uri de nivel senior:

  • mediana pe fereastră glisantă: trebuie și ștergeri; cu heap-uri folosești ștergere leneșă și un dicționar cu elementele „de eliminat”;
  • flux uriaș, distribuit: mediana exactă cere toate datele; în practică se folosesc structuri aproximative de cuantile, precum t-digest.

Ce urmărește intervievatorul: Este o problemă clasică de proiectare a unei structuri de date. Intervievatorul urmărește invariantele celor două heap-uri și discuția despre alternative și scalare.

73 Senior

De ce au nevoie bazele de date și bibliotecile standard de arbori echilibrați (AVL, roșu-negru, B-tree)? Ce folosești în Python când ai nevoie de un dicționar sortat?

Răspuns scurt: Un BST simplu poate degenera la înălțimea n. Arborii echilibrați garantează O(log n): AVL e mai strict, roșu-negru face mai puține rotații, B-tree are noduri late, potrivite pentru disc. În Python folosești bisect, heapq sau sortedcontainers.

Garanția O(log n) a unui BST depinde de înălțime, iar datele reale vin des sortate sau aproape sortate (ID-uri crescătoare, timestamp-uri). Fără echilibrare, exact cazul frecvent devine cel mai rău.

Variantele principale:

  • AVL: pentru fiecare nod, înălțimile subarborilor diferă cu cel mult 1. Înălțimea e cel mult aproximativ 1,44 · log₂ n. Căutările sunt foarte rapide, dar inserările și ștergerile fac mai multe rotații;
  • roșu-negru: reguli de colorare care garantează că cel mai lung drum este cel mult dublul celui mai scurt. Mai puține rotații la modificări. Este structura folosită de obicei pentru TreeMap în Java și pentru std::map în implementările uzuale de C++;
  • B-tree / B+ tree: noduri cu sute de chei, deci înălțime foarte mică. Un nod corespunde unei pagini de disc, iar fiecare nivel înseamnă o citire. Este baza indecșilor din PostgreSQL, MySQL InnoDB și a multor sisteme de fișiere.

Operațiile care justifică un arbore în locul unui hash map: iterare în ordine, minim și maxim, floor și ceiling (cea mai mare cheie ≤ x), interogări pe interval.

În Python:

  • dict păstrează ordinea inserării, nu ordinea cheilor;
  • pentru date statice: listă sortată și bisect, O(log n) la căutare;
  • pentru minim/maxim dinamic: heapq;
  • pentru un dicționar sau set sortat dinamic: biblioteca sortedcontainers (SortedDict, SortedList), care nu folosește arbori, ci o listă de liste sortate, cu performanță practică foarte bună datorită localității memoriei.

La interviu, rar ți se cere să implementezi rotațiile. Se așteaptă să știi garanțiile, compromisurile și ce structură ai alege într-un sistem real.

Ce urmărește intervievatorul: Verifică legătura dintre teorie și sisteme reale (indecși, colecții standard). Candidații de nivel senior știu de ce bazele de date folosesc B-tree și nu arbori binari.

Grafuri

74 Junior

Cum reprezinți un graf în cod? Compară lista de adiacență cu matricea de adiacență.

Răspuns scurt: Lista de adiacență ține pentru fiecare nod lista vecinilor: O(V + E) memorie, ideală pentru grafuri rare. Matricea de adiacență are V × V celule: verifici o muchie în O(1), dar memoria e O(V²), potrivită doar pentru grafuri dense sau mici.

Un graf are V noduri și E muchii. Reprezentarea influențează direct complexitatea algoritmilor.

Listă de adiacență, cea mai folosită la interviuri:

PYTHON
from collections import defaultdict

muchii = [(0, 1), (0, 2), (1, 2), (2, 3)]
graf = defaultdict(list)
for u, v in muchii:
    graf[u].append(v)
    graf[v].append(u)      # doar pentru graf neorientat

print(dict(graf))  # {0: [1, 2], 1: [0, 2], 2: [0, 1, 3], 3: [2]}
  • memorie O(V + E);
  • parcurgerea vecinilor unui nod: O(grad(nod));
  • „există muchia u–v?”: O(grad(u)), sau O(1) dacă folosești seturi în loc de liste;
  • BFS și DFS rulează în O(V + E).

Matrice de adiacență: m[u][v] = 1 (sau costul muchiei).

  • memorie O(V²): pentru 10⁵ noduri, 10¹⁰ celule, imposibil;
  • verificarea unei muchii: O(1);
  • parcurgerea vecinilor: O(V), indiferent câți vecini are nodul, deci BFS devine O(V²);
  • potrivită pentru grafuri dense, pentru V mic sau pentru algoritmi ca Floyd–Warshall.

Lista de muchii, [(u, v, cost), …]: folosită de Kruskal (sortezi muchiile) și Bellman–Ford.

Graful nu e mereu explicit. O grilă este un graf implicit: vecinii celulei (r, c) sunt (r±1, c) și (r, c±1). Stările unui joc sau ale unui puzzle sunt și ele noduri, iar mutările sunt muchii. Recunoașterea unui graf ascuns în enunț este adesea partea cea mai grea.

Întrebări de clarificare: graful e orientat? Are costuri pe muchii? Poate avea cicluri, muchii multiple sau bucle? Este conex? Nodurile sunt numerotate de la 0 sau sunt șiruri?

Ce urmărește intervievatorul: Verifică dacă alegi reprezentarea potrivită și știi impactul asupra complexității. Recunoașterea grafurilor implicite, cum sunt grilele, e semnul unui candidat pregătit.

Eroarea, în practică:KeyError la graf[nod] în BFS / DFSIndexError: graf cu noduri de la 1 la n

75 Junior

Scrie un BFS care găsește cel mai scurt drum (în număr de muchii) între două noduri ale unui graf neorientat și reconstruiește drumul.

Răspuns scurt: BFS explorează nodurile în ordinea distanței față de sursă, deci prima dată când ajungi la destinație ai drumul cel mai scurt. Reții pentru fiecare nod părintele din care l-ai descoperit, apoi reconstruiești drumul mergând înapoi. O(V + E).

PYTHON
from collections import deque

def drum_minim(graf, sursa, dest):
    parinte = {sursa: None}
    coada = deque([sursa])
    while coada:
        u = coada.popleft()
        if u == dest:
            drum = []
            while u is not None:
                drum.append(u)
                u = parinte[u]
            return drum[::-1]
        for v in graf[u]:
            if v not in parinte:
                parinte[v] = u
                coada.append(v)
    return None

graf = {"A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D"],
        "D": ["B", "C", "E"], "E": ["D"]}
print(drum_minim(graf, "A", "E"))  # ['A', 'B', 'D', 'E']

De ce BFS dă drumul minim: coada procesează întâi toate nodurile la distanța 1, apoi pe cele la distanța 2 și așa mai departe. Un nod descoperit la distanța d nu poate fi atins mai târziu printr-un drum mai scurt.

Dicționarul parinte are un rol dublu: marchează nodurile vizitate și reține de unde ai venit. Marchezi un nod când îl pui în coadă, nu când îl scoți. Altfel, același nod poate fi pus de mai multe ori în coadă de vecini diferiți, iar memoria și timpul cresc inutil.

Complexitate: fiecare nod intră o dată în coadă și fiecare muchie e examinată de două ori, deci O(V + E) timp și O(V) memorie.

Limitări și extensii:

  • BFS dă drumul minim doar când toate muchiile au același cost. Cu costuri diferite folosești Dijkstra; cu costuri 0 și 1, un BFS cu deque în care muchiile de cost 0 se pun în față (0-1 BFS);
  • BFS bidirecțional: pornești simultan din sursă și din destinație și te oprești când frontierele se întâlnesc; pe grafuri cu ramificare mare explorezi mult mai puține noduri;
  • BFS multi-sursă: pui în coadă toate sursele de la început, de exemplu pentru distanța fiecărei celule până la cea mai apropiată ieșire.

Ce urmărește intervievatorul: Este algoritmul de bază pe grafuri. Intervievatorul urmărește momentul marcării ca vizitat și reconstruirea drumului, unde se greșește des.

Eroarea, în practică:BFS-ul nu se oprește: lipsesc nodurile vizitateBFS cu pop() în loc de popleft()

76 Junior

Primești o hartă ca grilă de „1” (uscat) și „0” (apă). Numără insulele, adică grupurile de uscat conectate pe orizontală sau verticală.

Răspuns scurt: Parcurgi grila; când găsești un „1” nevizitat, ai găsit o insulă nouă și pornești un DFS sau BFS care marchează toată insula ca vizitată. Numărul de porniri este răspunsul. O(R · C) timp.

Grila este un graf implicit: fiecare celulă de uscat e un nod, iar vecinii ei de uscat sunt muchiile. Numărul de insule este numărul de componente conexe.

PYTHON
from collections import deque

def numar_insule(grila):
    if not grila:
        return 0
    R, C = len(grila), len(grila[0])
    vazut = [[False] * C for _ in range(R)]
    insule = 0
    for r in range(R):
        for c in range(C):
            if grila[r][c] == "1" and not vazut[r][c]:
                insule += 1
                vazut[r][c] = True
                coada = deque([(r, c)])
                while coada:
                    x, y = coada.popleft()
                    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                        nx, ny = x + dx, y + dy
                        if (0 <= nx < R and 0 <= ny < C and
                                grila[nx][ny] == "1" and not vazut[nx][ny]):
                            vazut[nx][ny] = True
                            coada.append((nx, ny))
    return insule

harta = ["11000",
         "11000",
         "00100",
         "00011"]
print(numar_insule([list(rand) for rand in harta]))  # 3

Am folosit BFS cu coadă explicită și nu un DFS recursiv dintr-un motiv practic: pe o grilă de 1000 × 1000 numai cu uscat, recursivitatea ar ajunge la un milion de niveluri și ar depăși limita din Python.

Dacă ai voie să modifici intrarea, poți marca uscatul vizitat transformându-l în „0” și renunți la matricea vazut. Întreabă înainte dacă e permis.

Lista de direcții ((1, 0), (-1, 0), (0, 1), (0, -1)) face codul curat. Pentru conectivitate pe diagonală, adaugi cele patru diagonale.

Complexitate: fiecare celulă este vizitată o dată, deci O(R · C) timp și O(R · C) memorie în cel mai rău caz.

Variante: aria celei mai mari insule, perimetrul unei insule, numărul de insule distincte ca formă (normalizezi coordonatele relativ la prima celulă), insule care apar pe rând (union-find, ca să eviți recalcularea).

Ce urmărește intervievatorul: Este una dintre cele mai frecvente probleme pe grafuri la interviuri. Intervievatorul urmărește marcarea corectă, verificarea marginilor și riscul de recursivitate prea adâncă.

Eroarea, în practică:RecursionError la DFS fără noduri vizitateGrilă: indicii negativi nu dau eroare

77 Junior

Scrie un DFS iterativ care numără componentele conexe ale unui graf neorientat dat prin n noduri și o listă de muchii. Când ai alege DFS și când BFS?

Răspuns scurt: Pornești un DFS cu stivă explicită din fiecare nod nevizitat; numărul de porniri este numărul de componente. DFS și BFS sunt ambele O(V + E): BFS pentru drum minim, DFS pentru cicluri, sortare topologică și backtracking.

PYTHON
def componente(n, muchii):
    graf = [[] for _ in range(n)]
    for u, v in muchii:
        graf[u].append(v)
        graf[v].append(u)
    vazut = [False] * n
    numar = 0
    for start in range(n):
        if vazut[start]:
            continue
        numar += 1
        vazut[start] = True
        stiva = [start]
        while stiva:
            u = stiva.pop()
            for v in graf[u]:
                if not vazut[v]:
                    vazut[v] = True
                    stiva.append(v)
    return numar

print(componente(5, [(0, 1), (1, 2), (3, 4)]))  # 2
print(componente(4, []))                        # 4

Bucla exterioară pe toate nodurile este esențială: un singur DFS din nodul 0 vede doar componenta lui. Nodurile izolate, fără muchii, sunt și ele componente, cum arată al doilea exemplu.

Stiva explicită evită limita de recursivitate. Ordinea de vizitare diferă puțin de DFS-ul recursiv, dar pentru numărarea componentelor nu contează. Pentru algoritmi care depind de ordinea de terminare a nodurilor (sortare topologică prin DFS, detectarea ciclurilor cu culori), varianta iterativă trebuie scrisă mai atent.

DFS sau BFS:

  • drum minim neponderat: doar BFS;
  • componente conexe, accesibilitate: oricare;
  • detectarea ciclurilor, sortare topologică, componente tare conexe, puncte de articulație: DFS, pentru că folosesc ordinea de intrare și ieșire din noduri;
  • memorie: BFS ține o frontieră care poate fi foarte lată; DFS ține un drum, care poate fi foarte lung;
  • găsirea unei soluții oarecare adânci (labirint, puzzle): DFS, eventual cu backtracking.

Complexitate: O(V + E) timp, O(V) memorie.

Pentru muchii care sosesc pe rând și întrebarea „câte componente sunt acum?”, union-find e mai potrivit, pentru că nu reface parcurgerea.

Ce urmărește intervievatorul: Verifică dacă poți scrie DFS fără recursivitate și dacă știi criteriile de alegere între DFS și BFS. Mulți candidați uită nodurile izolate.

Eroarea, în practică:RecursionError la DFS fără noduri vizitateGraf neorientat: muchii doar într-un sens

78 Mid

Cum detectezi un ciclu într-un graf orientat? De ce nu e suficient un simplu set de noduri vizitate, ca la grafurile neorientate?

Răspuns scurt: DFS cu trei stări: nevizitat, în curs (pe stiva curentă) și terminat. O muchie spre un nod „în curs” înseamnă ciclu. Un set simplu nu distinge nodul de pe drumul curent de unul terminat pe altă ramură, care nu formează ciclu.

În graful orientat A → B, A → C, C → B, nodul B e atins de două ori, dar nu există ciclu. Cu un singur set de vizitate, a doua atingere a lui B ar fi raportată greșit ca ciclu. Ce contează este dacă nodul atins se află pe drumul curent al DFS-ului.

PYTHON
def are_ciclu(n, muchii):
    graf = [[] for _ in range(n)]
    for u, v in muchii:
        graf[u].append(v)
    ALB, GRI, NEGRU = 0, 1, 2       # nevizitat, în curs, terminat
    stare = [ALB] * n

    def dfs(u):
        stare[u] = GRI
        for v in graf[u]:
            if stare[v] == GRI:
                return True          # muchie înapoi, ciclu
            if stare[v] == ALB and dfs(v):
                return True
        stare[u] = NEGRU
        return False

    return any(stare[u] == ALB and dfs(u) for u in range(n))

print(are_ciclu(3, [(0, 1), (0, 2), (2, 1)]))  # False
print(are_ciclu(3, [(0, 1), (1, 2), (2, 0)]))  # True

Un nod gri este pe stiva de apeluri. O muchie către un nod gri închide un drum înapoi spre un strămoș, deci ciclu. O muchie către un nod negru duce într-o zonă deja explorată complet, unde s-ar fi găsit deja ciclul dacă exista.

Varianta recursivă e cea mai clară, dar pentru grafuri mari în Python ai nevoie fie de o stivă explicită care reține și indicele următorului vecin, fie de algoritmul lui Kahn: dacă sortarea topologică nu reușește să scoată toate nodurile, cele rămase sunt implicate în cicluri. Kahn este iterativ prin natura lui.

La grafurile neorientate, un set de vizitate ajunge, dar trebuie să ignori muchia către părintele din care ai venit. Altfel, orice muchie u–v ar arăta ca un ciclu u → v → u. Alternativ, folosești union-find: dacă o muchie unește două noduri deja în aceeași componentă, ai un ciclu.

Complexitate: O(V + E) timp, O(V) memorie.

Aplicații: dependențe circulare între module, cursuri cu prerechizite imposibile, deadlock-uri în grafuri de așteptare.

Ce urmărește intervievatorul: Verifică dacă înțelegi diferența dintre grafurile orientate și cele neorientate la detectarea ciclurilor. Folosirea unui singur set de vizitate este greșeala clasică.

Eroarea, în practică:Sortare topologică: ciclul nu e detectatCiclu fals în graf orientat (doar vizitat)

79 Mid

Ai n cursuri și o listă de prerechizite (curs, prerechizit). Găsește o ordine în care pot fi urmate toate cursurile sau spune că nu există. Explică algoritmul lui Kahn.

Răspuns scurt: Este o sortare topologică. Kahn pune în coadă nodurile cu grad de intrare 0, le scoate pe rând și scade gradul vecinilor; vecinii ajunși la 0 intră în coadă. Dacă rămân noduri nescoase, există un ciclu. O(V + E).

PYTHON
from collections import deque

def ordine_cursuri(n, prerechizite):
    graf = [[] for _ in range(n)]
    grad_intrare = [0] * n
    for curs, pre in prerechizite:
        graf[pre].append(curs)        # pre trebuie înainte de curs
        grad_intrare[curs] += 1
    coada = deque(i for i in range(n) if grad_intrare[i] == 0)
    ordine = []
    while coada:
        u = coada.popleft()
        ordine.append(u)
        for v in graf[u]:
            grad_intrare[v] -= 1
            if grad_intrare[v] == 0:
                coada.append(v)
    return ordine if len(ordine) == n else []

print(ordine_cursuri(4, [(1, 0), (2, 0), (3, 1), (3, 2)]))  # [0, 1, 2, 3]
print(ordine_cursuri(2, [(1, 0), (0, 1)]))                  # []

O sortare topologică este o ordonare a nodurilor unui graf orientat în care, pentru fiecare muchie u → v, u apare înaintea lui v. Există dacă și numai dacă graful nu are cicluri (este un DAG, graf orientat aciclic).

Invariantul lui Kahn: un nod intră în coadă abia când toate prerechizitele lui au fost deja adăugate în ordine. Dacă există un ciclu, nodurile lui nu ajung niciodată la gradul 0, deci rămân pe dinafară, iar len(ordine) < n.

Direcția muchiei e o sursă clasică de bug-uri: perechea e (curs, prerechizit), dar muchia merge de la prerechizit la curs. Citește enunțul de două ori.

Complexitate: O(V + E) timp și memorie.

Ordinea nu e unică. Dacă se cere ordinea lexicografic minimă, înlocuiești coada cu un min-heap, iar complexitatea devine O(V log V + E).

Alternativa prin DFS: adaugi un nod în listă după ce i-ai terminat toți descendenții (postordine) și inversezi lista la final.

Aplicații reale: ordinea de build a modulelor (Maven, Bazel, make), migrațiile de baze de date, evaluarea celulelor dintr-un spreadsheet, rezolvarea dependențelor la instalarea pachetelor. Numărul de „runde” ale lui Kahn (nivelurile BFS) dă și numărul minim de semestre dacă poți urma oricâte cursuri în paralel.

Ce urmărește intervievatorul: Este o problemă foarte frecventă, cu aplicații evidente. Intervievatorul urmărește direcția muchiilor, detectarea ciclului și explicarea invariantului.

Eroarea, în practică:Sortare topologică: ciclul nu e detectat

80 Mid

Implementează structura union-find (mulțimi disjuncte) cu path compression și union by rank. La ce problemă de interviu o folosești?

Răspuns scurt: Fiecare element are un părinte; find urcă la rădăcină, union leagă două rădăcini. Path compression scurtează drumurile, iar union by rank pune arborele scund sub cel înalt. Împreună dau un cost amortizat aproape constant.

PYTHON
class UnionFind:
    def __init__(self, n):
        self.parinte = list(range(n))
        self.rang = [0] * n
        self.componente = n

    def find(self, x):
        while self.parinte[x] != x:
            self.parinte[x] = self.parinte[self.parinte[x]]   # înjumătățirea drumului
            x = self.parinte[x]
        return x

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                 # deja în aceeași mulțime
        if self.rang[ra] < self.rang[rb]:
            ra, rb = rb, ra
        self.parinte[rb] = ra
        if self.rang[ra] == self.rang[rb]:
            self.rang[ra] += 1
        self.componente -= 1
        return True

uf = UnionFind(5)
uf.union(0, 1); uf.union(3, 4)
print(uf.componente, uf.find(1) == uf.find(0))   # 3 True
print(uf.union(1, 0))                            # False: ar închide un ciclu

Varianta de find de mai sus este iterativă și folosește path halving: fiecare nod parcurs sare la bunicul lui. Are aceeași garanție ca path compression completă, dar evită recursivitatea, utilă în Python.

Fără optimizări, arborii pot degenera în lanțuri, iar find devine O(n). Cu ambele, costul amortizat este O(α(n)), unde α este inversa funcției Ackermann, mai mică decât 5 pentru orice n practic.

Probleme tipice de interviu:

  • conectivitate dinamică: muchiile sosesc pe rând și întrebi oricând dacă două noduri sunt conectate;
  • detectarea ciclului într-un graf neorientat: union întoarce False, deci muchia unește noduri deja conectate. Problema „muchia redundantă”;
  • Kruskal pentru arborele parțial de cost minim;
  • numărul de provincii sau de conturi de unit după e-mailuri comune (mapezi e-mailurile la indici);
  • insule care apar pe rând pe o grilă.

Limitarea: union-find nu suportă eficient separarea mulțimilor. Dacă muchiile se și șterg, ai nevoie de alte tehnici sau de procesarea offline în ordine inversă.

Ce urmărește intervievatorul: Verifică dacă știi structura și ambele optimizări, nu doar ideea. Candidații buni recunosc rapid problemele de conectivitate unde union-find e mai simplu decât DFS repetat.

Eroarea, în practică:Union-Find: leagă nodurile, nu rădăcinile

81 Mid

Implementează algoritmul lui Dijkstra cu heapq. Ce complexitate are și de ce nu funcționează cu muchii de cost negativ?

Răspuns scurt: Un min-heap cu (distanță, nod): scoți nodul cel mai apropiat, care devine definitiv, și îi relaxezi muchiile. Cu heap binar, O((V + E) log V). Cu costuri negative, un nod deja definitiv ar putea fi îmbunătățit ulterior.

PYTHON
import heapq

def dijkstra(graf, sursa):
    dist = {sursa: 0}
    heap = [(0, sursa)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue                    # intrare veche, ignorată
        for v, cost in graf[u]:
            nd = d + cost
            if nd < dist.get(v, float("inf")):
                dist[v] = nd
                heapq.heappush(heap, (nd, v))
    return dist

graf = {"A": [("B", 4), ("C", 1)], "B": [("D", 1)],
        "C": [("B", 2), ("D", 5)], "D": []}
print(dijkstra(graf, "A"))  # {'A': 0, 'B': 3, 'C': 1, 'D': 4}

heapq nu are operația „scade prioritatea unui element”. În locul ei, pui o intrare nouă cu distanța mai mică, iar intrările vechi rămân în heap. Linia if d > dist[u]: continue le ignoră când ies. Fără ea, algoritmul e tot corect, dar relaxezi muchiile de mai multe ori inutil. Heap-ul poate ajunge la O(E) intrări, deci complexitatea este O(E log E), echivalent cu O(E log V).

De ce e corect: când un nod iese din heap cu distanța minimă dintre toate cele rămase, orice alt drum spre el ar trece printr-un nod cu distanță cel puțin la fel de mare și ar adăuga costuri nenegative, deci nu poate fi mai scurt. Cu o muchie negativă, raționamentul cade: un drum care trece printr-un nod mai „îndepărtat” poate ajunge mai ieftin, după ce nodul a fost deja declarat final.

Pentru costuri negative folosești Bellman–Ford, în O(V · E), care detectează și ciclurile negative. Pentru costuri 0 și 1 ajunge 0-1 BFS, în O(V + E). Pentru distanțele între toate perechile, pe grafuri mici, Floyd–Warshall, în O(V³).

Pentru reconstruirea drumului reții parinte[v] = u la fiecare relaxare reușită. Dacă îți trebuie doar drumul către o destinație, te oprești când destinația iese din heap.

Aplicații: rutare în rețele (OSPF), navigație. În practică, pentru hărți se folosește A*, adică Dijkstra ghidat de o estimare a distanței rămase.

Ce urmărește intervievatorul: Este algoritmul de drum minim pe care se așteaptă să-l știi. Intervievatorul urmărește intrările vechi din heap și argumentul pentru care costurile negative îl strică.

Eroarea, în practică:'<' not supported between 'Nod' and 'Nod'Dijkstra: vizitat marcat prea devreme

82 Senior

Verifică dacă un graf neorientat este bipartit, adică nodurile pot fi colorate cu două culori astfel încât fiecare muchie să lege noduri de culori diferite. Ce legătură are cu ciclurile?

Răspuns scurt: Colorezi graful prin BFS: sursa primește culoarea 0, vecinii culoarea opusă și așa mai departe. Dacă o muchie leagă două noduri de aceeași culoare, graful nu e bipartit. Un graf este bipartit dacă și numai dacă nu conține cicluri de lungime impară.

PYTHON
from collections import deque

def este_bipartit(n, muchii):
    graf = [[] for _ in range(n)]
    for u, v in muchii:
        graf[u].append(v)
        graf[v].append(u)
    culoare = [-1] * n
    for start in range(n):
        if culoare[start] != -1:
            continue
        culoare[start] = 0
        coada = deque([start])
        while coada:
            u = coada.popleft()
            for v in graf[u]:
                if culoare[v] == -1:
                    culoare[v] = 1 - culoare[u]
                    coada.append(v)
                elif culoare[v] == culoare[u]:
                    return False
    return True

print(este_bipartit(4, [(0, 1), (1, 2), (2, 3), (3, 0)]))  # True, ciclu de 4
print(este_bipartit(3, [(0, 1), (1, 2), (2, 0)]))          # False, triunghi

Bucla exterioară pe toate nodurile tratează grafurile neconexe: fiecare componentă se colorează independent, iar graful e bipartit doar dacă toate componentele sunt.

Legătura cu ciclurile impare: într-un ciclu, culorile alternează la fiecare muchie. Ca să revii în nodul de start cu aceeași culoare, ai nevoie de un număr par de muchii. Un ciclu impar forțează un conflict. Invers, dacă BFS-ul găsește un conflict, muchia respectivă, împreună cu drumurile spre strămoșul comun din arborele BFS, formează un ciclu impar. Deci colorarea greedy prin BFS nu e o euristică: e o decizie completă, care nu poate eșua dacă exista o colorare validă.

Complexitate: O(V + E) timp și O(V) memorie.

O alternativă cu union-find: pentru fiecare nod u, toți vecinii lui trebuie să fie în aceeași mulțime, diferită de a lui u. Uniți vecinii între ei și verificați că niciunul nu ajunge în mulțimea lui u.

Unde apare la interviu, adesea deghizat:

  • împarte oamenii în două grupuri astfel încât cei care nu se plac să fie separați;
  • graful de conflicte dintre examene, cu două săli disponibile;
  • potrivirile pe grafuri bipartite (candidați și posturi), care duc la algoritmi de cuplaj maxim, precum Hopcroft–Karp.

Colorarea cu 3 sau mai multe culori este NP-completă, deci nu există o generalizare la fel de simplă.

Ce urmărește intervievatorul: Verifică dacă recunoști problema deghizată și poți justifica corectitudinea colorării greedy. Legătura cu ciclurile impare și tratarea grafurilor neconexe arată profunzime.

83 Senior

Ai n orașe și o listă de drumuri posibile cu costuri. Conectează toate orașele cu cost total minim. Explică algoritmul lui Kruskal și de ce e corect.

Răspuns scurt: Este arborele parțial de cost minim (MST). Kruskal sortează muchiile crescător după cost și adaugă fiecare muchie care leagă două componente diferite, verificând cu union-find. Se oprește după n − 1 muchii. O(E log E), dominat de sortare.

PYTHON
def kruskal(n, muchii):
    parinte = list(range(n))

    def find(x):
        while parinte[x] != x:
            parinte[x] = parinte[parinte[x]]
            x = parinte[x]
        return x

    total, folosite = 0, []
    for cost, u, v in sorted(muchii):
        ru, rv = find(u), find(v)
        if ru != rv:
            parinte[ru] = rv
            total += cost
            folosite.append((u, v, cost))
            if len(folosite) == n - 1:
                break
    if len(folosite) != n - 1:
        return None          # graful nu e conex
    return total, folosite

muchii = [(1, 0, 1), (4, 0, 2), (3, 1, 2), (2, 1, 3), (5, 2, 3)]
print(kruskal(4, muchii))  # (6, [(0, 1, 1), (1, 3, 2), (1, 2, 3)])

(Pentru brevitate, union-find de aici nu folosește union by rank; cu path halving rămâne foarte rapid în practică.)

Corectitudinea se bazează pe proprietatea tăieturii (cut property): pentru orice împărțire a nodurilor în două grupuri, muchia cea mai ieftină care traversează împărțirea aparține unui MST. Când Kruskal ia muchia curentă, cea mai ieftină rămasă care leagă două componente distincte, ea este cea mai ieftină muchie peste tăietura dintre componenta unui capăt și restul nodurilor. Deci alegerea greedy e sigură.

Muchiile care ar lega noduri deja conectate sunt ignorate, pentru că ar închide un ciclu și ar fi cele mai scumpe din acel ciclu.

Complexitate: sortarea O(E log E), plus E operații union-find aproape O(1). Memorie O(V + E).

Alternativa este Prim: pornește dintr-un nod și adaugă mereu cea mai ieftină muchie care iese din arborele construit, folosind un heap. O(E log V). Prim e preferat pe grafuri dense date ca matrice (cu varianta O(V²) fără heap), Kruskal pe grafuri rare date ca listă de muchii.

Detalii de discutat: verificarea conexității (dacă nu obții n − 1 muchii, nu există arbore), costurile egale (MST-ul poate să nu fie unic, dar costul total este), varianta „conectează punctele din plan” unde muchiile sunt implicite și sunt O(n²).

Aplicații: proiectarea rețelelor (cabluri, conducte), clustering (oprești Kruskal înainte de final și obții k grupuri).

Ce urmărește intervievatorul: Verifică dacă știi un algoritm greedy pe grafuri și poți argumenta de ce e optim. La nivel senior se așteaptă proprietatea tăieturii și comparația cu Prim.

Eroarea, în practică:Union-Find: leagă nodurile, nu rădăcinile

Programare dinamică, greedy și biți

Exersează capitolul cu exerciții reale: Curs algoritmi pentru începători →
84 Junior

Ce este programarea dinamică? Explică pe problema: în câte moduri urci o scară cu n trepte, dacă poți face pași de 1 sau 2 trepte?

Răspuns scurt: DP rezolvă o problemă din subprobleme care se repetă, fiecare calculată o singură dată. Pe treapta n ajungi de pe n − 1 sau de pe n − 2, deci moduri(n) = moduri(n-1) + moduri(n-2): O(n) timp, O(1) memorie.

O problemă se pretează la programare dinamică (DP) când are două proprietăți:

  • subprobleme care se suprapun: aceeași subproblemă apare de multe ori în recursivitatea naivă;
  • substructură optimă: răspunsul se construiește din răspunsurile subproblemelor.

Pașii de lucru, utili de spus cu voce tare la interviu:

  • definești starea: dp[i] = numărul de moduri de a ajunge pe treapta i;
  • scrii tranziția: ultimul pas a fost de 1 treaptă (din i − 1) sau de 2 (din i − 2), cazuri disjuncte, deci dp[i] = dp[i-1] + dp[i-2];
  • fixezi cazurile de bază: dp[0] = 1 (un singur mod, să nu faci nimic), dp[1] = 1;
  • alegi ordinea de calcul: crescător după i;
  • reduci memoria, dacă se poate.
PYTHON
def moduri_scara(n):
    a, b = 1, 1           # dp[0], dp[1]
    for _ in range(n - 1):
        a, b = b, a + b
    return b if n > 0 else 1

print([moduri_scara(n) for n in range(1, 7)])  # [1, 2, 3, 5, 8, 13]

Recurența este Fibonacci, decalat cu o poziție. Varianta recursivă fără memoizare ar fi O(2ⁿ), pentru că recalculează aceleași trepte de foarte multe ori.

Extensii care arată dacă ai înțeles tiparul, nu doar ai memorat formula:

  • pași din mulțimea {1, 3, 5}: dp[i] = dp[i-1] + dp[i-3] + dp[i-5];
  • unele trepte sunt stricate: dp[i] = 0 pentru ele;
  • fiecare treaptă are un cost și vrei costul minim: dp[i] = cost[i] + min(dp[i-1], dp[i-2]), adică trecerea de la numărare la optimizare.

Diferența față de divide et impera (merge sort): acolo subproblemele sunt disjuncte, deci nu ai ce memora.

Ce urmărește intervievatorul: Intervievatorul verifică dacă știi să definești starea și tranziția, nu doar să recunoști Fibonacci. Extensiile cu alte mulțimi de pași arată dacă ai înțeles metoda.

Eroarea, în practică:IndexError la dp[n]: tabelul DP e prea scurt

85 Junior

Care este diferența dintre memoizare (top-down) și tabulare (bottom-up)? Arată ambele pe problema costului minim pentru a urca o scară, unde fiecare treaptă are un cost.

Răspuns scurt: Memoizarea pornește de la problema mare, recursiv, și memorează rezultatele subproblemelor. Tabularea umple un tabel de la cazurile de bază spre problema mare, iterativ. Au aceeași complexitate; memoizarea calculează doar stările necesare, tabularea evită recursivitatea și permite reducerea memoriei.

Problema: cost[i] este costul treptei i. Pornești de pe treapta 0 sau 1, urci 1 sau 2 trepte o dată și vrei să ajungi deasupra ultimei trepte cu cost total minim.

Memoizare, top-down:

PYTHON
from functools import lru_cache

def cost_minim_memo(cost):
    n = len(cost)

    @lru_cache(maxsize=None)
    def f(i):                    # costul minim de la treapta i până sus
        if i >= n:
            return 0
        return cost[i] + min(f(i + 1), f(i + 2))

    return min(f(0), f(1))

Tabulare, bottom-up, cu memoria redusă la două variabile:

PYTHON
def cost_minim(cost):
    a = b = 0                    # dp[i-2], dp[i-1]: costul de a ajunge pe treapta i
    for i in range(2, len(cost) + 1):
        a, b = b, min(b + cost[i - 1], a + cost[i - 2])
    return b

c = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
print(cost_minim_memo(c), cost_minim(c))   # 6 6

Comparație:

  • memoizarea urmează direct recurența, deci e ușor de scris corect. Calculează doar stările atinse, avantaj când spațiul stărilor e mare dar rar folosit. Dezavantaje în Python: overhead-ul apelurilor și limita de recursivitate (o scară cu 10⁴ trepte dă RecursionError);
  • tabularea cere să știi ordinea în care depind stările, dar e mai rapidă și nu are probleme de stivă. Mai ales, vezi exact ce stări precedente folosește fiecare pas, deci poți păstra doar o fereastră a tabelului (aici două valori, deci O(1) memorie).

Strategie bună la interviu: scrii întâi recurența și varianta cu memoizare, verifici pe un exemplu, apoi o transformi în tabulare și reduci memoria, explicând fiecare pas. Arată că înțelegi DP-ul, nu că ai memorat o soluție.

Atenție la lru_cache pe o funcție interioară: cache-ul trăiește cât funcția exterioară, deci nu se amestecă între apeluri diferite.

Ce urmărește intervievatorul: Verifică dacă știi ambele stiluri și compromisurile lor concrete în Python. Mulți candidați cunosc doar unul și nu pot face trecerea la O(1) memorie.

Eroarea, în practică:fib(40) recursiv nu se termină (fără memo)Memo greșit: cheia nu are toți parametrii

86 Junior

Un hoț nu poate jefui două case vecine. Primești sumele din fiecare casă; care este suma maximă pe care o poate obține?

Răspuns scurt: dp[i] este suma maximă din primele i case: ori sari casa i (dp[i-1]), ori o iei și sari vecina (dp[i-2] + a[i]). Iei maximul. O(n) timp și O(1) memorie, pentru că ai nevoie doar de ultimele două valori.

Greedy nu merge aici: alegerea casei cu cea mai mare sumă sau a tuturor caselor de pe poziții pare dă rezultate greșite pe exemple simple, de pildă [2, 1, 1, 2], unde optimul 4 se obține luând prima și ultima casă.

DP-ul compară exact două opțiuni pentru fiecare casă:

PYTHON
def jaf_maxim(a):
    precedent, curent = 0, 0      # dp[i-2], dp[i-1]
    for x in a:
        precedent, curent = curent, max(curent, precedent + x)
    return curent

print(jaf_maxim([1, 2, 3, 1]))     # 4: casele 1 și 3
print(jaf_maxim([2, 7, 9, 3, 1]))  # 12: 2 + 9 + 1
print(jaf_maxim([2, 1, 1, 2]))     # 4
print(jaf_maxim([]))               # 0

Starea: curent este cel mai bun total folosind casele de până acum. Tranziția: casa x se poate adăuga doar la cel mai bun total care nu include casa precedentă, adică precedent.

Atribuirea simultană din Python evită o variabilă temporară. În alte limbaje ai scrie tmp = max(curent, precedent + x); precedent = curent; curent = tmp.

Complexitate: O(n) timp, O(1) memorie. Inițializarea cu zero tratează automat lista goală și cea cu un singur element.

Variante construite pe aceeași idee:

  • casele sunt în cerc (prima și ultima sunt vecine): rulezi algoritmul de două ori, o dată fără prima casă și o dată fără ultima, și iei maximul;
  • casele sunt într-un arbore (nu poți lua un nod și copilul lui): fiecare nod întoarce o pereche (cu nodul, fără nod), calculată în postordine;
  • reconstruirea caselor alese: păstrezi tot tabelul dp și mergi înapoi: dacă dp[i] == dp[i-1], casa i nu a fost luată.

Același tipar „iau sau nu iau, cu restricție de vecinătate” apare la programarea de ședințe neconsecutive sau la alegerea de proiecte incompatibile.

Ce urmărește intervievatorul: Este o problemă de DP de bază. Intervievatorul verifică formularea celor două opțiuni și dacă poți explica de ce greedy eșuează.

Eroarea, în practică:IndexError la dp[n]: tabelul DP e prea scurt

87 Junior

Un robot pornește din colțul stânga-sus al unei grile m × n și se poate mișca doar la dreapta sau în jos. În câte moduri ajunge în colțul dreapta-jos, dacă unele celule sunt blocate?

Răspuns scurt: dp[r][c] este numărul de drumuri până la celula (r, c): suma drumurilor venite de sus și din stânga, sau 0 dacă celula e blocată. Poți păstra un singur rând, deci O(m · n) timp și O(n) memorie.

Fiecare drum care ajunge în (r, c) a venit fie din (r − 1, c), fie din (r, c − 1). Cele două mulțimi de drumuri sunt disjuncte, deci se adună.

PYTHON
def drumuri_unice(grila):          # 1 = blocat, 0 = liber
    m, n = len(grila), len(grila[0])
    dp = [0] * n
    dp[0] = 1 if grila[0][0] == 0 else 0
    for r in range(m):
        for c in range(n):
            if grila[r][c] == 1:
                dp[c] = 0
            elif c > 0:
                dp[c] += dp[c - 1]
    return dp[-1]

g = [[0, 0, 0],
     [0, 1, 0],
     [0, 0, 0]]
print(drumuri_unice(g))            # 2
print(drumuri_unice([[0] * 7 for _ in range(3)]))  # 28

Trucul cu un singur rând: înainte de actualizare, dp[c] conține valoarea de pe rândul de deasupra (drumurile venite de sus), iar dp[c - 1] a fost deja actualizat pe rândul curent (drumurile venite din stânga). dp[c] += dp[c - 1] le adună exact pe cele două.

Cazurile de bază sunt tratate natural: celula de start primește 1, iar prima coloană nu primește nimic din stânga. O celulă blocată devine 0 și „taie” toate drumurile care ar trece prin ea, inclusiv pe prima linie și prima coloană. Dacă startul e blocat, răspunsul e 0.

Complexitate: O(m · n) timp, O(n) memorie.

Fără obstacole există o formulă: drumul are m − 1 pași în jos și n − 1 la dreapta, deci răspunsul este combinări de (m + n − 2) luate câte (m − 1): math.comb(m + n - 2, m - 1) (din Python 3.8). E un bonus bun de menționat.

Varianta înrudită drumul de cost minim are aceeași structură, cu min în loc de sumă: dp[c] = grila[r][c] + min(dp[c], dp[c-1]), cu atenție la marginile unde există o singură direcție de intrare.

Ce urmărește intervievatorul: Verifică DP-ul pe două dimensiuni și reducerea memoriei la un rând. Intervievatorul urmărește tratarea obstacolelor de pe prima linie și coloană.

Eroarea, în practică:'int' object is not subscriptable la dp[i][j][[0] * m] * n: toate rândurile se schimbă

88 Junior

Ai o listă de activități cu oră de început și de final. Câte activități poți face, maxim, dacă nu se pot suprapune? De ce funcționează aici o soluție greedy și cum îți dai seama în general dacă greedy e corect?

Răspuns scurt: Sortezi după ora de final și alegi mereu următoarea activitate care începe după ultima aleasă. Finalul cel mai devreme lasă cel mai mult timp pentru rest. În general, demonstrezi printr-un argument de schimb sau cauți un contraexemplu.

Un algoritm greedy face la fiecare pas alegerea care pare cea mai bună local și nu revine asupra ei. E rapid și simplu, dar corect doar pentru anumite probleme.

PYTHON
def max_activitati(activitati):
    activitati = sorted(activitati, key=lambda x: x[1])
    numar, final = 0, float("-inf")
    for s, f in activitati:
        if s >= final:
            numar += 1
            final = f
    return numar

print(max_activitati([(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11)]))  # 3

Argumentul de schimb (exchange argument): fie o soluție optimă oarecare. Prima ei activitate se termină cel puțin la fel de târziu ca activitatea cu finalul cel mai devreme, aleasă de greedy. Dacă o înlocuiești cu alegerea greedy, soluția rămâne validă (nimic nu se suprapune, pentru că se termină și mai devreme) și are la fel de multe activități. Repeți raționamentul pe restul și obții că greedy e optim.

Criterii greedy care par rezonabile, dar sunt greșite:

  • cea mai scurtă activitate întâi: o activitate scurtă poate tăia două lungi compatibile între ele;
  • cea care începe cel mai devreme: o activitate lungă care începe devreme le poate bloca pe toate celelalte.

Cum decizi la interviu:

  • încerci să construiești un contraexemplu mic pentru criteriul greedy. Dacă îl găsești, treci la DP;
  • dacă nu găsești, schițezi argumentul de schimb;
  • semnal de DP: alegerea de acum schimbă ce opțiuni ai mai târziu într-un mod pe care criteriul local nu îl vede (rucsac 0/1, restul cu monede arbitrare).

Exemple corecte de greedy: rucsacul fracționar, codificarea Huffman, Dijkstra, Kruskal și Prim, restul cu monedele uzuale (1, 5, 10, 50), „sari cât de departe poți” (jump game).

Complexitate aici: O(n log n), din sortare.

Ce urmărește intervievatorul: Verifică dacă știi să justifici un greedy și dacă recunoști când nu merge. Răspunsul „pare corect” fără argument sau contraexemplu este cel mai slab răspuns posibil.

89 Junior

Într-o listă, fiecare număr apare de două ori, în afară de unul. Găsește-l în O(n) timp și O(1) memorie. Cum verifici, cu operații pe biți, dacă un număr este putere a lui 2?

Răspuns scurt: Faci XOR între toate numerele: perechile egale se anulează (x ^ x = 0), iar rezultatul este numărul singur. Un număr pozitiv n este putere a lui 2 dacă n & (n - 1) == 0, pentru că are un singur bit de 1.

Proprietățile lui XOR (^) care fac trucul posibil:

  • x ^ x = 0;
  • x ^ 0 = x;
  • este comutativ și asociativ, deci ordinea nu contează.
PYTHON
from functools import reduce
from operator import xor

def numar_unic(a):
    rez = 0
    for x in a:
        rez ^= x
    return rez

print(numar_unic([4, 1, 2, 1, 2]))     # 4
print(reduce(xor, [7, 3, 7]))          # 3

Toate perechile se anulează reciproc, indiferent unde sunt în listă, și rămâne doar valoarea fără pereche. O(n) timp, O(1) memorie, față de O(n) memorie la soluția cu set sau Counter.

Puterea lui 2: o putere a lui 2 are în binar un singur bit de 1, de exemplu 8 = 1000₂. Scăzând 1, acel bit devine 0, iar toți biții de sub el devin 1: 7 = 0111₂. Deci n & (n - 1) șterge cel mai de jos bit de 1, iar rezultatul este 0 doar dacă era singurul.

PYTHON
def putere_a_lui_2(n):
    return n > 0 and n & (n - 1) == 0

print([x for x in range(20) if putere_a_lui_2(x)])  # [1, 2, 4, 8, 16]

Testul n > 0 e necesar: pentru 0, expresia 0 & -1 dă tot 0. Parantezele nu sunt necesare aici: în Python, & are prioritate mai mare decât ==. În C și Java e invers, deci acolo scrii (n & (n - 1)) == 0.

Alte trucuri din aceeași familie:

  • n & -n izolează cel mai de jos bit de 1, folosit la Fenwick tree;
  • bin(n).count("1") sau, din Python 3.10, n.bit_count() numără biții de 1;
  • două numere unice: XOR-ul tuturor dă a ^ b; un bit de 1 din acest rezultat împarte numerele în două grupuri, iar XOR-ul fiecărui grup dă câte unul dintre ele;
  • numărul lipsă din 0..n: XOR între toți indicii și toate valorile.

Ce urmărește intervievatorul: Verifică dacă știi proprietățile lui XOR și trucurile clasice pe biți. Mulți candidați uită cazul n = 0 sau precedența operatorilor în alte limbaje.

Eroarea, în practică:x ^ 2 nu e pătratul lui x (XOR)

90 Mid

Primești valorile unor monede și o sumă. Care este numărul minim de monede cu care poți plăti suma? De ce greedy-ul „ia mereu moneda cea mai mare” nu e corect în general?

Răspuns scurt: dp[s] = 1 + min(dp[s - m]) peste monedele m ≤ s, cu dp[0] = 0: O(S · k) timp, O(S) memorie. Greedy eșuează pentru monedele {1, 3, 4} și suma 6: alege 4 + 1 + 1, iar optimul este 3 + 3.

Greedy-ul funcționează pentru sistemele monetare uzuale (1, 5, 10, 50), care au fost proiectate astfel. Pentru valori arbitrare, o monedă mare luată devreme poate forța mai multe monede mici la final.

PYTHON
def monede_minime(monede, suma):
    INF = float("inf")
    dp = [0] + [INF] * suma
    for s in range(1, suma + 1):
        for m in monede:
            if m <= s and dp[s - m] + 1 < dp[s]:
                dp[s] = dp[s - m] + 1
    return dp[suma] if dp[suma] != INF else -1

print(monede_minime([1, 3, 4], 6))     # 2: 3 + 3
print(monede_minime([2], 3))           # -1: imposibil
print(monede_minime([1, 2, 5], 11))    # 3: 5 + 5 + 1

Starea: dp[s], cel mai mic număr de monede cu suma exact s. Tranziția: ultima monedă folosită a fost una dintre cele k, deci încerci toate variantele. Infinitul marchează sumele imposibile, care trebuie tratate separat la final.

Complexitate: O(S · k) timp, unde S este suma și k numărul de tipuri de monede, plus O(S) memorie. Este pseudo-polinomial: polinomial în valoarea lui S, nu în numărul de biți necesari pentru a-l scrie. Pentru S = 10⁹, tabelul nu mai încape.

Ca alternativă, poți vedea problema ca un drum minim într-un graf: nodurile sunt sumele 0..S, iar fiecare monedă e o muchie de cost 1. Un BFS de la 0 dă același rezultat și se oprește devreme când găsește suma.

Pentru a reconstrui monedele, reții pentru fiecare s ce monedă a dat minimul și mergi înapoi de la S.

Varianta înrudită „în câte moduri poți plăti suma” (combinații, nu permutări) cere ordinea buclelor inversată: bucla exterioară pe monede, cea interioară pe sume, cu dp[s] += dp[s - m]. Dacă inversezi buclele, numeri permutările: 1 + 2 și 2 + 1 ar fi socotite separat.

Ce urmărește intervievatorul: Verifică dacă știi DP-ul clasic de optimizare și poți da un contraexemplu pentru greedy. Ordinea buclelor la varianta cu numărare este un follow-up care prinde mulți candidați.

Eroarea, în practică:Monede: DP inițializat cu 0, nu cu infinit

91 Mid

Calculează distanța de editare (Levenshtein) dintre două cuvinte: numărul minim de inserări, ștergeri și înlocuiri de caractere care transformă primul cuvânt în al doilea.

Răspuns scurt: dp[i][j] este distanța dintre primele i caractere din a și primele j din b. Dacă a[i-1] == b[j-1], iei dp[i-1][j-1]; altfel, 1 + min dintre ștergere, inserare și înlocuire. O(m · n) timp, iar memoria se poate reduce la două rânduri.

PYTHON
def distanta_editare(a, b):
    m, n = len(a), len(b)
    prev = list(range(n + 1))          # dp[0][j] = j inserări
    for i in range(1, m + 1):
        cur = [i] + [0] * n            # dp[i][0] = i ștergeri
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                cur[j] = prev[j - 1]
            else:
                cur[j] = 1 + min(prev[j],       # ștergi a[i-1]
                                 cur[j - 1],    # inserezi b[j-1]
                                 prev[j - 1])   # înlocuiești
        prev = cur
    return prev[n]

print(distanta_editare("horse", "ros"))          # 3
print(distanta_editare("intention", "execution")) # 5
print(distanta_editare("", "abc"))               # 3

Cum citești tranzițiile, gândindu-te la ultimul caracter al fiecărui prefix:

  • dacă ultimele caractere sunt egale, nu costă nimic: rezolvi prefixele mai scurte;
  • ștergere: elimini a[i-1], rămâne să transformi a[:i-1] în b[:j], adică dp[i-1][j];
  • inserare: adaugi b[j-1] la final, rămâne a[:i] față de b[:j-1], adică dp[i][j-1];
  • înlocuire: transformi a[i-1] în b[j-1] și rămân ambele prefixe mai scurte.

Cazurile de bază: transformarea unui prefix în șirul gol costă câte o ștergere pe caracter, iar invers câte o inserare.

Complexitate: O(m · n) timp. Cu două rânduri, memoria scade de la O(m · n) la O(n). Poți alege ca b să fie șirul mai scurt, pentru O(min(m, n)). Dacă trebuie să afișezi și operațiile, ai nevoie de tot tabelul (sau de algoritmul lui Hirschberg, mai complicat).

Rude apropiate: cel mai lung subșir comun (LCS) are aceeași structură, cu dp[i-1][j-1] + 1 la egalitate și max(dp[i-1][j], dp[i][j-1]) altfel. Variantele cu costuri diferite pe operații sau cu transpoziții (Damerau–Levenshtein) se obțin modificând tranzițiile.

Aplicații: corectoare ortografice, sugestii „ați vrut să scrieți…”, diff, alinierea secvențelor ADN.

Ce urmărește intervievatorul: Este DP-ul clasic pe două șiruri. Intervievatorul urmărește interpretarea fiecărei tranziții, cazurile de bază și reducerea memoriei.

Eroarea, în practică:'int' object is not subscriptable la dp[i][j]Distanța de editare: lipsește inițializarea

92 Mid

Rezolvă problema rucsacului 0/1: ai obiecte cu greutăți și valori și un rucsac de capacitate W; fiecare obiect se ia o dată sau deloc. De ce, în varianta cu o singură listă, parcurgi capacitatea descrescător?

Răspuns scurt: dp[c] e valoarea maximă la capacitatea c: pentru fiecare obiect, dp[c] = max(dp[c], dp[c - g] + v), cu c de la W în jos. Așa, dp[c - g] nu include încă obiectul curent, deci îl folosești cel mult o dată. O(n · W).

Varianta clasică are tabelul dp[i][c]: valoarea maximă folosind primele i obiecte cu capacitatea c. Pentru obiectul i ai două opțiuni: nu-l iei (dp[i-1][c]) sau îl iei, dacă încape (dp[i-1][c-g] + v).

Fiecare rând depinde doar de rândul anterior, deci păstrezi o singură listă:

PYTHON
def rucsac(greutati, valori, W):
    dp = [0] * (W + 1)
    for g, v in zip(greutati, valori):
        for c in range(W, g - 1, -1):     # descrescător!
            dp[c] = max(dp[c], dp[c - g] + v)
    return dp[W]

print(rucsac([1, 3, 4, 5], [1, 4, 5, 7], 7))  # 9: obiectele de 3 și 4

De ce descrescător: când calculezi dp[c], ai nevoie de dp[c - g] din rândul anterior, adică fără obiectul curent. Parcurgând de sus în jos, dp[c - g] nu a fost încă actualizat în această iterație. Dacă ai parcurge crescător, dp[c - g] ar include deja obiectul curent, iar acesta ar putea fi adăugat din nou: obții varianta nelimitată (unbounded knapsack), în care fiecare obiect se poate lua de oricâte ori. Bucla crescătoare este, deci, corectă pentru acea variantă.

Bucla se oprește la g pentru că, sub această capacitate, obiectul nu încape, iar dp[c] rămâne neschimbat.

Complexitate: O(n · W) timp, O(W) memorie. Este pseudo-polinomial: pentru W foarte mare (de exemplu 10⁹), tabelul nu mai e fezabil, iar problema este NP-dificilă în general. Pentru valori mici, poți inversa dimensiunea: dp[valoare] = greutatea minimă.

Varianta fracționară (poți lua bucăți de obiect) se rezolvă greedy, sortând după valoare pe unitate de greutate.

Probleme care sunt rucsac deghizat: împărțirea unei liste în două grupuri cu sume egale (dp[c] boolean, capacitatea este jumătate din sumă), „target sum” cu semne + și −, alegerea proiectelor cu buget limitat.

Ce urmărește intervievatorul: Verifică dacă înțelegi DP-ul de bază și optimizarea de memorie. Direcția buclei este detaliul care separă înțelegerea de memorare: un candidat bun știe și ce obține dacă o inversează.

Eroarea, în practică:Rucsac 0/1: capacitatea parcursă crescător

93 Senior

Găsește lungimea celui mai lung subșir strict crescător (nu neapărat contiguu) dintr-o listă. Dă soluția O(n²) și apoi pe cea O(n log n).

Răspuns scurt: DP O(n²): dp[i] = 1 + maximul dp[j] pentru j < i cu a[j] < a[i]. În O(n log n) ții cozi[k], cel mai mic final al unui subșir crescător de lungime k + 1, actualizat prin căutare binară.

Varianta O(n²), ușor de explicat:

PYTHON
def lis_patratic(a):
    if not a:
        return 0
    dp = [1] * len(a)
    for i in range(len(a)):
        for j in range(i):
            if a[j] < a[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

Varianta O(n log n), cu „patience sorting”:

PYTHON
from bisect import bisect_left

def lis(a):
    cozi = []
    for x in a:
        i = bisect_left(cozi, x)
        if i == len(cozi):
            cozi.append(x)        # extinde cel mai lung subșir
        else:
            cozi[i] = x           # un final mai mic pentru lungimea i + 1
    return len(cozi)

print(lis([10, 9, 2, 5, 3, 7, 101, 18]))  # 4, de exemplu 2, 3, 7, 18
print(lis([7, 7, 7]))                     # 1

Ideea: dintre toate subșirurile crescătoare de lungime k, cel cu finalul cel mai mic e cel mai promițător, pentru că lasă cele mai multe opțiuni de continuare. cozi este mereu strict crescătoare: un subșir mai lung are un final mai mare decât cel mai bun final al unuia mai scurt. De aceea poți căuta binar poziția lui x.

Pentru fiecare x, bisect_left găsește primul final ≥ x. Dacă nu există, x extinde cel mai lung subșir. Altfel, x devine un final mai bun pentru acea lungime.

Atenție: cozi nu este un subșir crescător valid din listă. Doar lungimea ei e corectă. Pentru a reconstrui subșirul, reții indicii finalurilor și, pentru fiecare element, predecesorul lui.

Detalii pe care le verifică intervievatorul:

  • bisect_left dă subșir strict crescător; bisect_right dă subșir nedescrescător (permite egalități);
  • complexitate: n căutări binare, deci O(n log n) timp și O(n) memorie.

Aplicații: problema plicurilor imbricate (sortezi după lățime crescător și după înălțime descrescător, apoi LIS pe înălțimi), numărul minim de șiruri crescătoare în care poți împărți o listă, versiunile compatibile într-un lanț de dependențe.

Ce urmărește intervievatorul: Este o problemă de nivel avansat. Intervievatorul urmărește trecerea de la O(n²) la O(n log n) și dacă știi că cozi nu este subșirul propriu-zis.

Eroarea, în practică:LIS: dp[-1] în loc de max(dp)

94 Senior

Primești un text fără spații și un dicționar de cuvinte. Spune dacă textul poate fi împărțit în cuvinte din dicționar (word break). Cum ai întoarce toate împărțirile posibile?

Răspuns scurt: dp[i] e True dacă primele i caractere se pot împărți: există j < i cu dp[j] True și s[j:i] în dicționar. Limitezi j la lungimea maximă a unui cuvânt. Toate împărțirile: backtracking cu memoizare, cu rezultat posibil exponențial.

PYTHON
def se_poate_imparti(s, cuvinte):
    dictionar = set(cuvinte)
    L = max(map(len, dictionar), default=0)
    dp = [False] * (len(s) + 1)
    dp[0] = True                           # prefixul gol
    for i in range(1, len(s) + 1):
        for j in range(max(0, i - L), i):
            if dp[j] and s[j:i] in dictionar:
                dp[i] = True
                break
    return dp[len(s)]

print(se_poate_imparti("leetcode", ["leet", "code"]))                     # True
print(se_poate_imparti("catsandog", ["cats", "dog", "sand", "and", "cat"])) # False

Optimizarea cu L, lungimea maximă a unui cuvânt, contează: fără ea bucla interioară merge înapoi până la 0, deci O(n²) verificări, fiecare cu o felie de cost O(n), adică O(n³). Cu ea, ai O(n · L) felii de cost O(L).

Backtracking-ul fără memoizare explodează exponențial pe intrări precum „aaaa…ab” cu dicționarul {„a”, „aa”, „aaa”}: încearcă toate împărțirile prefixului, deși niciuna nu poate trece de „b” de la final.

Toate împărțirile:

PYTHON
from functools import lru_cache

def toate_impartirile(s, cuvinte):
    dictionar = set(cuvinte)

    @lru_cache(maxsize=None)
    def f(i):
        if i == len(s):
            return [[]]
        rez = []
        for j in range(i + 1, len(s) + 1):
            if s[i:j] in dictionar:
                for rest in f(j):
                    rez.append([s[i:j]] + rest)
        return rez

    return [" ".join(p) for p in f(0)]

print(toate_impartirile("catsanddog", ["cat", "cats", "and", "sand", "dog"]))
# ['cat sand dog', 'cats and dog']

Memoizarea evită recalcularea sufixelor, dar numărul de împărțiri poate fi el însuși exponențial, deci nicio soluție nu le poate enumera în timp polinomial. Merită spus explicit. Un pas practic este să rulezi întâi varianta booleană și să renunți imediat dacă răspunsul e False.

Un trie cu cuvintele dicționarului înlocuiește feliile și testele în set: din poziția i cobori în trie caracter cu caracter și te oprești când nu mai există ramură. Util când dicționarul e mare și cuvintele au prefixe comune.

Aplicații: segmentarea textelor în limbi fără spații, hashtag-uri lipite, tokenizare.

Ce urmărește intervievatorul: Verifică DP-ul pe prefixe, optimizarea cu lungimea maximă și conștientizarea limitei exponențiale la enumerare. Candidații de nivel senior discută și varianta cu trie.

Abordarea problemei la interviu

95 Junior

Primești la tablă (sau într-un editor partajat) o problemă de algoritmi pe care nu ai mai văzut-o. Ce pași urmezi de la enunț până la cod?

Răspuns scurt: Clarifici enunțul și constrângerile, lucrezi un exemplu de mână, spui o soluție brută și complexitatea ei, o optimizezi, abia apoi scrii codul și la final îl testezi pe exemple și cazuri limită. Tot timpul gândești cu voce tare.

Intervievatorul evaluează procesul cel puțin la fel de mult ca rezultatul. Un traseu care funcționează pentru aproape orice problemă:

  • clarifici: ce tipuri au intrarea și ieșirea? Cât de mare e n? Pot exista duplicate, valori negative, intrare goală? Ce întorc dacă nu există soluție? Lista e sortată? Am voie să o modific?
  • un exemplu de mână: iei un exemplu mic, dar netrivial, și îl rezolvi pe hârtie. Deseori, așa observi tiparul;
  • soluția brută: o spui explicit, cu complexitatea ei. Arată că ai o soluție corectă și îți dă un punct de plecare;
  • optimizezi: te uiți la ce repetă soluția brută și cauți structura care elimină repetiția (un set, sortare, doi indici, prefix sums, DP). Spui noua complexitate și confirmi cu intervievatorul înainte de a scrie;
  • scrii codul: nume clare, funcții mici, fără optimizări premature. Spui ce faci în timp ce scrii;
  • testezi: treci codul prin exemplul de la început, linie cu linie, apoi prin cazuri limită: gol, un element, toate egale, valori extreme;
  • analizezi: dai complexitatea finală de timp și memorie și menționezi ce ai putea îmbunătăți.

Un exemplu de gândire cu voce tare: „Soluția brută verifică toate perechile, O(n²). Pentru fiecare element caut complementul, deci dacă țin valorile văzute într-un set, căutarea devine O(1) și totul O(n), cu O(n) memorie. Vi se pare o abordare bună înainte să o scriu?”

Greșeli frecvente: să începi să scrii cod în primul minut, să taci minute în șir, să ignori indiciile intervievatorului, să declari „gata” fără să testezi.

Ce urmărește intervievatorul: Verifică dacă ai un proces structurat și dacă poți comunica în timp ce gândești. Mulți candidați slabi sar direct la cod și se blochează la jumătate.

96 Junior

Ai terminat de scris funcția la interviu. Cum o testezi fără să o rulezi? Ce cazuri limită verifici de obicei la problemele cu liste, șiruri și grafuri?

Răspuns scurt: Urmărești codul linie cu linie pe un exemplu mic, notând valorile variabilelor, apoi verifici cazurile limită: intrare goală, un singur element, toate elementele egale, valori negative sau zero, valori la margini și intrări care declanșează fiecare ramură din cod.

Testarea „de mână” (dry run) este o abilitate distinctă pe care intervievatorul o urmărește. Nu reciți codul: urmărești starea.

Metoda:

  • alegi un exemplu mic, de 4–6 elemente, care trece prin toate ramurile importante;
  • scrii pe tablă un tabel cu variabilele cheie (indici, sumă, stivă) și îl actualizezi la fiecare iterație;
  • verifici condiția de oprire la ultimul pas: aici apar cele mai multe erori off-by-one;
  • compari rezultatul cu răspunsul calculat independent.

Cazuri limită, pe categorii:

  • liste: goală, un element, două elemente, toate egale, deja sortată, sortată invers, cu duplicate, cu negative și zero;
  • șiruri: șir gol, un caracter, toate caracterele identice, majuscule și minuscule, spații, caractere Unicode;
  • numere: 0, 1, negative, foarte mari (în Python nu ai overflow, dar în alte limbaje da), împărțirea la zero;
  • liste înlănțuite: None, un nod, operația pe cap sau pe coadă, ciclu;
  • arbori: arbore gol, doar rădăcina, arbore degenerat (o linie), valori duplicate;
  • grafuri: noduri izolate, graf neconex, cicluri, bucle (muchie de la un nod la el însuși), muchii multiple;
  • matrice: 0 × 0, 1 × n, n × 1.

Dacă ai voie să rulezi codul, scrie câteva aserțiuni rapide:

PYTHON
def test():
    assert two_sum([2, 7, 11, 15], 9) == (0, 1)
    assert two_sum([3, 3], 6) == (0, 1)
    assert two_sum([1, 2], 7) is None
    print("ok")

Pentru o verificare serioasă, compari soluția optimizată cu cea brută pe date aleatoare mici (testare diferențială). La interviu e suficient să menționezi tehnica.

Când găsești un bug, spune-l calm și repară-l. Un bug găsit chiar de tine în timpul testării contează pozitiv, nu negativ.

Ce urmărește intervievatorul: Intervievatorul verifică dacă îți validezi singur codul. Candidații care declară „gata” fără să testeze și lasă intervievatorul să găsească bug-ul pierd mult.

97 Mid

Te-ai blocat la o problemă în mijlocul interviului și nu vezi soluția optimă. Ce faci concret în următoarele minute?

Răspuns scurt: Nu taci. Spui unde ești, revii la soluția brută pe care o știi, încerci tehnicile standard una câte una, lucrezi un exemplu mic și ceri sau folosești indiciile intervievatorului. O soluție brută corectă, explicată bine, valorează mai mult decât una optimă neterminată.

Blocajul e normal; contează cum îl gestionezi. Un model de răspuns structurat, pe pași:

  • spui unde ești: „Am o soluție O(n²) care funcționează. Mă gândesc cum să elimin bucla interioară.” Tăcerea lungă e cel mai rău semnal, pentru că intervievatorul nu te poate ajuta dacă nu știe ce gândești;
  • asiguri o bază: dacă nu ai scris încă nimic, propune să scrii soluția brută. Ai astfel ceva corect și testabil, iar optimizarea vine deseori din observarea ei;
  • treci prin lista de tehnici: lista e sortată sau o pot sorta? Pot folosi un set sau un dicționar? Doi indici sau o fereastră? Sume prefix? Stivă monotonă? Heap? Căutare binară pe răspuns? E un graf ascuns? Are subprobleme care se repetă, deci DP?
  • schimbi exemplul: un exemplu mai mic sau un caz particular (toate pozitive, toate distincte) poate scoate la iveală tiparul;
  • simplifici problema: rezolvi o variantă mai ușoară (o dimensiune în loc de două, k = 1) și vezi dacă ideea se generalizează;
  • folosești indiciile: dacă intervievatorul spune „ce-ar fi dacă lista ar fi sortată?”, nu e o întrebare retorică. Preia ideea și spune ce schimbă.

Exemplu de formulare: „Nu văd încă soluția liniară. Propun să scriu varianta cu sortare, O(n log n), ca să avem ceva corect, și apoi să caut unde pierd timp. E în regulă?”

Ce să eviți: să ștergi tot și să o iei de la capăt în tăcere, să insiști pe o idee care evident nu merge, să spui „nu știu” și să te oprești.

Ce urmărește intervievatorul: Intervievatorul evaluează cum lucrezi sub presiune și cum colaborezi. Un candidat care comunică clar și progresează cu indicii este adesea preferat unuia care ghicește soluția în tăcere.

98 Mid

La code review, vezi că un coleg junior a scris o funcție care caută, pentru fiecare comandă, clientul ei într-o listă de clienți, cu o buclă în buclă. Testele trec. Cum îi explici problema și ce îi propui?

Răspuns scurt: Arăți, pe volumele reale, de ce bucla în buclă e O(n · m) și ce se întâmplă când cresc datele. Propui un dicționar {id: client} construit o dată, care reduce totul la O(n + m), și explici fără ton de reproș.

Situația e frecventă: codul e corect, testele folosesc date mici, iar problema apare abia în producție. Un model de răspuns structurat:

Contextul: testele au câteva zeci de clienți, dar în producție sunt, de exemplu, 50.000 de clienți și 200.000 de comenzi pe zi. Bucla în buclă face ordinul a 10¹⁰ comparații. Calculul concret convinge mai bine decât „e O(n²)”.

Explicația: pentru fiecare comandă, for c in clienti parcurge, în medie, jumătate din listă. Costul crește cu produsul celor două dimensiuni.

Propunerea:

PYTHON
# înainte: O(n · m)
for comanda in comenzi:
    for c in clienti:
        if c["id"] == comanda["client_id"]:
            comanda["client"] = c
            break

# după: O(n + m)
dupa_id = {c["id"]: c for c in clienti}
for comanda in comenzi:
    comanda["client"] = dupa_id.get(comanda["client_id"])

Dicționarul se construiește o dată, în O(m), iar fiecare căutare e O(1) în medie. get întoarce None pentru o comandă fără client, iar asta merită discutat: e un caz pe care codul vechi îl trata la fel, dar tăcut.

Cum o spui: întrebi întâi („ce volum crezi că avem în producție aici?”), ca să ajungă singur la concluzie. Formulezi comentariul ca sugestie, cu motivul și cu codul propus. Dacă datele vin din baza de date, discuți și varianta cu un JOIN, care mută munca acolo unde există indecși.

Ce eviți: comentarii de tipul „asta e greșit” fără explicație, optimizarea codului care rulează rar pe date mici (acolo lizibilitatea contează mai mult) și transformarea discuției într-o lecție de teorie.

Urmarea: propui un test cu volum realist sau o măsurătoare simplă (timeit), ca regula să rămână și pentru alte cazuri.

Ce urmărește intervievatorul: Verifică dacă poți lega teoria complexității de cod real și dacă știi să dai feedback constructiv. Intervievatorul urmărește calculul concret și tonul colaborativ.

Eroarea, în practică:x in lista în buclă: soluție prea lentă

99 Senior

Un endpoint din producție a devenit tot mai lent pe măsură ce au crescut datele. Suspectezi un algoritm ineficient. Cum investighezi și cum decizi ce optimizezi?

Răspuns scurt: Măsori înainte să schimbi ceva: reproduci cu date realiste, folosești un profiler ca să găsești funcția care consumă timpul, verifici cum crește timpul cu volumul, identifici complexitatea reală, optimizezi punctul fierbinte, apoi validezi cu măsurători și teste.

Un model de răspuns pe pași, cu accent pe dovezi:

1. Confirmi simptomul. Metricile arată latența în creștere odată cu volumul de date, nu brusc după un deploy? Creșterea graduală sugerează o problemă de complexitate; un salt brusc sugerează o modificare de cod sau de infrastructură.

2. Reproduci local cu un set de date de dimensiune realistă, anonimizat. Fără reproducere, optimizezi pe ghicite.

3. Profilezi. În Python, cProfile arată timpul pe funcție:

BASH
python -m cProfile -s cumtime script.py | head -30

Pentru un serviciu care rulează, un profiler prin eșantionare, precum py-spy, se atașează la proces fără să-l repornești. Deseori, timpul nu e în locul bănuit.

4. Verifici scalarea. Rulezi cu n, 2n, 4n. Dacă timpul se dublează, e liniar; dacă se înmulțește cu 4, e pătratic. E cel mai rapid test de complexitate în practică.

5. Identifici cauza. Tipare frecvente: in pe o listă într-o buclă, sortări repetate în buclă, interogări SQL în buclă (problema N+1), concatenări de șiruri, recalcularea agregatelor de la zero la fiecare cerere, lipsa unui index în baza de date.

6. Alegi remedierea cu cel mai bun raport impact/risc: o structură de date potrivită (set, dicționar, heap), precalculare sau cache, mutarea muncii în baza de date, paginare, procesare asincronă. Nu rescrii tot sistemul dacă o singură funcție consumă majoritatea timpului.

7. Validezi: testele existente trec, compari rezultatele vechi și noi pe aceleași date, măsori din nou și adaugi un test de performanță sau o alertă, ca regresia să nu revină.

Concluzia de spus explicit: complexitatea algoritmică îți spune unde să cauți, dar măsurătoarea îți spune ce să repari.

Ce urmărește intervievatorul: Verifică dacă abordezi performanța metodic și bazat pe date, nu pe intuiție. Un candidat de nivel senior leagă Big O de profilare și de riscul schimbărilor în producție.

100 Senior

Ai rezolvat problema la interviu, iar intervievatorul continuă: „Și dacă datele nu mai încap în memorie?” sau „Dacă primești datele ca flux, unul câte unul?” Cum abordezi astfel de întrebări de scalare?

Răspuns scurt: Se schimbă modelul de cost: nu mai ții totul în RAM sau nu poți reveni asupra datelor. Răspunzi cu sortare externă, partiționare după hash, structuri de mărime fixă (heap de k, ferestre), algoritmi aproximativi și map-reduce.

Nu se așteaptă cod perfect, ci recunoașterea constrângerii și a tehnicii potrivite.

Datele nu încap în memorie (de exemplu, sortează sau deduplică 500 GB):

  • sortare externă: citești bucăți care încap în memorie, le sortezi și le scrii pe disc, apoi interclasezi cele k fișiere cu un heap de mărime k;
  • partiționare după hash: împarți datele în fișiere după hash(cheie) % p; toate aparițiile unei chei ajung în aceeași partiție, deci deduplicarea sau numărarea se fac pe partiții mici, independent;

Datele sosesc ca flux (nu le poți parcurge de două ori):

  • top k: un min-heap de mărime k;
  • mediana: două heap-uri, sau structuri aproximative de cuantile, dacă volumul e uriaș;
  • ultimele n minute: o fereastră glisantă cu deque;
  • elemente distincte sau frecvențe aproximative: HyperLogLog și Count-Min Sketch, cu memorie fixă și eroare controlată.

Datele sunt distribuite pe multe mașini:

  • tiparul map-reduce: fiecare mașină calculează un rezultat parțial, apoi rezultatele se combină. Atenție: mediana exactă nu se obține din medianele parțiale.

Cum răspunzi:

  • reformulezi constrângerea: „Deci nu pot ține tot setul; pot ține cel mult k elemente”;
  • spui ce parte a soluției actuale nu mai funcționează și de ce;
  • propui tehnica și compromisul ei (exactitate contra memorie, latență contra cost);
  • întrebi dacă un răspuns aproximativ e acceptabil, pentru că schimbă complet soluția.

Exemplu: pentru „cele mai căutate 10 cuvinte dintr-un jurnal de 1 TB”, partiționezi după hash-ul cuvântului, numeri exact în fiecare partiție, păstrezi top 10 local cu un heap și combini cele p liste de câte 10.

Ce urmărește intervievatorul: Verifică dacă poți trece de la algoritmi de manual la constrângeri reale de sistem. Candidații de nivel senior cunosc tehnicile de flux și de date externe și discută compromisul exact/aproximativ.

Întrebări de interviu pe meserie

Alte tehnologii

← Toate întrebările de interviu

Tudor Andrei Dumitrescu
Cine coordonează pregătirea de interviu

Tudor Andrei Dumitrescu

Senior Software Developer · fondatorul Academiei Programatorilor

LinkedIn
  1. 2019 Junior JavaCognizant Softvision
  2. 2021 Mid JavaCognizant Softvision
  3. 2022 Team LeaderEndava
  4. 2023 Senior Software DeveloperUniCredit
  5. Acum Senior Software DeveloperHCLTech
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu
Certificat de formator autorizatMinisterul Muncii și Ministerul Educației · 2022
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu

Certificat de formator autorizat · Ministerul Muncii și Ministerul Educației · 2022

Din 2020 construiește Academia Programatorilor, iar din 2026 și JoburiIT.ro. Întrebările de aici urmăresc ce se cere la interviurile de Algoritmi și structuri de date, de la junior la mid, iar pe JoburiIT.ro îți poți certifica apoi cunoștințele.

Învață Algoritmi și structuri de date scriind cod, nu doar citind

Curs Algoritmi pentru interviuri: lecții scurte, fiecare cu un exercițiu verificat automat, direct în browser. Primele 2 lecții sunt gratuite.