Danas sam na poslu dobio pitalicu zagonetku, sto je ustvari sa Google interview-a, pa me interesuje koliko bi vas uspjelo rijesiti ovaj problem: Provjeriti da li zadati string (koji unosi korisnik ) ima u sebi dva ista znaka u n vremenu ili O(n). Za one koji ne znaju O(n) znaci ugrubo da ne smijete koristiti ugnijezdene petlje. Sretno!
Jedino što mi pada na pamet je da za svaki char u stringu kreira dictionary item kome će taj char biti key value (ili neki ekvivalent, govorim o C#). Za svaki znak provjeriti da li već postoji unos pod tim ključem.
Mozes tako isto u Hashset u Javi i vrati ti index ako postoji taj sto ubacujes. Ali ne garantuje ti da je insert u dictionary ili hashset slozenosti O(1), tako da nije O(n) ukupno. Postoji opcija da kreiras niz integera velicine max velicine char tipa (npr.256) i inicijaliziras ih sa nekom negativnom vrijednosti. Onda prolazis kroz string i ascii vrijednosti karaktera koristis kao index gornjeg niza i stavljas neku vrijednost. Ako je vec postavljena onda izlazis iz petlje. To je kao slozenost O(n).
Mah, uletio bi... Zamalo ne rekoh Radile se nekad ove "zagonetke" pa se pokupi fazona, pogotovo u C-u naucis.