Don't be like me. I went overboard and overprepared for the interview. I studied way more topics than I needed to.
I recently confirmed with my contact at Google what I need to know for the interview.
This is for software engineer positions. If you're applying for other positions (e.g. systems engineer), obviously the criteria change.
-- quote from my contact
This is based on how much experience you have. If you are coming to Google as an intern or entry-level software engineer, you only need the basics. There are a lot of basics, but it's manageable. Even if you're looking at less than 3 years experience, the list is the same.
If you are new to Computer Science topics, even if you have many years as a software/web developer, just say you have 2-3 years experience. If not, they will expect much more knowledge out of you. At Google, software engineering means you need to know:
- complexity/space analysis
- bitwise operations
- linked lists
- hash tables (maps)
- binary search
- merge sort
- priority queues
- binary heap
- binary search trees
- balanced search trees (general concept)
- traversals: preorder, inorder, postorder, BFS, DFS
- adjacency matrix
- adjacency list
- dynamic programming (note: does not appear in coaching notes, but is useful)
- permutations and combinations
- object-oriented programming
- deadlock avoidance
- testing practices (1+ year experience)
If you have a networking background, expect to be asked:
- network stack / OSI
If you have 4 or more years of experience, expect system designs in addition to coding problems.
- scaling large systems
- designing for scale
What You Don't Need to Know
I would not expect any given candidate, regardless of experience, to know any of these items.
Even though you don't need these, my contact mentioned: "It is expected that a candidate can understand and apply any of those concepts if they are explained, however."
- Dijkstra - single-source shortest paths
- Bellman-Ford - single-source shortest paths, allowing negative weight edges
- Floyd-Warshall - all-pairs shortest paths
- Ford-Fulkerson - maximum flow
- Minimum spanning tree
- geometric algorithms
- convex hull
- union-find / disjoint sets
- pattern/substring matching
- Boyer-Moore (Horspool)
- suffix trees
- suffix arrays
- Selection (k smallest items, etc)
- Other types of graph representation:
- adjacency map
- edge list
- Linear-time sorts:
- radix sort
- bucket sort
- counting sort
- Other types of trees:
- (a,b) trees, k-ary trees (example: (2,4)-trees)
- k-D trees
- balanced search trees (details such as rotations)
- red-black trees
- splay trees
- data compression, information theory
- linear programming
- garbage collection
- skip lists
- van Emde Boas trees
- fast Fourier transform
- Bloom filter
Why I Over-Prepared
My sense of fear ("What if they ask me a question about red-black trees?") led me to study way more topics than I needed to.
But I didn't want to just prepare for the interview, I wanted to prepare for a career at Google, solving large-scale problems. That means knowing algorithms that will save computing resources of time, space, and I/O.
I may not need to know a maximum flow algorithm (Ford-Fulkerson), but it's nice to know I have that tool available if the situation arises, and can recognize its application to a problem space.
If you love data structures and algorithms, as I do, go nuts!