The person who interviewed you is going to write their brain-teasery questions into their interview feedback and get a strongly worded email from the Hiring Committee.
Statistically, across multiple interviewers, Google does not allow these questions.
You actually indirectly highlighted one of the problems with these types of "brain teaser" questions.
Condition 1: If you are actually as brilliant as Donald Knuth, and independently derive the Floyd's cycle-detection algorithm, then obviously you must have cheated, because only Donald Knuth could have come up with that sort of thing in 20 minutes.
Condition 2: If, on the other hand, you aren't brilliant like Donald Knuth, you'll probably come with the naive solution using a visited data structure of some sort, in which case you're stupid because you can't come up with the optimal algorithm.
In either case, you bombed with that interviewer.
Condition 3: Cheat. Do the naive algorithm first, then have an "ah-ha" moment that magically gives you the optimal algorithm, because you actually knew it before hand. I suspect, but can't prove, that some hires get in this way. During my time as a PhD researcher studying deception under a related NSA grant, I routinely found that a) people are horrible at lie detection, and b) people greatly overestimate their ability to detect lies.* The perfect way to game the system!
Alternatively:
Condition 4: Inform the interviewer that you're aware of the cycle detection algorithm, and get another brain teaser that reduces you to Condition 1 or Condition 2 (and if less than ethical, Condition 3). Oops.
Ideally, you want interview questions from which you can start at Condition 1, and without deus ex machina, eventually get to Condition 2, perhaps having the interviewer give some hints along the way. Better is to start with a problem that has a reasonable Condition 1 solution, and then slowly modify the problem specification for increasingly complexity ("Now pretend this is an arbitrary graph instead of a tree, what would you have to change?").
Finally, Google maintains a list of banned questions which have such brain teasers (technically, they have an entire question pool), but unfortunately, interviewers don't seem to check them frequently enough and so brain teasers continue to persist (even in 2015).
* If you're fascinated by lie detection, start with scholarly publications from Aldert Vrij, and work from there.
Maybe to solve optimally, but most algorithm questions should be able to be answered with the knowledge attained in a Data Structures and an Algorithms course.
Statistically, across multiple interviewers, Google does not allow these questions.