28 martie 2015

E limba chineza!!


La Politehnica (Bucuresti) se invata chineza...

Asa cum prevestea un profesor de matematica de la Automatica (cred ca O. Stanasila era), o sa ajungem sa invatam chineza. 
Gata cu engleza, franceza, limbi depasite. Chineza e de viitor. 

Cata dreptate a avut. 
tsai dzien...

25 martie 2015

Problema canibalilor si a misionarilor folosind KLEE

Despre problema canibalilor si a misionarilor am mai scris si aici, unde am prezentat o solutie clasica. Aceasta problema se mai poate rezolva si printr-un fel de forta bruta, folosind unealta KLEE

Klee genereaza automat teste cat mai exhaustive care sa acopere cat mai multe ramificatii, ghicind astfel cateva seturi de valori posibile pentru datele de intrare care trimit programul spre o ramura principala sau alta. Asadar, se pot afla si valorile pentru care se obtine solutia. 

Chiar daca pentru "Problema canibalilor si a misionarilor" timpul de executie a reiesit mult mai mare decat rezolvarea clasica, acesta vrea sa fie doar un model de cum se poate aplica Klee, care este cu siguranta mult mai util in alte situatii unde nu exista o rezolvare precisa.

Mai intai, cateva slide-uri introductive despre Klee:



Si in cele din urma, codul pentru problema canibalilor si a misionarilor (care desigur mai poate fi imbunatatit).


16 martie 2015

Probleme pentru interviu - Operatii pe biti & Brain teasers

---------------------------- cap. 5 - bit manipulation -----------------------------------------------------


Pe langa operatiile AND, OR, XOR, NOT, deplasare la dreapta sau la stanga, este bine de avut in vedere urmatoarele operatii pe biti:

* get bit at position i
(( num & (1 << i)) != 0)
(1 << i) inseamna 1 deplasat la stanga, i pozitii. 
Pe locul acelor pozitii se pune 0. Devine: 100....0 (0 de i ori) sau 0...010...0 , unde 1 se afla pe pozitia i.
num & (1 << i) = num & (0..0100....0) , de unde rezulta fix valoarea bitului i, care se compara cu 0.


* set bit at position i (adica bitul devine 1)
(num | (1 << i))
1 << i are aceeasi valoare cum am explicat, iar operatia OR va seta automat (cu 1) bitul i din num, pentru ca 1 OR x = 1 .


* clear bit at position i (adica bitul devine 0)
int mask = ~ (1 << i);
return num & mask;
Masca este opusul lui (0...010...0) adica (1...101...1), cu 0 pe bitul i.
num & mask pastreaza bitii din num asa cum sunt, mai putin bitul i care este obligat sa devina 0.


* clear all bits from most significant to bit i
int mask =  (1 << i) - 1;
return num & mask;
(1 << i) - 1 = (0..010...0) - 1 = (0...001...1) , adica toti bitii de la cel mai semnificativ pana la i inclusiv devin 0, iar restul 1.  num & mask pastreaza acest rest de biti si ii sterge pe ceilalti.


* clear all bits from the least significant to bit i
int mask = ~ ((1 << (i+1)) - 1);
return num & mask;
Sa o luam pe rand.
1 << (i + 1) inseamna (0...010...0), cu (i+1) zerouri in coada. Scazand 1 => (0...001....1), cu i de 1 in coada. Negand totul => (1...10...0), cu i zerouri in coada, si in final aplicand AND, se curata ultimii i biti din num, restul ramanand la fel.


* actualizarea unui bit la pozitia i, cu valoarea v
int mask1 = ~ (1 << i);
int mask2 = v << i;
return (num & mask1) | mask2;
mask1: ~(0...010...0) = (1..101..1) , cu i biti de 1 in coada
mask2: (0...0v0...0), cu i biti de 0 in coada
num & mask1 => pastreaza num asa cum e, mai putin bitul i care este curatat
| mask2 => modifica bitul i cu 1 daca v = 1, sau il lasa curatat daca v = 0


Si acum problemele propuse:

* N, M sunt doua numere pe 32 de biti. Se dau doua pozitii i si j. Sa se insereze M in N astfel incat M sa inceapa de la bitul j si sa se termine la bitul i din N.

