Dropbox challenge | Hacker News Reader

Dropbox challenge

dropbox.com

52 pointsratsbane20 comments

The first one is a knapsack problem: http://en.wikipedia.org/wiki/Knapsack_problem

The third on is Zero-sum problem: http://en.wikipedia.org/wiki/Zero-sum

Nor sure about the second one. Anyone who knows?

Second one isn't a traditional algorithms problem, as the "correct" result is subjective.

The second problem seems open-ended and a test of UX/creativity skills: "There is no objectively 'right' answer here, and in fact there may be multiple ways to interpret a provided list of file events."

The third problem is not zero-sum, it's subset-sum: http://en.wikipedia.org/wiki/Subset_sum

I never understood the value of these simplified competitions. If your goal is to test implementations of approximation algorithms, then at least make the conditions realistic, like the Netflix prize.

These simplified competitions seem to filter for applicants who can recognize the canonical problems like knapsack/zero-sum/etc. and then successfully implement them.

While you might think of these sorts of problems as simplified, they really do work well to filter out the sort of programmers you definitely don't want to hire.

And for many programmers you might want, its a simple enough problem that it isn't very time-consuming for them.

I think the Netflix prize is a pretty bad comparison since it fueled years of active research from top machine learning and data mining people. It's great work, but if you're trying to find new hires the time scale is quite a ways off.

On the contrary, within a few days of the Netflix prize challenge being launched, a guy put up a detailed blog post with a simple linear algebra method that could beat Netflix's system at the time (link below). It didn't come anywhere near the 10% improvement threshold, but it beat Netflix's system with a handful of lines of C code, and it ran off his laptop. Sounds like he would have made an excellent hire.

http://sifter.org/~simon/journal/20061211.html

Haha, I stand very well corrected!

>"The third problem is not zero-sum, it's subset-sum: http://en.wikipedia.org/wiki/Subset_sum

That is correct. I have messed the names up :P

I think you are killing the point with this answers.

Naming problem you are trying to solve does not always solve it. Even more so for problems where common belief is that only way to solve them is essentially brute-force and what counts are various tricks in the actual implementation of solution.

First one is not knapsack problem (which is about packing largest possible value into available "capacity" without regard to actual geometry of considered objects), but one variant of packing problems.

Ha, the first one is cute. It's stolen almost directly from some CS competition training problems I did back in high school.

I saw it and _knew_ I'd seen it before. ;)

(edited to remove the name of the competition, since it turns out some answers are Googleable :-\)

1st one just screams Genetic Algo. Maybe thats just a case of "When you have a hammer..." though. I don't see any CPU/time limit though so maybe there is a proper solution.

You're right about the "when you have a hammer" issue. The biggest problem with genetic algorithms is that there's rarely a good reason for using them for cookie-cutter combinatorial optimization like the problem, when there are hundreds of papers on very good approximation algorithms.

This reminds me of what Facebook just recently started doing. I remember reading an article about how Facebook's plan failed though (regarding the hackathon)

Facebook started Facebook Puzzles long time ago. http://www.facebook.com/careers/puzzles.php

Facebook's Hackation has very little to do with these challenges. Btw why was Hackation a failure?

"mexican-coke". That doesn't sound very legal...

It's a popular cola that's sweetened with sucrose.

It is call sarcasm. People on the internet use it all the time.

Reply on news.ycombinator.com