I interviewed with google last year - onsite so the recruiter skipped my OA or telephonic round.

Onsite:
1.) Some cars, road weird question. You are given starting state of cars. something like R _ _ L. Now, this example has 4 lanes. R means this car has put the indicator on to move R, this car can only move right or stay where it wants to be. and the car blimking L can chose to stay there or move left only. but cars can't collide. You are given a end state and you have to tell if that state is possible. Initially I thought it is a word ladder question but that was not the case. Then I thought may be if I assign a unique Id to a car say 1, 2, 3 and so on. the right car can only move right so the value will get smaller and the left car can only go towards most significant bit so some kind of number comparison. I don't know the right answer though. one more example can _ R can not have R _ as the final state.
2.) check if you can insert an interval. Started with Binary search on sorted list end up on a search in a BST traversal because handling of mid conditions in the sorted list was getting way to complex at that time. The interviewer allowed me to assume the input in whatever format(just state the assumptions). Follow up qs : what if the given list of schedule in all in the range of 1 .. 100. No need of any fancy data structure just use an array.. arr[i..j] = 1 will represent some interval k's start to end. to check if you can insert just check if you there is any 1 in arr[incoming.start... incoming.end]

3.) Basically word ladder problem. With time + space complexity. The interviewer asked why did you chose bfs over dfs. I said because as of now you haven't mentioned any minimum step constraint but If I have to extend the problem to find the end state in minimum step then bfs is a better option in any case.
4.) Robot clean up problem. Another bfs/dfs traversal problem with time and space complexity discussion.
5.) goolyness - Again cook up stories, let's talk kinda interview. 80 percent of the questions were around unethical behaviour that someone was unethical, you were unethical.

Not too optimistic because in the first round I didn't understand the question and somehow I feel Google wants candidates to be very suave with the code. No typo, no second guess, no more than 900 ms should be spent in order to come up with the most optimim approach.