Blog infoarena

Viata de dupa olimpiade (II) - Industria de tehnologie

domino
Mircea Pasoi
01 februarie 2012

Acesta este al 2-lea post din seria “Viata de dupa olimpiade?”. Citeste si partea 1.

Industria de tehnologie

Despre ce e vorba?

Ca “software engineer” bun esti intr-o pozitie extraordinara in momentul de fata. Uite ce zice Joel Spolsly:

“education system is massively failing us: it’s not producing even remotely enough programmers to meet the hiring needs of the technology industry. Not even remotely enough. Starting salaries for smart programmers from top schools are flirting with the $100,000 mark. Supply isn’t even close to meeting demand.”

El vorbeste de sistemul de US, dar se aplica in toata lumea. Nu sunt destui programatori buni in lume pe cat pot angaja companiile de tehnologie. Un trend trecator? Toate semnele arata ca suntem abia la inceputul revolutiei digitale/tehnologice, un moment istoric in timp, cel putin la fel de important ca revolutia industriala.

Daca ti-a placut sa scrii cod, sa implementezi probleme, sa faci aplicatii (web, mobile, etc.) si esti genul care “Get Things Done”, atunci o cariera in industrie este mult mai potrivita pentru tine. Daca esti bun (ex: ai premii pe la concursuri, olimpiade - nu e obligatoriu totusi) o sa fii foarte cautat si o sa fii tratat ca un rege: salariu bun (incepe de la $80.000-$120.000), multe beneficii (mancare gratis, asigurare de sanatate, vacanta, cursuri, etc.) si “stock” (actiuni din companie).

Daca ai noroc poate prinzi si “loteria de stock”, caz care poti sa faci milioane de dolari din “stock” daca 1) stai 4 ani (ca sa primesti tot stock-ul), 2) valoarea stock-ului creste foarte mult de cand tu te angajezi si 3) compania se listeaza la bursa. Exista cateva exemple de oameni de pe la olimpiade care au prins asta (Cristi Francu si Catalin Francu - Google, 2002; Florin Ratiu - Facebook, 2007; eferLiviu Ciortea efer - Facebook, 2008).

Chiar daca nu prinzi loteria, tot ai sa inveti o gramada. La companiile cu un impact mare exista probleme foarte interesante (si grele) pentru ca au foarte multe date si folosesc tehnologii “state of the art” (MapReduce, BigTable, Hadoop, etc.). Poate erai “superstar” in liceu sau facultate, dar intr-un astfel de mediu, o sa ai mereu de la cine invata, mai ales in primele luni. Se zice ca “great people go to Google to be average” :)

Personal, eu recomand o companie cat mai mica, dar cu challenge-uri foarte mari! Astfel, poti sa inveti de la altii mai buni, dar sa si ai o contributie foarte mare in companie. De exemplu, Dropbox are numai 200+ de angajaţi, Twitter 750+ de angajati, Facebook peste 3K+, Google peste 32K+ si Microsoft are 90K+.

Cum ajung acolo?

Din fericire nu iti trebuie prea multa scoala si nici nu trebuie sa fie facuta in afara. E o industrie destul de “meritocratica”, nu conteaza ce rasa esti, de unde vii, cine sunt parintii tai, cati bani ai, etc., conteaza doar sa faci treaba. Poti sa ai oferta foarte buna chiar daca ai facut doar facultatea (fara master sau PhD) in Romania. Cel mai important e sa te pregatesti bine pentru interviuri (algoritmica, coding, systems), subiect despre care s-a mai scris destul pe blogul asta.

Nu esti convins? Pe timpul facultatii poti face internship (unu sau mai multe) la o gramada de companii (Twitter, Facebook, Google, Microsoft in afara, Adobe, Amazon, BitDefender in Romania) si poti sa vezi care-i mediul de lucru. Esti bine platit ca intern, si chiar ai sanse mai mari la o pozitie de full-time pentru ca oamenii au vazut cum e sa lucreze 3 luni cu tine (mai bine decat si-ar putea da seama dupa 5-6 interviuri de 45 de minute).

