I interviewed with google starting last year in december.

Went through the Prelim round, the interviewer asked a medium problem that asked for Topological sorting. Coded the solution in 5 minutes and spent 15 minuites taking interviewer through the different test cases using the solution. After he was satified he gave me what if, I found the hint to be an improvement, not in terms of run-time but just simpler code. I made the improvements and he was satisfied.

Onsite:
1.) This round stated with a problem that asked for depth first search, i coded the solution and he added on the problem, for which i modified the approach to cover. He asked me for runtime complexity. I realised the runtime complexity was bad. he asked me for some what if, and i did the changes, they made the code readable but did nothing for runtime. Note: After the interview i thought of a perfect solution that could have improved the runtime complexity a lot, but it didn't come to me during the interview.
2.) In this round i was given a problem that required DFS or BFS, but i found that these solutions will less optimum so i went with Union find. Coded Union-Find and explained the algorithm to the interviewer.
3.) This problem too required DFS/BFS, but i applied Union-find to it, improving the runtime from DFS/BFS, this round went like a dream.
4.) System design problem, discussed capacity estimate, domain design, service design, cache and database sharding. Used the capacity estimate to answer some quatitative questions asked later.
5.) goolyness - Spoke from heart, and itterated real stories from my previous experiance.

Got the offer. I think the most important thing for me was time managment, i talked while i coded, explained away as i was writing the code. I wanted to give the most optimal solution, so i went with them, i discussed why the optimal solution is better then the other. After finishing would take one of the test cases and go through the code with that test case - line by line, to talk the interviewer through the solution again and check for any mistakes and corner cases.

I think the key was time managment.