For a company whose main claim-to-fame is indexing the web (rather than mirroring it in their databases), Google sure doesn't seem to understand that CS learning is done by mentally indexing textbooks (rather than mirroring them in your brain.)
I'm interviewing engineers frequently and although I agree that the question asked by GP is maybe not the best it still gives the signal if someone is willing to power through a problem with minimal guidance and/or ambiguous constraints. Something I'm willing to find out at the peril of pissing off a few candidates.
Software engineers aren't mathematicians. We don't invent algorithms or data-structures. That's not our trade-skill. And even actual mathematicians don't sit down to solve a real-world problem that no maths they're aware of directly solve—and then produce novel maths, and then use them to solve the problem—the very same year, let alone the same hour.
What I can do, as a software engineer, is to take algorithms that exist, and repurpose them or glue them together in novel ways that the designers of those algorithms never thought of, to do something new. Bitcoin, for one example, is a feat of pure software-engineering: it takes four or five existing well-known algorithms, and puts them together in a novel combination to solve a problem. I could maybe invent Bitcoin. But I can't invent Floyd-Warshall, if I don't know about it.
Google doesn't employ computer scientists (i.e. mathematicians who invent algorithms.) Alphabet does, under DeepMind and Waymo; but Google itself only employs—and only needs—software engineers.
Asking a software engineer, under pressure, to derive a novel algorithm, is a bit like asking a chemist, under pressure, to derive a novel class of chemical reaction; or a materials scientist, under pressure, to derive a novel material.
That's not the type of pressure that a real-world person in these jobs will ever be under. And moreover, it's precisely the type of pressure that people with experience in these positions have learned to mentally associate with "going in the wrong direction, toward wasted effort", flinch away from, and to turn around and study the literature instead.
It's ironic that Google expects its employees to all have university degrees. If there's one skill people who've gone to university are guaranteed to know (and to have built up a reliance on), it's consulting the literature.
Open-mindedness goes a long way. Also typically our interview questions are set up in a way where it's expected you won't finish but try, which reveals a lot about personality and how problems are attacked.
This attitude will keep you from hiring someone who will just "do the right thing," which is to look up stuff that can be looked up, and also persevere when an off-the-shelf solution won't be sufficient. Plenty of engineers will spend time trying to reinvent the wheel when it is totally unncesssary.
He left eventually but person was hard to work with because you had to beat back this kind of shenanigans every step of the way.
It's much more efficient to remember the general shape of problems, to remember where you can find further information (books, chapters, etc). Remembering that something is a well-studied problem, and where to find a solution, is straight-up more efficient than remembering that solution.
Dijkstra once remarked that trying to make a computer act like a human brain was far less interesting than seeing what the limits are of a computer as something that is unlike a human brain. It seems the reverse observation is also true - human brains, once freed from rote memorization and computation (that's literally what programming does to us), can tackle much larger, more interesting, and more complex problems.