Sol.: 
- creeaza o masca pe 32 de biti a.i. pozitiile > j (la stanga) si cele < i (la dreapta) sa fie 1, iar spatiul intre bitii i si j inclusiv sunt 0:
int left = (~ 0) << (j+1);    // 11....1 << (j+1)  =  11..10....0 , cu 0 de j+1 ori pt ca right most are poz. 0
int right = (( 1 << i) - 1);  //  (10...0) - 1 = 0...01..1 , cu i biti de 1 in coada
int mask = left | right;      //  "join"

- aplica masca pentru a curata portiunea dorita din N:
int cleared = N & mask;

- creeaza un M' care, la fel ca si masca, are pozitiile din afara sirului j->i cu 0, si portiunea dinauntru este copia lui M:
int m = M << i;  // M00...0 , cu i zero-uri 

- rezultatul va fi:    return cleared | m;


* Se da un numar real intre 0 si 1. Sa se scrie reprezentarea binara a acestuia sau eroare daca nu este posibil.

Sol.: Aceasta este o problema clasica de introducere in informatica.
Se ia un exemplu in baza 2:
0.101 = 1 * (1/2^1) + 0 * (1/2^2) + 1 * (1/2^3)
Ne trebuie operatia inversa: inmultire cu 2

String printBinary (double num) {
  if ( num >= 1 || num <= 0) return "error";
  StringBuilder sb = new StringBuilder().append(".");
  while ( num > 0 ) {
    if (binary.length() >= 32) return "error";
    double r = num * 2;
    if (r >= 1) { binary.append(1); num = r-1; }
    else { binary.append(0); num = r; }
  }
  return binary.toString(); }

ex. numarul 0.625 
r = 1.25 => binary = .1 , num = 0.25
r = 0.5   => binary = .10 , num = 0.5
r = 1      => binary = .101  , num = 0


* O functie care sa determine nr. de biti necesari pentru a converti un nr. intreg A la un nr. intreg B

int bits (int A, int B) {
  int xor = A ^ B; int cnt = 0;
  while (xor != 0) {
    if (xor & 1) cnt++;  // daca xor nu e in intregime 0
    xor = xor >> 1;       // se taie bitul din coada, deplasare la dreapta
  }
  return cnt; }


* Sa se interschimbe bitii de pe pozitiile pare si impare astfel: bit 0 cu bit 1, bit 2 cu bit 3, samd... in cat mai putine instructiuni posibile.

Sol.: 
- se ia numarul x si se face o masca a.i. toti bitii de pe pozitii impare sunt 1, restul sunt 0
Daca nr. ar avea 8 biti, masca ar arata 10101010, reprezentat ca AA in baza 16. Fiind un intreg de 32 biti, in hexazecimal arata: 0xaaaaaaaa  (de 8 ori A) 
int mask1 = 0xaaaaaaaa;
int left = (x & mask1) >> 1;  // pozitiile impare se muta pe pozitiile pare (ex. bitul 3 peste bitul 2, etc)
- se face o alta masca a.i. toti bitii de pe pozitiile pare sunt 1, restul 0
Masca ar arata gen: 01010101 , adica 55 in baza 16.
int mask2 = 0x55555555;
int right = (x & mask2) << 1; // pozitiile pare se muta peste cele impare, la stanga (ex. bitul 2 peste bitul 3, etc) 
- rezultatul final este:  left | right ;


* Se da un sir A in care toate elementele sunt intregi distincte de la 0... n mai putin un element care lipseste :) Singurul mod in care se poate accesa un intreg este printr-o operatie "binara": fetch(i, j) = bitul j din A[i] . Aflati elementul lipsa, in O(N).

Sol1: S = n*(n+1)/2 , S' se poate afla parcurgand sirul => elementul lipsa este S-S' , dar complexitatea este O (n * log n) , cu log n = lungimea lui n, nr. de biti pe care sunt repr. elementele (desi mie imi suna a constanta, 32 biti pt int)

Sol2: operatii pe biti. Se face un desen cu un exemplu. Se ia pozitie cu pozitie, ce se intampla la o eventuala suma, de la rangul cel mai mic la cel mai mare. In primul rand, daca n este par, vom vedea cifra "unitatilor" ca fiind 0, 1, 0, 1, .... , 0 , deci nr. de 0-uri = 1 + nr. de biti 1. Daca n este impar, nr. de 0-uri si 1-uri sunt egale. Astfel se poate deduce bitul cel mai putin semnificativ. Solutia sugereaza acest procedeu pentru toti bitii, ceea ce mie mi se pare de aceeasi complexitate ca in sol. 1. Alte idei gasiti si aici.


