h2. Problema 1 ( _interviu Microsoft_ )

Se dau <tex>n-1</tex> numere distincte de la <tex>1</tex> la <tex>n</tex>, sa se dea un algoritm cat mai eficient care sa determine numarul lipsa.

Se dau $n-1$ numere distincte de la $1$ la $n$, sa se dea un algoritm cat mai eficient care sa determine numarul lipsa.

h3. Rezolvare

Prima rezolvare ce ne poate veni in minte este aceea ca pentru fiecare numar de la <tex>1</tex> la <tex>n</tex> sa verificam daca numarul curent nu exista in sir prin o parcurgere. Un astfel de algoritm are complexitatea <tex>O(n^{2})</tex> si vom vedea mai departe ca putem obtine solutii mult mai bune.

Prima rezolvare ce ne poate veni in minte este aceea ca pentru fiecare numar de la $1$ la $n$ sa verificam daca numarul curent nu exista in sir prin o parcurgere. Un astfel de algoritm are complexitatea <tex>O(n^{2})</tex> si vom vedea mai departe ca putem obtine solutii mult mai bune.

O rezolvare triviala ar fi sa sortam cu metoda noastra preferata numerele si sa le parcurgem pentru a vedea cand <tex>a[i] != i</tex>. Aceasta rezolvare are complexitatea <tex>O(n \log n)</tex>.

O rezolvare triviala ar fi sa sortam cu metoda noastra preferata numerele si sa le parcurgem pentru a vedea cand $a[i] != i$. Aceasta rezolvare are complexitatea <tex>O(n \log n)</tex>.

O rezolvare mai eficienta poate fi data urmarind ideea algoritmului **Quick Sort**. Putem imparti numerele in doua multimi, una in care vom pune mumerele mai mici sau egale cu <tex>n/2</tex>, iar in cealalta numerele mai mari decat <tex>n/2</tex>. Acum vom sti daca numarul lipsa este mai mic sau egal cu <tex>n/2</tex> sau mai mare ca <tex>n/2</tex>, dupa numarul de elemente din fiecare lista. Astfel in <tex>O(n)</tex> pasi am redus problema la jumatate. Daca avem <tex>T(n)</tex> timpul de executie al acestui algoritm, atunci <tex>T(n) = T(n/2) + O(n) = O(n)</tex>. Deci algoritmul este liniar, si foloseste memorie <tex>O(n)</tex> ignorand memoria consumata de sirul de numere <tex>O(\log n)</tex> pentru stiva din algoritmul _divide et impera_.

O rezolvare mai eficienta poate fi data urmarind ideea algoritmului **Quick Sort**. Putem imparti numerele in doua multimi, una in care vom pune mumerele mai mici sau egale cu $n/2$, iar in cealalta numerele mai mari decat $n/2$. Acum vom sti daca numarul lipsa este mai mic sau egal cu $n/2$ sau mai mare ca $n/2$, dupa numarul de elemente din fiecare lista. Astfel in <tex>O(n)</tex> pasi am redus problema la jumatate. Daca avem <tex>T(n)</tex> timpul de executie al acestui algoritm, atunci <tex>T(n) = T(n/2) + O(n) = O(n)</tex>. Deci algoritmul este liniar, si foloseste memorie <tex>O(n)</tex> ignorand memoria consumata de sirul de numere <tex>O(\log n)</tex> pentru stiva din algoritmul _divide et impera_.

O alta idee este aceea de a folosi un tabel de dispersie sau un sir de valori _booleene_ care va folosi memorie suplimentara <tex>O(n)</tex>, iar daca folosim biti reducem memoria suplimentara la <tex>O(n/\log n})</tex>.

O rezolvare eleganta se foloseste de proprietatea ca suma numerelor naturale de la <tex>1</tex> la <tex>n</tex> este <tex>n(n+1)/2</tex>, iar suma numerelor o putem afla prin o parcurgere. Acum determinarea numarului lipsa se face prin scaderea din suma numerelor de la <tex>1</tex> la <tex>n</tex> a sumei numerelor noastre. Aceasta solutie are complexitatea <tex>O(n)</tex> ca timp si <tex>O(1)</tex> ca memorie folosita.

