Despre Blog

# Probability shortlist

Cosmin Negruseri
18 iunie 2014

Here's a set of probability problems. Try to solve them in the comments section.

1. (von Neumann’s biased coin) You’re given a biased coin. It falls heads with an unknown probability p and tails with the probability 1 - p. Can you come up with a way to generate fair 0 and 1 results?
2. A rand5() function gives uniform integer results between 1 and 5. How can you use it to build a rand7() function? (microsoft interview)
3. Build a function rand(x, y, r) that returns a uniformly random point in the circle given by the (x,y) center and the r radius. (dropbox interview)
4. Build an algorithm that returns a uniform random permutation of numbers 1 to n. (google interview)
5. (Reservoir sampling) Given a stream of integers build an algorithm that returns a uniform random sample of size k using O(k) memory. (google interview)
6. (Coupon collector’s problem) Suppose a kid wants to collect all the cartoon characters in a kinder surprise series. Given that there are n different characters in total and they are distributed uniformly random. What's the average number of kinder eggs he has to buy so that the selection is complete. (twitter interview)
7. (Balls and bins problem) m balls are thrown into n bins. Each ball has 1/n probability of falling into each bin. What’s the expected number of empty bins? (twitter interview)
8. What’s the average number of times line 4 is executed if p is a random permutation of numbers 1 to n. (pinterest interview)
``````min = p[0]
for x in p:
if min > x:
min = x``````
Categorii:

# In memoriam Mihai Patrascu

Heidelbacher Andrei
05 iunie 2014

Astazi, 5 iunie 2014, se implinesc doi ani de la plecarea lui Mihai Patrascu pe drumul fara intoarcere, cunoscut in comunitatea informatica romaneasca pentru rezultatele lui impresionante la olimpiadele internationale de informatica (4 medalii de aur si 3 de argint) si pentru problemele lui originale.

Ca student la MIT, in 2005, a obtinut premiul pentru cel mai bun student in cercetare din SUA si Canada, iar cu lucrarea de doctorat a obtinut premiul pentru cea mai buna teza de la MIT. In 2012, Asociatia Europeana de Informatica Teoretica i-a acordat premiul Presburger pentru revolutionarea domeniului de structuri de date.

Mihai a fost un apropiat al comunitatii infoarena, a fost presedintele Comisiei Stiintifice a Balcaniadei (2011) si a Olimpiadei Europei Centrale (2009), membru al Comitetului Stiintific al Olimpiadei Internationale de Informatica (2011), s-a implicat in comisiile stiintifice ale mai multor olimpiade si concursuri nationale si a sustinut conferinte la universitati romanesti pe marginea rezultatelor sale in cercetare.

Rog toti utilizatorii infoarena sa pastreze un moment de reculegere in memoria lui Mihai.

Odihneasca-se in pace.

Categorii:

# Olimpiada Nationala de Informatica pentru Studenti 2014

Teodor Plop
20 mai 2014

In acest weekend, la Bucuresti a avut loc runda finala a primei editii a Olimpiadei Nationale de Informatica pentru Studenti. Au participat peste 20 echipe din tara, doua zile de concurs, aceleasi taste apasate si multe pizza consumate. Felicitari tuturor participantilor si multumiri sponsorilor si partenerilor nostri pentru implicare: Fundatia eMAG, Bitdefender, TechHub, Asociatia Studentilor la Matematica si Informatica, Facultatea de Matematica si Informatica, Universitatea din Bucuresti. Speram ca a fost o experienta placuta pentru toti si va asteptam si la anul, in numar cat mai mare!

Clasament Runda Finala

Clasament ACM-ICPC Faza Nationala

Poze

Categorii:

# Why your bisection search is wrong

Cosmin Negruseri
19 mai 2014

What is bisection search? The bisection method or bisection search is a numerical algorithm for finding a value x such that f(x) = 0, for a given continuous function f. It works by repeatedly bisecting an interval and choosing a subinterval that contains x. It's pretty simple and robust, but it has few gotchas.

Let's solve the following problem:

For a given number c find it's cubic root using the +, -, *, / operations.

Let's choose f(x) = x3 - c. f is continuous and x is the cubic root of c, when f(x) = 0. Thus, we can apply the bisection method.

