Skip to content

Întrebări de la interviu – 3

28 August 2010

Soluții de la întrebările precedente și întrebări noi/continuări. Trebuie să menționez că întrebările simple au fost urmate de continuări și în timpul interviului (deci nu o oră pentru a copia lista simplu înlănțuită – se așteaptă ca răspunsul la o întrebare simplă să-l dai rapid, apoi vine întrebarea follow-up). Iar întrebările simple fără continuări au fost urmate de alte întrebări – am primit câte 2, 3 sau 4 în aceași oră. Și încă ceva la întrebările simple – nu pentru toate trebuie scris cod – câteodată a fost OK dacă am explicat conceptual soluția. De obicei coding pentru 1 sau 2 e suficient (ca să se lămurească cel ce dă interviul că știi să scrii cod). Următoarele sunt mai interesante din punct de vede algoritmic.

Soluții

6. Continuare la 1 – cum copiezi o listă simplu înlănțuită dacă, pe lângă pointerul la următorul nod (next), fiecare nod mai are un pointer și la nodul care urmează după nodul următor (next->next)?

Din nou întrebarea e destul de simplă. Eu am spus că folosesc doi pointeri, pentru nodul curent și nodul următor. Astfel, pointerul la next->next poate fi setat folosind pointerul next al nodului următor.

7. Continuare la 2 – se dau doi vectori sortați. Să se scrie o funcție care combină vectorii păstrând elementele în ordine in-place, modificând mărimea unuia din vectori ca să poată acomoda și elementele celuilalt vector.

Aici în primul rând trebuie știută funcția realloc, cu care poți extinde mărimea unui vector. Și mai este o mică șmecherie când faci merge in-place: se începe de la ultimele elemente ale vectorilor, nu de la primele. Dacă începi de la primele elemente, atunci inserarea în vector ar presupune mutarea tuturor celorlalte elemente spre dreapta. Dacă începi de la coadă, atunci nu e nevoie.

8. Continuare la 5 – să se scrie clasa/clasele care modelează arborele de lookup descris mai sus.

Eu am scris clasa care corespunde unui nod din arbore. Copiii nodului pot fi stocați într-un vector deoarece cheile sunt totdeauna tastele de la 1 la 9 și așa se obține cel mai rapid lookup – indexarea într-un vector e cea mai rapidă operație în acest caz (menționez asta deoarece inițial am vrut să folosesc o listă sau un dicționar, dar nu e nevoie – vectorul face treaba mai bine aici).

9. Se dă un display monocrom. Un pixel (cu coordonate x, y pe ecran) poate fi aprins sau stins. Avem la dispoziție o funcție getpixel(x, y) care returnează 0 dacă pixelul de la coordonatele (x, y) e stins și 1 dacă e aprins și o funcție setpixel(x, y, on) care aprinde sau stinge pixelul de la coordonatele (x, y) în funcție de parametrul on. Să se scrie o funcție care poate colora un poligon – poligonul are conturul format din pixeli aprinși iar funcția primește coordonate (x, y) în interiorul poligonului (restul suprafeței poligonului are pixelii stinși). Pe scurt – ca și găleata din Paint.

Altă problemă simplă – acesta e algoritmul clasic de flood fill și se implementează printr-o funcție recursivă: dacă getpixel(x, y) e aprins – return, dacă nu setpixel(x, y, true) și apel recursiv pentru (x-1, y), (x+1, y), (x, y-1), (x, y+1).

10. Se dă un șir de caractere reprezentând o expresie aritmetică. Pentru simplitate, să presupunem că operatorii pot fi doar întregi pozitivi, operațiile suportate sunt doar + și * și mai sunt suportate și paranteze. De exemplu 3 * (4 + 5). Să se scrie o funcție care primește o astfel de expresie și returnează valoarea în urma evaluării.

Evaluarea expresiilor aritmetice se face cu două stive – una pentru operatori, una pentru operanzi. Se parcurge expresia și operanzii sunt împinși pe stiva de operanzi. Operatorii sunt tratați în funcție de precedență, astfel dacă operatorul din vârful stivei are precedență față de operatorul curent, se scoate de pe stivă și se aplică primilor doi operanzi din stiva de operanzi, aceștia fiind înlocuiți cu rezultatul operației. Când se ajunge la sfârșitul expresiei, se golește stiva de operatori în același fel – aplicând fiecare operator primilor doi operanzi de pe stivă și înlocuindu-i cu rezultatul operației.

Întrebări

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. De exemplu pentru lista A, B, C, D, E, F, G și n = 4:

A are un pointer la B (pentru că e listă simplă înlănțuită) și un pointer la E (al patrulea nod de la A).

B are un pointer la C și unul la F.

C are un pointer la D și unul la G.

D are un pointer la E, celălalt fiind NULL (nu există al patrulea element de la D). La fel și E, F, G.

Cum se poate clona o astfel de listă?

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.

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.

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

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.

From → code complete

4 Comments
  1. George Florentin permalink

    Bun, de cod ai scris, ba chiar 3 posturi, insa de partea economico-financiara nu ai spus nimic.

    In ceea ce priveste banii, cand ai discutat despre asta (daca ai discutat), si cum a decurs discutia? Nu ma intereseaza sume (ai putea sa zici in dolari de monopoly). Ai negociat suma pe care au oferito ei? Ti-au oferit >, < sau == decat aveai inainte?

  2. vladr permalink

    Nu am renegociat. A fost transfer intern pe exact aceași poziție – titlu, nivel, salar. De obicei așa se face când te transferi intern.

  3. George Florentin permalink

    Ok, insa cand ti-au facut ei prima oara oferta, ai negociat ceva?

  4. vladr permalink

    Personal nu am negociat nimic. Cred că dacă ții neapărat, poți negocia, dar nu știu sigur. Eu am fost mulțumit de oferta primită…

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: