Am gasit problema in cartea "Introduction to Algorithms: A Creative Approach" de Udi Manber. Udi e VP of engineering la Google si daca stiti de suffix arrays, Udi a publicat cum se poate face eficient operatia de LCP (longest common prefix). Cartea imi place mai mult decat Cormen-ul pentru ca partea de teorie e orientata mai mult spre intelegerea lucrurilor decat spre demonstratii matematice stufoase si pe langa asta fiecare capitol are foarte multe probleme interesante la sfarsit. Eu cred ca problemele sunt esentiale cand inveti un subiect tehnic, pentru ca intelegi bine ideile din un domeniu cand esti obligat sa le aplici in contexte diverse.

Am gasit problema in cartea "Introduction to Algorithms: A Creative Approach" de Udi Manber. Udi e VP of engineering la Google si daca stiti de suffix arrays, el a publicat o metoda eficienta pentru a determina LCP (longest common prefix) a doua sufixe. Cartea imi place mai mult decat Cormen-ul pentru ca partea de teorie e orientata mai mult spre intelegerea lucrurilor decat spre demonstratii matematice stufoase si pe langa asta fiecare capitol are foarte multe probleme interesante la sfarsit. Eu cred ca problemele sunt esentiale cand inveti un subiect tehnic, pentru ca intelegi bine ideile din un domeniu cand esti obligat sa le aplici in contexte diverse.

Pana sa vad cerinta din cartea respectiva credeam ca problema selectiei celor mai mici k numere din un stream se poate face doar in O(n log k) daca esti obligat sa folosesti O(k) memorie, dar citind-o mi-am dat seama ca nu e greu sa scoti o solutie in O(n) timp si O(k) spatiu. E o diferenta mare intre a sti ca o problema e rezolvabila sau nu :), de aceea munca de cercetare e foarte dura.