Questions like this can work in a phone screen if you have a shared virtual whiteboard. Otherwise it is painful for the interviewer to try to transcribe code as the candidate thinks of it and says it alout.

There is also the common problem where candidates google for answers or at least seem to google for answers during phone screens.

The problem with asking truly challenging coding questions during an interview is that they are often too challenging to finish in the time allotted. Frequently challenging coding questions require an ahah moment or domain knowledge. For example if an interviewer asks a candidate to invent an advanced algorithm on the spot what is being measured? If the candidate gets the answer right they might be really smart, they more likely have been previously exposed to the idea, or they got lucky. If they got the answer wrong the interviewer must judge them on their ability to communicate their thought process during their attempt - but from that the interviewer didn't learn if they can code.

You shouldn't be disappointed that interviewers don't know straight away that you aren't a charlatan. You should instead be disappointed by the fact that there is such a high number of successful charlatans in our industry.