Another favourite of mine is basically "implement a very sparse 100Mx100M matrix". Thought process much more important than result. (important things to consider: access time, storage size, static vs. dynamic, use cases, adversarial coordinate selection).
I actually consider the "cycles in the input" question a bit of a trick question -- I calibrated the test on people I knew were good, and no one who didn't know it already was able to come up with "the trick" in reasonable-settings-for-interview-time, and not many were able to come up with any O(1)space O(n)time solution.
The discussion with those who don't know the solution is useful, of course.
Agreed, the discussion on these questions is the whole point, not whether you can come up with a "correct" solution (and I tell candidates this up front).
I generally draw a small example input with a cycle, and ask what their list-reversing solution will do with it, which I feel makes it much less of a trick question. "Can you work out what the code you just wrote will do with inputs that don't meet the assumptions you made?" seems like a fair thing to ask anyone who will be required to write code that handles untrusted data.
I've found that having common questions used across many interviews allows for more objective direct comparisons. I like this one in particular because even if they solve it quickly, you can move on to questions about cycles in the input.
What do you use now?