Blog infoarena

Interviu cu Matei Zaharia

Cosmin
Cosmin Negruseri
14 august 2015

Matei Zaharia e o celebritate in domeniul sistemelor distribuite. El este fondatorul Spark, solutia de procesare big data cu cresterea cea mai mare din ultimii ani. Acum e assistant professor la MIT si CTO al firmei DataBricks. El cauta programatori ce vor sa lucreze la un startup pe domeniu de sisteme distribuite in San Francisco. Puteti sa il contactati la adresa [email protected]ricks.com El a raspuns la cateva intrebari pentru blogul infoarena.

Matei are un parcurs interesant pentru comunitatea infoarena. Familia lui s-a mutat in Canada in 1996 cand Matei avea 11 ani. In liceu a facut parte din echipa Canadei la Olimpiada Internationala de Informatica. A luat doua medalii de argint. A urmat cursurile de informatica a univestitatii Waterloo. Echipa lui s-a clasat pe locul 15 in 2004 si pe locul 4 in 2005 la finala concursului ACM ICPC.

A urmat un doctorat la UC Berkeley in sisteme distribuite. Acolo l-a avut ca si coordonator pe profesorul Ion Stoica. El are o activitate de cercetare impresionanta, lucrarile lui fiind citate de alte 15664 lucrari de cercetare. Acum are o pozitie de assistant profesor la MIT in grupul care e probabil cel mai puternic gup de cercetare de sisteme distribuite din lume (fiind la competitie cu grupul de la UC Berkley de unde vine Matei).

In paperul Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing Matei introduce o noua metoda de a procesa seturi de date mai flexibila si mai rapida decat metoda Mapreduce popularizata de Google.

In 2013 a fondat compania DataBricks care pune in productie aceasta metoda si o face mai accesibila analistilor. Compania are acum 47 de milioane de dolari finantare. Spark e cea mai activ proiect open source pe domeniul big data.

1. Matei ne poti spune ce utilitate au avut pentru tine concursurile de programare?

Matei Am invatat foarte mult in concursuri. Pe de o parte, am invatat algoritmi, dar in plus am invatat si cum sa scriu solutii in mod minimal si sa anticipez cat mai multe cazuri posibile. In general, un lucru important in programare este sa anticipezi si sa minimizezi starile posibile ale aplicatiei.

2. Care a fost tranzitia de la concursuri de programare la cercetare?

Matei Multe lucruri pe care le-am invatat la concursuri au fost aplicabile direct. In cercetare, vrei sa testezi o idee noua cat mai repede, si iti trebuie agloritmi si cod eficient. Totusi, pentru proiecte mari ai nevoie nu doar de algoritmi si optimizari ci si abstractizari care sa ajute la organizarea buna a acestora.

3. Cum se compara activitatea de cercetare cu cea de a fi Chief Technical Officer pentru un un startup in crestere?

Matei La startup, avem aceiasi nevoie sa dezvoltam idei in mod rapid, dar trebuie si stabilitate pentru un produs care merge direct la clienti si pentru o echipa de ingineri care creste repede. Noi am reusit sa atragem o echipa foarte buna cu background similar cu mine, deci putem sa atacam problemele noi repede. Ca CTO am incercat sa tin un standard ridicat pe partea de inginerie si sa stabilesc procese si o infrastructura care ne permit sa construim software fantastic in mod rapid.

4. Cum sari intre rolurile de coordonator pentru o comunitate open source foarte populara si cea de coordonator tehnic al unei companii private?

Matei Nu e foarte greu, pentru ca procesele sunt similare. In ambele cazuri, avem un grup mare de programatori care contribuie si procese de code review si de testare automata similare. Noi dezvoltam toate modificarile noastre la Spark in open source, deci sunt foarte bine aliniate cu comunitatea de utilizatori.

5. Ce sfaturi ai pentru programatorii din comunitatea infoarena?

Matei Daca aveti o sansa sa participati in open source, deschide multe usi pentru o cariera in software. Va incurajez sa participati la niste proiecte sau sa va publicati proiectele voastre ca sa invatati intregul ciclu de software engineering si sa aveti projecte interesante de a arata pe CV.

Multumim pentru interviu!

 Comentarii (1)

Categorii:

Balance

Cosmin
Cosmin Negruseri
29 iulie 2015

