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ă 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:
Î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ă:
| Etapa | Ce faci |
|---|---|
| Enunțul | Primești o problemă, de exemplu „găsește două numere din listă care au suma 10”. |
| Clarificări | Pui întrebări: lista poate fi goală? pot fi numere negative? |
| Ideea | Spui cu voce tare cum ai rezolva, întâi varianta simplă. |
| Codul | Scrii funcția, de obicei într-un editor simplu, fără ajutor. |
| Testarea | O rulezi în minte (sau pe calculator) pe câteva exemple. |
| Complexitatea | Explici cât de rapidă este soluția, cu notația O(...). |
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.
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.
Cel mai scump produs din coș sau cea mai mare reducere sunt calculate exact așa.
Temperatura maximă a săptămânii este maximul unei liste de valori.
Variante ale acestei probleme (al doilea maxim, maxim fără o funcție de bibliotecă) apar des la primul interviu.
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.
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])) 