Daca te-ai convins, pasul urmatorul e aproape unic determinat: nu are rost sa stai in Romania. Daca iti place mai mult lifestyle-ul (petreceri, vacante, mai putina munca), atunci alege Europa, New York sau Seattle. Daca vrei sa impingi limitele tehnologiei, sa fii acolo unde se inventeaza viitorul tehnologiei zi de zi, sa schimbi lumea, atunci trebuie sa fii in Silicon Valley. Un mic sfat: daca alegi US, fa tot posibilul sa iti iei green card (dureaza 3-5 ani), ca sa te poti angaja unde vrei tu apoi.

Desigur, trebuie sa mentionez ca Twitter (compania care a cumparat Summify) angajeaza din greu, contactati-ma (mircea.pasoi [at] gmail.com) daca sunteti interesati :)

Cu cine sa mai vorbesc?

CosminCosmin Negruseri Cosmin are foarte multa perspectiva in domeniul asta, fiind la Google din 2006. In plus, vezi lista de olimpici, majoritatea sunt angajati pe la companii din industrie si pot sa-si dea cu parerea.

 Comentarii (22)

Code golf challenge: logaritm

Cosmin
Cosmin Negruseri
31 ianuarie 2012

Code golf e o intrecere ce are scopul de a implementa un algoritm folosind un numar minim de caractere.

Va propun sa rezolvam urmatoarea problema de interviuri in comentarii:

Sa se implementeze functia logaritm in baza 2 din x cu precizie de 4 zecimale unde x e un numar real pozitiv. Sunt permise doar umatoarele operatii matematice +,-,*,/,sqrt.

 Comentarii (9)

Categorii:

Viata de dupa olimpiade (I) - Mediul academic

domino
Mircea Pasoi
27 ianuarie 2012

Bun, dupa 3 ani intensi cu balaur.ro si summify.com am un moment de pauza si vreau sa discut putin despre optiunile de cariera a unui pasionat de informatica.
Sa zicem ca am participat la concusuri tot liceul (eventual si in facultate), poate am luat si niste premiii sau medalii… ce fac acum cu viata mea? Nu stiu cati au avut problema asta, dar pentru mine a fost un mare semn de intrebare dupa terminarea liceului si mi-a luat mult timp sa gasesc niste raspunsuri satisfacatoare. Asadar, am facut acest (scurt) ghid bazat pe experientele mele, poate e de ajutor.

Evident, tot ce scrie aici sunt parerile mele personale, nu sunt adevaruri absolute, probabil multe idei sunt chiar gresite - nu e un ghid “how-to”, doar food for thought. Deci, sa incepem...

Mediul academic

Despre ce e vorba?

Cred ca mediul academic se potriveste in special celor carora le-a placut partea teoretica de “computer science”, sa citeasca paper-uri, sa se gandesca toata ziua la probleme si idei, dar nu prea le-a placut sa le si implementeze in cod.

In principiu, dupa multa scoala (PhD), poti sa ajungi researcher intr-o facultate (caz in care trebuie sa fii si profesor si sa petreci vremea cu studenti de toate felurile) sau intr-un laborator de research (unde nu trebuie sa predai).

Daca esti cercetator “world class” intr-un domeniu mai popular poti sa ai o viata foarte buna (salariu mare, calatoresti in toata lumea la conferinte), in schimb daca esti “mediu” poate fi destul de frustrant dupa atatia ani petrecuti in scoala. Pe langa asta, am inteles ca mediul academic este destul de politic, conteaza sa stii profesorii care trebuie, trebuie sa astepti sa plece de pe posturi ca sa avansezi, etc.

