Găleți care dau pe din afară
Scris de Denis Nuțiu
- 2 minute de citit
- 1 exemplu de cod în Python
- 1 imagine
Disponibil și în English
Salut tuturor 👋,
Astăzi vreau să vă împărtășesc o problemă pe care am întâlnit-o pe drumul meu.
Problema este destul de simplă:
- Ai un număr finit de unități de apă.
- Ai un număr finit de găleți.
- Trebuie să distribui unitățile de apă în găleți.
- Fiecare găleată are o capacitate maximă.
- Când o găleată este plină, apa se revarsă în următoarele două găleți, împărțindu-se egal.
- Trebuie să afișezi numărul găleților care sunt pline.
Următoarea diagramă ilustrează problema:
Dacă vrei să încerci să rezolvi problema singur, te rog oprește-te din citit aici. Și încearcă 😄.
Am avut această problemă la un interviu tehnic pe tablă și nu am reușit să o rezolv, pentru că în timp ce scriam clasa, intervievatorul m-a îndrumat către o altă direcție și asta mi-a derutat gândirea. Sunt un mare fan al designului orientat pe obiecte.
Timpul meu era limitat pentru că enunțul problemei era foarte vag, iar cea mai mare parte a timpului am încercat să îmi dau seama ce trebuie să rezolv.
Oricum, sper că veți avea mai mult noroc la interviurile tehnice pe tablă și sper să ajungeți să le faceți în IDE-ul vostru. Nu am avut nicio problemă să trec testele de programare Toptal când mi-au permis să le fac în IDE-ul meu.
Ciclul de feedback Run, Evaluate, Improve este foarte important pentru mine ca programator. Lucrez zilnic în IDE scriind
sute de linii de cod, așa că, brusc, să primesc o problemă de rezolvat pe hârtie mă derutează.
Chiar și în proiecte complexe, când vreau să îmi testez ideea, scriu un test unitar simplu. Acest lucru este posibil doar dacă proiectul este structurat bine și codul este proiectat pentru testare unitară. Dacă vrei să înveți mai multe despre testarea unitară, nu pot recomanda suficient această carte: Growing Object-Oriented Software, Guided by Tests
Mai jos poți găsi soluția mea în Python pentru problemă.
import dataclasses@dataclasses.dataclassclass Bucket: id: int left: "Bucket" = None right: "Bucket" = None current_capacity: float = 0 max_capacity: int = 10 def fill(self, unit: float): if self.current_capacity < self.max_capacity: self.current_capacity += unit return unit else: units_needed = 0 if self.right: units_needed += self.right.fill(unit / 2) if self.left: units_needed += self.left.fill(unit / 2) return units_needed def print_bucket(self): print(f"Bucket: #{self.id} has capacity {self.current_capacity}") if self.left: self.left.print_bucket() if self.right: self.right.print_bucket()if __name__ == '__main__': b5 = Bucket(5, left=Bucket(7)) root = Bucket(1, left=Bucket(2, left=Bucket(4), right=b5), right=Bucket(3, left=b5, right=Bucket(6))) root.print_bucket() print("=====================") number_of_units = 51 while number_of_units > 0: units_used = root.fill(1) if units_used == 0: break number_of_units -= units_used root.print_bucket()Desigur, soluția mea nu este perfectă, dar dacă ai sugestii, te rog să mi le spui.
Sper că ți-a plăcut acest articol și ne vedem în următorul!
Mulțumesc că ai citit! 📚