_Postez a doua parte a interviului cu Radu Berinde. In aceasta parte el ne povesteste despre _

_Postez a doua parte a interviului cu Radu Berinde. In aceasta parte el ne povesteste despre concursuri, despre MIT, despre Google si despre cat impinge la piept, de asemenea va aparea si putin context legat de poza cu masina din prima parte a interviului. Enjoy!  _

*Dupa terminarea liceului ai fost fost in comisii la cateva concursuri, cum e participarea pe cealalta parte a baricadei?*

Ca sa stii sa optimizezi, trebuie sa intelegi cat de cat ce se intampla mai jos de compilator; in majoritatea situatiilor, trebuie sa ai idee de cum functioneaza calculatorul, sa stii cum sa te folosesti de cache-ul de memorie, sau sa stii care operatii sunt mai costisitoare.

Pot sa va povestesc despre o problema la un lot (Petrol din 2003); era despre un graf cu N noduri si M muchii si avea o solutie evidenta care folosea N BF-uri (timp N*M). Solutia care se cerea era in M*log N daca imi amintesc bine, iar solutia in N*M ar fi trebuit sa ia in jur de 30-40 de puncte. Eu am reusit sa iau 90 de puncte cu aceasta solutie. Cum? O singura linie conta - cea care definea bucla de expandare a vecinilor unui nod. Trebuia sa optimizez cat mai mult enumerarea vecinilor unui nod. Ideea a fost sa citesc mai intai intrarea doar pentru a numara vecinii fiecarui nod, sa aloc cate un vector exact de marimea necesara pentru fiecare nod, apoi sa citesc din nou intrarea si sa completez vectorii. Astfel, efortul de a enumera toti vecinii in unui nod in parcurgere este minim; vecinii sunt unul langa altul in memorie si cache-ul este folosit foarte bine. Mai era o singura decizie de luat - cum sa stii cand sa te opresti in enumerarea vecinilor; am testat in timpul concursului tot felu de metode si cea mai rapida a fost sa adaug un numar special (0) la sfarsitul fiecarui vector. Sigur, ar fi fost mai bine sa fiu mai destept si sa ma prind de solutia corecta, dar care ar mai fi fost spectacolul? :)

Pot sa va povestesc despre o problema la un lot (Petrol din 2003); era despre un graf cu $N$ noduri si $M$ muchii si avea o solutie evidenta care folosea $N$ BF-uri (timp $N*M$). Solutia care se cerea era in $M*log N$ daca imi amintesc bine, iar solutia in $N*M$ ar fi trebuit sa ia in jur de 30-40 de puncte. Eu am reusit sa iau 90 de puncte cu aceasta solutie. Cum? O singura linie conta - cea care definea bucla de expandare a vecinilor unui nod. Trebuia sa optimizez cat mai mult enumerarea vecinilor unui nod. Ideea a fost sa citesc mai intai intrarea doar pentru a numara vecinii fiecarui nod, sa aloc cate un vector exact de marimea necesara pentru fiecare nod, apoi sa citesc din nou intrarea si sa completez vectorii. Astfel, efortul de a enumera toti vecinii in unui nod in parcurgere este minim; vecinii sunt unul langa altul in memorie si cache-ul este folosit foarte bine. Mai era o singura decizie de luat - cum sa stii cand sa te opresti in enumerarea vecinilor; am testat in timpul concursului tot felu de metode si cea mai rapida a fost sa adaug un numar special (0) la sfarsitul fiecarui vector. Sigur, ar fi fost mai bine sa fiu mai destept si sa ma prind de solutia corecta, dar care ar mai fi fost spectacolul? :)

Stiu ca pentru un an erai inscris la Universitatea Bucuresti si la Universitatea Politehnica, iar apoi ai plecat la MIT. Poti sa ne povestesti mai mult? Ce te-a facut sa alegi MIT?

*Stiu ca pentru un an erai inscris la Universitatea Bucuresti si la Universitatea Politehnica, iar apoi ai plecat la MIT. Poti sa ne povestesti mai mult? Ce te-a facut sa alegi MIT?*

