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?

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:

struct Node {
    ...
    Node* left, right;
}

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

Rezolvarea pe scurt:
Functia 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 unde e un domeniu convex (interval etc.) atunci pentru oricare doua puncte si din si orice din intervalul avem ca . 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:


=>

Astfel e si ea o functie convexa.

Maximul pentru o functie convexa e realizat pe marginea domeniului de definitie.
demonstratie:
Din definitie, graficul intre si se afla sub segmentul determinat de si astfel pentru si 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.

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

O problema misto de la un baraj IMO:

Se da un triunghi ABC cu laturile AB = 3, AC = 4 si BC = 5. Se cere sa se determine punctul M in interiorul triunghiului ABC cu proprietatea ca suma 2MA + MB + MC este maxima.

Hai sa o rezolvam in sectiunea de comentarii.

Un coleg avea acum cativa ani training pentru a fi intervievator tehnic la Google. Ca parte a trainingului trebuia sa asiste la cateva interviuri coordonate de ingineri mai experimentati.

Unul dintre interviuri a avut o parte mai interesanta:

Candidatul, sa ii zicem Xing, tocmai terminase facultatea. CVul lui zicea ca are o medalie de aur la la olimpiada internationala de informatica. Intervievatorul nu stia prea multe despre olimpiade si a pus o intrebare clasica:

"Scrie un program care tipareste in cate moduri pot fi asezate 8 regine pe tabla de sah astfel ca ele sa nu se atace."

#include <cstdio>
main() {
  printf("92\n");
}

:)

Am auzit recent niste intrebari mai interesante care au aparut la interviuri la companii mari din zona IT si m-am gandit sa le impartasesc cu voi. Iat-o pe prima:

Se da un sir de N numere intregi. Sa se determine, in complexitate O(N), submultimea maxima ce contine elemente consecutive. De exemplu, pentru sirul 6 3 1 5 9 11 8 7 2, raspunsul este 5 6 7 8 9.

Va invit sa discutati problema in comentarii.

Un prieten mi-a pus recent intrebarea din titlu si am vrut sa imi ordonez putin gandurile pe tema asta.

Argumente pro agajare:

• independenta financiara. E foarte atractiv sa nu mai depinzi de parinti.
• curba de invatare rapida si cunostinte practice. Spre deosebire de facultate vezi imediat utilitatea lucrurilor ce le inveti.

Argumente contra:

• partea de invatare se termina rapid. In trei pana la sase luni cam inveti tot ce e de invatat.
• fiind junior, pentru multa vreme un angajat va avea parte de munca de jos.
• pierzi contactul cu facultatea. Foarte putini sunt in stare sa exceleze in acelasi timp la servici si la facultate. E foarte greu sa recuperezi cunostintele fundamentale pe care le poti acumula in facultate.
• nu vei putea aplica la joburi mai avansate unde e nevoie de statistica, machine learning, compilatoare etc. De asemenea nu mai ai optiunea internshipurilor.
• ajungi sa te blochezi intrun optim local. De exemplu, te angajezi ca QA sau ca web developer, lucrezi un an doi si apoi e greu sa schimbi jobul.

Desi pe termen scurt e un castig net, cei ce se angajeaza in timpul facultatii full time fac o decizie proasta in majoritatea cazurilor. Absenta unui job full time se poate suplini usor prin internshipuri pe vara, proiecte personale sau proiecte open source.

Voi ce motive pro si contra gasiti?

In martie 2007 roypalacios , un user de pe TopCoder ce avea rating in zona gri a clasamentului intreba pe forum daca exista participati pe site care sa fi ajuns de la nivelul de rating demarcat de cularea gri la cel demarcat de rosu.

Daca ati participat la concursuri pe TopCoder stiti ca diferenta intre cele doua nivele e ca de la cer la pamanat. Un participant care are ratingul in zona gri are probleme sa implementeze fara buguri o parcurgere a unui arbore pe cand unul cu rating in zona rosie are sanse bune la o medalie de aur sau argint la olimpiada internationala de informatica.

