In general I feel that deep algorithm knowledge is overrated in the software industry. In the early 90’s, one needed to know about common algorithms because you needed to actually implement them. Today in the 00’s and 10’s one mainly needs to know which algorithms are appropriate to use, since most common algorithms are already implemented in the standard library of modern programming languages. Therefore I would like to give a summary of the minimum that I think modern coders actually need to know to do their job effectively.
All advice in this article is directly towards those who write applications: primarily rich web applications, desktop applications, and server-side tools. In this context the most advanced type of program you would be asked to write would be a compiler or other program transformation tool.
If on the other hand you work in a low-level environments close to the hardware^{1}, are performing scientific calculations^{2}, or are regularly processing insanely large data sets^{3}, you will need to know more about algorithms that what I cover here.
In general the main algorithmic work you’ll be doing when writing programs will involve the use of collections included in your language’s standard library. Collections hold values. The algorithms for manipulating these collections will also typically be included in the standard library.
The following kinds of collections are so common as to be fundamental. Practically all programs involve the efficient manipulation of data stored in these collections.
Sets and Maps in particular come in different flavors depending on what kind of ordering guarantee (if any) they provide:
Other useful more-advanced collections exist such as Bidirectional Maps, Counted Bags, Partitioning Bags, and Priority Queues, but they will not be considered here.^{4}
All collections support operations for adding elements, removing elements, and iterating over elements.^{5} However they do so at different speeds. It is important to choose the best kind of collection to use based on which operations your program will perform on it most frequently.
Below are the operations that each collection type supports most efficiently, along with the operation’s speed in Big-Oh notation^{6} when using the best^{7} implementation available:
† = Assumes using an Unordered or Stable implementation with a well-designed hash function. If using a Sorted implementation then performance degrades from O(1) to O(log(n)). If using a poor hash function then performance degrades from O(1) to as low as O(n).
Common algorithms exist for performing these operations. As mentioned previously it is rare that you will need to code such collection-manipulating algorithms manually unless you are working in a constrained environment. Instead you just need to be a smart shopper when picking a collection implementation to use from your language’s standard library.
Generally speaking the collections available in the standard library of a programming language will be include one or more of the following specific implementations, possibly using different names:
Here is a table of implementations for various common programming languages:
The only advanced operation you commonly need to perform on a collection is to sort it.
The following sorting algorithms are worth knowing about for actual use:
It’s also worth knowing that there are even faster sort algorithms that are not based on comparisons. For example:
In interviews, knowing about and being able to implement merge sort, quicksort, and insertion sort has always been sufficient for me.
Standard libraries vary in what specific sorting algorithms they offer:
Beyond collections, it’s useful to know how to both to implement tree data structures - particularly N-Ary Trees - how to traverse them, and how to manipulate them.
N-Ary Trees are made of Nodes, starting at a root node, where each node contains a list of children nodes. A node with no children is a leaf. A node can be related to another node as a child, parent, descendant, ancestor, or cousin. A node may or may not track who its parent is, depending on how it is implemented.
Trees can be traversed in either Depth-First Order or Breadth-First Order. Most programs use Depth-First Order because it is easy to implement via recursion. Breadth First-Order traversal may be useful, however, in writing algorithms related to the shortest-path from the tree root.
In interviews, I’ve found useful the ability to improvise new tree-related algorithms. For example an algorithm to find the nearest common ancestor.
It is rare that you will need to use graphs in real-world application development except for the most demanding kinds of applications, such as compilers and program transformation tools. Therefore I will only cover them briefly here.
A Graph is made of Nodes (sometimes called “vertices”) and Edges. Edges connect pairs of nodes together. Beyond that:
In a “directed” graph (or “digraph”), each edge has a head and tail. By contrast in an “undirected” graph, each edge is unoriented and just joins two nodes together.
Some graphs are “weighted”, meaning that nodes and/or edges are annotated with numerical weights.
Some graphs are “multi-graphs”, meaning that they explicitly allow multiple edges between the same pair of nodes.
Graphs are useful for representing and manipulating connected structures, such as the intersections and roads on a map, the set of statements and related next-statements in source code, and the set of squares on a game board plus its neighbors.
Algorithms for working with graphs are similar to those for working with trees but are more complicated, since each node in a graph can be typically be reached along multiple paths.
Knowing how to traverse a graph in both Depth-First Order and Breadth-First Order without revisiting a node twice is extremely useful, both in practice and for interviews. For example how could you implement the paint bucket tool in a drawing program, coloring in a region of neighboring pixels without coloring in any pixel twice?
There are a few other miscellaneous concerns worth mentioning:
Strings in many languages (Java, Python, JavaScript) are immutable. Therefore appending to a string takes O(n) time. By itself this is not a problem, however you need to be careful not to repeatedly append to a string inside a loop because then your runtime will be closer to O(n^{2}). Instead, append the string parts to a temporary list and then join the list together afterwards using the appropriate standard library function. That will get you back to O(n) time.
Implementing binary search in a list correctly is a lot harder than you think. The first couple of attempts in the academic literature actually had flawed algorithms.
Algorithms involving array rearrangement and index manipulation are good to practice for interviews, since some interviewers ask for low-level tricky algorithms of this sort. For example the Dutch National Flag problem is a classic.
Series
This article is part of the Programming for Perfectionists series.
Low-level environments typically lack rich standard libraries. So you’re back to implementing linked lists and friends by hand.↩
Scientific calculations involve lots of floats, which have a host of additional considerations to worry about. Chiefly float imprecision and numerical stability. The data sets involved are also typically very large.↩
Web services that have the popularity of Facebook, Amazon, Apple, Microsoft, or Google are dealing with unbelievable data volumes that merit using specialized algorithms. Other websites, although perhaps still popular, don’t receive anywhere near the same level of traffic.↩
Further, other useful more-advanced non-collection data structures exist such as Trees, Directed Graphs, and Undirected Graphs, but they also will not be covered here.↩
The runtimes quoted here are for operations that are performed in-place, modifying the original collection value. If you require operations that efficiently return modified copies of the original collection, look into persistent data structures, such as used by Rich Hickey in the Clojure standard library.↩
In Big-Oh notation, O(1) is a constant amount of time, O(log(n)) is time proportional to the order of magnitude of the collection’s size, and O(n) is time proportional to the size of the collection. Other common runtimes include O(n⋅log(n)) and O(n^{2}).↩
Considerably worse performance can result if you use a poor implementation. For example if you attempt to append (not prepend) an element to a list in a functional language that uses the default singly-linked list implementation, it will take O(n) time rather than the usual O(1) amortized time.↩
O(1) amortized time means that in aggregate the per-operation time cost will average out to O(1). However individual operations may take O(1) in the average case or O(n) in the worst case.↩