Problema saptamanii Duplicate - Solutie

Cosmin Negruseri
20 august 2010

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

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. Doua exemple:

1. Un sir de lungime n contine numere intregi din multimea {1, 2, ..., n-1}. Folosind Principiul lui Dirichlet deducem ca cel putin un element se repeta. Gasiti un algoritm liniar care afiseaza o valoare ce se repeta, folosind memorie suplimentara constanta si nemodificand la nici un pas vreun element din sir.

2. Se dau n numere de la 1 la n. Unul din ele apare in sir de doua ori, 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 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 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.