The patent approval process isn't perfect. Had you violated the patent, and had Google sued you, you could always argue prior art. What would your evidence be?

As I understand it it's much harder and more expensive to win a prior art claim after a patent has been granted.

The patent office could have just missed the prior art, or more likely is that the claims are more narrow than and represent an improvement upon said prior art.