Am aflat problema anul trecut de la Mihai Patrascu, ea e pe stilul multor intrebari din interviuri de joburi de programare. Ea 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-o

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-o

*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.

Problema a fost studiata recent.

{'Finding duplicates in a data stream, P Gopalan, J Radhakrishnan - … of the Nineteenth Annual ACM-SIAM …, 2009':'http://www.cadmo.ethz.ch/education/lectures/FS09/RA_PM/duplicates_datastream.pdf'}Aici se arata un algoritm randomizat ce foloseste o parcurgere si O(log^3(n)) memorie.

{'Finding duplicates in a data stream, P Gopalan, J Radhakrishnan - … of the Nineteenth Annual ACM-SIAM …, 2009':'http://www.cadmo.ethz.ch/education/lectures/FS09/RA_PM/duplicates_datastream.pdf'} Aici se arata un algoritm randomizat ce foloseste o parcurgere si O(log^3(n)) memorie.

{'Finding a duplicate and a missing item in a stream
J Tarui - Proceedings of the 4th international conference on …, 2007':'http://www.jtlab.ice.uec.ac.jp/~tarui/tarui-tamc07.pdf'} Aici se demonstreaza ca pentru algoritmi deterministi la k parcurgeri trebuie folosita cel putin O(n^(1/(2k - 1)) spatiu, iar pentru algoritmi ce folosesc doar O(log n) spatiu e nevoie de cel putin O(log n/log log n) parcurgeri.