_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)._

Din nou parcurgem sirul dar in loc sa adaugam fiecare element, vom adauga Sum[i], suma cumulata a elementelor de la 1 la i Sum[i] = sum(A[1..i]) in structura noastra de date. Acum la fiecare element curent cautam daca exista vreun j astfel ca Sum[j] == S - Sum[i].

Din nou parcurgem sirul dar in loc sa adaugam fiecare element, vom adauga Sum[i], suma cumulata a elementelor de la 1 la i Sum[i] = sum(A[1..i]) in structura noastra de date. Acum la fiecare element curent cautam daca exista vreun j astfel ca Sum[j] == Sum[i] - S.

_3. (Microsoft, algoritmiada) 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)._

Foarte similar cu ideea din problema anterioara. La cand coboram pe o muchie adaugam in arbore valoarea drumului de la radacina pana la nodul curent, iar cand urcam o stergem.

Foarte similar cu ideea din problema anterioara. Cand coboram pe o muchie adaugam in arbore valoarea drumului de la radacina pana la nodul curent, iar cand urcam o stergem.

_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)._

private

protected