What You Need to Know for Your Google Interview, and What You Don't

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
  • stacks
  • queues/deques
  • arrays/vectors
  • hash tables (maps)
  • sets
  • binary search
  • sorting
    • selection
    • insertion
    • heapsort
    • quicksort
    • merge sort
  • priority queues
  • binary heap
  • trees
    • binary search trees
    • balanced search trees (general concept)
    • traversals: preorder, inorder, postorder, BFS, DFS
  • graphs
    • directed
    • undirected
    • adjacency matrix
    • adjacency list
  • dynamic programming (note: does not appear in coaching notes, but is useful)
  • probability
  • permutations and combinations
  • object-oriented programming
  • processes/threading
    • memory
    • caching
    • deadlock avoidance
    • scheduling
  • 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
    • Prim-Jarnik
    • Kruskal
  • geometric algorithms
    • convex hull
    • positional/overlap/horizons
  • union-find / disjoint sets
  • backtracking
  • pattern/substring matching
    • Rabin-Karp
    • Boyer-Moore (Horspool)
    • Knuth-Morris-Pratt
    • suffix trees
    • suffix arrays
    • tries
  • 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)
    • B-trees
    • k-D trees
  • balanced search trees (details such as rotations)
    • red-black trees
    • AVL
    • splay trees
  • data compression, information theory
  • linear programming
  • garbage collection
  • cryptography
  • skip lists
  • van Emde Boas trees
  • treap
  • multisets
  • multimaps
  • 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!

comments powered by Disqus