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
* să se înlocuiască fiecare spațiu dintr-un string cu %20 . Șirul este alocat fără limită superioară. A nu se folosi resurse suplimentare.
Sol: se iterează stringul pentru a vedea câte spații sunt. Se triplează numărul de spații pentru a găsi unde va fi poziția ultimului caracter. Apoi, de la coadă către capăt, se va copia caracter cu caracter, cu '%20' în loc de spațiu.
-------------------------- 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.
