I would say that interviewing for engineering knowledge (coding, algorithms, software engineering) is pretty straight forward, but interviewing to figure out if a candiate can get 'real' work done is very difficult.

I don't know of any magic way of testing for that. There are some good signals, of course, such as:

1) pre-interview open source reputation and release. 2) References from people you trust and respect. 3) Publications with significant content written by the candidate.

But I've seen each of these fail, even in combination, in predicting the ability to execute. That said, it's better than nothing.

(disclaimer, I work for Google, and am also waiting for the part about Google in the OP)