Interviu cu Radu Berinde - partea a doua

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?

Pe de-o parte, esti mult mai relaxat si distantat de ce se intampla in concurs; pe de alta parte, trebuie sa te gandesti foarte bine la ce faci, pentru ca deciziile tale afecteaza multi oameni. In rest nu prea vad ce comparatie sa fac intre cele doua activitati, sunt foarte diferite..

Cum se compune o problema pentru concurs?

Mi se pare destul de greu (si frustrant) sa scoti o problema buna; e ceva la care trebuie sa te gandesti in timp, si apoi sa te decizi unde/cand sa o propui. Sunt mai multe variante de compunere a unei probleme: una e sa te gandesti (probabil pornind de la o problema pe care o cunosti) la o cerinta noua, apoi sa te gandesti cum s-ar putea rezolva. Astfel e destul de greu sa nimeresti o cerinta buna, insa in gasirea rezolvarii pot sa apara idei noi.

Alta varianta e sa te gandesti la o idee pe care vrei sa se bazeze solutia, si apoi sa te gandesti la ce ar trebui sa ceara o problema care se rezolva in modul respectiv. Astfel e mai usor sa scoti problema, dar idei noi de rezolvare par mai greu (din moment ce solutia e oarecum deja fixata).

Pentru cei ce participa la concursuri pe infoarena, esti cunoscut prin "jmenurile de implementare" pe care le invata din sursele tale. Poti sa ne povestesti de unul dintre aceste "jmenuri"?

Regula de baza cand incerci sa optimizezi un program (in afara de a imbunatati algoritmul) e sa fii atent numai la partile din program care folosesc majoritatea timpului de executie. Mi se intoarce stomacul pe dos cand vad oameni care "optimizeaza" inlocuind in orice loc posibil inmultirile cu operatii pe biti, sau alte chestii asemanatoare (de parca nu le-ar optimiza oricum compilatorul). Codul trebuie sa fie cat mai usor de citit si inteles - asa e cel mai probabil sa iasa corect (si degeaba merge repede daca e gresit). Cand vrei sa optimizezi, te concentrezi pe ceea ce conteaza. De obicei este vorba de cateva linii de cod si e inutil sa optimizezi orice altceva in afara de aceste linii. Era o vorba care suna ceva de genul: in majoritatea cazurilor, 99% din timpul de rulare este petrecut in 1% din liniile de cod.

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

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.

Care sunt cursurile ce ti-au placut mai mult in facultate (si de ce)?

Mi-au placut materia la multe cursuri. La unele mi-au displacut lucruri legate de cerinte, proiecte finale, etc. insa materia mi-a placut la majoritatea cursurilor de informatica.

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

Cum e viata de stundent la MIT? Cum se imbina munca cu distractia?

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.

De ce nu ai participat la ACM ICPC?

N-am ajuns nicaieri, dar asta nu inseamna ca n-am participat. Am participat o data pentru Politehnica cu Marius Andrei si Mugurel Andreica; am fost primii care nu ne-am calificat. Am avut ghinion la o problema simpla care nu iesea deloc si la alta care avea o greseala in enunt si am pierdut mult timp rezolvand practic alta problema. "Ghinion" poate insemna si ca totusi nu ne antrenasem foarte mult (nu cat ar fi trebuit).

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

Nu am mai lucrat demult la un proiect; pe la inceputul liceului eram pasionat de grafica 3d, si am facut un engine 3d care citea harti de quake1 si apoi quake3 si te puteai plimba prin ele.

Care sunt programele de pe calculator care le folosesti cel mai des, pt programare si in rest?

Lucrez in Windows XP dar am mai tot timpul un Slackware deschis intr-un VMware (si folosesc X-Win32 in loc de X). Documentele/temele le scriu in linux, cu vim si latex (si xdvi). In Windows nu folosesc mult Total Commander (fostul Windows Commander). Programe mici le scriu in linux, folosesc vim si gcc. Mai lucrez in Eclipse si in Visual Studio din cand in cand.

Care sunt siteurile tale preferate?

infoarena :p
howstuffworks
wikipedia
mininova
theonion

Ai ceva carti de programare preferate?

Introduction to Computational Geometry, de Shamos si Preparata.
Theory of Computation, de Sipser.

Dar carti ce nu au legatura cu programarea?

Maximum Boost de Corky Bell :)

Cat timp petreci in fata calculatorului?

Mult prea mult.

Alte pasiuni inafara de programare?

Acum sunt pasionat de mesterit la masini, lucrez la masina cand am timp si cand nu e prea frig afara. Am schimbat sau imbunatatit pana acum tot felu de chestii - componente de suspensie, etriere, discuri de frana, arbore cu came, chestii de la esapament, tot felu de relee si circuite - si inca merge :) Cred ca daca as avea timp si bani, un timp destul de mare as face numai asta.

Cat impingi la piept?

Haha, cel mai mult am impins 120kg la declinat, dar asta s-a intamplat cu (prea) mult timp in urma..

Te mai intorci in Romania sau ramai in State?

In viitorul apropiat probabil ca voi ramane in State. Mai departe e greu de spus, cred ca depinde de prea multe lucruri pe care nu pot sa le prevad. In orice caz, am pastrat contactul cu prietenii din Romania, si il voi pastra in continuare indiferent de ce se va intampla - deci intotdeauna voi avea motive sa ma intorc.

Ce faci dupa ce termini facultatea?

Nu stiu inca. Cred ca voi mai face un an pentru master, apoi probabil voi lucra in State, cel putin pentru un timp.

Multumesc pentru interviu!