this is a great question that I personally struggled myself about a year ago as I was having a though time getting passed Senior roles.
In my case what I did, was starting to write. Every month I dedicated one full weekend to write a high quality blog post about a specific topic to position myself as expert and leader in my field.
Earlier this year I received two offers, in both I received questions similar to the second ones you mention. One of the questions was subjective and I said the "wrong" answer, in the other case the question was outside my area of expertise and I said "I don't know" with confidence. Your attitude is more important that knowing something you can easily google.
About the first kind of questions, sure do study but being a Staff Engineer is not about speed but depth in your analysis, ability to handle complex problems, and creativity when solving them. In that case my approach was choosing better companies to apply.
Couple more pieces of advice Omi: when interviewing ask hard and intelligent questions yourself, that will level the plain field for you. Finally, when choosing a job thing long about the technology and complexity of what you will be working on. Before making the jump I took a six month contract on a highly technical and innovative project before moving past the Senior level.
Best of luck!