---------------------------- cap. 6 - brain teasers --------------------------------------------------------

Aceste probleme se pot numi si de logica / matematica aplicata / gandire si aduc putin aminte de concursul Cangurul.

* avem 2 franghii, fiecare poate arde o ora. Densitatea unei franghii variaza, deci o jumatate nu arde neaparat intr-o jumatate de ora. Cum numaram 15 minute?

Sol.: o franghie, daca o ardem la ambele capete, va arde in 30 minute. O franghie, daca stim sigur ca a ars jumatate din timp (fiind arsa doar la un capat) si apoi o ardem si la celalalt capat, va arde inca 15 minute pana e gata. Asadar: dam foc la ambele capete ale primei franghii si la un singur capat al celei de-a doua. Cand prima se consuma, dam foc si la celalalt capat al celei de-a doua si atunci incepe minutul 0. Cand se consuma si aceasta, vor fi trecut 15 minute.


* avem 9 mingii, 8 au aceeasi greutate, una este un pic mai grea. O balanta spune daca partea stanga sau dreapta este mai grea. Cu 2 utilizari ale balantei, sa se afle bila grea.

Sol.: se iau 3 + 3 mingii si se cantaresc. 
Daca sunt diferite, se iau cele 3 mai grele, se aleg 2 dintre ele si se cantaresc. Daca sunt egale, cea de-a 3-a este bila grea, altfel, se ia bila care a iesit mai grea.
Altfel, daca sunt egale, se iau celelalte 3 bile puse deoparte si se repeta procedeul se mai sus (se aleg 2... )


* avem 20 de sticle cu medicamente, 19 sticle au pastile de fix 1 gram, ultima are pastile de 1.1 grame. Un cantar arata greutatea exacta, dar poate fi folosit o singura data. Cum se poate determina care este sticla cu pastilele cele mai grele?

Sol.: daca cantarul se poate folosi o singura data, inseamna ca trebuie cantarite cel putin 19 sticle odata (sau ceva din continutul lor). Se ia un exemplu cu 2 sticle. Nu putem pune o sticla si alta pe ambele parti ale balantei pt ca nu stim daca au nr egal de pastile. Dar putem lua o pastila din prima si 2 din a doua sticla si astfel putem obtine:
  1 + 2 = 3 g daca sticlele sunt normale
  1.1 + 2 = 3.1 g daca prima sticla are medicamente mai grele
  1 + 2.2 = 3.2 g daca a doua ...
Astfel, pentru 20 de sticle, luam 1 pastila din prima, 2 pastile din a doua.... 20 de pastile din a treia. Stim ca ar trebui sa obtinem (1 + 2 + ... + 20) daca sticlele ar fi toate la fel. In schimb, cantarul va arata mai mult, si facem diferenta. Stim ca surplusul este (1.1 - 1) * k, unde k este indicele sticlei, asadar 0.1 * k = diferenta si aflam k.


* O tabla de sah 8 x 8 in care s-au taiat 2 colturi diagonal opuse. Se dau 31 piese de domino, in care un domino poate acoperi 2 patratele. Intrebarea este daca se pot folosi toate cele 31 piese pentru a acoperi complet tabla?

Sol.: in primul rand, o piesa de domino care ocupa 2 patratele adiacente inseamna ca ocupa un patratel alb si unul negru. Pentru 31 piese => tabla ar trebui sa aiba cel putin 31 patratele albe si 31 negre. Dar 2 colturi care erau de aceeasi culoare s-au indepartat. Tabla are 64-2 = 62 patratele, dar nr. de patratele albe nu e egal cu cel de negre. Asadar, piesele nu pot acoperi tabla.


* Niste oameni rationali traiesc pe o insula, unde un vizitator vine cu o porunca ciudata: toti oamenii cu ochii albastri trebuie sa paraseasca insula cat mai curand. Exista un zbor pe zi. Fiecare persoana vede ochii celorlalti, dar nu ii poate vedea pe ai sai, si nici nu are voie sa afle. Nimeni nu stie exact cati oameni au ochii albastri, desi se stie ca exista cel putin 1 persoana. Cate zile le vor lua oamenilor in cauza sa paraseasca insula?

