Problema saptamanii - Interclasare

[•Cosmin]

Aici puteti comenta la http://infoarena.ro/blog/problema-saptamanii-interclasare

[•Mishu91]

Cam ce complexitate trebuie mai exact, pentru că se poate face un heapsort care are complexitatea O(NlogN), în cazul de față O((N+M)log(N+M)), complexitate mai bună decât O(N^2).

[•stef2n]

Heapsort nu e stabil.

[•Mishu91]

Poți da un exemplu la partea cu stabilitatea, că nu mă prea prind ce vrea defapt.

[•klamathix]

Totusi eu stiam ca o sortare stabila presupune ca ordinea relativa a elementelor egale sa ramana aceeasi, adica exact invers fata de ce scrie in cerinta.

M-am verificat si cu wikipedia : Stability

Stable sorting algorithms maintain the relative order of records with equal keys.

Probabil este o neintelegere la mijloc, cum e pana la urma?

[•stef2n]

@klamathix: Da, se pare că era o greșeală în enunț și era pe dos. Am schimbat acum.

@Mishu91: Pentru o secvență

Cod:

1 2 3 4 2 5

după ce a fost sortată va deveni

Cod:

1 2 2 3 4 5

Algoritmul trebuie să garanteze că primul 2 este cel din secvența inițială aflat pe o poziție mai mică. Practic, în caz de egalitate a valorilor, trebuie să ții cont de poziția în șirul inițial.

[•gorgovan]

Dar o interclasare in O(n+m) ca la Merge sort nu merge ?
Si o putea face si stabila daca este nevoie.
Daca tinem un vector cu primele n si unul cu ultimele m.Si doi indici initial 1.
Cand avem valoare mai mica in primul vector, punem valoare in vectorul solutie si ii marim indicele.
Cand avem valoare mai mare in primul vector, punem valoarea din vectorul al doilea in solutie si ii marim indicele.
Iar cand avem valori egale prioritate are valoarea din primul vector.
Si facem asta cat timp nu am ajuns la sfarsitul unuia din vectori, dupa care punem elementele ramase in celalalat vector in solutie.
LE:am vazut ca trebuie memorie suplimentara O(1)

[•Mishu91]

Dar la heapsort, în momentul în care se (re)face heapul, se poate face ca în cazul în care două elemente sunt egale, cel cu poziția minimă să fie mai "sus".

[•mlazari]

Dacă sunt mai mult de log₂(n+m) elemente egale va trebui oricum să pui 2 elemente egale pe acelaşi nivel în heap, nu?

[•Mishu91]

Dacă sunt mai mult de log₂(n+m) elemente egale va trebui oricum să pui 2 elemente egale pe acelaşi nivel în heap, nu?

Da, dar oricum contează doar "vârful". Iar atunci când refaci heapul verifici să îl muți în vârf pe cel de poziție minimă.

[•devilkind]

@Mishu: Tre sa ai memorie auxiliara O(1). Probabil ca poti sa faci intr-un fel sa tii heapul in vectorul in care tii numerele dar nu sunt sigur ca ramane aceeasi complexitate.

[•Bogdan_tmm]

Ca sa faci heap sortul stabil trebuie sa retii si pozitiile pentru fiecare nod, deci ai o(n) memorie suplimentara. Probabil e alta idee.
LE: sau bagam un stable_sort

Stable_sort is an adaptive algorithm: it attempts to allocate a temporary memory buffer, and its run-time complexity depends on how much memory is available. Worst-case behavior (if no auxiliary memory is available) is N (log N)^2 comparisons, where N is last - first, and best case (if a large enough auxiliary memory buffer is available) is N (log N)

sau

Inplace_merge is an adaptive algorithm: it attempts to allocate a temporary memory buffer, and its run-time complexity depends on how much memory is available. Inplace_merge performs no comparisons if [first, last) is an empty range. Otherwise, worst-case behavior (if no auxiliary memory is available) is O(N log(N)), where N is last - first, and best case (if a large enough auxiliary memory buffer is available) is at most (last - first) - 1 comparisons.

Implementarile sunt in headerul algorithm.

[•MciprianM]

Eu sunt curios ce asteapta angajatorii de la tine cand iti dau o asemenea problema. Eu vad doua variante: ori stii de dinainte problema ori gasesti solutia in 10-15 minute(pb de interviu). A doua varianta mi se pare prea putin probabila pentru cea mai mare parte a angajatilor. Chiar si pe un site pentru olimpici cred ca s-au gasit putini rezolvitori. Asa ca nu cred ca oamenii astia care fac angajarile cauta sa le dai raspunsul. Dar ce asteapta de la tine? Daca sunt persoane informate, le rog sa raspunda. Daca sunt offtopic, imi cer scuze.

[•devilkind]

