Problema saptamanii - Stream (Solutie)

Cosmin Negruseri
27 iulie 2009

Am gasit problema in cartea "Introduction to Algorithms: A Creative Approach" de Udi Manber. Udi e VP of engineering la Google si daca stiti de suffix arrays, el a publicat o metoda eficienta pentru a determina LCP (longest common prefix) a doua sufixe. Cartea imi place mai mult decat Cormen-ul pentru ca partea de teorie e orientata mai mult spre intelegerea lucrurilor decat spre demonstratii matematice stufoase si pe langa asta fiecare capitol are foarte multe probleme interesante la sfarsit. Eu cred ca problemele sunt esentiale cand inveti un subiect tehnic, pentru ca intelegi bine ideile din un domeniu cand esti obligat sa le aplici in contexte diverse.

Pana sa vad cerinta din cartea respectiva credeam ca problema selectiei celor mai mici k numere din un stream se poate face doar in O(n log k) daca esti obligat sa folosesti O(k) memorie, dar citind-o mi-am dat seama ca nu e greu sa scoti o solutie in O(n) timp si O(k) spatiu. E o diferenta mare intre a sti ca o problema e rezolvabila sau nu :), de aceea munca de cercetare e foarte dura.

Cei ce au rezolvat corect problema sunt urmatorii: Stefan Istrate, Andrei Marius Teodorescu, Adrian Vladu, Marius Pungaru, Marius Buzea, Daniel Pasaila si Alexandru Mosoi.

Va dau si solutia:
Pastram un sir A in care avem cele mai mici k numere din stream pana la momentul curent. Apoi la fiecare pas citim k noi elemente din stream in sirul B. Acum in sirul C punem elementele din ambele siruri si aplicam algoritmul de gasire a medianei care are complexitate O(k), vom pastra in A elementele din C mai mici sau egale cu mediana. Astfel obtinem un algoritm de complexitate O(n) timp si O(k) spatiu.