Cateva probleme care apar prin cartile de algoritmica, majoritatea folosite frecvent in interviuri:
1. (Amazon) Se da un sir de n elemente intregi. Se cere sa se determine doi intregi din sir a, b astfel ca a + b = X. Complexitate O(n).
_1. (Amazon) Se da un sir A de n elemente intregi. Sa se determine doi intregi din sir a, b astfel ca a + b = X. Complexitate O(n)._
2. (Google, Facebook) Se da un sir de n elemente intregi. Se cere sa se determine o subsecventa a sirului care are suma elementelor egala cu X. Complexitate O(n).
_2. (Google, Facebook) Se da un sir A de n elemente intregi. Se cere sa se determine o subsecventa a sirului care are suma elementelor egala cu X. Complexitate O(n)._
3. (Microsoft, 'algoritmiada':problema/arbore3) Se da un arbore cu radacina ce are costuri intregi pe muchii. Se cere sa se determine un drum ce merge in jos in arbore care are suma costurilor muchiilor egala cu X. Complexitate O(n).
_3. (Microsoft, 'algoritmiada':problema/arbore3) Se da un arbore T de n noduri ce are costuri intregi pe muchii. Sa se determine un drum ce merge in jos in arbore care are suma costurilor muchiilor egala cu X. Complexitate O(n)._
4. Se da un arbore, sa se determine un nod care, atunci cand este eliminat rupe arborele in componente conexe in care fiecare are mai putin de n/2 din noduri. Complexitate O(n).
_4. (CLRS) Se da un arbore T de n noduri. Sa se determine un nod pentru care stegerea din graf genereaza componente conexe cu dimensiuni mai mici de n/2 noduri. Complexitate O(n)._
Problema Race de la olimpiada internationala de informatica de anul asta are urmatoarea cerinta:
Danduse un arbore ce are costuri intregi pentru muchii, sa se gaseasca un drum cu numar minim de muchii care are suma costurilor S. Complexitatea solutiei trebuie sa fie mai buna de O(n^2).
_Dandu-se un arbore ce are costuri intregi pentru muchii, sa se gaseasca un drum cu numar minim de muchii care are suma costurilor S. Complexitate mai buna de O(n^2)._
Rezolvarea ei consta in combinarea ideilor de la cele patru probleme de mai sus. Romanii au luat 100, 21 si 43 de puncte la problema asta, mai trebuie sa se antreneze un pic pt Silicon Valley, dar nu sunt prea departe :).
Rezolvarea problemei consta in combinarea ideilor celor patru probleme de mai sus. Romanii au luat 100, 21 si 43 de puncte pe ea in concurs.
Mai trebuie sa se antreneze un pic pentru Silicon Valley, dar nu sunt departe :).
Voi cate din cele 5 le stiti rezolva?
