Astăzi vom încerca să prezentăm și să rezolvăm împreună problema albumele foto.
O familie formată din doi părinți au doi copii. Fiecare din cei doi copii este stabilit într-o țară diferită față de cea unde trăiesc părinții și totodată diferită față de cea a celuilalt frate.
Familia se vede foarte rar, motiv pentru care mama copiilor se cere acestora ca fiecare copil în parte să le trimită un album foto cu ei. Fiecare copil în parte, trimite prin poștă un album foto în care toate pozele prezente acolo sunt ordonate după momentul în care pozele au fost făcute. Cu alte cuvinte, este un album foto de tip timeline.
După ce a primit ambele albume, mama dorește să creeze unul singur din ele, dar ar vrea ca pozele să fie în continuare ordonate după momentul în care au fost făcute. Ajutați-o să definească un algoritm prin care să realizeze ceea ce își dorește. Algoritmul trebuie să fie cât mai rapid din perspectiva timpului de execuție.
Iată și un exemplu concret
Pentru simplitate, vom considera că fiecare copil în parte, trimite un album foto cu doar 3 poze:
Pe baza celor 2 albume, mama va crea un alt album, cu următoarea configurație a pozelor:
La ce rezumă problema?
La o primă vedere, un album foto nu este altceva decât o listă ordonată de poze după un timestamp. Pentru simplitate, acest timestamp poate reprezenta numărul de zile care au trecut de la 1 decembrie 2021. În altă ordine de idei, ceea ce ni se cere de fapt este să conbinăm două liste deja ordonate, în așa fel încât ordinea să se mențină. Plus de asta, ne dorim ca algoritmul implementat să fie cât mai optim din perspectiva timpului de execuție.
Fără să ne focusăm încă asupra implementării, putem să ne gândim puțin la ceea ce înseamnă complexitatea algoritmului nostru. Pentru că rezultatul final îl va reprezenta o altă listă cu toate elementele listelor inițiale combinate, ne dăm seamă cu certitudine că vom avea cel puțin o complexitate liniară. În cel mai bun caz, va trebui să iterăm peste toate elementele listelor inițiale pentru a le pune în noua listă. Astfel, dacă vom obține un algoritm liniar și cu complexitate O(1) spațială, adică fără structuri interne de date de timpul Map, List, Set etc, va fi perfect.
Descrierea algoritmului
Am zis că vom codifica data fiecărei poze ca fiind numărul de zile trecute de la 1 decembrie 2021. Dacă doriți express, se poate codifica și ca fiind numărul de zile trecute de la 1 ianuarie 1970 - epoch time.
Cum vor arăta cele două liste interne:
Ca să putem obține o complexitate liniară de timp, va trebui cumva să iterăm în același timp peste ambele liste și la fiecare moment de timp să selectăm elementul cel mai mic (adică poza cea mai veche).
Iată cum ar fi acest algoritm:
- Într-o structură repetitivă mergem până când am finalizat atât elementele din prima listă cât și pe cele din a doua listă.
- Primul pas este să comparăm primul element din prima lista cu primul element din a doua. Cu alte cuvinte 10 cu 11. Cum 10 e mai mic decât 11, primul element extras va fi 10. Incrementul pointerul aferent listei de la care am extras un element.
- În următorul pas vom compara elementul 11 cu elementul 14. 11 e mai mic decât 14, deci vom selecta 11. Incrementăm pointerul aferent celei de-a doua liste.
- În următorul pas, vom compara 13 cu 14. Extragem 13.
- Și tot așa până când am ajuns la capătul ambelor liste. Pentru simplitate putem să considerăm că cele două liste inițiale sunt LinkedList și ajungem la capăt când next element în listă e null.
O dată ce algoritmul este clar pe hârtie, implementarea sa este straightforward. De această dată, las implementarea la latitudinea cititorului.
Dacă notăm cu s1 dimensiunea primei liste și cu s2 dimensiunea celei de-a doua liste, vom obține o complexitate de timp de: O(s1 + s2).
Happy coding!