Eram deja decis sa aplic la MIT inainte sa incep facultatea in Romania. Motivul in principal a fost ca in facultatile din Romania nu prea se invata mare lucru (la informatica). In nici un caz nu cat se invata la una ca MIT. Simteam ca am totusi un talent deosebit si ca trebuie sa il folosesc/extind in continuare (ceea ce clar nu se intampla la facultate in Romania). Nu eram chitit sa plec din tara; faptul ca trebuia sa plec era un dezavantaj. Am aplicat doar la MIT, in ideea ca daca plec din tara, macar sa merite. Plus ca aici aveam si cele mai mari sanse sa fiu acceptat, pentru ca aici conteaza (sau contau..) cel mai mult medaliile.

Cursul de sisteme de operare a fost foarte interesant; pe de-o parte, am studiat in detaliu un sistem foarte mic de la care a plecat UNIX, pe de alta parte am implementat un sistem bazat pe cu totul alte idei.
La sfarsit am avut si un proiect in care puteam sa facem cam orice in sistemul nostru de operare; a fost foarte interesant - unii au portat stackuri TCP/IP si web-servere, altii sisteme de fisiere distribuite, si multe alte chestii. Eu am portat un compilator, vi, si quake1 :)

Alt curs interesant a fost unul de sisteme distribuite, in care am invatat despre multe sisteme si tehnici care au avut succes, si am si implementat un sistem la sfarsit. Alt curs a fost unul de grafica, la are am implementat multe chestii misto.

Alt curs interesant a fost unul de sisteme distribuite, in care am invatat despre multe sisteme si tehnici care au avut succes, si am si implementat un sistem la sfarsit. Alt curs a fost unul de grafica, la care am implementat multe chestii misto.

Din cele teoretice, mi-au placut teoria complexitatii, geometrie computationala, algoritmi avansati; la toate am invatat lucruri foarte interesante. Am luat si un algoritm mai avansat care mi-a placut foarte mult; se chema "sketching, streaming, and sub-linear space algorithms". A fost despre tehnici si algoritmi cu care sa aproximezi (probabilistic) ceva folosind mult mai putin spatiu decat ar lua "ceva"-ul respectiv (care de obicei era un vector intr-un spatiu de
dimensiune foarte mare).

De multe ori nu prea frumoasa; sunt cam exagerati in volumul de materie, teme, cerinte si uneori trebuie sa depui eforturi foarte mari sa tii pasul. In unele perioade esti mai relaxat, si poti sa te bucuri de mai mult timp liber.  Nu e la fel de distractiv in Romania, unde sunt majoritatea prietenilor mei mai apropiati. Insa sunt locuri, oameni, si lucruri frumoase si acolo; si ai si avantajul de a trai intr-o tara mult mai dezvoltata si mai civilizata.

*Cand ai inceput cu concursurile pe topcoder ai ajuns foarte repede intre cei mai buni de pe sait, e usor pentru tine sa participi la concursuri la un nivel inalt dupa ce ai facut o pauza?*
Mi se pare ca in timp se clarifica ideile si cunostiintele. Cred ca acum as fi mai bun decat eram in liceu daca m-as duce din nou la olimpiadele din liceu (dupa ce m-as mai antrena un pic).
*Cum se compara concursurile pe topcoder cu celelalte la care ai participat?*

La topcoder e foarte important sa scrii codul repede. La olimpiade, niciodata nu ma grabeam sa scriu codul, preferam sa ma concentrez sa fiu sigur ca e corect; ba mai mult, de multe ori scriam si generatoare de teste, si variante mai incete de rezolvare cand se putea, ca sa verific programele.  La topcoder nu poti sa faci asta si mai pierzi cateodata din greseli mici; antrenamentul conteaza foarte mult. In rest, problemele nu mi s-au parut cu mult diferite fata de ce eram obisnuit.

La Topcoder e foarte important sa scrii codul repede. La olimpiade, niciodata nu ma grabeam sa scriu codul, preferam sa ma concentrez sa fiu sigur ca e corect; ba mai mult, de multe ori scriam si generatoare de teste, si variante mai incete de rezolvare cand se putea, ca sa verific programele.  La topcoder nu poti sa faci asta si mai pierzi cateodata din greseli mici; antrenamentul conteaza foarte mult. In rest, problemele nu mi s-au parut cu mult diferite fata de ce eram obisnuit.

