...
← Curs Algoritmi pentru interviuri: toate lecțiile
Lecția 1 · Introducere

Ce este un algoritm și cum arată un interviu tehnic

La aproape orice interviu pentru un post de programator primești o problemă și trebuie să scrii un algoritm care o rezolvă, apoi să explici cât de rapid este. În acest curs exersezi exact asta, în Python, direct în browser: problemă cu problemă, de la cele simple la cele care apar la marile companii.

Înainte să începi

Cursul pornește de la ce ai învățat în cursul Python: variabile, if, bucle for și while, liste, dicționare și funcții cu def. Nu le mai explicăm de la zero, doar le reamintim pe scurt când apar.

Dacă ești la început

Dacă nu ai scris încă funcții în Python, parcurge mai întâi cursul Python al Academiei. Aici te concentrezi pe cum gândești o soluție, nu pe sintaxa limbajului.

Ce este un algoritm?

Un algoritm este o listă de pași clari care transformă niște date de intrare într-un rezultat. O rețetă de prăjitură este un algoritm: ingrediente (intrarea), pași în ordine, prăjitura (rezultatul).

Exemplu: vrei să afli cel mai mare număr dintr-o listă. Pașii sunt:

1
Presupui că primul număr este cel mai mare și îl ții minte.
2
Treci prin restul numerelor, unul câte unul.
3
Dacă găsești un număr mai mare decât cel ținut minte, îl ții minte pe el.
4
La final, numărul ținut minte este maximul.

În Python, acești pași devin o funcție:

def maxim(lista):
    cel_mai_mare = lista[0]
    for x in lista:
        if x > cel_mai_mare:
            cel_mai_mare = x
    return cel_mai_mare

print(maxim([4, 8, 1, 6]))
8

Cum arată un interviu tehnic

Un interviu tehnic durează de obicei 45–60 de minute și are aproape mereu aceeași structură:

EtapaCe faci
EnunțulPrimești o problemă, de exemplu „găsește două numere din listă care au suma 10”.
ClarificăriPui întrebări: lista poate fi goală? pot fi numere negative?
IdeeaSpui cu voce tare cum ai rezolva, întâi varianta simplă.
CodulScrii funcția, de obicei într-un editor simplu, fără ajutor.
TestareaO rulezi în minte (sau pe calculator) pe câteva exemple.
ComplexitateaExplici cât de rapidă este soluția, cu notația O(...).
Ce contează cu adevărat

Intervievatorul nu vrea doar răspunsul corect. Vrea să vadă cum gândești: cum pui întrebări, cum testezi și dacă știi să spui de ce soluția ta e rapidă sau lentă.

Cum lucrăm în acest curs

Fiecare exercițiu are aceeași formă: tu scrii funcția, iar programul o apelează pe mai multe date de test și afișează rezultatele. Așa verifici soluția pe mai multe cazuri dintr-o dată, ca la interviu:

def suma(lista):
    total = 0
    for x in lista:
        total += x
    return total

print(suma([1, 2, 3]))
print(suma([10, -4]))
print(suma([]))
6
6
0

Observă testul suma([]): lista goală este un caz limită. La interviuri, cazurile limită sunt locul unde apar cele mai multe greșeli.

Prima privire la complexitate

Funcția maxim se uită la fiecare element o singură dată. Dacă lista are 10 elemente, face cam 10 pași; dacă are un milion, face cam un milion de pași. Spunem că are complexitatea O(n), unde n este lungimea listei.

Complexitate

Timp: O(n), o singură parcurgere a listei. Spațiu suplimentar: O(1), doar variabila cel_mai_mare, oricât de mare ar fi lista.

Vei învăța notația O(...) pas cu pas în lecțiile următoare. Deocamdată reține ideea: numărăm câți pași face algoritmul când datele cresc.

Greșeli frecvente

  • Pornești de la 0: cel_mai_mare = 0 dă rezultat greșit pentru o listă doar cu numere negative, de exemplu [-5, -2] ar da 0. Pornește de la primul element.
  • **Folosești max(lista)**: e corect în Python, dar la interviu ți se cere de obicei să scrii chiar algoritmul.
  • **Uiți return**: funcția fără return întoarce None, iar print afișează None.
Magazin online

Cel mai scump produs din coș sau cea mai mare reducere sunt calculate exact așa.

Aplicația meteo

Temperatura maximă a săptămânii este maximul unei liste de valori.

Interviuri

Variante ale acestei probleme (al doilea maxim, maxim fără o funcție de bibliotecă) apar des la primul interviu.

Exercițiul tău

Scrie funcția maxim(lista) care returnează cel mai mare număr din listă, fără să folosești max(). Testele sunt deja scrise sub funcție.

  • Pornește cu primul element ca maxim.
  • Parcurge lista cu for și actualizează maximul.
  • Returnează maximul și rulează programul: trebuie să apară 9, -1 și 7.
Pentru [-5, -1, -8] rezultatul este -1: de aceea nu pornești de la 0, ci de la lista[0].

Soluția exercițiului

def maxim(lista):
    cel_mai_mare = lista[0]
    for x in lista:
        if x > cel_mai_mare:
            cel_mai_mare = x
    return cel_mai_mare


print(maxim([3, 9, 2]))
print(maxim([-5, -1, -8]))
print(maxim([7]))
Excelent! Continuă cu lecția următoare →
main.pyPython
ConsolăSe încarcă...
Mediul de lucru se încarcă. Poți citi lecția între timp.
Rulează codul cu butonul de sus sau cu Ctrl + Enter / Cmd + Enter.
Parcursul tău Primele lecții gratuite Lecția 1 · Ce este un algoritm și cum arată un interviu
Progres 0% 0 din 3
Lecția curentă 1 / 2 Introducere