Put me in a room with a couple of people, a not-real-world problem, a compressed timeframe and tell me to go, and it's a different story. After that time is up, you'll swear I don't know the first thing about technology and go to the next guy.
Why is this? Interviewing psyches people out sometimes. In my case, the act of being judged by my peers gets me to the point where I actually do blank out.
By the way, I failed my very first interview just like the guy you talked about. Complete brain freeze. Luckily, I got an internship and here I am with 7 years of software development under my belt. You probably might not care. But it really makes me wonder about all that wasted potential. Not everybody is as lucky as me.
However, my challenge was to implement Conway's Game of Life from scratch, which I consider markedly more difficult than Fibonacci.
Interviewing candidates is hard. I know because I've done it before. It's much easier to have a boilerplate CS 201 problem that you give to every candidate vs tailoring the interview to each candidate each time. However, I've hired some of the smartest people I know based on this tailored, specific to the business, approach. Most of the candidates I helped hire were still at the company when I left.
If you do boilerplate CS questions you'll get either students right out of CS programs that have these concepts fresh in their minds or people that have been unemployed for a while who have brushed up on their algorithm skills via Cracking the Coding Interview. Maybe these are the types of people you want because they might be cheaper? Most of the software work I've done in the past 7 years has been taking existing frameworks, libraries, systems and adding in some custom logic. Maybe that custom logic becomes a new library on its own and maybe not. You know what's more important to me than the ability to solve Fibonacci? Do you write clean, documented code? What is your ideal software development methodology and can you ship code in that environment? Do you test? Are you a dick or not? What does your gitHub account look like?
Software development employment isn't college. The hiring process shouldn't be a "hazing" as others have stated. I recently had an interview where I as the candidate partially spaced out a problem that was similar to Fibonacci (duh on my part). However, at the end of it the interviewer I think recognized the situation and said "We are all a team here and we help each other out. I'm OK if you are a little weak on generic algorithms in this situation because you know things I'm weak on." That was a good experience and hopefully I'll get a chance to be on that team.
Overall, I'm guessing most companies out there aren't trying to solve "Google" like problems. We should stop interviewing like we are.
Fibonacci is not such a problem. It includes declaring one argument, a handful of variables, one for loop, a couple of assignments and a return statement. And he could not do this with open and explicit guidance.
As he was applying for a senior backend developer position, I can only conclude that morphing complex data structures and calculating shopping carts with taxes, rounding and campaign deductions will be a problem. Maybe I'm wrong, and I should mention that there were additional interview steps and questions where my interview partner didn't have confidence in the candidate, but I really feel that this excercise tells me something. And that's the problem with these kinds of interview techniques I guess. That they do feel very relevant.
This excercise in particular took a little more than an hour, because even though I explained a few solutions in various ways he had a hard time actually completing any code. I wrote a whiteboard solution and explained it using arrows and walk-through examples, but he couldn't translate the solution into actual code (using a language of his choice). In order not to break the hour limit we ended up with me writing and explaining code one line at a time for him. I reassured him that it's okay that he can't come up with the code right now, we're not evaluating the result etc.
I turned this candidate down. I feel that while my methodology (close to OP's) has flaws, it does help me with filtering out the worst candidates. I simply can't hire someone that doesn't manage to, with an unlimited amount of help and a generous timeframe, code a Fibonacci sequence in his/her favourite language.