Yup, this worked really well for us too - we asked candidates to submit a 20-line "binary chop" search over a given data file (well, that was the solution, we described the problem and restrictions such that that was the only right answer). All the interviewees were good when we did that, and it also seems like a good test for recruitment agencies (i.e. which ones understand what we're trying to do).

We did get one answer that was both incorrect, too slow, and massively over-engineered. I got emailed a multi-megabyte Rails project, boilerplate, tests for correctness and all. Bit It Didn't Solve The 20-line Problem. He was the guy we wrote the test to avoid!