Sol.: Se ia pe cazuri in functie de cate persoane cu ochii albastri sunt.
> c = 1 persoana. Se uita la toti ceilalti si vede ca nu exista nimeni cu ochii albastri, deduce ca e singura care ar trebui sa aiba ochii albastri, ia avionul si pleaca din prima zi.
> c = 2 persoane. In prima zi cei doi se uita in jur si vad o singura persoana cu ochii albastri. Asteapta ca ea sa plece din prima zi, dar acest lucru nu se intampla, pt ca fiecare ramane pe insula in asteptarea celuilalt. A doua zi, amandoi isi da seama ca se afla in cazul c = 2 si pleaca cu avionul.
Despre ceilalti: se uita in jur si observa ca exista doua persoane cu ochii albastri. A doua zi ii vad plecand si isi dau seama ca se afla in cazul 2.
> c = 3 persoane. Cei 3 se uita in jur si vad ca exista 2 persoane cu ochii albastri. Nu fac nimic in prima zi pentru ca stiu ca nu este cazul 1. In a doua zi nu ii vad plecand pe ceilalti 2, deci isi dau seama ca c > 2 si cum nu vad decat alti 2 cu ochii albastri, isi dau seama ca ei sunt a treia. Pleaca imediat in a treia zi. Despre ceilalti: vad de la inceput 3 oameni cu ochi albastri, asteapta o zi, doua, in a treia ii vad plecand, si ofteaza usurati.
> caz general: daca exista N oameni cu ochii albastri, le va lua N zile sa paraseasca insula


* Intr-o sala de sport avem 100 lacatele incuiate. Un paznic vine si le deschide pe toate. A doua oara, paznicul vine si le inchide din 2 in 2. Apoi vine si schimba starea lacatelului din 3 in 3, 4 in 4, tot asa pana la 100. Cate lacatele descuiate vor fi la sfarsit?

Sol.: O intrebare tipic "Cangurul". Se poate lua un exemplu, din care se poate observa ca:
lacat 1: sta deschis
lacat 2: deschis + inchis => inchis
lacat 3: deschis + ___ + inchis => inchis
lacat 4: deschis + inchis +  ____ + deschis => deschis
Pozitiile ____ sunt pt ca nr. lacatului nu a fost divizibil cu runda de trecere a paznicului, deci paznicul nu a atins lacatul. In final, se poate observa ca nr. de treceri reprezinta nr. de divizori al nr. de ordine al lacatului: 1 {1}, 2 {1, 2} , 3 {1, 3} , 4 {1, 2, 4} , iar lacatele ramase deschise sunt cele ale caror nr. de ordine are nr. impar de divizori. Aceste numere sunt patratele perfecte. Asadar, pana la 100 exista 10 patrate perfecte.


Probleme asemanatoare "brain teasers" am citit si aici. Unele sunt incluse chiar in acest post.

11 martie 2015

Probleme pentru interviu - Structuri de date

M-am apucat de Cracking the coding interview, cartea-minune care promite sa te trimita in bratele jobului bine platit pe care il visezi :)

It claims that it "gives you the interview preparation you need to get the top software developer jobs". Asa ca mi-a atras atentia si am inceput sa o parcurg. Din primele 4 seturi, care au tangenta cu structurile de date, am selectat cateva enunturi mai interesante, pentru "luare aminte". 

---------------------------- cap. 1 - siruri de caractere -----------------------------------------------------

* aflati daca s1 este o rotatie a lui s2, avand la dispozitie functia isSubstring(s1,s2) = true daca s1 subsir al lui s2.

Sol: daca s1 = "water", s2 = "terwa" => s1 este o rotatie a lui s2
s1+s1 = "waterwater" 
if s1.length () == s2.length && if isSubstring (s1+s1, s2) then true
else false

-------------------------- cap. 2 - liste inlantuite -----------------------------------------------------------

* aflati al k-lea element de la coada al unei liste simplu inlantuite (nu se stie dimensiunea ei)

Sol.1: se ajunge pana la capat recursiv si se intoarce incrementand pasii pana la locul de unde s-a pornit
int nthToLast (LinkedListNode head, int k) {
  if (head == null) return 0; // a ajuns la capat
  int i = nthToLast(head.next, k) + 1; // 1+ distanta urmatorului
  if (i == k) System.out.println(head.data);
}

Sol.2: cu doi pointeri aflati la distanta k unul de altul, se plimba pe lista, pana cand al doilea a ajuns la capat => returneaza informatia primului