``````def cubicRoot(c):
lo, hi = 0.0, c
while lo * lo * lo != c:
mid = (lo + hi) / 2
if mid * mid * mid < c:
lo = mid
else:
hi = mid

return lo``````

Any bugs? Well, quite a few. Try to spot as many as you can, before reading on.

You may notice the precision issue right from the start. We'll discuss it a bit later.

What else? The code doesn’t work for negative values of c. This is easily fixable:

``````def cubicRoot(c):
lo, hi = 0.0, c
while lo * lo * lo != c:
mid = (lo + hi) / 2
if mid * mid * mid < c:
lo = mid
else:
hi = mid

return lo

def cubicRoot(c):
if c < 0:
return - _cubicRoot(-c)
else:
return _cubicRoot(c)
}``````

What else? This code doesn't work for c = 1/1000. Why is that? We’re setting the cubic root upper limit to c (line 3). But, the cubic root of c in (0, 1) is larger than c, meaning the upper bound we’re setting is wrong.

Let's fix it:

``````def _cubicRoot(c):
lo, hi = 0.0, max(1, c)

while lo * lo * lo != c:
mid = (lo + hi) / 2
if (mid * mid * mid < c):
lo = mid
else:
hi = mid

return lo

def cubicRoot(c):
if c < 0:
return -_cubicRoot(-c)
else:
return _cubicRootABS(c)``````

Going back back to the precision issue:

If you've read nearly all binary searches and merge sorts are wrong you know that mid = (lo + hi) / 2 has an overflow problem. So we change that line to mid = lo + (hi - lo) / 2.

Testing for equality doesn't work with floating point numbers. The first idea that comes to mind is to use an absolute error comparison (|a - b| < eps).

``while lo * lo * lo != c:``

switch to

``while abs(c - lo * lo * lo) > 1e-3:``

This doesn't work. For large numbers like 1e37 the code goes into an infinite loop. Try to figure out why. Discuss it in the comment section. Let’s try using the relative error (|(a - b) / b| < eps). There are some weird cases when a and b are close or equal to 0. Can the code be cleaner?

After each while loop iteration we learn something new about x’s range. A double has only 64 bits of precision. So instead of a tricky floating point stopping criteria we can run the loop a fixed number of times so that the interval is as small as the precision of our floating point numbers allows.

Tomek Czajka(of topcoder fame) pointed out that my final version was buggy as well. I chose the number of iterations to be 120 but that’s way too small. It doesn't work for c = 1e60.

A double is represented by the mantissa which consists of 52 bits and the exponent which contains 11 bits(signed). One loop iteration either decreases the exponent of our interval by 1 or we find out a new bit of the mantissa. The maximum value of the exponent is 210 and the mantissa has 52 bits. Thus we need about 1100 steps to figure out the answer.

``````def _cubicRoot(c):
lo, hi = 0.0, max(1, c)

for iter in range(0, 1100):
mid = lo + (hi - lo) / 2
if (mid * mid * mid < c):
lo = mid
else:
hi = mid

return lo

def cubicRoot(c):
if c < 0:
return -_cubicRoot(-c)
else:
return _cubicRoot(c)``````

No more epsilon! But now, because of cases with large exponents, the code runs pretty slow on all cases. An idea is to stop as soon as we don't decrease the lo..hi interval, instead of doing a constant number of iterations. So here’s this faster version:

``````def _cubicRoot(c):
lo, hi = 0.0, max(1, c)
prev_range_size = hi - lo
while True:
mid = lo + (hi - lo) / 2
if (mid * mid * mid < c):
lo = mid
else:
hi = mid
if hi - lo == prev_range_size:
break
prev_range_size = hi - lo

return lo

def cubicRoot(c):
if c < 0:
return -_cubicRoot(-c)
else:
return _cubicRoot(c)``````

This is still slow when we’re dealing with large numbers. To address it one can binary search first on the exponent, or get close to the real exponent by dividing the original exponent by 3. Try it out in the comment section.

I'm curious, did your solution have any of these problems?

notes:

• Thanks Tomek for pointing out the iteration problem and possible efficient solutions.
• When c is large, mid * mid * mid will overflow but the algorithm still works.
• We’ve addressed negative numbers, numbers in (0, 1), overflow problems, absolute and relative error problems.
• Some tests for your own code -1, 0, 1, 2, 8, 0.001, 1e30, 1e60
• In practice faster methods like Newton Rapson method are used.
Categorii:

