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.
Was this for a software engineering role? I've never been asked this, and I'm pretty sure during interview training you are explicitly told not to ask those sorts of questions.
No, not software engineering - product management. That said, the position in question was still of a fairly technical nature as far as I understood it.
Sure, but coding doesn't apply to the position you applied for. Fermi questions are a good way of determining cognitive ability and problem solving, especially when coding or algorithmic questions aren't appropriate. I've gone through both PM and SWE interviews at Google, and am currently a SWE and interviewer. My PM interview had a Fermi question, and thought it was enjoyable and appropriate for the position.
So I'll try to respond to this with as little bias as possible considering I was an interviewee and you have self-identified as an interviewer.
I am not debating the utility of Fermi questions, I can see how they might be useful and/or might be harmful during the interview process. My statements have been simply that my experience differed from what others have been saying, in that I definitely had that type of question during an interview with Google, so clearly they cannot be "against the rules" or anything like that.
That said, these types of questions are a bit like any standardized test (such as the SAT/ACT, etc.), which may or may not be strong indicators of cognitive ability/problem solving depending on who you ask. I think there is enough controversy over standardized testing to be able to at least say that solely relying on such methods, especially in a high-stress situation or even due to cultural differences, might come with some drawbacks and not be an accurate indicator for all candidates.
Lest I forget, Google is a business, and if such tools are what help Google find the candidates it wants, then so be it. It might also be an indicator to candidates about what kind of organization Google is. As a business, the organization will usually prioritize its desires/needs/benefits over those of the candidate - it's not a charity, and I get that. All I am saying is, it may just be that they are excluding certain diversity or individuals unnecessarily without realizing it. Perhaps that is the motivation behind the reported change in attitude towards such types of questions, I'm not sure.
It may or may not be that coding skills were relevant to the specific position. That said, in my experience, product management in software companies in particular is not stovepiped in such a way that you need not have any experience in coding. In fact, I think that some of the best product managers in such companies have coding experience, business experience, hardware/software/etc., and/or cross-disciplinary skill-sets. Perhaps such strong candidates don't fit the standard model, I'm not sure.
Brain teasers are not as frowned upon as much for non engineering interviews but they are absolutely banned for engineers (source: former Google employee with about 300+ interviews during my time there and also former hiring committee member).
No, unfortunately, I can't give you a useful answer here. It seems that, in the first rounds of interviewing, you might not be interviewing for a specific position initially, rather, a function/role (for example, product management or software engineering).
In my case, I was clear that I was unable to relocate, which left only a specific position available as a possibility which was nearby. The reason I thought that specific position had technical responsibilities was by the description of said responsibilities in the job description as posted. Also, I was told that I was contacted by Google in large part because of my technical background, but during the interview, that background was not discussed or explored.
In general, our product managers are technical -- almost all have a computer science degree, many have worked as engineers. When going through the initial interviews you are usually not interviewing for a particular position, but rather as a "generalist."
After the hiring committee has decided whether or not to hire you, your specific background will be matched with specific openings around Google. Naturally, some products require less technical expertise than others.
Disclaimer: recent Google interviewee.