Hero Image
- Mihai Surdeanu

Problema albumelor foto

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:
poza1

Pe baza celor 2 albume, mama va crea un alt album, cu următoarea configurație a pozelor:
poza2

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:
poza3

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:

  1. Î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ă.
  2. 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.
  3. Î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.
  4. În următorul pas, vom compara 13 cu 14. Extragem 13.
  5. Ș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!

Related Posts:

Bugurile și viața unui programator

Bugurile și viața unui programator

Cel mai trist lucru din viața unui programator: bugurile. Culmea este faptul că acestea sunt create tot de el. Fiecare programator, ar vrea să dezvolte numai feature-uri. Nimănui nu îi place să investigheze un bug sau să ofere mentenanță unei aplicații. Toate lumea vrea să dezvolte ceva de la zero!

2nd Apr 2020 - Mihai Surdeanu
Algoritm pentru determinarea celui mai sigur loc pentru a viziona un film pe timp de Covid

Algoritm pentru determinarea celui mai sigur loc pentru a viziona un film pe timp de Covid

Dragilor,

Revin astăzi cu o nouă problemă, de actualitate pentru vremurile în care trăim noi acum. Să zicem să vreau să mă duc la cinematograf, în vreme de pandemie, pentru a viziona un film și am bilet pe un anumit rând. Nu aș vrea totuși să stau pe locul care mi s-a oferit, ci aș vrea să îmi determin singur locul pe rând unde aș vrea să stau în așa fel încât să fie cât mai safe pentru mine. Ce înseamnă cât mai safe pentru mine, înseamnă să stau cât mai departe de cineva atât în partea stangă cât și în partea dreaptă.

17th Jan 2022 - Mihai Surdeanu

Comments:

Blog Comments powered by Disqus.