* stergerea unui nod dintr-o lista simplu inlantuita, avand doar un pointer p la acel nod

Sol: se copiaza informatia din nodul urmator in cel curent si se sare peste nodul urmator catre celalalt
p.data = p.next.data;
p.next = p.next.next;


* intr-o lista inlantuita circulara, ret. nodul aflat la inceputul unei bucle (daca bucla exista)

Sol: se folosesc 2 pointeri. Unul merge cu pasul 1 (p1), celalalt sare din 2 in 2 pozitii (p2). Daca unul din pointeri ajunge la null => nu exista bucle
Altfel: pp ca lista incepe cu o parte liniara si apoi urmeaza bucla. Daca p1 ajunge la inceputul buclei aflat (sa spunem) la o distanta "k" fata de inceputul listei, p2 deja va fi parcurs k noduri in interiorul buclei. Distanta intre p1 si p2 = k = loop_size - k . Toate parcurgerile de acum inainte ale lui p1 si p2 se vor petrece in cadrul buclei: la fiecare un pas al lui p1, p2 parcurge 2 pasi. Dupa un calcul simplu, se poate vedea ca p1 si p2 se vor intalni dupa loop_size - k pasi simultani (la fiecare pas devin din ce in ce mai aproape). loop_size - k inseamna si k pasi distanta de inceputul buclei, care la randul ei se afla la k pasi distanta fata de startul listei (un desen ajuta f.mult). Se introduce un al treilea pointer p3 la startul listei, care se misca in acelasi timp cu p1, incepand de la momentul intalnirii lui p1 cu p2. Cand p1 si p3 se intalnesc (dupa k pasi) acela este inceputul buclei.


* verificare daca o lista e palindroma, cand nu ii cunoastem dimensiunea

Sol: se poate refolosi ideea a doi pointeri care merg unul cu pasul 1, celalalt din 2 in 2.
Pentru fiecare pas al lui p1, se salveaza informatia nodului parcurs intr-o stiva, timp in care p2 tot sare mai departe. Cand p2 a ajuns la null, p1 se opreste din push() si incepe sa faca pop(), continuand parcurgerea in lista si comparand elementul extras cu informatia nodului curent. La nepotrivire => false, altfel, daca a ajuns la null => true. (Daca lista are nr. impar de noduri, pt. p2 trebuie facuta verificarea ca p2!=null && p2.next==null) .


-------------------------- cap. 3 - stive & cozi ------------------------------------------------------

* def. o stiva s1 care are in plus o functie min ce returneaza elementul minim (conditie: O(1) pt push, pop, min)

Sol.1: pt fiecare element sa se pastreze, pe langa valoare, si un minim curent => push(value, newMin), unde newMin = Math.min (value, min()) si min() = peek().min; Pb.: consuma mult spatiu

Sol.2: o noua stiva s2 care pastreaza minimele, in care se adauga numai valori din ce in ce mai mici. 
=> push :   s1.push(value);    if(value < s2.peek()) s2.push(value);
     pop:      val = s1.pop();       if(val == s2.peek())   s2.pop();
     min:      s2.peek()


* Pb. turnurilor din Hanoi

Sol.: Despre asta am mai scris aici, dar era o rezolvare doar de suprafata. Pentru rezolvarea cu stive, pp ca fiecare turn este o stiva, iar discurile sunt elementele ce trebuie mutate de pe stiva 1 pe stiva 3, prin intermediul stivei 2. Ideea porneste de la cazurile de baza: un singur disc se muta direct de pe s1 pe s3. Pentru 2 discuri, primul se muta pe s2 intermediar, al doilea direct pe s3, iar apoi cel de pe s2 direct pe s3. Pentru 3 discuri si mai mult, se muta primul disc direct, apoi se presupune ca pasii sunt la fel ca in cazurile anterioare deja rezolvate, deci se poate apela la recursivitate, dar de data asta schimband rolurile intre s2 si s3.

void move (Stack from, Stack via, Stack to) {
  n = from.size();
  if (n == 1) {
    // caz de baza
    disk = from.pop();
    to.push(disk);
  }
  else if (n == 2) {
    // al doilea caz de baza
    disk2 = from.pop();
    via.push(disk2);
    disk1 = from.pop();
    to.push(disk1);
    disk2 = via.pop();
    to.push(disk2);
  }
  else {
    disk = from.pop();
    move(from, to, via);
    // totul e mutat in via
    to.push(disk);
    // se muta celelalte discuri din via in to
    move(via, from, to);
  }
}