*De ce nu ai participat la ACM ICPC?*

Am participat si o data pentru MIT insa am fost pus exact inainte de concurs intr-o echipa cu doi americani pe care nu-i cunosteam deloc (al treilea membru al echipei lor pleca in finala topcoder si nu putea participa). Evident ca am fost dat la o parte, din moment ce ei nu stiau nimic despre mine. Am participat la faza regionala, unde toate problemele in afara de una erau foarte simple; le-au facut ei doi pe toate foarte repede. La cea grea ma gandisem deja dar nu m-au lasat sa o scriu eu, si tot unul din ei s-a apucat; m-am enervat ca stateam langa el si ii ziceam ca nu face ceva bine si nu ma asculta chiar daca aveam dreptate. Ma enerva ca se si complica, si scria un Dijkstra cu heapuri in STL cand putea sa il faca in N^2 si sa fie mult mai usor si clar. N-a iesit din prima, si a durat pana am rezolvat-o; intre timp, cealalta echipa de la MIT le facuse deja. Celelalte echipe n-au reusit sa faca nici macar toate problemele simple, deci oricum echipele de la MIT au iesit distantat pe primele locuri. Din pacate, chiar daca erau mai multe locuri de calificare, nu se putea califica decat o singura echipa de la fiecare facultate (nu mi-e clar de ce). In echipele de la MIT aproape toti fusesera in primii 10 la un IOI, deci nu e de mirare ca ne-am luptat intre noi.

Dupa aceea n-am mai participat. Motivul principal a fost ca imi manca destul de mult timp - cateva saptamani din semestru, cel putin o zi din weekend o pierdeam cu concursuri/antrenamente pt. ACM. Cum temele si alte chestii iau si ele destul timp mult, era prea mult. In plus, in fiecare an vin tipi proaspat dupa IOI, si cred ca e destul de greusa tii pasul. Si oricum e foarte greu sa iti gasesti colegi cu care sa mearga bine lucrul in echipa.

Dupa aceea n-am mai participat. Motivul principal a fost ca imi manca destul de mult timp - cateva saptamani din semestru, cel putin o zi din weekend o pierdeam cu concursuri/antrenamente pt. ACM. Cum temele si alte chestii iau si ele destul timp mult, era prea mult. In plus, in fiecare an vin tipi proaspat dupa IOI, si cred ca e destul de greu sa tii pasul. Si oricum e foarte greu sa iti gasesti colegi cu care sa mearga bine lucrul in echipa.

*Ai fost de doua ori la internship pe vara la Google, cu ce impresii ai ramas?*

Nu cred ca mi-ar placea sa lucrez full-time la Google. Cred ca depinde destul de mult de proiect, insa pare ca pana la urma ce faci tu nu conteaza asa de mult. Probabil ca asa e peste tot.. In comparatie cu majoritatea companiilor, probabil ca foarte bine la Google; imi displace totusi stilul asta american (sau poate nu e doar american?) de a sta toata ziua la servici. Eu prefer sa lucrez in continuu si sa plec cat mai repede acasa, ca am lucruri mai bune/placute de facut.

Nu cred ca mi-ar placea sa lucrez full-time la Google. Cred ca depinde destul de mult de proiect, insa pare ca pana la urma ce faci tu nu conteaza asa de mult. Probabil ca asa e peste tot.. In comparatie cu majoritatea companiilor, probabil ca e foarte bine la Google; imi displace totusi stilul asta american (sau poate nu e doar american?) de a sta toata ziua la servici. Eu prefer sa lucrez in continuu si sa plec cat mai repede acasa, ca am lucruri mai bune/placute de facut.

Majoritatea par ca stau la servici 10-11 ore din care 2-3 freaca menta. Ma rog, probabil ca nu mi-ar placea sa lucrez full-time nicaieri si de-aici vine problema :)
*Poti sa ne zici un proiect software misto la care ai lucrat?*

mininova
theonion

*Ai ceva carti de programare preferate?*
Introduction to Computational Geometry, de Shamos si Preparata.
Theory of Computation, de Sipser.

 
*ar carti ce nu au legatura cu programarea?*

*Dar carti ce nu au legatura cu programarea?*

Maximum Boost de Corky Bell :)

private

protected

2554