O rezolvare eleganta se foloseste de proprietatea ca suma numerelor naturale de la $1$ la $n$ este $n(n+1)/2$, iar suma numerelor o putem afla prin o parcurgere. Acum determinarea numarului lipsa se face prin scaderea din suma numerelor de la $1$ la $n$ a sumei numerelor noastre. Aceasta solutie are complexitatea <tex>O(n)</tex> ca timp si <tex>O(1)</tex> ca memorie folosita.

Daca <tex>n</tex> este destul de mare, s-ar putea ca <tex>n(n+1)/2</tex> sa depaseasca domeniul de reprezentare al intregilor de pe calculatorul nostru si ar trebui sa implementam operatii cu numere mari ca solutia anterioara sa produca rezultatul corect. O rezolvare ce nu are aceasta problema se foloseste de operatia **xor** si de proprietatile ei <tex>a \hspace{1mm} xor \hspace{1mm} a = 0</tex> si <tex>a \hspace{1mm} xor \hspace{1mm} b = b \hspace{1mm} xor \hspace{1mm} a</tex>. Vom face suma _xor_ a numerelor <tex>a[i] \hspace{1mm} xor \hspace{1mm} i</tex> cu <tex>i</tex> de la <tex>1</tex> la <tex>n</tex>:

Daca $n$ este destul de mare, s-ar putea ca $n(n+1)/2$ sa depaseasca domeniul de reprezentare al intregilor de pe calculatorul nostru si ar trebui sa implementam operatii cu numere mari ca solutia anterioara sa produca rezultatul corect. O rezolvare ce nu are aceasta problema se foloseste de operatia **xor** si de proprietatile ei <tex>a \hspace{1mm} xor \hspace{1mm} a = 0</tex> si <tex>a \hspace{1mm} xor \hspace{1mm} b = b \hspace{1mm} xor \hspace{1mm} a</tex>. Vom face suma _xor_ a numerelor <tex>a[i] \hspace{1mm} xor \hspace{1mm} i</tex> cu <tex>i</tex> de la <tex>1</tex> la <tex>n</tex>:

<tex>S = a[1] \hspace{1mm} xor \hspace{1mm} 1 \hspace{1mm} xor \hspace{1mm} a[2] \hspace{1mm} xor \hspace{1mm} 2 \hspace{1mm} xor \hspace{1mm} ... \hspace{1mm} xor \hspace{1mm} a[n] \hspace{1mm} xor \hspace{1mm} n</tex>

h2. Problema 2 ( _interviu Microsoft_ )

Se da un sir de <tex>n+1</tex> numere de la <tex>1</tex> la <tex>n</tex> in care unul se repeta, iar restul sunt distincte. Sa se dea un algoritm cat mai eficient care sa determine numarul ce se repeta.

Se da un sir de $n+1$ numere de la $1$ la $n$ in care unul se repeta, iar restul sunt distincte. Sa se dea un algoritm cat mai eficient care sa determine numarul ce se repeta.

h3. Rezolvare

h3. Rezolvare

Fie <tex>n</tex> numarul total de elemente ale listei. O solutie in <tex>O(n)</tex> timp si <tex>O(n)</tex> memorie ar fi sa parcurgem lista si sa adaugam pe rand elementele listei unui tabel de dispersie. Cand am introdus acelasi element de doua ori in lista este evident ca am gasit un ciclu. O metoda folosita de unii concurenti a fost parcurgerea listei pe o perioada de timp determinata, de exemplu timpul de executie fixat in problema. Acum sunt sanse mari ca daca nu am ajuns la capatul listei aceasta sa aiba ciclu.

