Are you up to the challenge? Dropbox wants to know

https://www.dropbox.com/jobs/challenges

by trevorb • 16 years ago

96 36 16 years ago

Ainab• 16 years ago

I have been asked similar question in an interview. it is not so trivial, it is NP problem.

varjag3• 16 years ago

It is trivial in the sense that you solve it with exhaustive search. It can be stressful to implement during a live interview however.

harpastum3• 16 years ago

I had some fun creating graphical output for the various algorithms I used to solve their packing problem.

You can play with them here: http://dbpacker.samwarmuth.com/ (make sure to scroll horizontally to see all of them -- there are 10 different methods)

I'm planning on doing a short write-up of the process once they remove it from their jobs page.

vessenes3• 16 years ago

Interesting! It looks like none of them are optimal. Is this an NP-hard problem?

Keyframe2• 16 years ago

That is an NP-hard problem. http://en.wikipedia.org/wiki/Bin_packing_problem

stevejohnson• 16 years ago

Yes, there are several papers on the subject. I found a few by searching "rectangle packing algorithm."

asmosoinio• 16 years ago

That url gives me this responce: "Request timed out -- This application failed to respond within 30 seconds."

vessenes3• 16 years ago

Hilariously, their output for the packing problem is wrong. Oops! an 8x8, 4x3 and 3x4 set of rectangles cannot be easily packed into an 8x8 square without resorting to ... the third dimension ... (cue music)

tomerico• 16 years ago

The 88 in the output is the area of the smallest square (an 8x11 square)

vessenes3• 16 years ago

Ah, thanks, I thought it was the dimensions.

harpastum3• 16 years ago

I'm actually not sure what the 'correct' answer is to their given problem. The problem statement says "Files can be rotated 90° if it helps...any files sharing dimensions should be considered identical/interchangeable." That could mean that 3x4 and 4x3 are identical boxes. The final area would still be the same (88), but the given ascii drawing output would be incorrect.

Keyframe2• 16 years ago

One might find this interesting: http://gamedev.stackexchange.com/questions/2829/texture-pack...

koblas• 16 years ago

Are people having success with hiring based on problems like this? I've seen it at Dropbox, Facebook, Bump, Quora (and many others). While I agree that it would remove the chaff from the job submission pipeline, does it fill it with enough quality candidates to make it worthwhile? I know in at least one case where I played with a problem that the "easy" solution was not appropriate at large scale and it wasn't worth the time to spend the time researching the problem space for an optimal solution.

Anybody else have experiences either positive or negative on the hiring from (candidate or employer)?

jrockway• 16 years ago

I did this once when considering applying to ITA. I got bored in the middle of the puzzle and went to work for someone else instead.

(They wanted me to do, "using any language, write an IRC-like client and server". 10 lines of code these days, but still not interesting to do for free.)

twymer• 16 years ago

I think these are good ideas to get a different view on candidates who love problems like these or see one that they are willing to do the problem set research about, but for this reason, should not be a "requirement" for candidates.

varjag3• 16 years ago

I solved one of their puzzles and mailed them the answer, must be decade ago now. Did not even get an acknowledgement e-mail back.

hugh32• 16 years ago

And presumably instead of hiring you, they hired somebody just as capable but with a higher tolerance for solving boring problems for insufficient pay?

Sounds like a win-win.

webspiderus• 16 years ago

I actually had a bit of fun doing a challenge problem for Bump (although I was in school at the time and admittedly had a bit more time to spend).. It felt like a more sensible assessment than a resume or some simple fizzbuzz problem would provide, as well.

r00k• 16 years ago

I solved a puzzle for ITA. It got me an interview, and made good discussion fodder once I was there.

tomlin2• 16 years ago

This only proves that the potential employee is competent, with complete disregard to passion. Which is, IMO, much more valuable.

adorton• 16 years ago

This just looks like a way to screen candidates that are competent. Of course they will interview each candidate to assess passion, but they need to make sure they're at least technically competent.

hugh32• 16 years ago

Not really. For instance, I could probably solve the problems, but I don't care enough to try, so I'm obviously not sufficiently passionate about it.

Now if they'd asked me the infinite-grid-of-resistors problem...

tomlin2• 16 years ago

Are there competent programmers who could solve puzzles such as these and yet dread going to work every day?

Passion is thinking of better code while you're in the shower, or getting so excited about a new idea that you can't sleep.

Finding a great mind in this way will have a similar outcome to finding a great vocal artist through first round American Idol eliminations.

edanm• 16 years ago

I wonder if the fact that people find this problem and bother to answer it, regardless of the results they get, is proof enough that they should pass an initial screening, considering the way most companies say that 90% of candidates are just spamming their resumes to everyone.

sahillavingia• 16 years ago

While this does put a higher bar up that needs to be passed by quality candidates, I think the true benefit is that if you want the job you'll spend hours on a problem - which means they know each candidate really does want to work there (unlike those who generically spam tens of companies).

xpaulbettsx• 16 years ago

That 2nd problem would be very elegant / interesting to solve using the Reactive Extensions (http://msdn.microsoft.com/en-us/devlabs/ee794896.aspx) - a good intro is at http://haacked.com/archive/2010/03/26/enumerating-future.asp...

jhuckestein• 16 years ago

I'd love to know how well this is working for them.

I think the first problem is easy to solve inefficiently but finding a very good solution takes an inappropriate amount of time. The second problem is rather boring.

Perhaps asking open/creative questions makes more sense? Here's some ideas

- Write a script that saves you at least one minute of time every day

- Draw a picture of the future of the internet/technology/whatever

- Build a tool that amplifies people's need for cloud storage

dagw• 16 years ago

I'm guessing they need people to solve the sorts of questions they're asking, so filtering out the sort of people who find those problems "boring" or "takes too much time" probably makes a lot of sense.

Your questions would be more useful if you're looking for more of a high level concept architect rather than a low level algorithms hacker.

nl• 16 years ago

I think the second problem is much more interesting, because the first one can be judged pretty objectively.

The second one is more about trade offs.

Assuming optimal coding, "better" output means more complex code, and means lower performance in terms of processing time and memory usage.

For example, you could write a very complex version that tracked the lifecycle of a file by it's name, and "folded up" the manipulations into a couple of lines of output.

This would be more complex, slower and bug prone - but more human readable.

A test like this is a very interesting way to understand someone's programming taste.

donohoe• 16 years ago

I wish they included more sample data for the 2nd problem, Events, as that has a lot of potential - especially if the allowed single readable lines for multiple actions (instead of one)

Are you up to the challenge? Dropbox wants to know

Related Stories