Last Thursday over at Hyperpublic we launched The Hyperpublic Developer Challenge. It consisted of two programming problems, one of easy/medium difficulty, and one which was slightly harder. We built it for fun, because we’re developers, and we love when there’s a fun problem around to work on if we get bored or need a distraction. The response to the challenge was phenomenal. We had thousands of developers from around the world working on the problems, and hundreds submit correct solutions. Here’s a summary of the response, the problems, the winners, and some observations.
To our amazement, 5,759 people landed on our challenge start page. From there 2/3rds of them, or 3,856, were feeling brave enough to at least look at the first problem. I’m sure it didn’t hurt that we were giving away free Dropbox and Github accounts, so even the non-programmers who landed on the page at least wanted to take a look at the first problem. The response peaked out with 400+ people viewing/working on the challenge concurrently.
The first problem, summarized below, proved to be a strong filter. Only 446 people, or 11.57% of people who looked at the problem, submitted a correct response. 4,860 incorrect answers were submitted, meaning that the successful submission rate was under 10%.
Problem 2, the more challenging problem, received 231 correct submissions. This means that of the 446 people who made it through question 1, only 51.79% of people made it through problem 2. There were 753 incorrect submission attempts.
All in all, 4.01% of people who viewed the challenge made it through to completing both problems.
Problem 1 asked developers to calculate the influence of fictitious users in Hyperpublic based upon the influence of the users which they have added to the system. The data was given as a text file, but it could easily be converted into a 2-D array representing which users added which other users to the system.
The most common approach was to use the input as a matrix representation of a directed graph. For each user in the input, traverse the graph recursively to sum up the number of users that the initial user was responsible for. Then find the three users with the highest scores, and use them to compute your answer to problem 1.
While we won’t be posting code examples here because we’ll leave the contest up for others to try, there are various solutions available around the internet and github, which can be found quite easily be googling/searching github.
Problem 2 assigned point values to various tasks around Hyperpublic and gave 4 users point totals. It asked the developer to compute the minimum number of tasks required in order to reach their exact point totals. This proved a bit trickier, in that many people’s first instinct was the use a greedy algorithm in which they always executed the task with the largest point total before moving on to tasks with smaller point totals. This would lead to an incorrect submission and developers to rethink their solutions.
The best way to write this program for inputs and point values of any size is using dynamic programming. This is analogous to the optimal solution coin changing problem which asks what the optimal way to make change for a given amount of money is using coins of various values. It uses a technique called memoization, where you compute the optimal ways to make change for values 1, 2, 3…up to your highest amount, and you use the previously computed values to compute the next unknown values in k attempts, where k is the number of distinct values of coins.
The other way common way in which people solved this problem efficiently was by solving 4 different linear equations. There were some one line solutions using Mathematica and Matlab linear solvers.
Fortunately, the problem size was limited enough in that a brute force solution would run quite quickly if people really got stuck as well.
From the 231 correct submissions, we randomly selected winners of the following prizes:
Github “Medium” account free for one year – Norbert Fekete. Norbert hails from Mosonmagyarovar, Hungary, and submitted his solutions in C++. He’s new to github, so follow him over there and suggest some repos for him to fork.
Dropbox “Pro 100” account free for one year – Brian Barthel. Brian is from Memphis, Tennessee, submitted a C# solution, and runs an independent software company called Zoasoft.
Free desk for a month for two hackers to work on their own project at Hyperpublic HQ – Martin Czygan. Martin is from Leipzig, Germany, submitted a python solution, and since he can’t take advantage of a free desk in NYC anytime soon he has graciously donated the prize to an NYC based hacker who can use it. You can find him on github and twitter.
Many people who submitted commented that the problems were too easy, and they would have preferred a harder challenge. We think that judging by the number of people who made it through, the number of people who emailed for help, and the number of people who submitted incorrectly, that the difficulty was about right. The majority of responses were very positive in that they said “this was a fun way to kill an hour or two.” We wanted the problems to take only an hour or two, and as such I think we got the difficulty right. People got to brush up on their dynamic programming or linear solving, they got to construct a graph, or they got to get their hands dirty with a new language. We think people had fun.
The last thought, is that we did this for fun, and we’re glad people enjoyed it. We also wanted to meet more developers and make them aware of Hyperpublic. We’re working on structuring data around every “local object” in the world, which is a big technical problem. If you’re interested in working on this with us, or hearing more about it. Don’t hesitate to contact me.
Looking forward to the next programming challenge.