infoarena

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

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

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.

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

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.

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

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! :)

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.

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;
   
}

da, e corect, dar practic e exact ce a zis mishu inainte. :eyebrow:
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  :D)

Da ai dreptate.

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