Google's interview system is not great but there are various reasons why it feels less than it is. Most candidates don't know what the goal of our interviews are. First rule, it is not about finding an optimal solution or any solution at all.
You are interviewed for multiple skills simultaneously. Cognitive skills, communication, leadership are a few to name. If the point is not finding a solution, then what is it? Let me explain.
Your interviewers try to understand what it feels like to work with you on a daily basis. An interview question is just a tool in achieving that, it is not there to specifically measure your skills on a topic but a tool to understand the depth of your thinking.
Before the interview starts, ask them what they want to get out of this interview. Good interviewers should already have a plan and a set of expectations. Ask them what you should do. Don't start coding yet. Ask them you should produce. Discussion, diagrams, pseudo code, code?
Then, start cracking the question. List whatever questions you think it is important to solve this question, ask your edge cases. Get to a point where you are discussing about pros/cons of the solutions. These steps are critical. Don't just start coding. Have a consensus first.