9 thoughts on “Interviu Infoarena”

  1. Misto. Am observat si eu ca multi programatori (din pacate si cativa care sunt deja angajati la Google) nu se prea pricep la structuri de date.

    Ca intrebare de interviu, imi place „construieste un cache LRU care mapeaza un sir de caractere la un obiect arbitrar, si poate conttine cel mult N elemente” pentru ca solutia corecta cere sa implementezi o lista dublu inlantuita (nu ajunge sa folosesti java.util.LinkedList; trebuie sa poti sterge un element din lista in O(1)).

  2. Mersi, ba! 🙂 (ca m-ai mentionat in interviu).
    „Francu’s List”, o, ce ploaie si ce vant… 🙂

    Vrei probleme? Gogule, probleme, ma? 🙂 Ia d-acilea… Se considera o matrice binara N x M (e cu 0 si 1). Sa se afle sub-matricea de arie maxima umpluta doar cu 1. Complexitate ceruta: O(N x M).

    –D

    p.s. Frate, de cand au devenit capchas astea asa grele? Am unu’ de 8 caractere pe care abia-mi merge built-in OCR-ul (read: ochii) 🙂

    p.p.s. Pozele alea din Hawaii… n-apare macar o versiune BETA? 🙂

  3. p.p.p.s. Sigur mai tii minte bine problema cu becurile? 🙂 Sa se identifice o ordine de atingere a becurilor astfel incat in final toate becurile sa fie aprinse. Ordinea e irelevanta… subsetul de becuri atinse e relevant. 🙂 Nu?

    –D

  4. Hai ca azi iti troll-uiesc blogu’ in prostie 🙂

    Nu stiam problema cu becurile, si acum c-am ajuns acasa m-am gandit cateva minute. Maybe I’m wrong, dar ce mi se pare mie e asa:
    (1) Un bec il atingi o data sau deloc (atingi de 2 ori, se anuleaza);
    (2) Ordinea e nerelevanta, deci poti sa zici ca le atingi bottom-up;
    (3) Therefore, dinamica.
    — Cand decizi ca you’re done cu un nod (si subarborele sau), inseamna ca nivelul de sub el trebuie sa fie lit (de deasupra lui n-o sa mai poti actiona). Nodu’ in sine poate sa fie ne-aprins momentan, dar sub el tre’ sa fie aprins tot.
    — Pentru un nod, conteaza daca e aprins si daca e atins. Deci tii pentru un nod patru bool vars: touched + lit possible, touched + not lit possible, not touched + lit possible, not touched + not lit possible.
    — Initializezi frunzele;
    — Faci regulile: de exemplu touched + lit possible = all sons not lit + number of sons touched even. Adica in cazul asta vrei toti fiii sa fie not lit (ca se aprind cand il touch-esti pe nodu’ radacina in sine) si dintre ei, un numar par de noduri atinse (ca se canceleze actiunile lor). Deci toti fiii trebuie sa poata fi intr-una din starile (t, non-l) sau (non-t, non-l); apoi numeri pe aia care sunt obligatoriu in (t, non-l) (adica nu pot fi in (non-t, non-l)); daca sunt pari, okay; daca nu, vezi daca ai unul in (non-t, non-l) care poate fi (t, non-l) si esti okay din nou; daca nu, nu se poate.

    Mi-e lene sa dezvolt restul de 3 cazuri, dar cam asa cred ca se face.

    Si e O(N)…

    Cum e, sunt in balarii sau merge? 🙂

    –D

  5. dumi: pare corecta solutia.

    Eu o vazusem in un Ginfo din 95, si era propusa la olimpiada nationala. Stiu ca in concurs a fost rezolvata de 100 de puncte cu un „backtracking optimizat” si ca dupa concurs Radu Lupsa s-a prins de o solutie asemanatoare cu a ta. Era mare minune la vremea aia sa rezolvi o problema cu programare dinamica.

Leave a Comment

Adresa ta de email nu va fi publicată.