Tech Interview 101

Dijkstra's Algorithm

Runtime: O(|V|)² or O((|V|+|E|) log |V|) Depends on implementation: the former using an array/linked this, and the latter using a binary heap.
Notes: Cannot process negative edge weights.

function dijkstra(G,s):
  dist(v in V) = infinity
  prev(v in V) = null
  dist(s) = 0
  PQ = PriorityQueue(V)
  tree = []
  while PQ is not empty:
      u = PQ.removeMin()
          for all edges (u,v):
              if dist(v) > dist(u) + cost(u,v):
                  dist(v) = dist(u) + cost(u,v)
                  prev(v) = u
                  PQ.replaceKey(v, dist(v))
  for v in V:
      if v.prev is not null:
          tree.append(connecting_edge(v,v.prev))
  return tree

Bellman-Ford Algorithm

Runtime: O(|V|*|E|)
Notes: Relaxes |E| edges, |V|-1 times. Can process negative edge weights.

function BellmanFord(V,E,src):
  for each vertex v in vertices:
      v.dist = infinity
      if v = src:
          v.dist = 0
          v.prev = null
  repeat |V|-1 times:
      for each edge (u,v) in E:
          if u.dist + (u,v).weight < v.dist:
              v.dist = u.dist + (u,v).weight
              v.prev = u
  // checking for negative cycles
  for each edge (u,v) in E:
      if u.dist + (u,v).weight < v.dist:
          throw new NegativeCycleException()
  // build tree
  for v in V:
      if v.prev is not null:
          tree.append(connecting_edge(v, v.prev))

Top Sort

Runtime: O(|V|+|E|)

function TopSort(G):
  S = Stack()
  L = []
  for each vertex in G:
      if vertex has no incident edges:
          S.push(vertex)
  while S is not empty:
      v = S.pop()
      L.append(v)
      for each outgoing edge e from v:
          w = e.destination
          delete e
          if w has no incident edges:
              S.push(w)
  return L

Prim-Jarnik Algorithm

Runtime: O((|V|+|E|) log|V|)
Notes: Best to prove correctness by induction. This is a greedy algorithm.

function prim(G):
  for all vertices v in G:
      v.cost = infinity
      v.prev = null
  source = a random v in V
  source.cost = 0
  MST = []
  PQ = PriorityQueue(V)
  while PQ is not empty:
      v = PQ>removeMin()
      if v.prev != null:
          MST.append((v,v.prev))
      for all incident edges (v,u) of v:
          if u.cost > (v,u).weight
              u.cost = (v,u).weight
              u.prev = v 
          PQ.replaceKey(u,u.cost)
  return MST

Kruskal's Algorithm

Runtime: O(|E|log|E|) Thanks to union find/path compression this is the runtime. Without union find/recursive path compression, the runtime is O(|V|³)
Notes: Sorts all edges of the graph by weight in ascending order, and if its addition doesn’t create a cycle, add it to the MST. Detect cycles with “clouds”.

function kruskal(G):
  for vertices v in G:
      v.parent = v
      v.rank = 0
  MST = []
  for all edges(u,v) in G sorted by weight:
      if u and v are not in same cloud:
      if v.prev != null:
          MST.append((u,v))
          this.mergeClouds(u.parent, v.parent)
          this.pathCompress(v)
  return MST

Helper Functions
Runtime: Amortized O(1)

function mergeClouds(p1, p2): // union
  if p1.rank > p2.rank:
      p2.parent = p1
  else if p1.rank < p2.rank:
      p1.parent = p2
  else:
      p2.parent = p1
      p1.rank++


function pathCompress(v): // find
  if v != v.parent:
      v.parent = pathCompress(v.parent)
  return v.parent

Runtime Overview

Algorithm	Time	Notes
Selection sort	O(n²)	in place slow (good for small inputs)
Insertion sort	O(n²)	in place slow (good for small inputs)
Merge sort	O(n log n)	fast (good for large inputs)
Quick sort	O(n log n) expected	randomized fastest (good for large inputs)
Radix sort	O(nd)	d is number of digits in largest number basically linear when d is small

