Interviews: Algorithms
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.
Depth-First Search
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|)
Breadth First Search
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|)
Binary Search
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)