You should know, in decreasing order of importance:
BFS
DFS
Topological Sort & Shortest-path in a DAG
Dijkstra's algorithm
Bellman-Ford
A-star (A*)
Floyd-Warshall (debatable, but it's 5 lines of code, so no reason not to know it)
With the exception of Floyd-Warshall, I have seen every single one of these topics come up in a Google interview.
BFS & DFS are self-explanatory. There are a huge number of variants that can be asked using them.
I applied online. I interviewed at Google (Warsaw, Masovia)
Interview
Recruitment is insane - you don't know the project, very tedious (second step is circa 5 hours), you don't know the team - they will try to match you to one when you pass coding session.
You need to write, error free, working code on notepad.
I don't recommend however the staff was friendly.
