I agree with ironcode that FizzBuzz can be done over the phone, if you're willing to deal in pseudocode. If you're worried about the interviewee merely reading a question off a web page, just propose a change in the requirements and see how they handle it. Just ask, "Instead of all integers, what if we wanted it to print out only Fibonacci numbers?", and if they get totally flustered, you'll know.
Another route is to talk through the high level design of something, asking them questions about what data structures they would choose. I used to follow a script that went like this:
- "We want to implement the Observable pattern. How would you store the Observers?"
- In my experience almost everyone starts with an array.
- "How would you implement
addObserver, removeObserver, notifyObservers?"
- They usually say add to array, remove from array, and loop through array.
- "We want to guarantee that even if
addObserver is called multiple times, the object will only be notified once. Would you change anything?"
- A bad candidate will get confused, and maybe propose some bizarre changes to
notifyObservers.
- A decent candidate will add a check to
addObserver. (You can quiz them to see if they think removeObserver needs to change also.)
- A better candidate may also consider changing the data structure to a set.
- "Let's say in our application we know that we will be frequently adding and removing observers. Would you change anything?"
- If they are still using an array, this push a decent candidate to consider a set.
On the surface it may seem like I'm encouraging people to use more sets instead of arrays, but really the point is that the whole problem is just a framework for having a conversation about choosing a data structure. It isn't about getting a right answer so much as seeing if the candidate will revisit their earlier choices, or if they dig in and never look back. In the rare case that they happen to start with a set, you can change the questions to make an array a better choice (e.g., "We want notifyObservers to be as fast as possible. Would you change anything?").
I also think there is some value in framing it in terms of implementing the Observer/Observable pattern, because you're asking the interviewee to work on a more abstract level. Really terrible candidates might not understand how you can do this without the Java class Library's Observable abstract class, or might spout a bunch of gibberish about "using design patterns" in a way that implies they don't know how to write code at all.