This series contains review materials for software engineer interview questions. This guide provides a high-level overview of basic algorithms including their implementations, applications and efficiency.

Overview:

  • Systematically search through a tree or graph, start at the root.
    • E is number of edges.
    • V is number of vertices.
  • Analyzes paths by searching depth of the tree or graph first (nodes farthest away).
  • Algorithm implemented using a stack (LIFO).
    • Unvisited vertices added to stack.
    • Visited vertices are marked to deal with cycles in graph (not required for a tree).
    • Retrace steps when no unvisited options.
    • Typically implemented using recursion.
  • Optimal for searching graphs and tress that are deeper than they are wide.

Applications:

  • Find all vertices connected to a given source vertex.
  • Find a path between two vertices.

Efficiency:

  • Search: O(|E| + |V|)

Overview:

  • Systematically search through a tree or graph, start at the root.
    • E is number of edges.
    • V is number of vertices.
  • Analyzes paths by searching closest nodes first.
  • Algorithm implemented using queue (FIFO).
    • Put unvisited vertices in the queue.
    • Repeat until queue is empty.
      • Remove vertex v from queue.
      • Add to queue all unmarked vertices adjacent to v and mark them as visited.
  • Examines vertices in increasing distance from root.
  • Optimal for searching graphs and trees that are wider than they are deep.

Applications:

  • Shortest path: Find path from s to t that uses fewest number of edges.

Efficiency:

  • Search: O(|E| + |V|)

Overview:

  • Search through an array to locate a specific element.
  • Algorithm typically implemented recursively.
    • Compare element x to the midpoint of the sorted array.
    • If x less than the midpoint, then search the left half of the array.
    • If x greater than the midpoint, then search the right half of the array.
    • Repeat the process treating the halves as subarrays until finding x or subarray is size 0.

Applications:

  • Find element in sorted array.

Efficiency:

  • Search: O(log N)

Quick Sort

Overview:

  • Comparison based sorting algorithm.
  • Algorithm typically implemented recursively.
    • Shuffle the array (to ensure average element selected).
    • Partition array so that for some element x (typically first element of subarray).
      • Entry a[x] is in place.
      • No larger entry to the left of x.
      • No smaller entry to the right of x.
    • Sort each subarray.
    • Requires special handling for duplicate keys, otherwise quadratic performance.
  • Quicksort is generally faster than mergesort.
  • In-place sorting algorithm (constant extra space).
  • Not a stable sorting algorithm (long range exchanges of elements).

Applications:

  • Sort an array of elements.
  • Java primitive type sorting uses quick sort.

Efficiency:

  • Best Case Sort: O(N log N)
  • Average Case Sort: O(N log N)
  • Worst Case Sort: O(N^2)

Merge Sort

Overview:

  • Comparison based sorting algorithm.
  • Algorithm typically implemented recursively.
    • Divide array into two (recursively).
    • Sort each subarray.
    • Merge the two subarrays.
  • Merging algorithm.
    • Create a temporary array that is the same size as the two halves.
    • Keep track of three indices: output, first half, and second half.
  • Not an in-place sorting algorithm (linear extra space).
  • Stable sorting algorithm (maintains relative order of equal keys).

Applications:

  • Sort an array of elements.
  • Java generic object type sorting uses merge sort.

Efficiency:

  • Best Case Sort: O(N log N)
  • Average Case Sort: O(N log N)
  • Worst Case Sort: O(N log N)

Sources