Cred ca alegerea asta trebuie facuta doar daca esti 100% convins ca asta e pasiunea ta, pentru ca este un drum foarte lung, destul de greu (faci foarte putini bani, inclusiv la PhD) si riscant. Daca esti convins, bravo tie, ideea in sine este foarte nobila si o sa poti sa zici ca ai impins omenirea si stiinta inainte intr-un anumit domeniu.

Cum ajung acolo?

Primul pas e sa pleci cat mai repede din tara la o scoala din afara (as recomanda US). Trebuie sa faci undergraduate, si master si PhD si daca poti sa faci cat mai multe din astea in afara, e mai bine. In plus, ajuta sa ai cateva paper-uri (lucrari de cercetare) in undergraduate pt admitere la master si PhD.

Cu cine sa mai vorbesc?

Experienta mea in acest domeniu este bazata doar pe ce am citit si auzit de la alti oameni. Cateva exemple bune de oameni care au trecut prin asta ar fi mpatrascuMihai Patrascu mpatrascu, flmaneaFlorin Manea flmanea, azotlichidAdrian Vladu azotlichid si Alex Andoni, si ii invit sa-si dea cu parerea in comentarii.

 Comentarii (14)

Când matematica își bagă nasul în lumea muzicală

wefgef
Andrei Grigorean
25 ianuarie 2012

Orice om pasionat de matematică o sa îţi spună „Matematica e peste tot!” şi nu te-ar minţi cu nimic. Lumea în care trăim este de o exactitate impresionantă, chiar şi în haos găsim explicaţii şi formule.

După această premisă, nu e de mirare că matematica există şi în muzică: structuri repetitive, artişti care compun piese după raportul de aur, frecvenţe, tempo şi aşa mai departe. Totuşi, când un matematician se implică în muzică şi are scopul de a compune cea mai proastă simfonie scrisă vreodată trebuie să îţi dai seama că va reuşi.

iNFOMUSIC.ro a publicat un articol interesant despre Scott Rickard, care la TEDxMIA în 2011 a prezentat publicului ceea ce el numeşte „Muzica ce putea fi scrisă numai de un matematician”. Folosind teoria numerelor prime şi eliminând orice structură repetitivă, matematicianul a creat cea mai proastă muzică. Provocarea lui este să găsim ceva reptitiv sau plăcut în compoziţia lui.

Vă recomand să citiţi articolul, să urmăriţi filmuleţul cu explicaţii şi să ascultaţi „capodopera” lui Scott Riockard pe "iNFOMUSIC".

 Comentarii (2)

Categorii:

Secretele negocierii unei oferte de munca

Cosmin
Cosmin Negruseri
18 ianuarie 2012

Dupa Sfaturi pentru interviuri de programare si cum sa scrii un CV continui cu structura ofertei de job de la companii din Silicon Valley si negocierea ei.

Ai primit o oferta de munca. Felicitari! Mai ai putin de lucru.

O greseala frecventa pe care o fac absolventii de facultate este ca nu isi negociaza salariul primului job pe care il iau.

Desi la firme bune oferta initiala va fi destul de atractiva , ea este doar startul negocierii şi de multe ori puteti obtine ceva mai bun. Firmele de soft au costuri foarte mari pe partea de recrutare, astfel preferă să accepte negocierea unei oferte deja extinse decât să o refuze şi să ia procesul de recrutare de la inceput pentru a gasi alt om.

Structura unei oferte de job
Dacă ai trecut cu bine de interviuri şi vei fi angajat, ţi se va extinde ceea ce se numeşte “o ofertă”. Compania îţi face o propunere pe care tu o poţi accepta sau nu. În principiu, propunerea este alcătuită din:

  • Salar de baza: specificat brut si pe an.
  • Pachet de actiuni: de obicei esalonat pe 4 ani.
  • Bonus de relocare: Daca nu te angajezi in acelasi oras in care esti acum de obicei primesti un bonus de relocare.
  • Bonus de angajare: Ignorati la negociere bonusul de angajare. E mai bine sa primiti salariul initial ceva mai mare.
  • Vacanta: In State se dau mult mai putine zile de vacanta ca in Romania. In unele firme incepi de la 12 zile. Cateodata poti negocia numarul zilelor de vacanta. Astfel am cativa prieteni ce au obtinut o saptamana de vacanta in plus pe an dupa negocieri.
  • Bonus anual: aici e cam la fel pentru toata compania, nu prea e loc de negociere.
  • Beneficii: Din ce in ce mai multe companii dau mancare gratis, sucuri, cafea si o gramada de alte chestii. Nu sunt o componenta importanta da e util sa stii de ele.

