Skip to content

Întrebări de la interviu – 2

22 August 2010

Răspunsuri de la primele întrebări și întrebări noi. Anunț de pe acum că nu voi posta cod pentru nicio soluție, doar idea.

Soluții

1. Se dă un pointer la nodul head al unei liste simplu înlănțuite. Să se scrie o funcție care copiază (clonează) lista

Asta am primit la interviu pentru poziție de developer C++ – de obicei acolo sunt probleme cu liste. Algoritmul pentru copiat o listă este simplu – începi de la head și copiezi fiecare nod până ajungi la capătul listei, menținând un pointer la noul head care trebuie returnat. Două cazuri deosebite: nodul head primit e NULL sau nu este suficientă memorie pentru a copia toată lista (malloc întoarce NULL). Funcția ar trebui să primească parametri nodul head și, ca parametru out noul nod head și să întoarcă un error code (0 dacă copierea a funcționat, coduri diferite pentru cazurile menționate mai sus). Plus, lista parțial construită trebuie ștearsă dacă nu a putut fi copiată complet din lipsă de memorie.

2. Se dau doi vectori sortați. Să se scrie o funcție care combină vectorii într-un nou vector, păstrând elementele în ordine (merge).

Din nou algoritmul este foarte simplu – aloci memorie pentru noul vector, începi de la index 0 de la ambii vectori primiți și introduci elementul mai mic în noul vector. Avansezi în vectorul din care ai copiat.

Atenție din nou la cazuri speciale: insuficientă memorie pentru a aloca noul vector sau dacă un vector primit este NULL.

3. Un program ca Excel numește coloanele cu litere, începând cu A, B, C până la Z, apoi AA, AB și așa mai departe. Să se scrie o funcție care primește numărul coloanei și întoarce stringul care reprezintă numele coloanei în litere.

Destul de simplu – construiești rezultatul ca string astfel: cât timp numărul este mai mare sau egal cu 0, iei restul împărțirii numărului la 26 (numărul de litere din alfabet), apoi împarți numărul la 26 și scazi 1 apoi repeți. Atenție că fiecare nouă literă se inserează la începutul nu la sfârșitul stringului.

Întrebarea am primit-o la interviu pentru poziție de developer C# și am impresionat când am construit rezultatul cu un StringBuilder în loc să folosesc un string și am știut explica de ce (când faci o operație pe un string, .NET crează automat o instanță nouă, folosind StringBuilder eviți asta).

4. Se dă un string care începe cu A și continuă cu următoarele litere în ordine alfabetică (B, C, D…). Literele sunt întotdeauna sortate și nu lipsește nicio literă din mijlocul stringului (“ABCD” e un posibil string, “ABDE” nu este deoarece lipsește C). Există 26 astfel de stringuri posibile (“A”, “AB”, “ABC”, …, “ABC…Z”). Pentru un astfel de string, să se genereze toate stringurile ce conțin submulțimi unice de caractere din stringul dat. De exemplu pentru “ABC” se generează “A”, “B”, “C”, “AB”, “BC”, “AC”, “ABC”. Fiind submulțimi unice, “AB” și “BA” nu trebuie să apară simultan în soluție (oricare din ele apare e corect). Ordinea în care stringurile sunt generate nu conteză.

Soluția corectă aici este bitmasking – pentru cazul “ABC” de exemplu, iei într-un ciclu for toate numerele de la 001 la 111 (în baza doi). Fiecare bit corespunde unei litere din string. Dacă e 1, adaugi litera în rezultat, dacă e 0 nu. Astfel generezi toate submulțimile.

Verificarea pe biți se face astfel: începând de la cel mai puțin semnificant bit, cât timp numărul e mai mare ca 0, verifici dacă bitul e setat cu un și binar (n & 1 == 1). Pe urmă faci shift dreapta o poziție (n = n >> 1) și repeți.

Idea se aplică la majoritatea problemelor care necesită generarea tuturor submulțimilor.

5. Telefoanele asociază unui număr de pe tastatură litere. De exemplu la 2 corespunde ABC, la 3 corespunde DEF și așa mai departe. În momentul în care utilizatorul apasă taste pe telefon, telefonul îi poate recomanda auto-completarea unui cuvânt (T9). De exemplu dacă sunt apăsate tastele 2 (ABC) și 7 (PQRS), telefonul ar putea recomanda APPLE sau CROSS ca și completări posibile. Cum se implementează un astfel de sistem de auto-completare?

Structura de date care trebuie folosită este un arbore ce are ca și cheie la fiecare nod tasta de pe telefon și conține cele mai bune recomandări la nivelul respectiv. Pentru exemplul din enunț, parcurgi arborele de la rădăcină – prima tastă e 2 deci mergi pe nodul cu cheia 2 (ABC). Următoarea tastă e 7 (PQRS) deci mergi pe copilul nodului care are cheia 7 (PQRS). Aici trebuie să ai cele mai bune recomandări pentru combinația 27 (APPLE și CROSS în exemplul de mai sus). Astfel se pot regăsi rapid recomandări pentru toate combinațiile de taste pentru care există recomandări.

Înainte să dau niște probleme noi menționez că nu e atât de dificil cum pare, și eu am primit ajutor sau hint-uri la unele soluții, nu am rezolvat totul cap coadă. De exemplu la problema 1 eu am început cu o funcție care primește ca parametru doar nodul head și întoarce noul head, pe urmă, când m-a întrebat de cazurile speciale, am realizat că implementarea corectă are altă semnătură la funcție. Deci no stress dacă nu iese soluția perfect din prima.

Să continuăm cu probleme:

Întrebări

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

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.

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

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.

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.

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: