I think it might be the classic distinction between "simple" and "easy".
I do believe that most of those problems are "simple" - typically when you read solutions, it's under 20 Python lines of code; and not really complex or difficult to understand code.
At the same time, I agree it's not very "easy" to do them well (come up with a solution, code it up, test it, and explain everything along the way considering trade-offs and pros and cons) under the interview stress and time pressure. Even the most brilliant and well prepared people do fail them for a reason.
Its hard to grok you calling them "simple", then saying brilliant people fail them. One could define hard as "a thing that even brilliant people fail at".
For me, easy is something that a person of average skill in that domain can do and that the top 20ish% person in that domain can do with their eyes closed.
I have a masters in CS, I know all of the words and stuff in your essay. I have been programming python for a while. I would most definitely need to study up on graph algos, implementing sorting algos, dynamic programming, etc. Then refresh my big-O notation as well. Unless you are doing it everyday, this stuff ain't simple or easy to master to the level of being able to code it up during a 45 min online session.
I can easily see 2-3 weeks of full time studying for myself to even be minimally ready to code up a BFS search in python, as part of a larger problem, in python, in 45 minutes, while writing an example down, while writing a test case, while talking out loud.
