Lawrence's Guide to Crushing Google

Algorithm Approaches

Five Algorithm Approaches

  1. Examplify

    Write out specific examples of the problem, and see if you can figure out a general rule.

  2. Pattern Matching

    Consider what problems the algorithm is similar to and figure out how to modify it to make it work.

    I should probably use this more often

  3. Simplify and Generalize

    Change a constraint (data type, size, etc.) to simplify the problem. Then (try to) solve it. Then generalize and solve it.

  4. Base Case and Build

    Solve for one case. Then two. Then n. Naturally recursive.

  5. Data Structure Brainstorm

    "Hacky". Go through a list of data structures and see which one(s) applies/apply.

Trees

Potential Issues to Watch Out For

Binary Tree vs. Binary Search Tree

Don't jump to conclusions. Remember to ask the interviewer to clarify.

Balanced vs. Unbalanced

Ask interviewer to clarify. Usually balanced within a certain tolerance.

Full and Complete

Again, ask to clarify. Full - 0 or n children, where n is derived from the n-ary tree.

Common Types

Binary Trees

Tree structure categorized by having at most two children, commonly referred to as left and right. Other terms often associated with binary trees arefull, complete, balanced, and perfect.
Link: https://en.wikipedia.org/wiki/Binary_tree

Binary Search Trees

A subset of binary trees, where for all nodes left of root, left.val < root.val. Similarly, for all nodes right of root, root.val < right.val.
https://en.wikipedia.org/wiki/Binary_search_tree

AVL Trees

A self-balancing binary search tree. This leads to better worst case performance for typical BST functions such as insert, find, and remove.
https://en.wikipedia.org/wiki/AVL_tree

B Trees

Yo dude

n-ary Trees

A tree that for any node, it can have at most n children. Binary trees are a special case of n-ary trees where n=2. https://en.wikipedia.org/wiki/K-ary_tree

Trie Trees

Also called a prefix-tree or radix-tree, According to Wikipedia:

"All the descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string. Values are normally not associated with every node, only with leaves and some inner nodes that correspond to keys of interest.
Though tries are most commonly keyed by character strings, they don't need to be. The same algorithms can easily be adapted to serve similar functions of ordered lists of any construct, e.g., permutations on a list of digits or shapes. In particular, a bitwise trie is keyed on the individual bits making up a short, fixed size of bits such as an integer number or memory address."


They are sometimes used as a replacement to hashtables. This StackOverflow thread does a great job weighing why you'd use one over the other. In summary (because I know no one likes clicking on links), it says, verbatim:https://en.wikipedia.org/wiki/Trie

k-d Trees

A multi-dimensional binary search tree. Very trippy stuff man. Nearest neighbor is a common thing on this tree.
https://en.wikipedia.org/wiki/K-d_tree

Graphs

Three Ways to Represent Graphs in Memory

  1. Nodes as objects and edges as pointers - very readable and conceptually intuitive
  2. Adjacency Matrix - best used if the graph is dense, as resizing is costly
  3. Adjacency List - best used if the graph is sparse