# Binary Search Shortlist

Cosmin Negruseri
16 mai 2014

Figure out an algorithm for each of the following problems. What’s the complexity? Code it.

1. Given A, a sorted int array of length n. How many times does the value x occur in A.
2. Given a real number x, find out it’s cubic root.
3. Given A a sorted array of distinct integers, find out an i such that A[i] == i.
4. Given the +,-,*,/,sqrt operations and a real number x find an algorithm to get log_2(x).
5. Given an array A such that A[ 0] > A[ 1] and A[n-1] > A[n-2] find out a local minimum (find out an i such that A[i-1] > A[i] < A[i + 1]).
6. Let A be a sorted array with distinct elements. A is rotated k positions to the right (k is unknown). Find out k.
7. Let A be a sorted array with distinct elements. A is rotated k positions to the right (k is unknown). Find out if A contains a number x.
8. Given two sorted arrays of length n and m, find out the kth element of their sorted union.
9. An array is bitonic if it is comprised of an increasing sequence of integers followed immediately by a decreasing sequence of integers. Write a program that, given a bitonic array of N distinct int values, determines whether a given integer is in the array.
10. Write a program that, given an array of N distinct int values in ascending order, determines whether a given integer is in the array. You may use only additions and subtractions and a constant amount of extra memory. The running time of your program should be proportional to log N in the worst case.
Categorii:

# Interviu cu romanii acceptati in YCombinator

Cosmin Negruseri
10 aprilie 2014

Razvan si Radu de la stanga la dreapta

Radu Spineanu si Razvan Roman sunt fondatorii companiei Two Tap. Ei au format prima echipa de romani acceptati in YCombinator, cel mai renumit incubator de startups din Silicon Valley. Prin YCombinator au mai trecut companii ca reddit, AirBNB sau dropbox. Acum sunt si in faza de crestere a echipei tehnice, cauta ingineri foarte buni la inceputul carierei. Puteti sa ii contactati la [email protected]

1. Spuneti-ne putin despre voi si despre TwoTap.

Radu: Backgroundul meu este de Network Engineer (am lucrat 5 ani la RoEduNet). Am inceput sa fac companii in timpul facultatii. Printre multe am fondat 2Parale, cea mai mare retea de afiliere din RO. De asemenea am creat prima aplicatie care permitea crearea de cinemagraphs pe iOS, care a fost featured de Apple si a avut in jur de 1 milion de downloaduri). In timpul liber sunt Developer Debian (o distributie Linux).

Razvan: Am invatat sa scriu si sa citesc cand aveam 5 ani pe un HC91 pe care am petrecut mult timp datorita Lode Runner, Dizzy si altele. Odata cu o conexiune broadband multi ani mai tarziu am avut acces la tot ce inseamna knowledge despre startupuri, in perioada in care Napster era hot. Dupa ce am pornit primul startup in liceu a urmat o lunga serie de eforturi cu rezultate mixte dar din care am invatat foarte mult despre factorii care influenteaza succesul unui startup, vazuti din multe perspective: am facut tot, de la copywriting si marketing la sales si programare sau recrutare, atat in RO cat si EU/UK sau US.

Two Tap rezolva o problema fundamentala a ecommerce-ului: in mod traditional daca vrei sa cumperi un produs trebuie sa mergi pe site-ul merchant-ului. Dar cum userii petrec timp pe diverse device-uri in prezent e foarte dificil sa faci o tranzactie oriunde in afara unui browser conventional. Two Tap permite userilor sa cumpere produsele atunci cand iau decizia respectiva, fie ca sunt intr-un FB app, intr-un app nativ sau pe mobile web, practic oriunde se afla. Asta se datoreaza API-ului care sta la baza Two Tap, API care poate plasa comenzi pe platformele retailerilor.

2. Piata angajatorilor in domeniu software e foarte activa. Corporatiile concureaza acerb pentru oameni foarte competenti. Ati refuzat traseul corporatist si ati ales sa fondati un startup. Cum ati luat decizia?

