Like I said, I have no desire for them to create the "perfect, correct" solution; but I do want to know how they think about a problem and what questions they ask in the face of deficient information. I proactively encourage them to do so, so I am not trying to trick them into failure or anything.
It seems like you're very interested in people asking questions like "how big might the array be" or "what order of time can you afford to wait for the answer to this", to which you might answer "a billion" or, "as little as possible", but those questions are very different and less meaningful than questions like "how many users will this system have", and "how much time can users of this system afford to wait for a response", even though the answers may be the same.
I have to say, I respond quite differently to "I have a problem I'm trying to solve" vs something like "I need this algorithm implemented", and a lot of the way these programming challenges are presented always come off to me as the latter, and as a result, contrived.
Do you specify this to your candidates when they write their code?
This is the thing that annoys me most about interview programming questions. If you don't give me constraints, I am going to implement a naïve version of your requirements, because you have not given me any additional criteria by which you are going to judge my code.
Knowing things about what sorts of inputs the method has to expect (should I assume that i'm going to encounter a billion elements or not?) is really important to judge correctness of fit, or whether you're just wasting your time thinking about cases you'll never encounter.