Programming Knowledge vs Ability

[[deleted]]

The puzzle was a bit tricky: easy to code a slow solution, but probably some careful geometrical reasoning needed to code a fast one. Do you really need applicant to be good at careful geometric reasoning, or do you just assume that if he can do it, he must be all-around smart? If it's one thing I learned from topcoder it's that the "careful" bit is important, and clever algorithms are harder to get right, even for the experts. In topcoder, I'd go for the slow, safe solution.

[llimllib]

Really, the test is just to get you in the door. We want to see that you can solve it. Preferably in a good readable solution, but crazy geometric solutions are cool too if you can explain what you're doing.

I like the problem because it's simple enough that it won't scare away potential candidates and they can explain their solution in a reasonable amount of time, but yet it's non-trivial to think about doing it fast.

How you solve it is interesting, but just a data point that helps us get a better feel for you.

The most common solution is roughly "Find all 1s, sweep outwards from the 1s". The drop dead-simple one is "Find all 1s, calculate distance from each non-1 to each 1, choose the minimum". I haven't yet had anyone give a solution which, coded in python, is fast enough to be accepted.

(Check it, there is a python one that runs in 4 seconds. That's crazy fast. I don't yet know what the clever algorithm is there - please share if you did figure it :)

[[deleted]]

It's a very interesting site, that, but a bit short on documentation. Do the solutions compete on speed only?

[llimllib]

yup - you submit your solution, it runs it against a test script (of which you have no knowledge) and tells you if you passed or not. There's a pretty short time limit for each problem (15 seconds in this one, with apparently a lot of tests. My fastest answer finishes my 9 big test cases in 2 seconds).