Prepping for a Google Interview

March 13, 2014

These are a bunch of notes I took when I was reading through Cracking the Coding Interview in prep for a Google Interview

  • spelling algorithms correctly is important


  • insertion sort always O(N^2) because going through and moving
  • binary sort can assist it to be O(log(n)n) for insertions but still N^2 for swaps
  • merge sort two arrays, sort, then merge, then split and repeat. O(log(n)n) complexity
  • priority queue - - maxheap, nodes are always larger than or equal to their children (max heap property) - minheap, nodes are always smaller than or equal to their children (min heap property)
  • heap sort – heap on a tree, (breadth first view,) int array[7]; indexies -AVL trees
    • traverse = n
    • insert nlog(n)
    • delete min
    • find next min and max and next smaller and next min
    • log(n),

Comparison Model -Searching: (lng) -Sorting nln(n) -All input items are blackboxes In reality

Linear time sorting for not large - O(n sqrt(lnln(n)) -Prehashing = alpha = n/m time, orderone = theta(1+alpha) (a*k)mod(2^w) » 2^(r-w) where m = 2^r also k mod m - hash the function and modulus

Hash table properties

  • make use of all info provided by key (Key:Value)
  • uniformly distrutes output across table
  • maps similar keys to very different hash values
  • uses only very fast operations to minimize run time.


  • Binary Tree / n-tree / AVL Tree / tr-tree
    • Their Traversals
    • Insert/delete/search
  • Make Graph / Search / Edges/Vertices
  • Quick/MergeSort