I didn't ask them to implement dijkstra's algorithm, or even something as "hard" as breadth-first or depth-first search (which I feel any senior that deals with trees should be able to do).
It's a marker of this... Can the candidate solve a basic problem? Once they solve it, can they explain their solution? Do they understand the memory/time tradeoffs they chose? Do they know whether the code they wrote is thread-safe? If you don't feel a senior engineer should be able to answer those questions, to a very basic problem, how do you expect them to tackle something more complex?
As for the interview itself, well I've never needed to ask someone to reverse a string to determine if they're going to be of value with the criteria mentioned above.
But to be fair I've never worked on a project where implementing StringUtils.reverse() was required. If I were interviewing someone to work on Apache Commons or the JDK then I suppose that would be a relevant question.
What I'm interested in from a senior engineer is how many systems they've designed, implemented, deployed to production and supported in their careers and what their specific roles were in those projects. If I can't get an idea from their resume I wouldn't contact them for an interview.
And when their resume looks good and claims they are an expert, and you call them in and talk to them and they say they are an expert, and you start by opening a warmup question on the most basic levels of their expertise and they totally flunk it on multiple levels - unable to even handle the situation with tact or diplomacy in any way, are you still going to trust what they say about the systems they've "deployed and supported"?
It's not that I think the question is too complicated, just not the best marker.
In my mind, more relevant questions are ones that demonstrate real life experience in the field. For example, populating a tree of objects in a high level language like Java from a DB where the tree of objects are stored as many to many relationships. You'd be surprised how many times I've run across production code which does this via SQL calls inside nested loops.
This whole infatuation with algorithm questions like you'd find in SICP might be good for new grads but misses the mark for Senior level engineers.