Nivelul pachetului
Componentele de mai sus pot varia dupa componente cum sunt: scoala care ai facut-o (MIT vs UNIBUC), notele primite la scoala conteaza, punctul asta poate fi dezbatut, dar notele bune arata ca ai vointa sa faci bine si lucruri care nu iti plac, nivelul de scolarizare (undergrad, master, phd), experienta care o ai in industrie. Performanta de la interviuri e si ea importanta. Te sfatuiesc sa te pregatesti bine. Performanta in interviu e singura componenta pe care o poti imbunatati intr-un interval de cateva saptamani.

Sunt artist, am valoare mânca-ţi-aş
Înainte de orice negociere ar fi bine să îţi cunoşti valoarea reală, altfel nu ai o poziţie de putere (şi poate oferta chiar este la valoarea ta :-) ).
glassdoor si payscale sunt doua siteuri cu informatii destul de bune pentru nivelele salariale la firme din state.
Colegii tai probabil isi cauta si ei de lucru in acelasi timp, vezi ce oferte au primit ei.
Cel mai important sfat este sa ai mai multe oferte competitive de la companii de top. Dacă ţi-au fost extinse oferte de la mai multe companii de talia Facebook sau Google eşti într-o poziţie excelentă să poţi spune “dar ia uite ce îmi oferă ceilalţi, voi ce părere aveţi?” :-) Nu exagera şi fi onest cu cele două companii de la care ai oferte, altfel s-ar putea să le superi pe amândouă dacă te dai prea mult în bărci.

Cum să pui problema
Doar mentiunea ca ai oferta si de la alta firma poate afecta valoarea ofertei. De asemenea e de recomandat sa spui ca intervievezi cu alte firme. Atunci aplicatia ta de job poate deveni prioritara si vei trece prin proces mai repede.
O fraza folosita frecvent in negocieri este "Imi place foarte mult locul asta de munca, dar
prietena/nevasta/parintii insista pentru locul celalalt care are oferta salariala mai potrivita pentru noi."
Am discutat deja cazul ofertelor explozive si sfatul pe scurt e sa ceri timp mai mult de decizie.

Anecdote
Un prieten a fost respins in faza de resume screening la Microsoft, la primirea mailului a multumit si a zis ca va accepta oferta Google. Urmatoarea zi cei de la Microsoft i-au cumparat bilet de avion pentru interviuri in Seattle.
Altul doar a mentionat la obtinerea unei oferte de la Facebook ca intervieveaza si cu Google si oferta de job i-a fost revizuita pe loc la una mai atractiva.

Voi ati negociat prima oferta de munca pe care ati primit-o?

 Comentarii (10)

Categorii:

Raspuns in interviu

Cosmin
Cosmin Negruseri
15 ianuarie 2012

Un thread popular pe stack overflow din 2008 enumera raspunsuri slabe din interviuri tehnice. Unele sunt destul de amuzante.

Mie mi-a placut mult urmatorul:

( From a very pleasant Nigerian national who came in for a technical interview )
"Would you like to hear about my implementation of a mass e-mailing program?"

 Comentarii (9)

Categorii:

Cautarea ta binara este gresita

Cosmin
Cosmin Negruseri
07 ianuarie 2012