Mnemonic: SQuIRM (n², n log n, n²,nd, n log n)

Merge Sort

Runtime: O(n log n)
Notes: not in-place

function merge_sort(A):
    n = A.length()
    if n <= 1:
        return A
    mid = n/2
    left = mergeSort(A[0 … mid-1])
    right = mergeSort(A[mid .. n-1])
    return merge(left,right)

function merge(A, B):
  result = []
  aIndex = bIndex = 0
  while aIndex < A.length() and bIndex < B.length():
      if A[aIndex] < B[bIndex]:
          result.append(A[aIndex])
          aIndex++
  if aIndex < A.length():
      result = result + A[aIndex...end]
  if bIndex < B.length():
      result = result + B[bIndex...end]
  return result

Selection Sort

Runtime: O(n²)
Notes: usually written iteratively and in-place. finds the min and moves it to the first index (then second, third, etc.)

function selection_sort(A):
  // Input: Unsorted List
  // Output: Sorted List
  n = A.length
  for i = 0 to n-2:
      min = argmin(A[i...n-1])
      swap A[i] with A[min]

Insertion Sort

Runtime: O(n²)
Notes: very fast if already partially sorted

function insertion_sort(A):
  n = A.length()
  for i = 1 to n-1:
      for j = i down to 1:
          if A[j] < A[j-1]:
              swap A[j] and A[j-1]
          else:
              break

Reverse

Notes: in-place

function reverse(A):
  n = A.length
  for i = 0 to n/2:
      temp = A[i]
      A[i] = A[n−1−i]
      A[n−1−i] = temp

Quick Sort

Runtime: worst case O(n²) , expected O(n log n)
Notes: divide and conquer around a random pivot point. partition the input list into L, E, and G for numbers less than equal to or greater than the pivot point. recursively solve until in order.

function quick_sort(A):
// Input: Unsorted List
// Output: Sorted List
  n = A.length
  if n <= 1
      return A
  pivot = random element from A
  L, E, G = [ ]
  for each x in A:
      if x < pivot:
          L.append(x)
      else if x > pivot:
          G.append(x)
      else:
          E.append(x)
  return quick_sort(L) + E + quick_sort(G)

Radix Sort

Runtime: O(n log n)
Notes: not in-place

function radix_sort(A):
// Input: unsorted list
// Output: sorted list
  buckets = array of 10 lists
  for place = least to most significant
      for number in A
          d = digit in number at place
          bucket[d].append(number)
      A = concatenate all buckets in order
      empty all buckets
  return A

Selection

Runtime:
expected: O(n)
worst case: O(n²)


function select(list, k):
\\ base case omitted
  pivot = list[rand(0, list.size)]
  L = E = R = []
  for x in list:
      if x < pivot: L.append(x)
      if x = pivot: E.append(x)
      if x > pivot: R.append(x)
  if k <= L.size:
      return select(L,k)
  else if k > L.size and k <= (L.size + E.size):
      return pivot
  else:
      return select(R,k - (L.size + E.size))

Median of Medians

Runtime: O(n)


function momSelect(list, k):
//base cases omitted
  miniLists = divide list into n/5 lists of 5
  medians = []
  for miniList in miniLists:
      // sort is O(1) because list is always of length 5
      sort(miniList) 
      medians.append(miniList[2])
  pivot = momSelect(medians, medians.size()/2)

  L = E = R = []
  for x in list:
      if x < pivot: L.append(x)
      if x = pivot: E.append(x)
      if x > pivot: R.append(x)
  if k <= L.size:
      return select(L,k)
  else if k > L.size and k <= (L.size + E.size):
      return pivot
  else:
  return select(R,k)

Binary Search

Runtime: O(log n)
Notes: Input: A – a sorted array, x – the item to find Output: true if x is in the array


function binarySearch(A, x):
  lo = 0
  hi = A.size - 1
  while lo < hi:
      mid = (lo + hi) / 2
      if A[mid] == x:
          return true
      if A[mid] < x:
          lo = mid + 1
      if A[mid] > x:
          hi = mid – 1
  return A[lo] == x

Angular Graham Scan