Acum cateva zile roypalacios a facut un update in threadul respectiv mentionand ca a reusit sa ajunga rosu.

Impresionant ce face munca pe parcursul a cativa ani

De curand mi-a zis un prieten o problema care mie mi s-a parut foarte interesanta si mi-a placut destul de mult si rezolvarea.

Avem un sportiv care a alergat 1000 m in 10 minute cu viteza neconstanta. Sa se demonstreze ca exista un interval de 5 min in care sportivul a alergat fix 500 m.

Rezolvarile le puteti trimite la tiberiu.savin at gmail.com

Update: Sportivul nu isi poate schimba viteza instantaneu, cu alte cuvinte daca definim functia f(x) = viteza sportivului in punctul x, atunci functia f este o functie continua.

Pentru că recent am tot văzut oameni puşi în situaţia unui ‘exploding offer’, m-am gândit că nişte sfaturi pe tema asta nu ar prinde rău. :-)

Americanii numesc 'exploding offer' o oferta care este făcută cu un deadline clar. “Fie accepţi oferta în următoarele trei zile, fie nu mai e valabilă”. În general, ofertele de tipul asta sunt o metoda de a pune presiune artificiala pe cei care nu au experienta cu negocierile şi a îi face să accepte oferte nu neapărat ideale.

Exploding offers apar în tot felul de situaţii
Un prieten a primit doua oferte de job de la aceiasi firma, una buna si una foarte buna dar limitata pe de patru zile pe care a acceptat-o.

Ele pot fi pe perioade scurte(zile) sau lungi(luni). Un alt prieten a primit oferta de internship in Romania. Firma ce oferea internshipul vroia raspunsul in o saptamana sau doua, iar candidatul avea programate interviuri de internship Adobe in doua saptamani. Facebook anul trecut vroia un raspuns final de la candidatii ce au primit oferte de internship pana la finalul lunii decembrie, in timp ce Google avea ultima runda de interviuri undeva in ianuarie, februarie.

Nu se rezuma doar la oferte de joburi, Vivi a primit o oferta limitata ca timp cand a vândut doizece.ro lui Calin Fusu.

De ce sunt făcute astfel de oferte?
Unul din scopuri este să te panicheze şi să te facă să acţionezi instictual. Sa iti limiteze timpul de informare si de aflare a nivelului ofertei pe piata curenta. Aşa că dacă te blochezi şi nu te informezi faci exact ce era intenţionat.

Alt scop al acestui fel de oferte este să te opreacă să foloseşti doi ofertanţi diferiţi pentru a licita unul împotriva celuilalt. O ofertă pe termen limitat face asta mult mai greu pentru că nu ai timp să tot faci drumul între cei doi care îţi fac oferte.

Câteva recomandări
Nu actiona sub presiune. Gândeşte calm, dacă te panichezi sigur nu o să te ajute cu nimic. Întreabă nişte prieteni cât de repede poţi, vezi dacă au trecut şi alţii prin asta.

Compara variantele si obtine cat mai multe date. Ai prieteni care au trecut prin asta? Stii pe cineva care a avut oferte asemănătoare? Ask!

Cere o extindere a termenului de decizie. Întrebatul este pe degeaba şi nu te costă nimic. Daca oferta are sens la un moment dat, ea ar trebui sa aiba sens si peste cateva saptamani.

Dacă toate astea nu merg şi nu ai altă opţiune, poţi accepta oferta verbal şi să continui căutarea unei oferte mai bune. Este o zonă de moralitate cam gri, dar dacă ai cuţitul la os şi chiar vrei, este şi asta o opţiune. In cazul joburilor la firme mari, nu e asa grav daca un candidat acceptă şi apoi se răzgandeste, dar trebuie să realizezi că firma respectiva va tine minte gestul asta.

Mersi Vivi pentru imbunatatirile semnificative aduse articolului.

Voi ati primit exploding offers? Cum le-ati abordat?