Cautarea binara este printre primii algorimi divide and conquer studiati la informatica. Algoritmul rezolva problema gasirii unui element x in un sir sortat A folosind monotonia elementelor pentru a injumatati la fiecare pas spatiul de cautare. Ideea algoritmului e simpla, insa aproape fiecare concurent olimpiada de informatica are cate o poveste cum a pierdut puncte la o problema din cauza implementarii. Majoritatea studentilor de informatica si chiar doctoranzilor, dupa cum ne spune Jon Bentley in Programming Pearls, nu reusesc sa scrie o cautare binara fara probleme.

Implementarile pot avea multe buguri in zone cum ar fi:

  • intrare ciclu infinit
  • conditii gresite de terminare
  • siruri scurte de lungime 0, 1, 2
  • siruri in care x nu exista sau x apare de mai multe ori
  • siruri in care x apare in apropiere de inceput sau final

Optimizari premature
Am vazut tot felul de variante, de exemplu unii testeaza daca a[mid] e egal cu x si scurt circuiteaza cautarea. Aceasta optimizare nu ajuta in cazul general, doar complica codul. Alta varianta e sa reduci mai mult problema folosind hi = mid - 1 sau lo = mid + 1. Optimizarea e mica si adauga un pas logic in plus la care trebuie sa fii atent. Cazurile la una din marginile sirului pot deveni mai dificile sau putem avea probleme de genul hi devine mai mic decat lo.

Multe implementari sunt "blindate" ca să evite bug-urile de mai sus. Problema e că lumea le blindează cu cod duplicat si error prone, repetand conditii.

Variante ale problemei
Exista versiuni diferite cum ar fi gasirea primei sau ultimei aparitii a lui x in sirul sortat, gasirea predecesorului sau succesorului valorii x in sir.

O solutie isteata folosita de membrii infoarena utilizeaza puterile lui 2.

int binary_search(int[] A, int x) {
  int i, step, N = A.length;
  for (step = 1; step < N; step <<= 1);
  for (i = 0; step; step >>= 1)
    if (i + step < N && A[i + step] <= x)
    i += step;
  if (A[i] == x) 
    return i;
  else
    return -1;
}

Aceasta varianta de implementare este eleganta insa mie nu imi place foarte tare. Dezavantajul principal este lizibilitatea codului.

Cum implementezi simplu, corect, clar si flexibil o cautare binara

Folosim un invariant in bucla cautarii binare, adica o asertiune care e adevarata de fiecare data cand intram in bucla. Pentru cazul nostru acest invariant e ca lo indica spre un element care e mai mic ca x sau spre -1 si hi indica spre un element mai mare sau egal cu x sau spre A.length. Pe scurt A[lo] < x \le A[hi] (consideram A[-1] = -\infty si A[A.length] = +\infty)

Sa vedem cum arata codul:

int binary_search(int[] A, int x) {
    int hi = A.length, lo = -1, mid;
    while (hi - lo > 1) {
      mid = (lo + hi) / 2;
      if (A[mid] < x)
        lo = mid;
       else
         hi = mid;
    }
    if (hi == A.length || A[hi] != x)
        return -1;
    else
        return hi;
}
  • linia 2: setam pe hi si lo inafara sirului, astfel invariantul e indeplinit si nu trebuie sa tratam cazuri speciale.
  • linia 3: conditia de continuare a buclei e hi - lo > 1. Invariantul ales face ca hi si lo sa fie tot timpul distincte. La fiecare pas distanta intre hi si lo se injumatateste, iar cand hi si lo ajung consecutive ca pozitii in sir putem lua o decizie.
  • linia 4: mid va fi tot timpul intre lo si hi.
  • linia 6: stim ca A[mid] < x si astfel facand atribuirea lo = mid micsoram spatiu de cautare si pastram invariantul
  • la linia 8 stim ca A[mid] >= x si putem face atribuirea hi = mid.
  • la linia 10 vedem daca x e in sir
    • in caz afirmativ putem sa returnam indexul hi
    • un caz negativ e cand ultimul element din sir e mai mic decat x. Atunci avem lo = A.length - 1 si hi = A.length
    • celalalt caz negativ e ca hi sa fie undeva in interiorul sirului si sa avem ca A[lo] < x < A[hi]

