SQL query - rezolvare

Cosmin Negruseri
07 iunie 2011

Asa cum ati vazut si in comentarii problema admite o rezolvare simpla si eleganta cunoscuta sub numele de nested set model

Facem o parcurgere dfs a structurii ierarhice si asociem fiecarui nod v doua numere start[v] si end[v] care ne spun la ce moment a intrat parcurgerea in nodul v respectiv la ce moment parcurgerea a terminat cu toti fii nodului v si iese din acest nod.

Astfel pentru a vedea ca nodul v e subordonat unui nod u e suficient sa testam daca start[u] < start[v] si end[v] < end[u].

Voi ce probleme interesante de interviu stiti?