Am aflat problema anul trecut de la Mihai Patrascu. Ea e pe stilul multor intrebari din interviuri de joburi de programare. Are aplicatii in multe contexte cum ar fi in baze de date unde vrem sa detectam duplicate, pentru motoare de cautare unde vrem sa detectam pagini duplicate in index, la monitorizarea traficului pe retele unde se incearca detectarea de anomalii. Ea a fost abordabila, fiind rezolvata de 16 cititori.

Am aflat problema anul trecut de la Mihai Patrascu. Ea e pe stilul multor intrebari din interviuri de joburi de programare. Are aplicatii in multe contexte cum ar fi in baze de date unde vrem sa detectam obiecte duplicate, pentru motoare de cautare unde vrem sa detectam pagini ce se repeta in index sau la monitorizarea traficului pe retele unde se incearca detectarea de anomalii. Ea a fost abordabila, fiind solutionata de 16 cititori.

*Rezolvitori:*
Dumitru Daniliuc, Andrei Grigorean, Tiberiu Savin, Andrei Dragus, Alex Mosoi, Marius Pungaru, Adrian Vladu, Marius Andrei, Daniel Dumitran, Marius Dragus, Andrei Marius Teodorescu, Laura Draghici, Delia David, Adrian Airinei, Armand Rotaru si Stefan Istrate.
*Solutie:*

Fie x = [sqrt n]. Timem un sir de x pozitii F[i] cu frecventele elementelor pe intervalul [i * x + 1, (i + 1) * x]. Din principiul lui Dirichet rezulta ca un interval va avea mai mult de x elemente in el. Prin o parcurgere al sirului aflam un astfel de interval. Cu o a doua parcurgere aflam frecventele exacte ale elementelor din intervalul respectiv folosind un sir de dimensiune x. Am determinat astfel un element duplicat folosind doua parcurgeri si memorie O(sqrt(n) log n) biti.

Fie x = [sqrt n]. Tinem un sir de x pozitii F[i] cu frecventele elementelor pe intervalul [i * x + 1, (i + 1) * x]. Din principiul cutiei rezulta ca un interval va avea mai mult de x elemente in el. Prin o parcurgere al sirului aflam un astfel de interval. Cu o a doua parcurgere aflam frecventele exacte ale elementelor din intervalul respectiv folosind un sir de dimensiune x. Am determinat astfel un element duplicat folosind doua parcurgeri si memorie O(sqrt(n) log n) biti.

Daca facem k parcurgeri putem folosi memorie O(n^(1/k) * log n) biti.