Am scapat de greselile ce le mentionam mai sus, pentru ca invariantul ne demonstreaza corectitudinea algoritmului nostru.
Ideea e foarte flexibila, putem schimba usor invariantul pentru a aborda variantele problemei mentionate. De exemplu pentru a gasi ultima pozitie din sir mai mica decat x putem folosi invariantul A[lo] \le x < A[hi]

Aceasta abordarea este detaliata in cartea Programming Pearls de Jon Bentley pe care v-o recomand.

Linkbaitul din titlu :)
Daca nu v-am convins de afirmatia din titlu, va mai zic ca, in 2006, Joshua Bloch, cel care a scris algoritmul de cautare binara in java.util.Arrays, a descoperit un bug in implementare. Acest bug aparea in majoritatea cautarilor binare sau a sortarilor prin interclasare scrise in ultimii 20 de ani. Lucrand la Google el a ajuns sa sorteze siruri de doua miliarde de numere. La pasul mid = (lo + hi) / 2 s-a depasit Integer.MAX_VALUE care e 2147483647 si codul a declansat o exceptie. Putem rezolva bugul folosind mid = lo + (hi - lo) / 2 in loc de mid = (hi + lo) / 2.

Stiu ca “You can’t teach an old dog new tricks” dar sper ca v-am convins de utilitatea invariantilor.

Despre cautare binara pe numere reale sau metoda bisectiei in episodul urmator :).

Intrebari: Voi ati avut vreodata probleme cu cautarile binare? Ce varianta folositi?

 Comentarii (22)

Categorii:

Carti pentru programatori

Cosmin
Cosmin Negruseri
29 decembrie 2011

Un prieten mi-a cerut recent cateva recomandari de carti de programare. Cresti cel mai rapid atunci cand codezi mult, duci un proiect de la inceput la sfarsit, lucrezi la proiecte variate, inveti de la colegi. Rar ai timp sau chef sa citesti o carte tehnica de la un capat la altul. Dar cum tot am fost intrebat va dau lista mea de recomandari:

