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 algoritm ce 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._

_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':http://en.wikipedia.org/wiki/Selection_algorithm#Partition-based_general_selection_algorithm 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._