Yes but Google wants the right answer, regardless of the way you think and regardless of the fact that you came up with a proof for P=NP on the interview
I've asked a few different interview questions in my time, and the number of candidates who have gotten the "optimal" solution currently sits at 0, to any of the questions.
Despite this, I've suggested that we hire some of those "wrong" answer candidates. And given the interview feedback I've seen, I'm not the only one like this.