This problem has been examined again and again. The only way to find people with sufficient skill in any field is to test them (formal graded test, not idiosyncratic problems).
No one has ever demonstrated a reliable technique for selecting "great" software developers (or great scientists, or great engineers, &etc).
If I remember it correctly, several of the pairs from the study were engaged shortly thereafter.
So the answer to your question is simple, but not for the reasons you think.
You are dealing with a high level of cost (direct cost and opportunity cost), not to mention a massive degree of risk (people are not predictable).
Therefore it is worth some mitigiation - and the budget for it depends on your assessment of (risk * the total cost of a mistake).
The mitigations (such as a few months initially contracting for potential new hires, running internship programmes, recommendation bonuses) can then be costed and compared against the savings you make by reducing the probability of, or the cost of, a hiring mistake.
I'd ask for 2-3 possible ways of designing the architecture. Then just drill down to the details, ask about the technology they would use, how they would go about implementing the algorithmic parts of things, the networking part of things, etc.
You'll get a good sense of how the person works on a high level as well as on a more detailed level. You'd also find out if the person is current on available technologies.
Algorithms are pointless to know, very rarely does one use that knowledge as a real life programmer. I know how quicksort works, but I've hardly ever _needed_ to know, and I've NEVER had to implement it.
Many of the schemes for hiring great programmers assume that said great programmers are (1) looking and (2) want to work for you. Neither one is true. WRT (2), you have to sell them.
I don't doubt that this would work in a perfect world, but it's going to be difficult finding candidates willing to go through with it. Right off the bat you're going to have a severely limited pool of talent to choose from. It's also important to think about what kind of candidates would be up for this. They obviously wouldn't already have jobs and that could be for a variety of reasons - good or bad. These candidates would likely have to put off other interviews for a week, assuming they have other leads. Would you pay candidates during this interview process? That's going to have an effect on the types of people you can bring in for consideration. My guess is that in the end you're going to have just as many difficulties finding a suitable candidate.
(It's like scoring students with exams; makes no sense at all, when an informal oral exam would really tell you how much the student knows. Scoring students while having a beer with them may not be conventional, yet my former PhD advisor used that as a pre-screen for hiring new grads.)
Interviews are all about probing. They shouldn't be a set of rote questions that you apply to every candidate regardless of background. You should make a guess at what the candidate's weaknesses are, and then push on them, push on them some more. This will also help you learn how well they deal with adversity.
Of course, before this, testing is a good way to determine what a candidate's strengths and weaknesses are.
As a total aside, I've found that US Customs and Border Patrol (the ones who do "secondary inspections") are about the best interviewers out there. They probe so much you end up feeling a little violated.
I disagree.
Find out what they think that their relevant strengths are. This is usually fairly easy because they'll almost always tell you, often without being asked.
Test said strengths because that's where they'll go first, when things are tough, etc. Also, said strengths are probably where you want them working. If your needs are elsewhere, they're not your solution.
If their actual strengths are elsewhere, they've got a problem. Are they worth making said problem yours? (There are lots of reasons why their strengths might be elsewhere, some worse for you than others.)
For what it's worth I came to exactly opposite conclusion, which probably means that this 'predictor' is a bogus one.
1. Weed out the truly incompetent. A very simple programming exercise is sufficient. Keep in mind that the goal of the exercise is not to identify a great programmer, but rather to identify those who can't program at all.
2. Set expectations. During the interviewing process, try your best to work out what you would expect from the individual if hired. Would you expect them to churn out a ton of quality code? Do you expect them to be great at determining business needs and writing less code, but code with a high impact? Is this going to be your go to guy for technology X? Do you expect your junior person to learn Y and Z so they can start contributing after N months?
3. Communicate your expectations clearly. Make sure the candidate knows what's expected of him or her. Towards the end of the interview discuss how they feel about those expectations. Ask how they plan on going about meeting them.
4. After hiring: If you get it right great, if not, let the person go sooner than later. You do yourself and the individual a great disservice if you try to turn them into something they are not. Don't try to turn a lump of coal into a diamond. It's a trap. It doesn't work. They will be unhappy and resentful if you try. Nobody likes to be fired (or do the firing) but you have to tell yourself it's best that they get back out there and find the job that they can be happy and successful at.
Add to that an intelligence filter (well, I have an affinity for smart people too), and maybe an informal chat about some past projects that they've worked on if still in doubt, and I think I can recognise good programmers even on a text chat system.
In fact, I spotted our last hire on IRC and was about 80% sure that he was someone we wanted to hire, after just 30 minutes of chatting.
Someone already posted the link to my article on how to recognise a good programmer - that breaks down the process I follow (though it's more internalised by now).
I worked at an oil services company where I fairly regularly interviewed candidates. I was 180 degrees wrong on every interview I did. The bad ones turned out good, and the good ones turned out bad.
I would not, knowing what I know now, bother with anything else except a chat with some managers, and a some pseudo-code testing of the kinds of problems I'd expect a computer science grad to be able to solve.
This opinion is backed up by a basic training course for some new hires I gave recently, where my ranking basically flipped around from my first impressions, and the guys with actual real ability didn't really float to the top until after about 10 or 12 hours of training / evaluation. However, this could be shortened easily into an interview format.
There's a lot of people who hide their light under a bushel, and a lot of people who talk a good game, but are basically just warm bodies.
People always misrepresent at interviews; I can't think of a way around this.
Usually the great programmers come up with clean, elegant, efficient and scalable solutions.