Radu: Intr-o corporatie esti doar o rotita dintr-un sistem enorm. Oportunitatea de a face ceva meaningful pornind de la zero e aproape inexistenta. In final avem doar o viata, si viata trebuie traita. De asta facem ceea ce facem. Pentru ca vrem ca atunci cand avem 80 de ani sa ne numaram cicatricile si traumele psihologice sa radem de fericire fara nici un regret.

Razvan: Impartasim mult perspectiva asta. Cand am o decizie importanta de facut intotdeauna ma gandesc daca voi regreta faptul ca nu am incercat optiunea care pare riscanta peste cativa ani. Daca raspunsul e da atunci las frica deoparte si merg inainte, oricat de dificil poate parea initial. Cred ca e mai dificil decat o cariera conventionala dar asta ma face fericit. Cred totodata ca lucrand cu un startup 2 ani inveti foarte mult fata de acelasi timp petrecut intr-o corporatie.

3. De ce Silicon Valley si nu Romania sau Europa?

Radu: Nu e nimic rau in a face o companie in Romania sau Europa. Prima companie fondata de mine a fost in Romania (se numeste 2Parale) si a fost una din cele mai misto experiente pe care le-am avut.

In acelasi timp e important sa 'always shoot for the stars'. Cand am inceput 2Parale nu stiam nimic despre startupuri, in nici o secunda nu m-am gandit ca as putea sa incep o companie in US. Si apoi incet incet am invatat tot mai multe, lucrurile au devenit mai clare, si drumul a fost evident.

Razvan: Starea economiei impiedica dezvoltarea unui startup pe o traiectorie normala de crestere. Oricat de bun esti exista limite date de piata locala care te obliga sa te plafonezi destul de repede. In Romania (si de multe ori Europa) greu te lovesti de problema de a scala produsul tau la zeci de milioane de useri, pe cand in SV asta e un given, te vei lovi de asta.
E foarte contraintuitiv dar din multe puncte de vedere e mai usor sa faci un startup in SV decat RO odata ce treci de barierele initiale. Daca ai product market fit ai din start o piata locala de 300M de consumatori care vor produsul tau, vorbesc aceeasi limba si au venituri substantiale pe care le pot cheltui.

4. Interviurile pentru intrarea in YCombinator sunt renumite. Povestiti-ne experienta voastra.

Radu: Am aplicat in total de cinci ori si am fost invitat la interviu de trei ori. PG scrie esee despre ceea ce cauta, dar probabil varianta scurta ar fi: echipa (accomplishments notabile, track record, fara accent, a cultural fit cu comunitatea YC), traction (daca compania ta face milioane de dolari pe zi that trumps everything), perseveranta, si un mod specific de a gandi asupra lucrurilor (foarte importanta e intrebarea about hacking a non-computer system).

YC a nimerit perfect momentul in care sa ne accepte ca sa folosim la maxim potentialul programului. O companie poate sa fie prea devreme in dezvoltarea ei, prea tarziu, sau poate sa fie nepotrivita cu viziunea YC. E greu sa iti dai seama cand e acel moment, dar probabil e atunci cand realizezi ca proiectul s-ar putea descurca bine-mersi si fara sa fie acceptat.

Natura interviului si interactiunea depinde de foarte multi factori si e greu de prezis.

5. Cum se compara experienta YCombinator cu munca pe cont propriu?

Razvan: Cel mai mare impact al YCombinator asupra companiei tale e faptul ca iti elimina toate lucrurile care iti pot distrage atentia timp de 3 luni. Elementul asta de focus extrem dublat de faptul ca esti inconjurat de alte echipe care trec prin aceeasi experienta e foarte motivant. Multe din companiile care trec prin program ajung sa fie lideri pe segmentul lor de piata in cele 3 luni.
Imaginati-va cum e sa lucrati la un mail client si sa aveti ca mentor pe Paul Buccheit (creatorul Gmail) sau Geoff Ralston care a fondat Rocket Mail, devenit mai tarziu Yahoo Mail.
In fiecare marti YCombinator organizeaza o cina pentru fondatori, eveniment unde participa oameni foarte influenti din SV, de la Marc Andreessen (creatorul Netscape, primul browser) pana la Ron Conway sau Mark Zuckerberg. Totul intr-o atmosfera casual, off the record si multe discutii la liber. Doar cateva sute de oameni au avut acces la resursele astea pana acum prin YCombinator.

6. Care sunt problemele cele mai grele pe care le rezolvati? Sunt de natura tehnica sau pe partea de business?

Radu: Two Tap rezolva o problema tehnica foarte complicata: cum abstractionezi mii de magazine prost facute intr-un API curat si reliable fara ca ele sa faca nimic (0 integrare). Iar dupa ce ai API-ul cum creezi cea mai buna experienta de shopping din lume pe orice platforma.

La Two Tap creem un layer care sta deasupra tot ce inseamna online ecommerce, care intelege mii de magazine. La core e un scraper hiper inteligent, iar posibilitatile cu ce putem face cu el sunt endless.

7. Ce sfaturi aveti pentru programatorii din comunitatea infoArena?

Radu: Sa nu se angajeze la o multinationala. Cand eram la RoEduNet cineva imi povestea ca cel mai mare pericol de a avea un job e ca devii comfortabil. Te obisnuiesti sa iesi in oras in fiecare seara, sa iti iei haine scumpe, sa mergi in vacante de doua ori pe an, sa iti iei rate, sa te casatoresti.

Este enorm de mult timp sa faci asta la 35-40 de ani. La 20 de ani e momentul sa fii curajos, sa faci chestii care schimba lumea, chiar daca unii le considera idioate sau a long shot. E important sa nu ai nici un regret mai incolo.

Razvan: La ce a zis Radu as adauga faptul ca e important sa se gandeasca foarte bine la parcursul profesional. Barierele lingvistice sau de distanta devin din ce in ce mai insignifiante si e mult mai usor decat pare la prima vedere sa lucreze la ceva care poate avea un impact major si deschide niste drumuri necalcate in loc de a invata o tehnologie proprietara a unei corporatii mari care tot ce vrea e sa maximizeze profiturile.

Mult curaj! Si luati legatura cu noi daca putem ajuta, am fost la randul nostru ajutati de multi oameni de-alungul anilor si ne face mare placere sa pay it forward.

Radu si Razvan, va multumim pentru interviu! Pentru orice startup problema angajarii de oameni buni e esentiala. Two Tap cauta oameni buni la inceputul carierei. Ii puteti contacta pe [email protected]

Categorii:

# Zece

Cosmin Negruseri
28 martie 2014

Infoarena aniverseaza luna aceasta 10 ani!

Categorii:

# Lansarea concursului naţional de algoritmică MindCoding

Petru Trimbitas
20 ianuarie 2014

## Lansarea concursului naţional de algoritmică MindCoding

Concursul Naţional MindCoding este un proiect care vine în atenţia pasionaţilor de informatică din întreaga ţară, indiferent de vârstă, încurajând dezvoltarea unei comunităţi de persoane pasionate de algoritmică, şi nu numai.
Concursul va avea 4 runde online ce se vor desfăşura pe site-ul competiţiei www.mindcoding.ro , urmând ca runda finală să aibă loc în perioada 11-13 aprilie 2014 în municipiul Cluj Napoca.
Fiecare rundă online va fi alcătuită din 4 probleme cu dificultate gradată în 90 de minute.
Prima rundă va avea loc în data de 30 ianuarie 2014, incepând cu orele 19.

Organizatorul acestui concurs este Societatea Hermes (Organizaţia Studenţilor din cadrul Facultăţii de Matematică şi Informatică Cluj Napoca). Mai multe detalii sunt disponibile aici De asemenea ne puteţi urmări pe facebook

Categorii:

# Transpose

Cosmin Negruseri
29 octombrie 2013

Here's an interesting interview question I've heard recently.

You are given an 100G size file on disk which represents a square matrix of 32 bit integers. Design an efficient way to transpose that matrix given that you only have 1G of available memory.

Categorii:

# Distance

Cosmin Negruseri
08 octombrie 2013

Here's a neat problem I solved in 8th grade during the preparation for the high school entrance exam:

Let A1B1C1D1A2B2C2D2 be a cube with A1B1C1D1 being the bottom face and A2B2C2D2 the top face. Given that A1A2 is of length 1 what's the distance between D2A1 and A2B1.

Categorii:
Vezi pagina: 1234567 89101112... 3738394041 (402 rezultate)