SQL query - rezolvare

[•Cosmin]

Comentarii la postul http://infoarena.ro/blog/sql-query-rezolvare

[•devilkind]

Pe oracle exista o chestie, ma rog, total ineficienta, insa exista si e bine de stiut pentru alte cazuri . Poti sa folosesti comenzile START WITH si CONNECT BY PRIOR parent.column = children.column si iti va da un tabel cu parcurgerea in adancime a arborelui determinat de relatia din CONNECT BY si radacina data de START WITH.

Exemplu

Cod:

SELECT employee.id
FROM employees
START WITH employee.id = "id"
CONNECT BY PRIOR employee.id = employee.manager_id

Si asta o sa iti dea un tabel cu toti subordonatii angajatului cu id-ul "id". Din pacate nu am reusit sa gasesc un echivalent pentru Mysql.

[•dbaluta]

Problema de interviu (posibil clasică): Cum putem determina minimul și maximul dintr-un șir de N elemente folosind cel mult 3N/2 comparații.

[•adelcosma]

Se dau doi vectori de numere naturale a si b. a are dimensiunea n+m si n elemente, iar b are dimensiunea m si m elemente. Sa se interclaseze cei doi vectori.

[•adelcosma]

Am uitat sa spun ca vectorii sunt ordonati si ca dupa interclasare trebuie sa se obtina un vector, evident, ordonat.

[•pauldb]

Daca cunoasteti probleme interesante care credeti ca se potrivesc pentru "problema saptamanii", puteti sa le trimiteti la adresa: [email protected] si pe cele mai interesante le vom publica pe blog!

[•Mishu91]

La problema cu minimul si maximul din 3N/2 comparatii ma gandesc la ceva de genul: Parcurg sirul din 2 in 2 elemente, iar la fiecare pas se pot afla minimul si maximul dintre elementul curent si cel imediat urmator dintr-o singura comparatie, si din inca 2 comparatii putem vedea daca minimul este mai mic decat minimul global, si daca maximul este mai mare decat maximul global. Deci la fiecare pas se fac 3 comparatii, si cum in total sunt N/2 pasi => in total se fac 3N/2 comparatii.

[•yonatan]

La problema cu minimul si maximul nu ar merge si o solutie recursiva gen:
Comparam elementele vecine 2 cate 2 => N/2 comparatii, N/2 maxime, N/2 minime
Comparam maximele, si minimele din fiecare perechi 2 cate 2=> N/4+N/4=N/2 comparatii si raman N/4 maxime si N/4 minime
Comparam din nou maximele si minimele din fiecare cvadrupluri=> N/8 comparatii la maxime + N/8 la minime=N/4 camparatii si raman N/8 maxime si N/8 minime
Comparam grupurile de maximele si minimele din grupurile de cate 8=>N/16 +N/16 = N/8 comparatii si raman N/16 maxime si N/16 minime si tot asa.
Ar veni N/2+N/2+(N/4+N/8+N/16+...+1)=3N/2

pair functie(int st,int dr)
{
   pair ret;
   if(st==dr)
   { ret.min=a[st];
     ret.max=a[st];
   }
   else
   {m=(st+dr)/2;
   pair pst=functie(st,m);
   pair pdr=functie(m+1,dr);
   
   ret.min=min(pst.min,pdr.min);
   ret.max=max(pst.max,pdr.max);}
   
   return ret;
   
}

[•Magnus]

da, e corect, dar practic e exact ce a zis mishu inainte.
tu faci asa cum a zis el pana la faza cu n/2 maxime si n/2 minime.
dupa asta in n/2 operatii afli care e maximul dintre cele n/2 maxime si minimul din cele n/2 minime (in loc sa iei numerele la rand tu le iei mai complicat  )

[•yonatan]

Da ai dreptate.

Eu asa am gandit, nu stiu daca este mai complicat dar asta mi-a venit in minte.