This is a great question that I personally struggled myself about a year ago as I was having a tough time getting past Senior roles.

In my case what I did was start to write. Every month I dedicated one full weekend to write a high quality blog post about a specific topic, to position myself as an 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, your ability to handle complex problems, and your creativity when solving them. In that case my approach was choosing better companies to apply to.

A couple more pieces of advice, Omi: when interviewing ask hard and intelligent questions yourself. That will level the playing field for you. Finally, when choosing a job, think long and hard 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!