Problema duplicate a fost abordabila, fiind rezolvata de 16 cititori. Am aflat-o de la Mihai Patrascu.

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

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

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

*Probleme inrudite:*
Pentru probleme pe acelasi stil cu nivel de dificultate bun pentru interviuri tehnice pentru programatori puteti citi articolul {'Probleme cu numere lipsa si nu numai':missing-numbers}. Doua exemple:

2. Se dau n numere de la 1 la n. Unul din ele unul apare de doua ori in sir, iar restul sunt distincte. Evident ca un numar nu va aparea niciodata. Sa se dea un algoritm cat mai eficient care sa determine numarul lipsa si numarul ce apare de doua ori.

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