Code complete contine multe subiecte care nu sunt abordate prea mult in facultate dar sunt folosite de programatori frecvent cum ar fi unit testing, coding style, software design, debugging etc.. Cartea contine multe reguli de bun simt, dar e bine ca sunt organizate si puse impreuna.E buna pentru un student care a lucrat doar laboratoare sau proiecte mici la scoala si vrea sa se maturizeze putin in plan profesional.
Effective C++ e o carte importanta daca lucrezi in C++ in industrie. Contine o gramada de sfaturi utile si e mult mai scurta decat alte carti care incearca sa faca acelasi lucru cum ar fi Thinking in C++ sau The C++ Programming Language.
Effective Java are multe subiecte din Java detaliate. E scrisa de Joshua Bloch care a facut pachetul de colectii in Java iar acum lucreaza la Google ca Chief Java Architect. Ea aduce cititorul de la incepator competent in Java la un programator avansat. Mi se pare mai la obiect decat Thinking in Java care foloseste destul de mult text ca sa explice o idee.
Design Patterns e o carte importanta pe care multi programatori o au pe raft, dar putini reusesc sa o citeasca. E greoaie, dar are concepte interesante. Eu am reusit sa parcurg mare parte din ea facand un curs de Desing Patterns la servici, unde impreuna cu alti colegi trebuia sa citim cate un capitol si sa il discutam. Astfel recomand sa incercati sa o parcurgeti in grup. Pe langa ideile din carte, dintre care unele nu sunt foarte complicate, ea ofera programatorilor un limbaj comun.
Cerintele unui proiect de cateva luni se schimba in mod continuu. Astfel o mare parte a muncii unui programator e sa refactorizeze codul. Refactoring: Improving the Design of Existing Code contine multe sabloane care fac partea de modificare si rescriere usoara. Pe langa asta contine o lista de asa numite "code smells", niste sabloane care iti spun ca ai putea imbunatati calitatea codului pe unele locuri. Multe din acestea sunt evidente, dar din nou, cartea ofera un limbaj comun pentru programatori.
Programming pearls e o carte foarte buna pe subiectul algoritmica in industrie. Stilul explicatiilor este foarte clar si curat.Se discuta probleme frumoase si nu exagerat de dificile. Are cateva capitole alocate structurilor de date si compelxitatii algoritmilor precum si unul despre "back of the envelope computations". Este foarte abordabila de incepatori si are destule trucuri si pentru avansati.
Introduction to algorithms sau Cormen cum ii zic romanii, e biblia algoritmilor. Contine material mult, tratat bine. Astfel parcurgerea ei poate dura multa vreme. Unele demonstratii sunt ceva mai lungi decat ar trebui, iar accentul e pus mai mult pe rigoarea matematica decat pe intuitia din spatele demonstratiilor. As recomanda oricui parcurgerea problemelor, si este cartea de baza pentru pregatirea la olimpiade.
The art of computer programming e probabil cea mai cunoscuta carte de informatica. Are un continut foarte misto, dar poate prea orientat matematic. Ea din nou e o carte pe care multi programatori o au pe raft dar nu o citesc. Eu mi-am petrecut bucata buna din timpul liber in liceu uitandu-ma peste probleme, dar acum nu cred ca as mai avea timpul liber si setea de cunoastere sa o parcurg.
The non-designer`s design book e carte scurta si la subiect pe tema designului. E plina principii de design fundamentale. Expuse frumos si cu exemple. Cunostintele de design sunt foarte utile pentru programatori pentru ca ai frecvent nevoie de interfetele web sau desktop adresate utilizatorilor.
The mythical man-month e o carte clasica despre managementului proiectelor software. Contine mai multe principii si discutii in jurul acestui domeniu. Un principiu interesant porneste de la ideea ca, cu 9 femei nu poti face un copil in o luna. Aplicat la proiecte software, ideea evidenteaza ca adaugarea de ingineri la un proiect care e pe cale sa nu isi atinga termenul limita nu ajuta proiectul.
Cracking the code interview e cea mai buna carte de pregatire pentru interviuri. V-am mai recomandat-o si in Sfaturi pentru interviuri de programare Descrie procesul interviurilor si are o gramada de probleme cu solutii. Ele sunt la nivelul de dificultate al interviurilor din Bay Area. Alte carti ca Programming Interviews Exposed au probleme ceva mai banale.

Voi ce parere aveti despre cartile de mai sus si ce alte carti ati recomanda unui student la info ce e la inceput de drum?

 Comentarii (14)

Categorii:

Parcurgere

pauldb
Paul-Dan Baltescu
23 decembrie 2011

Am vazut ca problema precedenta pe care am postat-o a starnit multe discutii interesante, asa ca va voi mai impartasi inca o intrebare de interviu mai deosebita:

Se da un arbore binar reprezentat astfel:
struct Node {
    ...
    Node* left, right;
}

Sa se realizeze o parcurgere in inordine a arborelui folosind memorie suplimentara O(1).

Va invit sa discutati problema la comentarii. Raspunsul la intrebare se poate gasi pe internet asa ca va rog sa nu postati link-uri sau idei care nu va apartin. :-)

 Comentarii (10)

Categorii:

Rezolvare pentru "suma in triunghi" si functii convexe

Cosmin
Cosmin Negruseri
21 decembrie 2011

Rezolvarea pe scurt:
Functia 2 dist(M, A) + dist(M, B) + dist(M, C) e o functie convexa. Functiile convexe isi ating maximul pe marginea domeniului de definitie. Astfel e de ajuns sa evaluam functia in punctele A, B si C si gasim ca maximul este 13 si e realizat in punctul C.

Functii convexe:
Problema este pretext pentru a discuta notiunea de functie convexa. O astfel de functie are proprietatea ca pentru oricare doua puncte de pe graficul ei, graficul se afla sub segmentul determinat de cele puncte. Mai formal, daca f:X->R unde X e un domeniu convex (interval etc.) atunci pentru oricare doua puncte x1 si x2 din X si orice t din intervalul [0, 1] avem ca f(tx_{1} + (1-t)x_{2}) \le tf(x_{1}) + (1-t)f(x_{2}). X poate fi orice spatiu vectorial, R, interval in o dimensiune, poligon convex in doua si asa mai departe.

O proprietate importanta a functiilor convexe este ca au doar un minim local care este si global. Astfel problema minimizarii valorii unei functii multi dimensionale este mai simplu de rezolvat pentru functii convexe. Ea apare frecvent in machine learning. Functiile generale nu sunt usor de minimizat. Nu au o forma care poate fi rezolvata matematic sau sunt neregulate si au multe optime locale. Pentru a putea obtine solutii bune, de multe ori functiile generale sunt aproximate de functii convexe pentru care exista algoritmi eficienti de minimizare, cum ar fi cautare ternara pentru cazul unidimensional sau gradient descent pentru cazul general.

Rezolvarea mai detaliata:
Functia distanta euclidiana fata de un punct fix e o functie convexa.
demonstratie:
Vedem usor daca facem un grafic care este un con sau putem incerca sa ne uitam la derivate.

Suma a doua functii convexe este tot o functie convexa.
demonstratie:
f_{1}(tx_{1} + (1-t)x_{2}) \le tf_{1}(x_{1}) + (1-t)f_{1}(x_{2})
f_{2}(tx_{1} + (1-t)x_{2}) \le tf_{2}(x_{1}) + (1-t)f_{2}(x_{2})
=>
f_{1}(tx_{1} + (1-t)x_{2}) + f_{2}(tx_{1} + (1-t)x_{2}) \le t(f_{1}(x_{1}) + f_{2}(x_{1})) +
(1-t)(f_{1}(x_{2}) + f_{2}(x_{2}))

Astfel 2dist(M, A) + dist(M, B) + dist(M, C) e si ea o functie convexa.

Maximul pentru o functie convexa e realizat pe marginea domeniului de definitie.
demonstratie:
Din definitie, graficul intre x1 si x2 se afla sub segmentul determinat de (x1, f(x1)) si (x_{2}, f(x_{2})) astfel pentru x_{1} si x_{2} pe contur unul dintre cele doua puncte va fi mai sus decat toate restul din grafic.

Acum am demonstrat toti pasii din prima propozitie a articolului.

In graficul alaturat puteti vedea cum se comporta functia. Punctele A, B si C au coordonatele (0, 0), (3, 0) respectiv (0, 4), iar culoarea graficului reprezinta suma ceruta in problema.

Aveti aici codul in Octave cu care e generat.
dist = @(x, y, x1, y1) sqrt((x - x1).^2 + (y - y1).^2)
sumt = @(x, y) 2 * dist(x, y, 0, 0) + dist(x, y, 3, 0) + dist(x, y, 0, 4)
x = linspace(0, 3, 50)
y = linspace(0, 4, 50)
[xx, yy] = meshgrid(x, y)
contourf(xx, yy, sumt(xx, yy))

Cerinta de gasire a maximului e putin fortata pentru a face problema posibil de rezolvat in cap. Pentru ca in general la functii convexe cautam minimul. Putem avea maxime locale in orice colt al frontierei, deci pentru o frontiera cu multe colturi nu avem algoritmi eficienti.

Adapost2 se poate rezolva folosind idei din acest post.
Sper ca v-am deschis apetitul pentru functii convexe :).

 Comentarii (4)

Categorii:
Vezi pagina: 12345... 8910111213 1415161718... 3637383940 (394 rezultate)