If you have the sense from whiteboard discussions that the candidate understands computer science (like gets recursion) but you want to make sure they can code, why not choose a subset of a problem that you (your company) needs to solve?
I do this, and provide a subset of REAL input data and perhaps a sample of the expected output. This ends up showing capabilities for more than just minor singleton operations, and shows that someone can use the atomic units of programming (loops, recursion, functions, etc) to actually produce a result. The chosen programming task is one someone in the office recently had to tackle themselves, so there is a working benchmark to compare against. I give it to them ahead of time, before an in-person interview, and say tell them I'm not necessarily expecting a working program (however, that would be nice), but come to the interview having considered the task and be prepared to talk about it, or talk about their specific solution/implementation. I find this also helps communicate the kinds of tasks the company deals with, and maybe a little of the company culture.
I don't think he means open questions, but things related to the problem.
I interviewed once with a company that OCRed medical documents. One guy held up a sheet of paper and asked "How much memory does this take up?" which was a deliberately open-ended question. I was initially stumped, but then he started feeding me domain knowledge and assumptions, such as common DPI values and expected fidelity. Then I started coming up with estimates.
I don't think he expected me to have answer right off. I think he wanted to see how much I could figure out on my own if given hints.
