Skip to content

Întrebări de la interviu – 4

7 September 2010

Am întârziat puțin cu acest post din cauză de long weekend🙂

Soluții

11. Continuare la 6 – cum copiezi lista dacă fiecare nod are, în locul pointerului la nodul care urmează după nodul următor, un pointer la al n-lea nod de la poziția sa în listă, cu n dat.

Aici idea e să pornești de la nodul head și să copiezi lista până la elementul n ignorând pointer-ul spre al n-lea element. Odată ajuns la elementul n (să zicem cu un pointer p), continui copierea și, în paralel, începi din nou de la nodul head (să zicem cu un pointer q), setând pointer-ul la al n-lea element al elementului q ca p. Apoi avansezi atât p cât și q și repeți.

12. Continuare la 8 – să se scire funcția de lookup care folosește un arbore de lookup (modelat la întrebarea 8 ) și populat care primește ca parametru o combinație de taste și întoarce recomandări.

Destul de simplu – parcurgi arborele în funcție de combinația de taste dată și te oprești fie când ajungi la nodul căutat, fie când ajungi la un nod frunză (în cazul în care ultimele taste date nu se regăsesc în arbore). Întorci recomandările de la nodul la care te-ai oprit.

13. Se dau două liste simplu înlănțuite care se unesc la un moment dat – de exemplu A->B->C->D->E și A’->B’->C->D->E se unesc la elementul C (atât B cât și B’ au un pointer spre același element). Astfel, cel puțin ultimul element al ambelor liste este același. Să se determine elementul la care listele se unesc. Se dau, desigur, pointeri spre elementele head ale listei. Soluție în timp liniar.

Ca să găsești primul nod comun în timp liniar, prima dată trebuie să parcurgi ambele liste până la capăt și să numeri elementele. Să zicem că prima listă are m elemente, a doua are n elemente. Vezi care din liste are mai multe elemente și avansezi în lista respectivă până când în ambele liste ai de parcurs același număr de elemente până la capăt (dacă de exemplu m > n, avansezi m-n noduri în lista de lungime m). Din acest punct, compari elementul curent al listelor – dacă este același, ai găsit elementul unde se unesc; dacă nu, avansezi la elementul următor și repeți.

14. Cum se sortează eficient o listă simplu înlănțuită? (nu in-place, se poate folosi memorie adițională)

Eu am spus că folosind heap-sort – parcurgi lista și introduci fiecare element într-un heap, apoi golești heap-ul și construiești lista sortată. Sigur există și alte soluții eficiente.

15. Întreabare de design – se dă o clasă utilitară de compresie cu două metode: byte[] Compress(byte[] buffer) și byte[] Decompress(byte[] buffer). Prima aplică un algoritm de compresie buffer-ului dat și întoarce un buffer comprimat. A doua aplică un algoritm de decompresie buffer-ului dat și întoarce buffer-ul decomprimat. Același algoritm este folosit, deci Decompress(Compress(data)) întoarce exact data. Se dorește implementarea unui CompressionStream (derivat din Stream, ca orice alt stream din .NET) ce utilizează clasa utilitară pentru a scrie informații compirmat într-un fișier și pentru a citi și decomprima un astfel de fișier, decomprimând datele. Stream-ul trebuie să suporte operațiunea Seek. Prima cerință – proiectează formatul fișierelor pentru acest CompressionStream.

Asta a fost mai mult o discuție așa că nu am o soluție exactă.

Un lucru de considerat e că nu vrei să compresezi datele imediat ce le primești pentru că poți ajunge în situația în care compresezi multe blocuri mici de date și operațiunea seek devine dificilă. Deci trebuie folosit un buffer, așa că fișierul va conține blocuri de date comprimate de aceași dimensiune. Pentru seek, mai trebuie asociat fiecărui bloc și poziția de început din datele necomprimate. Pe urmă întrebarea e unde pui informația respectivă pentru un seek eficient? Dacă o pui înainte de fiecare bloc, un seek presupune să sari de la un bloc la altul până găsești poziția pe care o cauți. Dacă pui toată informația într-un fel de index la începutul fișierului, seek-ul devine foarte eficient dar scrierea în fișier devine dificilă pentru că trebuie actualizat indexul la fiecare scriere. Soluția pe care am propus-o e să construiești mai multe indexuri. După o scriere, ai un index și un număr de blocuri (căutare eficientă). După următoarea scriere, adaugi la sfârșitul fișierului încă un index și blocurile scrise și tot așa (scriere eficientă). Un seek tot va trebui să sară dintr-o parte în alta dar măcar sare de la index la index nu de la bloc la bloc.

Întrebări

Ultimele întrebări:

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.

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

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?

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).

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.

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: