I applied through a friend at Google. I had a 45-minute phone interview with a software engineer. He asked for a brief overview of my research and then asked several coding questions. They were average difficulty, similar to the ones on CareerCup or Glassdoor.

Then, I had an on-site interview, which consisted of four coding interviews and one research interview. The four coding interviews went over algorithms and system design. The interviews had a shared document that let them know which topics had already been covered, so it pays to prepare for all of the topics covered in a typical software interview. The research interview was a casual conversation about my thesis research. My advice is to get a coding interview book and do as many of the practice problems as you can on paper.

Describe an implementation for a hash table. Explain how the data structure changes as more items are added and sketch a proof for the amortized complexity of operations.