Vor sa vada cum abordezi problema, cam asta se urmareste cu astfel de intrebari.
Uite aici un link interesant despre cum sa abordezi un interviu http://steve-yegge.blogspot.com/2008/03/get-that-job-at-google.html . Am citit destul de multe chestii de genu asta cand aveam interviuri pentru internship si am citit niste chestii destul de interesante insa nu mai stiu daca in articolu pe care ti l-am dat am gasit ca daca iti pune o intrebare pe care o stii, sa nu dai raspunsul direct, sa mai stai oleaca sa te gandesti, sa incerci sa faci pasi necesari pentru a ajunge la solutie (sa nu para ca o stiai dinainte si ca ai scos-o pe moment).
Stiu ca ptr interviurile la google citisem ca ei nu vor sa vada cat de multe chestii stii, ci cum abordezi o problema pe care nu ai mai intalnit-o.

[•Cosmin]

@Tarca Bogdan: Problema e veche, deci sunt sigur ca gasesti pe net idei de a o rezolva, ideea la problemele saptamanii e sa incerci sa le rezolvi singur. Pe langa asta solutia ta are o problema pe care o sa ti-o zic cand public solutia oficiala.

@Marginean Ciprian:
In timpul interviului mai primesti hinturi, deci chiar daca problema e grea poti sa discuti in jurul ei si sa vezi cum gandeste omul.
La o asemenea problema poti vedea daca candidatul poate analiza complexitatile de timp si memorie a algoritmilor si daca poate aplica idei de la diversele metode de sortare invatate in liceu si facultate in un context putin diferit, sau sa se prinda de ce unele metode nu merg. De exemplu ca nu poate folosi merge sort pentru ca foloseste O(n) memorie suplimentara sau ca heap sortul si quick sortul nu folosesc atata memorie dar nu sunt algoritmi stabili.

Daca folosesc in 5-10 interviuri, imi dau seama pentru un nou om ce intervieveaza care e viteza medie prin care trece un inginer bun prin problema asta si care sunt punctele in care se blocheaza.
Am mai discutat intrebarea cu colegi de la Google si multi au rezolvat-o fara a avea nevoie de ajutor.

Poate e la limita pentru a fi folosita in un interviu daca vrei sa testezi si alte chestii nu doar algoritmi, dar daca cineva are in CV ca a fost la concursuri de programare nu o sa ii dau ceva simplu ca o parcurgere pe arbore ci ceva care sa il faca sa gandeasca putin.

@Savin Tiberiu
Am mai avut in interviuri oameni care era destul de clar ca auzisera problema inainte dar daca schimbai putin restrictiile sau intrai in detalii mai adanc se blocau. Eu as sugera oricui sa zica ca a vazut ceva similar inainte, in loc sa triseze. Daca esti prins ti se respinge aplicatia la job din cauza ca nu ai principii morale bune.

[•ishisushi]

Poate un Shell Sort ar merge, folosind niste incrementi in functie de n si m. Asta mi-a venit prima data in minte, nu stiu ce sa zic, trebuie sa ma gandesc mai mult in ce fel sa se considere incrementii aceia. Cred ca ar respecta cerinta de a avea mai putin de O(n^2).

[•Cosmin]

Shell sort nu cred ca e sortare stabila.

[•ishisushi]

oh, chiar nu e!   

[•R.A.R]

Retinem in 2 vectori numerele ( in primul retinem primele n ) iar apoi pt fiecare element din V1 cautam binar pozitia pe care il putem plasa in V2( dupa ce il plasam in V2 in stergem din V1).Complexitatea este  N log₂M  insa memoria folosita se incradreaza ?

[•devilkind]

1. Nu se incadreaza memoria. Din moment ce la sfarsit vrei sa adaugi toate elementele in V1 inseamna ca V1 are N + M elemente iar V2 are M elemente deci ai O(M) memorie suplimentara.
2. Complexitatea ta e N^2 log N nu N log N deoarece nu poti insera un element in mijlocul unui vector (chiar daca ii stii pozitia) in O(1). Iar daca tii liste inlatuite unde poti sa adaugi la mijloc in O(1) nu mai poti sa faci cautarea binara.

[•mlazari]

Cred că oricum nu poţi să foloseşti liste înlănţuite pentru că trebuie să păstrezi pentru fiecare element adresa următorului şi/sau precedentului, deci nu va mai fi memorie suplimentară constantă.

[•toni2007]

Daca ti un treap se considera memorie suplimentara ?

[•Cosmin]

Daca tii un trip cu 10 elemente e ok, daca tii mai mult de O(1) elemente nu mai e ok.

[•wefgef]

Incercati sa gasiti o idee interesanta, nu sa adaptati algoritmi de sortare stiuti dinainte.

[•toni2007]

Pot tine sirul ca lista dublu inlantuita ?