The 12-ball problem
Example of a common, simple Oracle query being unexpectedly expensive.
When is a garbled string the one I'm looking for?
The Monty Hall Problem
A few less-interesting interview problems: