You're assuming that it's important to actually solve the problem. I'm not sure that's the case - it's really asking whether or not the candidate understands that brute forcing is a poor solution and determining whether they're capable of even looking for a better solution. A lot of developers find it very hard to look past the obvious first solution they find to a more efficient algorithm instead. Specifically companies like Google want to hire people who can do that deeper work.
The real issue with problems like this is when much smaller companies hiring a dev who'll be bolting together APIs and won't ever need to know an answer start to copy the technique believing "it's how you hire devs".
The real issue with problems like this is when much smaller companies hiring a dev who'll be bolting together APIs and won't ever need to know an answer start to copy the technique believing "it's how you hire devs".