I haven't had a Google interview, but looking at their past and current problems for the Google Code Jam would certainly get you some practice.