Fie $n$ numarul total de elemente ale listei. O solutie in <tex>O(n)</tex> timp si <tex>O(n)</tex> memorie ar fi sa parcurgem lista si sa adaugam pe rand elementele listei unui tabel de dispersie. Cand am introdus acelasi element de doua ori in lista este evident ca am gasit un ciclu. O metoda folosita de unii concurenti a fost parcurgerea listei pe o perioada de timp determinata, de exemplu timpul de executie fixat in problema. Acum sunt sanse mari ca daca nu am ajuns la capatul listei aceasta sa aiba ciclu.

Exista un algoritm mai elegant ce foloseste memorie suplimentara <tex>O(1)</tex> si este liniar. Acest algoritm se numeste _Algoritmul lui Floyd de detectie a ciclului intr-o lista_. O aplicatie importanta a lui este _Algoritmul Pollard_ <tex>\rho</tex>, folosit pentru factorizarea intregilor cu multe cifre. Algoritmul foloseste doi pointeri <tex>a</tex> si <tex>b</tex>, unde <tex>a</tex> se misca de doua ori mai repede decat <tex>b</tex> in lista, de aceea se mai numeste si _Algoritmul iepurelui si testoasei_.

Exista un algoritm mai elegant ce foloseste memorie suplimentara <tex>O(1)</tex> si este liniar. Acest algoritm se numeste _Algoritmul lui Floyd de detectie a ciclului intr-o lista_. O aplicatie importanta a lui este _Algoritmul Pollard_ <tex>\rho</tex>, folosit pentru factorizarea intregilor cu multe cifre. Algoritmul foloseste doi pointeri $a$ si $b$, unde $a$ se misca de doua ori mai repede decat $b$ in lista, de aceea se mai numeste si _Algoritmul iepurelui si testoasei_.

Reprezentarea grafica seamana cu litera greceasca <tex>\rho</tex>. Notam lungimea lantului cu <tex>\lambda</tex> si lungimea ciclului cu <tex>\mu</tex>.

cat timp (a!=b)
==

Cand <tex>a</tex> si <tex>b</tex> sunt amandoi in ciclu, <tex>a</tex> il va ajunge din nou pe <tex>b</tex>. Puteti vedea exact cum prin analiza cazurilor in care lungimea ciclului e para sau impara. In exemplul desenat, dupa sase iteratii cei doi pointeri vor indica acelasi element.

Cand $a$ si $b$ sunt amandoi in ciclu, $a$ il va ajunge din nou pe $b$. Puteti vedea exact cum prin analiza cazurilor in care lungimea ciclului e para sau impara. In exemplul desenat, dupa sase iteratii cei doi pointeri vor indica acelasi element.

Pentru determinarea lungimii ciclului se mai poate face o parcurgere in care doar un pointer se misca. Acum dupa ce stim lungimea <tex>\mu</tex> a ciclului putem afla si lungimea <tex>\lambda</tex> a lantului astfel: luam un pointer la inceputul listei si al doilea care a facut deja <tex>\mu</tex> pasi in lista. Acum ii miscam pe cei doi cu aceeasi viteza. Dupa <tex>\lambda</tex> pasi cei doi pointeri vor fi egali. Astfel am obtinut o rezolvare liniara.

 
h2. Problema 4 ( _IBM Research: Ponder This_ )
 
Un sir ce poate fi numai citit, 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.
 
h3. Rezolvare
 
Aici nu merge solutia cu suma _xor_ de la problemele $1$ si $2$ pentru ca numerele pot fi repetate oricum si nu putem folosi relatiile obtinute cu ajutorul lor pentru a determina un numar care se repeta.
Daca toate elementele din sir ar fi distincte, atunci sirul ar avea structura unei permutari. Cum ele nu sunt neaparat distincte ne vine ideea de a vedea care este diferenta intre un asemenea sir si o permutare. Astfel vom folosi idei care apar la permutari, cum ar fi ciclurile permutarilor. Fiecare element din sirul nostru indica inspre altul, deci ne putem gandi la sirul nostru ca un graf orientat in care arcele sunt $(i, a[i])$. De exemplu putem face urmatoarea reprezentare pentru sirul $3, 2, 1, 3, 4$: