Despre Blog

# Heaps shortlist

Cosmin Negruseri
17 iunie 2015

Here are a few problems where you can play with the heap data structure. Feel free to discuss them in the comment section.

We assume the input for the problems contains distinct numbers.

1. Given an array A, build a heap out of it efficiently.
2. Given k sorted arrays of length n each, describe an algorithm that merges them efficiently.
3. Given an array A where each number is at most k spots away from its spot in the sorted array, describe an efficient algorithm that returns the sorted array.
4. Given an array of n numbers, describe an efficient algorithm that prints out the smallest k numbers in the array.
5. A Young Tableau is a matrix where elements on each row or column appear in increasing order. Given a Young Tableau A, describe an efficient algorithm that returns the kth element of A.
6. Given a min heap A, give an efficient algorithm that outputs its kth smallest element.
7. Print out the first k numbers of the type 2i * 3j.
8. Build a data structure where you can do insert(x) in O(log n), findMedian() in O(1) and deleteMedian() in O(log n).
9. Given A and B sorted arrays of length n, find out the k smallest numbers of the form A[i] + B[j].
10. Given a min heap of size n and a number X, give an efficient algorithm that tests if the kth smallest element in the heap is smaller than X.

Categorii:

# How to get promoted in Silicon Valley

Cosmin Negruseri
13 iunie 2015

Warning: this is tongue in cheek!

Junior Engineer to Senior Engineer: Build a cache

When joining a team the engineers are building features and functionality. No one has time to address performance issues, so when you come in, you can easily improve a performance bottleneck by building a cache. Now you can claim 10x speed improvements and clear savings.

Senior Engineer to Staff Engineer: Build a dashboard

Now you have metrics and can easily spot some low hanging fruits in the project. Solve those and you can quantify your contribution to the project.

Staff Engineer to Senior Staff Engineer: Build a key value store

It doesn’t matter that the company already has 6 different key value store systems or that you can find open source solutions. Your problem is surely slightly different. Building a new one shows deep technical chops.

At this point getting promoted on the Individual Contributor track becomes difficult, so you do a lateral move to Management.

Manager to Director: do a reorg

BTW you might be able to apply the same trick several times in a row.

bonus If you’re in testing:

Senior Test Engineer: build a new testing framework and get teams to use it.

Categorii:

# Shortest snippet

Cosmin Negruseri
11 iunie 2015

My friend George Nachman (googler and iTerm2 developer) ran into this problem recently:

Given a string pattern P and a large text file T, find the shortest substring of T that contains the the characters of P in the same order.

For example:
P = aab
T = abaccacbab
The shortest substring is acbab

How would you design an algorithm that works well in practice?

How does your solution change if P is guaranteed to have distinct characters.

Categorii:

# A doua ediție MindCoding

Petru Trimbitas
21 ianuarie 2015

Avem plăcerea de a vă invita la a 2-a ediţie a Concursului de algoritmică MindCoding! Acesta este un proiect care vine în atenţia pasionaţilor de informatică din întreaga lume, 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, urmând ca runda finală să aibă loc î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 12 februarie 2015 de la ora 19.

Te aşteptăm să ni te alături şi să invăţăm împreună!

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

Nu uita! Anul trecut am avut premii în valoare de 1000 de euro!

Categorii:

Mihai Calancea
17 noiembrie 2014

Suntem încântaţi să anunţăm că Algoritmiada, cel mai important concurs Infoarena, se întoarce în sezonul 2014-2015!

Nou veniţi?

Algoritmiada este concursul tradiţional, de marcă, al Infoarenei. Este moştenitorul preONI-ului, primul concurs ţinut pe site (2004), care avea scopul de a pregăti elevii doritori pentru Olimpiada Naţională de Informatică. Între timp, concursul şi-a extins orizonturile şi a renăscut în anul 2009 sub numele de Algoritmiada, cu scopul declarat de a pregăti orice persoană pasionată de algoritmică şi concursuri de programare.

Arhiva concursurilor vă oferă acces la toate rundele preONI şi Algoritmiada desfăşurate până în prezent. Sunt mândria noastră şi vă invităm călduros să lecturaţi şi să rezolvaţi problemele din anii trecuţi!

De-ai casei?

Ei bine, avem de discutat şi cu voi! Începând cu această ediţie Algoritmiada îşi schimbă formatul, după cum vom explica în continuare.

Doar două grupe de vârstă

Din acest an Algoritmiada va avea doar două grupe de vârstă.

- Juniors. Dedicată elevilor de gimnaziu şi elevilor de clasa a 9-a începători, care aleg să participe la această grupă. Numărul de concurenţi care se vor califica la runda finală este de 15. Vă invităm să studiaţi criteriile de calificare aici.

- Seniors. Dedicată în primul rând elevilor din clasele 9-12, dar şi studenţilor, profesorilor şi pasionaţilor de algoritmică în general. Numărul de concurenţi care se vor califica pentru Runda Finală este de 25. Din nou, vă invităm să citiţi regulile de calificare în detaliu aici.

De ce?

- Credem că un set echilibrat de probleme poate fi o provocare adecvată atât pentru un concurent începător cât şi pentru unul experimentat, tematica atinsă nefiind un impediment. Considerăm, din acest punct de vedere, nenaturale limitele impuse de programa tradiţională a Olimpiadei.

- Ridicarea acestor limite stimulează în timp creşterea calităţii problemelor, o temă prioritară din punctul nostru de vedere.

- Vasta majoritate a ţărilor care au o cultură puternică în informatică au adoptat acest model chiar în cadrul Olimpiadelor Naţionale. Exemplul cel mai accesibil şi relevant pe care îl oferim este Polonia. Rusia, China, SUA, Japonia şi Croaţia continuă lista ţărilor care nu separă Olimpiada Naţională în funcţie de clasă.

Concluzii

Suntem încrezători că acest nou format reprezintă un pas în direcţia bună. În acelaşi timp, suntem conştienţi că această tranziţie trebuie realizată cu grijă. Echipa Infoarena vă stă la dispoziţie pentru orice fel de întrebări, comentarii şi sugestii pe această temă şi vă doreşte succes în noul sezon competiţional!

Categorii:

# Probability puzzle: Cars

Cosmin Negruseri
14 noiembrie 2014

Here's a neat problem I've heard from Christian Szegedy:

N cars are moving in the same direction with different speeds on an infinite straight road. The cars can't pass each other so clusters form. What's the expected number of clusters?

Feel free to discuss in the comment section. Don't forget to vote on Sunday!

Categorii:

# Schimbare rating + Java!

Mihai Calancea
04 noiembrie 2014

Rating

Infoarena a trecut prin multe schimbari in ultimii ani, iar din pacate procesul de update al rating-ului nu a fost adaptat in mod corespunzator. Ne referim in primul rand la:

1. Formula imperfecta, care de-a lungul vremii a cauzat cresteri/scaderi controversate.
2. Decizia nefericita de a mentine un rating unic pentru toate concursurile Infoarena, indiferent de formatul acestora.

Din aceste motive, am hotarat in cadrul echipei sa schimbam rating-ul pentru concursurile ce vor urma in continuare. Am considerat ca cea mai echitabila solutie este ca formula noua sa se aplice pe rating-urile curente, lasandu-le in timp sa se stabilizeze intr-o distributie conforma cu noile standarde. Rating-ul curent va ramane valabil doar pentru concursuri stil olimpiada (Algoritmiada + altele), urmand sa apara rating-uri separate pentru celelalte stiluri majore de concurs (ACM ICPC + altele). De-asemenea, userii care nu vor participa la niciun concurs pentru o perioada lunga de timp vor fi scosi temporar din clasamentul oficial, redevenind activi o data cu o noua participare.

Detaliile tehnice nu sunt inca stabilite, va dura o vreme pana vom finaliza schimbarea. Deocamdata, am dat un update mai mult decat necesar pentru rundele recente (dupa formula veche) :).

Java

Dupa cum unii dintre voi probabil ati observat, puteti acum submita solutii in Java pe infoarena! Proiectul este in faza Beta, fiind posibil sa intampinati unele dificultati, in special cu fisierele si limitele de timp si memorie. Momentan limitele sunt aceleasi pentru Java si C++. Va rugam sa semnalati orice problema in acest topic si vom incerca sa gasim o solutie. Pana atunci, spor la codat!

Categorii:

# Interviu cu romanii de la Talentbuddy

Cosmin Negruseri
14 august 2014

Andrei, Octav si Vlad de la stanga la dreapta

Il stiu pe Vlad de la concursurile de programare. Mai apoi am vorbit mai mult cu el si cu Andrei la Google in Mountain View unde faceau un internship pe vara. La terminarea facultatii au facut echipa cu Octav si au luat drumul strainatatii, incepand un startup in Canada. Le-am luat un interviu despre traseul lor.

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

Andrei: Primul meu contact cu programarea a fost in clasele 5-8, cand memoram programe Pascal ca sa nu raman corigent. In liceu programele au devenit mai mari, astfel incat am fost fortat sa le inteleg. Am descoperit ca imi place foarte mult sa programez si am inceput sa ma pregatesc cot la cot cu olimpicii la informatica.

Am continuat studiile la Politehnica Bucuresti, timp in care am lucrat pentru GNOME (in cadrul Google Summer of Code), Nokia (Berlin) si Google (San Francisco). In San Francisco am cunoscut multi antreprenori si am fost atras de lumea startup-urilor, asa ca imediat dupa terminarea facultatii am pornit la drum impreuna cu Vlad si Octav.

Vlad: In primul an de liceu am inceput sa invat programare si algoritmica destul de sistematic iar pentru urmatorii 4 ani infoarena.ro mi-a fost homepage. Ulterior, am mers la Universitatea Politehnica din Bucuresti si in prima vacanta de vara am facut un internship ca software developer la BitDefender. Pentru urmatoarele doua veri m-am alaturat echipei de Statistical Machine Translation din cadrul Google Research, Mountain View ca software engineer intern.

In final, am decis sa aleg o alta traiectorie in cariera si impreuna cu prietenii mei Andrei si Octav am pornint un startup in Vancouver, Canada.

Octav: Am studiat stiinta calculatoarelor si inginerie electrica la Jacobs University Bremen in Germania si am absolvit in anul 2007.

Prima mea interactiune cu un calculator a avut loc in clasa a 5-a, in 1995, in timpul primelor cursuri de informatica. Asa am invatat sa programez in Basic pe calculatoare CoBra si HC.

Am inceput sa folosesc calculatorul acasa incepand cu 1997 (clasa a 7-a) pentru a crea diverse proiecte pentru familie, rude, colegi si cateva firme din Romania. Am inceput cu design grafic (carti de vizita, brosuri, postere, etc) si am continuat cu site-uri si aplicatii web.

In 2007, dupa absolvirea facultatii, m-am intors in Romania si am inceput sa lucrez la aplicatii web comerciale (kmbio, Trigwee), iar in 2011 am plecat in Canada impreuna cu Andrei si Vlad unde am lucrat la Sunnytrail, Talentguide. In prezent lucram la Talentbuddy.

Mai am de lucru pana voi atinge nivelul de succes pe care mi-l doresc, insa fiecare dintre aceste proiecte, a fost un pas inainte. Am invatat multe lectii valoroase despre ce inseamna sa creezi, finantezi si distribui un produs.

Talentbuddy: este o platforma educationala pentru programatori. Oferim aplicatii web si mobile cu ajutorul carora un programator isi poate testa abilitatile precum si programe de educatie mentorate de experti.

2. Ati refuzat traseul corporatist si ati ales sa fondati un startup. Cum ati luat decizia?

Octav: Am hotarat sa incep un business in 2007, dupa ce am terminat facultatea in Germania. Cautam un mediu de activitate cu autonomie mare. Imi doream sa pot lucra direct cu oamenii care beneficiaza de serviciul / produsul meu si sa imi creez propriile responsabilitati. Nu am reusit sa gasesc joburi care sa ofere un astfel de mediu asa ca am decis sa creez un business in toamna lui 2007.

Andrei: Imi place sa creez produse noi, care sa ajute oamenii. La o companie ca Google sau Facebook sansele de a fi implicat in conceptualizarea si implementarea unui produs nou de la zero sunt foarte mici. Este posibil, bineinteles, dar cea mai sigura si rapida cale a fost sa infiintez o companie noua.

Vlad: Imi place sa programez, dar intotdeauna am fost fascinat de tot ceea ce inseamna business si organizatii de oameni. Nu vedeam totusi de unde ar trebui sa incep.

Ulterior, cunoscandu-i mai bine pe Andrei si Octav am realizat ca ei sunt punctul de start si sunt pus in fata unei oportunitati unice. Nu am avut nicio ezitare in a porni la drum cu ei si a lasa in urma Google sau alte companii interesante. Echipa a fost cel mai important element al deciziei.

3. De ce Canada, nu Romania sau Europa?

Din 2 motive:

a) Acces la investitori: in Europa sunt mult mai putini investitori si in general sunt mai reticenti sa investeasca in startup-uri early-stage. A fost si un factor de spontaneitate - tocmai ce ne fusese recomandat un accelerator nou in Vancouver care ne oferea \$175,000. In Europa nu exista un astfel de program care sa ofere o investitie comparabila in conditii legale la fel de bune.

b) Acces la o piata mare: Europa este formata din multe tari, fiecare cu limba si cultura lor, ceea ce creste dificultatea de a scala un business. In acelasi timp, North America ne pune la dispozitie o piata mare de oameni cu aceeasi cultura si cu putere de cumparare mare. Ne este mult mai usor sa scalam afacerea pe o piata mare si omogena.

Numarul ridicat de investitori si potentiali clienti cresc sansele de succes ale unui startup semnificativ. Desigur am fi putut porni un business si in Romania sau Europa, dar prin definitie sansele de success sunt foarte mici pentru un startup. Am avut oportunitatea sa crestem sansele si nu am ezitat.

4. Cum ati ajuns acolo?

Totul s-a intamplat destul de repede. Cu cateva luni inainte sa terminam facultatea am participat toti 3 la un concurs de business organizat de Ixia in Bucuresti. Am castigat premiul de \$20,000. Ulterior am aplicat la Growlab, am fost acceptati si am decis sa ne mutam in Vancouver.

5. Cum a fost partea de fundraising?

Am reusit sa obtinem finantare de la Version One Ventures, BDC si Initio Group - conexiuni pe care le-am legat pe parcursul Growlab.

Nu am avut acces la acelasi numar de investitori pe care il pune la dispozitie YCombinator, iar compania nu a fost evaluata la acelasi nivel ca o companie care participa la YC - dar optiunile au fost mai bune ca in Europa.

Per ansamblu, am avut acces la oportunitatile necesare pentru a trece la urmatorul nivel de dezvoltare si comercializare.

6. De ce se ocupa Talentbuddy? Ce problema rezolva?

Initial, Talentbuddy rezolva problema de training pentru interviuri la companii precum Google. Interviurile tehnice sunt dificile si e nevoie sa fii pregatit sa rezolvi anumite categorii de probleme inainte sa aplici. Talentbuddy ofera seturi de probleme, un IDE, un sistem care testeaza calitatea solutiilor automat si o modalitate de a accesa solutiile create de alti programatori la aceeasi problema.

Pe masura ce numarul de utilizatori ai platformei a crescut, scopurile in care este folosita s-au diversificat. Astazi platforma este folosita de profesori si studenti la cursuri de CS, de programatori profesionisti pentru distractie sau pentru a invata un limbaj de programare nou.

In mai 2014 am introdus doua programe de mentorat online pentru oamenii fara experienta in programare dar si pentru profesionistii care nu au timp sa mearga la cursuri de training offline sau nu au reusit sa capete experienta practica pe care si-o doresc prin alternative educationale precum Coursera, Udacity, Treehouse sau Lynda.

Majoritatea alternativelor mentionate mai sus se concentreaza pe predarea si aplicarea conceptelor in situatii izolate. Spre deosebire de alternativele existente, programele noastre de mentorship te ajuta sa inveti intr-un context foarte similar cu un job real. Am publicat recent un articol care explica in detaliu diferentele intre un program de mentorship si alte alternative pe care le poti gasi pe Internet.

7. Ce sfaturi aveti pentru programatorii din comunitatea infoArena?

Recomandam oricarui programator din comunitate sa fie atent la problemele care apar in mediul in care traieste si in loc sa le ignore, sa ia initiativa pentru a le rezolva. Nu gasesti un fotograf bun pentru o petrecere? Creaza un loc unde poti gasi fotografi usor. Nu iti place experienta de shopping online? Creaza una mai buna - si asa mai departe.

8. Cateva cuvinte de final?

Daca vrei sa schimbi felul in care oamenii isi dezvolta abilitatile de programare si daca stapanesti foarte bine fundamentele programarii, alatura-te echipei de mentori de la Talentbuddy. Esti platit, poti lucra in timpul liber, de oriunde din lume, impreuna cu fosti ingineri Google si Youtube.

Asteptam un email de la tine la adresa [email protected]

Categorii:

# Interni romani in strainatate (generatia 2014)

Cosmin Negruseri
25 iulie 2014

Edit: 110 nume de interni! Am extins spreedsheet-ul si la alti ani. Avem pagini diferite pentru anii trecuti. Adaugati cu incredere!

Edit: Impresionant, am ajuns la 80 de nume de interni! Dati share la prieteni si pe liste interne la univeristati poate mai gasim cativa!

Vreau sa fac un experiment similar cu cel din tabelul cu olimpici romani. Daca sunteti interni sau stiti vreun intern roman in strainatate anul asta, va rog sa adaugati un rand in tabelul din linkul urmator:

tabel

Mersi fain si bafta la internship!

Edit E ok si daca sunteti interni inafara Romaniei dar nu in Silicon Valley, adaugati cu incredere.

Cosmin

Categorii:

# 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:
Vezi pagina: 12345 678910... 3637383940 (391 rezultate)