There's a certain category of questions that fall into that sweet spot of "takes a tiny bit of thinking but not too much." Those can be used to validate early on some basic level of competence. Clearly, if they can't do a basic coding exercise, you know you can eliminate them.

Here's a problem that I like along these lines (this is from the soon-to-be-released 6th edition of Cracking the Coding Interview):

Given a list of people with their birth and end years (all between 1900 and 2000), find the year with the most number of people alive.

There are some more interesting algorithms for this problem, but people should be able to come up with a basic brute algorithm. Many, however, can't.

This is what the FizzBuzz problem is purported to be: a basic coding exercise. If you can't complete it quickly, you are obviously unable to write code. Out you go!

Here's the problem, if you haven't heard it before:

Write a program that prints the numbers from 1 (inclusive) to 100 (exclusive). But for multiples of 3, print “Fizz” (instead of the number). For multiples of 5, print “Buzz” (instead of the number). For numbers which are multiples of both 3 and 5, print “FizzBuzz”.

Surprisingly, according to the author of the original FizzBuzz post, a great number of developers can't do this.

The issue is that FizzBuzz has another element to it that throws people off. I call it the Smart Person's Mirage.

Some people who fail FizzBuzz are genuinely quite bad. Others are actually good developers who just get caught by the Smart Person's Mirage.

Beware the Smart Person's Mirage
The Smart Person's Mirage is when a problem looks like it has a "cool" solution, but it doesn't.

The dumb (or lazy or new) developer will not notice or care about the appearance of a potential cool solution. They'll just bang out whatever works. They actually do okay on this problem.

The smart developer -- not all, but many -- will notice the appearance of a "cool" solution and chase after it.

It's a "mirage" though because there isn't a cool solution. It just looks like there is.

This is the "obvious" solution:

for i in range(1, 100):
    if i % 3 == 0 and i % 5 == 0:
        print "FizzBuzz"
    elif i % 3 == 0:
        print "Fizz"
    elif i % 5 == 0:
        print "Buzz"
    else:
        print i

The smart person could do this, sure.

But come on! There's got to be something more elegant! The thing you print for divisibility by 3 and 5 (FizzBuzz) equals the thing for each value individually (Fizz and Buzz). That's not just a coincidence. Obviously, you should leverage this in your solution.

They really want to do something like this:

for i in range(1, 100):
    if i % 3 == 0:
        print "Fizz",

    if i % 5 == 0:
        print "Buzz",
    ....

But this doesn't work because you still need to print the number if neither of these are true.

So maybe they'll wind up here after some trial and error:

for i in range(1, 100):
    if i % 3 == 0:
        print "Fizz",

    if i % 5 == 0:
        print "Buzz",

    if not(i % 3 == 0) and not(i % 5 == 0):
        print i,

    print ''

That's no prettier in the end than the easy solution. But, arg! That repeated modulo-3 and modulo-5 is annoying. Let's combine them.

for i in range(1, 100):
    if i % 3 == 0:
        if i % 5 == 0:
            print "FizzBuzz"
        else:
            print "Fizz"
    elif i % 5 == 0:
        print "Buzz"
    else:
        print i

Now we just have confusing code. We should have just stuck with the easy, obvious solution. But the smart developer might just identify (intelligently) the potential for a "cool, elegant" solution and never find it. It's a mirage, after all.

But -- you might say -- a good programmer produces value for the business. So if they're chasing after these crazy solutions (wasting time and resources), then you want to reject them, right?

If they did this in the real world, sure. This would not be a good thing.

The problem is that the way someone acts in an interview is not necessarily representative of how they would act in real life. People act in an interview the way that they think you want them to act.

They think you want an elegant solution because the simple one is too obvious and it feels like there is an elegant solution. Off they go, trying to find that cool, elegant solution!

This isn't a reason to reject them. It's a reason to stop asking this question (there are better sanity-check questions), or at least be a heck of a lot clearer about your expectations.

.................

ADDENDUM: Well actually, Gayle, there IS a cool solution. You should...

Yes, yes, there are many other solutions. I know.

You could save the results of i % 5 == 0 and i % 3 == 0 into a variable. At best, you're getting a very, very minor efficiency improvement at the expense of readability. More likely, you won't really speed up much. This is the kind of thing compilers tend to optimize away.
Rather than doing i % 5 == 0 and i % 3 == 0, you could just do i % 15 == 0. Yes, but again, you're hurting readability for the sake of a minor efficiency boost... which probably won't even exist because the compiler will likely optimize this way.
Since the output repeats every 15 iterations, you could store those first 15 values in an array and then access them with the index of i % 15. See earlier comments. Minor efficiency improvement at the expense of readability.
You could use string concatenation to build the result at each iteration, concatenating "Fizz" if i % 3 == 0 and "Buzz" if i % 5 == 0 (if the string is empty, you just print i).

And so on.

Go ahead and brainstorm your own solution. There are many.

However, I have yet to see one that would actually be better in the real world than the simple, obvious solution.

This doesn't mean that I think poorly of someone in an interview for chasing after these "cool" solutions. How do they know that's not what you're looking for? How do they know that it doesn't exist before they've tried?