I attend a technical interview meetup group, and there have been a few times when a Google employee has given mock interviews. I'm not sure how these match up with actual Google interview questions, but this was a public event, so presumably there were no terms of non-disclosure. The problem that I was asked was, "Imagine you're implementing a table top marble maze.

(Holes in the floor of the maze weren't introduced during the problem, though that'd probably make it a bit more fun.) You can rotate the board only one direction at a time, and you can't pause the board mid-roll; each rotation will have the ball meet with the end of a wall."

1. What pattern might you use to implement this?
2. What would the API look like?
3. A maze has been serialized to a file in which each cell of the maze is represented by bits describing the presence or absence of a wall. So if a certain cell has a wall to the North and West but not to the South or East, it would be represented as 1001, or 9 (where the bits represent NESW in order). Given a CSV file where each row represents a comma-separated list of cells for a row of the maze, how would you parse this file into the API from step 2? (e.g., "9,6,11,12\n3,10,10,4\n13,9,12,5\n3,6,1,6" in a 4x4 maze where \n represents a new line.)

Given the group context, we went through the problem rather quickly; in an actual interview setting, I would have been given an hour, so the question probably would have additional parts. This also isn't necessarily representative of the average difficulty of a Google question; he did say that difficulty usually ramped up, to avoid quashing the interviewee's confidence.

Other interesting notes: all other things being equal, Python is a better language choice for whiteboard coding, given its relatively succinct syntax and whitespace-based indentation, so if you know Python well enough to answer a given question, go ahead and choose it over another language. Of course this depends on the position and even the interviewer, as different interviewers might have wildly different backgrounds and ask you a variety of different questions. There's also a difference between the technically-focused questions like the one above, and more design-oriented questions, which I think are covered in another answer.

There are several books (e.g., Cracking the Coding Interview) which supposedly speak more to the interviewing strategies of some of the major software companies, Google included, and they come with hundreds of questions which test the same concepts. Not a bad purchase if you're prepping for an upcoming interview.