Skip to content

Întrebări de la interviu – 5

13 September 2010

Și cu asta am terminat cu interviurile, cel puțin deocamdată.

Soluții

16. Continuare la 11 – cum copiezi lista dacă fiecare nod are, în locul pointerului la al n-lea nod de la poziția sa în listă, un pointer la oricare element din listă. Nicio regulă pentru acest pointer – pentru fiecare nod, pointerul poate referi orice alt nod din listă. Hint: lista poate fi distrusă în momentul copierii.

Asta este puțin mai tricky (eu cel puțin nu am știut să dau răspunsul în timpul interviului). Se dă lista A(D) -> B(A) -> C(A) -> D(D) -> E(B) – am trecut în paranteză pointerul aleator de la fiecare element. Poți distruge lista, deci copiezi fiecare element în felul A -> A’ -> B -> B’… deci copiezi nodul A în A’, faci A’->next = A->next și A->next = A’. Repeți pentru toată lista. În final ai A(D)->A’->B(A)->B’->C(A)->C’->D(D)->D’->E(B)->E’. Șmecheria: acum ca să setezi pointerul aleator din noua listă, A’->random = A->random->next șamd. Rezultă A(D)->A'(D’)->B(A)->B'(A’)->C(A)->C'(A’)->D(D)->D'(D’)->E(B)->E'(B’) și trebuie doar să elimini elementele din lista inițială – A->next = A->next->next și tot așa până la capătul listei.

17. Cum determini dacă un număr dat este prim? Cum poți optimiza soluția?

Algoritmul clasic ca să afli dacă n e prim e să verifici dacă restul împărțirii este egal cu 0 pentru toate numerele de la 2 la radical din n.

Optimizări – în funcție de cât spațiu ai, poți menține un tabel cu primele p numere prime, astfel că nu e nevoie să faci împărțirea pentru toate numerele cât timp nu ai epuizat tabelul. O altă optimizare ar fi să ignori toate numerele pare după 2.

18. Se dă un arbore cu o formă specifică – fiecare nod în afară de nodul rădăcină are maxim un copil. Toate nodurile au un pointer spre nodul părinte. Se dau două noduri dintr-un astfel de arbore – să se calculeze distanța dintre ele. Distanță înseamnă prin câte noduri trebuie să treci ca să ajungi de la unul din noduri la celălalt (mergând fie spre nodul copil, fie spre nodul părinte al fiecărui nod). Cum poți optimiza soluția?

Soluția simplă – pornești de la fiecare nod și mergi “în sus” până ajungi la rădăcină, numărând prin câte noduri ai trecut și aduni cele două numere. Șmecheria e că ai cazul special în care unul din nodurile date e părintele celuilalt, unde soluția simplă nu funcționează. Sunt mai multe feluri în care poți determina dacă un nod este părinetele celuilalt – o soluție ar fi pur și simplu să marchezi fiecare ramură din arbore cu un număr, astfel poți afla imediat dacă două noduri sunt pe aceași ramură sau nu.

Cât despre optimizări, dacă nu este o restricție, poți salva distanța de la fiecare nod la rădăcină ca parte din informația conținută în nod. În acest caz nici nu mai trebuie parcurs arborele.

19. Se dau 100 de calculatoare cu 20 GB de spațiu fiecare – 10 GB liberi și 10 GB un fișier format din numere întregi. Cum se poate construi un fișier care să conțină numerele întregi sortate de pe toate calculatoarele (desigur, partiționat după cum permite spațiul).

Aici soluția e, desigur, merge-sort. În primul rând sortezi fiecare fișier. Din moment ce fișierele sunt extrem de mari (nu încap în RAM), nu poți sorta tot fișierul odată așa că îl partiționezi, sortezi fiecare partiție în memorie și o scrii sortată pe disc. Apoi faci un merge la partițiile respective (partițiile le scrii în cei 10 GB liberi, apoi când faci merge le suprascrii peste fișier) și încă un merge la fișierele de pe fiecare calculator.

Aici am avut o discuție interesantă despre cum e mai eficient să faci un merge de pe 100 de calculatoare – toate partițiile deodată sau faci un merge mai mic (pe câte 10 calculatoare de exemplu) și apoi încă unul final. Cred că luate câte 10 e mai eficient, ca să nu menții 100 de conexiuni la un calculator dar recunoscă că partea de networking nu e punctul meu forte🙂

20. Continuare la 15 – să se implementeze metoda ReadBytes pentru CompressionStream care citește datele din fișierul al cărui format a fost stabilit ca răspuns la întrebarea 15.

Aici nu prea am ce soluție explica. Trebuie doar scris codul.

Și, după cum ziceam la început, am încheiat seria de posturi așa că nu mai urmează întrebări. Baftă la interviuri!

From → code complete

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: