It's normal to not be pleased when a candidate fails to understand a question (or exhibits smart-ass behavior), though in this case the easy and correct thing for the interviewer to do is to say "OK, how is Collections.shuffle implemented?"
And very likely that's what really happened. I have been in such interviews and it is sometimes hard to guess whether the interviewer wants the practical answer (calling a library function) from engineering standpoint or the conceptual answer (demonstrating that I can implement the inner workings of the function) from CS standpoint. Often I would just ask a follow up question to clarify exactly at which level of abstraction does the interviewer want my solution to be in?
In situations where I offer a solution that does not match the interviewer's expectation, they clarify the expectations.
Sure I can teach constant vs. linear time. But what incentive or reason do I have to spend time teaching these fundamental concepts when I can just hire an engineer who demonstrates the understanding of basic CS at the interview time itself?
Given two candidates with all things equal except that one demonstrates the understanding of CS fundamentals and other does not, why would I want to hire the second person and spend our time teaching him those concepts?
Someone commented on here recently that they would take motivated candidates over knowledgeable candidates. That's one reason. I can easily think of at least two others.
There are balance points here that vary according to all sorts of things.
I mean if there are two candidates who are equally motivated and are more or less equal in all things except that one is strong at CS fundamentals and another isn't, is there a good reason to reject the candidate who is good at CS fundamentals.
In many hiring decisions, I am faced with a similar choice, and I go for the person who is good at CS fundamentals. If two candidates are good in all other ways, then the understanding of CS fundamentals becomes a tie breaker. I see no rationale for selecting the guy who does not demonstrate his strength in CS fundamentals.
A real life task might be implementing a much more complex library over several days or weeks. Asking the person to implement a simple function like shuffle is the closest you can get in the span of an hour.