And when Google implemented Java for Android, how, pray tell, should they have implemented Collections.shuffle?

Implementing a stdlib isn't a thing you do every day. Presumably GP was referring to more common situations, where using the stdlib is (usually) preferable to rolling your own solution.

They were interviewing for Google. It's not uncommon to have to implement a standard library function (or not be able to use one) in many contexts at Google. Besides, the question is just the most basic setup to assess how a candidate would fare in comparable situations.

Is it though? Because the answer to "suddenly I need to implement a standard library" is "I google the accepted solutions" and if I don't have Google then I goto the library and check out a bunch of old CS books.

And then the interviewer's follow-up question should be "fine, since you don't want to indulge me and implement a solution to this toy problem, I'll ask you to implement a much more complicated function which doesn't exist in any library!"

They grabbed it out of harmony.

But you would not be concerned about a candidate that does not understand that this question is clearly (very clearly) meant to assess how they understand and approach algorithms and randomness?

It's obvious that you should use a library function if there is a library function.

A question like "how do you reverse a string" surely is like asking a chef to cook an egg? Any idiot can do it, it's got to be an opening on to "who are my customers?", "what are the cost and time constraints?", "what team members do I have?" "what's our angle" ...? If the answer is just "boil it for 5 minutes" then you know you're looking at someone with simplistic thinking; which is fine if you just need someone to mindlessly do as they're told. They might be an absolute expert at it.

Yeah, it's just an opener. Setting the stage, making sure everyone is on the same page, and then you can build onto that à la "and now suppose xyz...".