Runtime: O(n log n)

Breadth-First Traversal

Runtime: O(n log n)
Notes: not in-place


function bft(root):
// Input: root node of tree
// Output: None
  Q = new Queue()
  enqueue root
  while Q is not empty:
      node = Q.dequeue()
      visit(node)
      enqueue node’s left & right children

Depth-First Traversal


function dft(root):
// Input: root node of tree
// Output: None
  S = new Stack()
  push root onto S
  while S is not empty:
      node = S.pop()
      visit(node)
      push node’s left & right children

Recursive Breadth-First Traversal


function preorder(node):
// Input: root node of tree
// Output: None
  visit(node)
  if node has left child
      preorder(node.left)
  if node has right child
      preorder(node.right)

function inorder(node):
// Input: root node of tree
// Output: None
  if node has left child
      preorder(node.left)
  visit(node)
  if node has right child
      preorder(node.right)

function postorder(node):
// Input: root node of tree
// Output: None
  if node has left child
      postorder(node.left)
  if node has right child
      postorder(node.right)
  visit(node)

A graph G is a tree if and only if it satisfies any of the following 5 conditions:

G has V-1 edges and no cycles
G has V-1 edges and is connected
G is connected, but removing any edge disconnects it
G is acyclic, but adding any edges creates a cycle
Exactly one simple path connects each pair of vertices in G

ADT	Structure	Main Methods	Properties
PQ	Heap	insert(key,element) O(log n) removeMin() O(log n) upheap() O(log n) downheap() O(log n)	- Binary: each node has <= 2 children - Key/priority at each node - Left-complete - Preserves heap order: min or max - min: n.key >= n.parent.key - max: n.key <= n.parent.key
Treap	BST + Heap	insert(key,element) O(log n) removeMin() O(log n) upheap() O(log n) downheap() O(log n)	- A non-empty tree T with a key and a priority at each node - T has only one node, or - T has a root R whose left and right subtrees are both treaps - Node's priority preserves heap order - Node's key preserves BST ordering
Tree		tree methods: size() isEmpty() root() node methods: parent() children() isInternal() isExternal() isRoot() binary tree node methods: hasLeft() hasRight() left() right()	# nodes = n # edges = n - 1 height = h perfect binary tree: height = h = log(n+1)-1 _{(base 2)} # nodes = n = 2^(h+1)-1 = 2L-1 # leaves = L = 2^h
Trie	Prefix Tree	insert() find()	each node has a dictionary of children

Problem	Algorithm	Runtime	Data Structure
Sorting	Insertion sort	n²
	Selection sort	worst case: n² expected: n
	Merge sort	n log n
	Quick sort	n log n
	Radix sort	dn
Tree Traversals	Breadth first		Queue
	Depth first		Stack
	Pre-order
	In-order
	Post-order
	Euler tour	Left side: pre-order Bottom: in-order Right side: post-order
Graph stuff	BFT	V+E	Queue
	DFT	V+E	Stack
	Top Sort	V+E	Stack, Queue, etc.
Shortest Paths	Dijkstra	\|V\|² (\|V\|+\|E\|)* log\|V\|	Array/Linked list PQ / Binary Heap, etc.
	A*	(V+E)log(V)	PQ/Binary Heap, etc.
	Bellman-Ford	VE
MSTs	Prim-Jarnik	(V+E)logV	PQ
	Kruskals (plus union find)	ElogE

Tech Interview 101

Big O Cheat Sheet

Shortest Path Algorithms

Dijkstra's Algorithm

Bellman-Ford Algorithm

Top Sort

Minimum Spanning Tree Algorithms

Prim-Jarnik Algorithm

Kruskal's Algorithm

Sorting Algorithms

Runtime Overview

Merge Sort

Selection Sort

Insertion Sort

Reverse

Quick Sort

Radix Sort

Selection & Search Algorithms

Selection

Median of Medians

Binary Search

Angular Graham Scan

Tree Traversals

Breadth-First Traversal

Depth-First Traversal

Recursive Breadth-First Traversal

Graphs v Trees

Abstract Data Types (ADTs)

Algorithms