* implementarea unei cozi folosind 2 stive

Sol: enqueue() sa se faca la o stiva, dequeue() la cealalta. Cand s2 se goleste, se rastoarna elementele din s1 in s2 - astfel cele mai proaspete elemente din s1 vor deveni cele mai tarzii pentru s2.


* sortarea unei stive, a.i. cele mai mari elemente sa fie in varf. Se poate folosi cel mult inca o stiva, fara nici un fel de alta structura auxiliara.

Sol: s1 = stiva de sortat; s2 = o stiva auxiliara mereu sortata
Vrem sa mutam varful lui s1 in s2 => il scoatem (elem) din s1, apoi scoatem elemente din s2 punandu-le in s1, pana cand am gasit "locul" lui elem (elem >= s2.peek()). Numaram de cate ori s-au mutat elemente din s2 in s1, ca sa stim cate punem la loc. Deci, punem elem in s2 si peste el atatea elemente din varful lui s1 cate s-au scos. 
Pentru sortarea intregului s1, se repeta pasii de mai sus pana cand s1 devine goala.
Asadar: push - in s1 si apoi cum am spus mai sus, peek/pop se ofera din s2. 


---------------------------- cap. 4 - arbori binari & grafuri -------------------------------------------------

* crearea unui arbore binar de cautare cu inaltime minima, pornind de la un sir sortat

Sol: In arborele binar de cautare, left <= root < right .  Root = mijlocul sirului.

TreeNode createMinBST (int arr[], int start, int end) {
  if (end < start) return null;
  int mid = (start + end) / 2;
  TreeNode n = new TreeNode (arr[mid]);
  n.left = createMinBST(arr, start, min-1);
  n.right = createMinBST(arr, mid+1, end);
  return n;
}


* aflarea succesorului unui nod dintr-un arbore binar, metoda inordine

Sol: preordine = RSD; inordine = SRD; postordine = SDR
Deci, succesorului lui R (radacina) este nodul D (dreapta).
La o simulare pe hartie, se observa ca exista doua cazuri:
- nodul are un copil pe aripa dreapta => succesorul este cel mai din stanga nod frunza al copilului de pe partea dreapta
- nodul nu are un copil pe aripa dreapta => SRD curent este incheiat, intreg SRD-ul reprezinta parcurgerea aripii drepte ale unui predecesor => succesorul va fi ultimul stramos pe a carei ramuri drepte se afla nodul. 
Un desen cu numere de ordine ajuta.


* Primul stramos comun a doua noduri p, q dintr-un arbore binar, avand acces la nodul radacina.

Sol.1: Se verifica daca p, q se afla pe aceeasi parte (sa spunem stanga) a radacinii curente, printr-o parcurgere oarecare pt a afla daca un nod apartine unui arbore. Daca se afla pe parti diferite, radacina este stramosul comun. Altfel, se repeta recursiv procesul, in functie de partea pe care se afla ambele noduri: daca e stanga, noua radacina e acel nod stang, altfel, cel drept.

Sol.2: Parcurgerea arborelui o singura data. 
Result commonAncestor ( root, p, q) {
  if (root == null) return new Result(null, false);
  if (root == p && root == q) return new Result(root, true);
  Result rx = commonAncestor (root.left, p, q);
  if (rx.isAncestor) return rx;
  Result ry = commonAncestor (root.right, p, q);
  if (ry.isAncestor) return ry;
  if (rx.node != null && ry.node != null) return new Result(root, true);
  else if (root == p || root == q) {
    boolean isAnc = rx.node != null || ry.node != null ? true : false;
    return new Result (root, isAnc);
  }
  else return new Result (rx.node != null ? rx.node : ry.node, false);
}


* Toate caile dintr-un arbore binar ale caror sume sunt egale cu o anumita valoare V . 

Sol: "does this node end with a sum?"
La fiecare nivel se propaga un vector de noduri repr. calea de la radacina pana la nodul curent si nr. nivelului.
Nodul curent se adauga la cale. Apoi, de la cel mai recent la cel mai vechi, se aduna valorile nodurilor din cale, iar cand se obtine V => se afiseaza intreaga cale de la nodul curent la acel nod cu care s-a completat suma. 
Se repeta recursiv pentru copilul pe partea dreapta si cel pe partea stanga, cu nivelul++ si noua cale.