Google interview pitalica

Discussion in 'Operativni sistemi, aplikacije i programiranje' started by Shibby, Nov 18, 2014.

  1. Shibby

    Shibby Aktivista

    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!
     
  2. mirseth

    mirseth Aktivista

    Jel neko ovo rijesio ??
     
  3. Ninja

    Ninja Komšija

    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.
     
  4. selvin

    selvin Moderator

    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).
     
  5. Ninja

    Ninja Komšija

    U pravu si. Tvoj primjer je sigurniji.
     
  6. Shibby

    Shibby Aktivista

    Svaka cast selvine, mozda bi i uletio u google :D
     
  7. selvin

    selvin Moderator

    Mah, uletio bi... Zamalo ne rekoh :D Radile se nekad ove "zagonetke" pa se pokupi fazona, pogotovo u C-u naucis.