Here's a neat problem I've seen again recently.

Given A, a set of n points in the plane, each point having integer coordinates. Come up with an algorithm that colors some of the points in the set red and the remaining points white in such a way that for any straight line L parallel to either one of the coordinate axes the difference (in absolute value) between the numbers of white point and red points on L is not greater than 1.

 Comentarii (2)

Categorii:

Statistici pentru probleme (beta)

Vman
Duta Vlad
27 iulie 2015

Daca nu ati observat inca, pe pagina fiecarei probleme in partea dreapta sus avem acum un link catre statisticile problemei. Statisticile includ cele mai bune 5 rezultate obtinute pentru timpul de executie, memorie si lungimea codului sursa, precum si o histograma cu distributia punctajelor. Speram ca aceste statistici sa va ajute sa evaluati mai bine dificultatea problemelor si totodata sa va motiveze sa lucrati cat mai cu spor :)

Intreg meritul pentru lansarea statisticilor ii apartine lui PlayLikeNeverB4George Marcus PlayLikeNeverB4, drept pentru care ii multumim pentru efortul depus in implementarea acestui nou feature (round of applause). Ne bucuram cand membrii comunitatii se implica voluntar in dezvoltarea infoarena si speram ca exemplul sau va fi urmat si de alti membrii care doresc sa imbunatateasca "arena".

Ca de obicei asteptam sugestii, pareri, comentarii pe forum in topicul asociat. Spor la codat!

 Comentarii (17)

Categorii: statistici

Biografii olimpici

klamathix
Mihai Calancea
23 iunie 2015

Blogul merita o vizita. Veti recunoaste nume pe care le stiti deja, dar ale caror povesti poate nu le stiati inca.

 Comentarii (0)

Categorii:

Hill Climbing shortlist

Cosmin
Cosmin Negruseri
23 iunie 2015

Here are a few problems that involve hill climbing or some form of local search. Feel free to suggest others and to discuss solutions.

  1. You are given a list of A of n points with integer coordinates in the 2d plane. Find another point P(x, y) such that the sum of square distances from the points in A to P is minimum.
  2. You are given a list of A of n points with integer coordinates in the 3d plane. Find another point P(x, y) such that the maximum of the Manhattan distances from the points in A to P is minimum. (the manhattan distance between (x1, y1, z1) and (x2, y2, z2) is |x1 - x2| + |y1 - y2| + |z1 - z2|)
  3. You are given a list of A of n points with integer coordinates in the 2d plane. Find another point P(x, y) such that the sum of euclidean distances from the points in A to P is minimum.
  4. You are given a convex polygon P with n vertices, find out the radius of the largest inscribed circle in that polygon..
  5. You are given a list A of n points in the plane, find out the minimum enclosing circle.
  6. Given a number n, find out a placement of n queens on an nxn chessboard such that they don’t attack each other.
  7. Given n (n <= 1000) and S integers, find out a permutation p such that 1 * p[1] + 2 * p[2] + .. + n * p[n] = S.
  8. 2n knights have to sit around a roundtable. Each knight is friends with n + 1 other knights. Find a seating arrangement such that each knight is placed between two friends.
  9. Given two line segments in 3d space find the minimum distance between them.
  10. A party of n people is too large and has to be split to two tables. Given that each of the people has at most three enemies in the group, find a seating arrangement such that each person sits at a table with at most one of his enemies.
  11. Given a set A of n black points and a set B of n white points (no three points are collinear), join each point in A with one point in B respectively such that no two segments will intersect.
  12. Given a set A with n points and a set B with m points, find a line that separates the two sets.
  13. Given two points A and B and a circle C, find a point D on C such that AD + DB is minimized.
  14. Given a rectangle R find a list L of n points in it such that the sum of distances between all pairs of points in L is maximized.

 Comentarii (7)

Categorii:

Heaps shortlist

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

 Comentarii (10)

Categorii:

How to get promoted in Silicon Valley

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

 Comentarii (0)

Categorii:

Shortest snippet

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

 Comentarii (10)

Categorii:

A doua ediție MindCoding

S7012MY
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!

 Comentarii (1)

Categorii:

Algoritmiada 2015

klamathix
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!

 Comentarii (2)

Categorii:
Vezi pagina: 1234 56789... 3536373839 (386 rezultate)