Disclaimer: This article is basically a dump of my disorganized notes I took during my interview prep, don’t expect it to be good.

Preparing for coding interviews definitely gets our nerves rattling, even if we’ve been coding for years. No matter how seasoned you are, the pressure of interviews can still be overwhelming.

Before my Google interview, a friend pointed me to the blog Get that job at Google. The author introduces the concept of the “Interview Anti-Loop” which really stuck with me. It’s basically the idea that, no matter how prepared you are, there will always be someone who thinks you’re not the right fit or a problem you can’t solve on the spot.

And then there are those pesky interview-specific algorithms. A worst example would be swapping two numbers without using a third variable. It’s a tricky problem that defies common intuition, is rarely applicable in real-world coding, and can be solved with a bit of time or a quick search.

To boost my chances during my recent interviews, I put together a list of concepts using the MoSCoW method, which I could use to prepare based on how much time I got. I also noted down some interesting interview-specific algorithm styles. I’ll be sharing my personal interview prep list in this post.

The Ultimate Checklist

Must Have(s)

Have these or you are probably screwed.

  • Array
    • Two pointer
    • Sliding Window
  • String
    • Substring Problems
  • Hash Map
    • Storing previously seen values to reduce computation
    • Tree
      • Binary & N-ary Tree
      • Passing value down to the child node
      • Receiving value from the child node
      • Trie
      • BST
  • Graphs
    • BFS & DFS
    • Depth-Limited Search
    • Backtracking
  • Binary Search (& variations)
  • Dynamic Programming
    • Top-Down
    • Bottom-Up
    • Multiple dimensions
  • Prefix/Suffix Sum
  • Heap (Usage)
  • Interval Scheduling Problem

Should Have(s)

Definitely need but let’s hope luck is on your side.

  • Quick Sort
    • Quick Select
  • Merge Sort
  • Divide and Conquer
  • Union-Find
    • TBD (Two implementations?)
  • Graphs
    • DAGs
    • Topological Sort
    • Dijkstra’s
  • Data Streams
  • Dynamic Programming
    • Kadane’s Algorithm
    • Subset problem

Could Have(s)

The hard-to-solve why-would-anyone-ask section.

  • Bidirection BFS
  • Heap Sort
  • Counting Sort
  • Heap (Implementation)
  • Segment Tree
  • Rolling Hash
  • KMP Algorithm
  • Graphs
    • Minimum Spanning Tree
    • A* search
    • Traveling Salesman Problem
    • Morris Preorder Traversal
  • Math
  • Knapsack Problem
  • P, NP, NP Complete, NP Hard, Weakly NP Complete (Nice to know).
  • Two Heap Technique.

Won’t Have(s)

The I-have-too-much-time section.

  • AVL Tree
  • Red-Black Tree
  • Reservoir Sampling
  • Hash Heap
  • Radix Sort
  • Alias Method
  • Graphs
    • Bellman-Ford Algorithm
    • SPFA
    • Floyd-Warshall algorithm
    • Eulerian Circuit
    • Hamiltonian Circuit
    • Tarjan’s strongly connected components algorithm

The Algorithmic “Hacks”

I didn’t get to document everything and this list is very incomplete.

Light-Weight Datastructures

Bitwise Optimizations

  • x2 => << (shift left)
  • /2 => >> (shift right)
  • Find odd or even with &1, i.e., x&1 == 1 iff x is odd.
  • Re-using unused bits using a bitmask operation.
  • N%2i == N & (2i - 1).

System Design Pointers

Just rough notes.

  • Manage Time Better
    • Don’t clarify, let the interviewer disrupt your checkpoints.
    • Not all numbers are important. QPS is important. Storage is usually important.
    • Memorize all non-functional requirement possibilities, then just shoot them (yes, no).
    • Explain by use cases (read, end to end) vs by sections (API, then data schema, then high level design).
  • Have to mention trade-offs (SQL vs NoSQL, push Vs pull, REST Vs GraphQL, sync Vs async, core puzzle).
  • Non-functional checklist
    • Reliability
    • Scalability
    • Security
    • Durability
    • Latency
    • High Availability Vs Strong Consistency.
  • For estimations, don’t just list numbers but explain what choices it guides in your design.

Some Good Reads

A Disorganized list of articles that I liked.

Coding

System Design